Analysis with vector spaces · Selected prerequisite proofs

L8.2.4: Source Euclidean proof plus P9.3 for its full stated normed-space generality.

Proposition 8.2.4.

Let

X

and

Y

be normed vector spaces with

X

finite-dimensional, and let

A \in L(X,Y)\text{.}

Then

\snorm{A} < \infty\text{,}

and

A

is uniformly continuous (Lipschitz with constant

\snorm{A}

).

Proof.

As we said we only prove the proposition for euclidean spaces, so suppose that

X = \R^n

and the norm is the standard euclidean norm. The general case is left as an exercise.

Let

\{ e_1,e_2,\ldots,e_n \}

be the standard basis of

\R^n\text{.}

Write

x \in \R^n\text{,}

with

\snorm{x} = 1\text{,}

as

\begin{equation*} x = \sum_{k=1}^n c_k \, e_k . \end{equation*}

Since

e_k \cdot e_\ell = 0

whenever

k \neq \ell

and

e_k \cdot e_k = 1\text{,}

we have

c_k = x \cdot e_k\text{.}

By Cauchy–Schwarz,

\begin{equation*} \sabs{c_k} = \sabs{ x \cdot e_k } \leq \snorm{x} \, \snorm{e_k} = 1 . \end{equation*}

Then

\begin{equation*} \snorm{Ax} = \norm{\sum_{k=1}^n c_k \, Ae_k} \leq \sum_{k=1}^n \sabs{c_k} \, \snorm{Ae_k} \leq \sum_{k=1}^n \snorm{Ae_k} . \end{equation*}

The right-hand side does not depend on

x\text{.}

We found a finite upper bound for

\snorm{Ax}

independent of

x\text{,}

so

\snorm{A} < \infty\text{.}

Take normed vector spaces

X

and

Y\text{,}

and

A \in L(X,Y)

with

\snorm{A} < \infty\text{.}

For

v,w \in X\text{,}

\begin{equation*} \snorm{Av - Aw} = \bnorm{A(v-w)} \leq \snorm{A} \, \snorm{v-w} . \end{equation*}

As

\snorm{A} < \infty\text{,}

the inequality above says that

A

is Lipschitz with constant

\snorm{A}\text{.}

L8.2.5: Operator norm sum, scalar and composition inequalities and norm axioms.

Proposition 8.2.5.

Let

X\text{,}

Y\text{,}

and

Z

be finite-dimensional normed vector spaces.

If $A,B \in L(X,Y)$ and $c \in \R\text{,}$ then

$\begin{equation*} \snorm{A+B} \leq \snorm{A}+\snorm{B}, \qquad \snorm{cA} = \sabs{c} \, \snorm{A} . \end{equation*}$

In particular, the operator norm is a norm on the vector space $L(X,Y)\text{.}$
If $A \in L(X,Y)$ and $B \in L(Y,Z)\text{,}$ then

$\begin{equation*} \snorm{BA} \leq \snorm{B} \, \snorm{A} . \end{equation*}$

Proof.

First, since all the spaces are finite-dimensional, then all the operator norms are finite, and the statements make sense to begin with.

For i, let

x \in X

be arbitrary. Then

\begin{equation*} \bnorm{(A+B)x} = \snorm{Ax+Bx} \leq \snorm{Ax}+\snorm{Bx} \leq \snorm{A} \, \snorm{x}+\snorm{B} \,\snorm{x} = \bigl(\snorm{A}+\snorm{B}\bigr) \snorm{x} . \end{equation*}

So

\snorm{A+B} \leq \snorm{A}+\snorm{B}\text{.}

Similarly,

\begin{equation*} \bnorm{(cA)x} = \sabs{c} \, \snorm{Ax} \leq \bigl(\sabs{c} \,\snorm{A}\bigr) \snorm{x} . \end{equation*}

Thus

\snorm{cA} \leq \sabs{c} \, \snorm{A}\text{.}

Next,

\begin{equation*} \sabs{c} \, \snorm{Ax} = \snorm{cAx} \leq \snorm{cA} \, \snorm{x} . \end{equation*}

Hence

\sabs{c} \, \snorm{A} \leq \snorm{cA}\text{.}

For ii, write

\begin{equation*} \snorm{BAx} \leq \snorm{B} \, \snorm{Ax} \leq \snorm{B} \, \snorm{A} \, \snorm{x} . \qedhere \end{equation*}

L8.2.6: Invertible neighbourhood and continuity of inversion in every finite-dimensional normed space.

Proposition 8.2.6.

Let

X

be a finite-dimensional normed vector space. Let

GL(X) \subset L(X)

be the set of invertible linear operators.

²

GL(X)

is called the general linear group, that is where the acronym GL comes from.

If $A \in GL(X)\text{,}$ $B \in L(X)\text{,}$ and

$\begin{equation*} \snorm{A-B} < \frac{1}{\snorm{A^{-1}}},\tag{8.2} \end{equation*}$

then $B \in GL(X)\text{,}$ that is, $B$ is invertible. In particular, $GL(X)$ is open.
$A \mapsto A^{-1}$ is a continuous function on $GL(X)\text{.}$

Proof.

Let us prove i. We know something about

A^{-1}

and

A-B\text{;}

they are linear operators. So apply them to a vector:

\begin{equation*} A^{-1}(A-B)x = x-A^{-1}Bx . \end{equation*}

Therefore,

\begin{equation*} \begin{split} \snorm{x} & = \bnorm{A^{-1} (A-B)x + A^{-1}Bx} \\ & \leq \snorm{A^{-1}}\,\snorm{A-B}\, \snorm{x} + \snorm{A^{-1}}\,\snorm{Bx} . \end{split} \end{equation*}

Assume

x \neq 0

and so

\snorm{x} \neq 0\text{.}

Using (8.2), we obtain

\begin{equation*} \snorm{x} < \snorm{x} + \snorm{A^{-1}} \, \snorm{Bx} . \end{equation*}

Thus

\snorm{Bx} \neq 0

for all

x \neq 0\text{,}

and consequently

Bx \neq 0

for all

x \neq 0\text{.}

So

B

is one-to-one; if

Bx = By\text{,}

then

B(x-y) = 0\text{,}

so

x=y\text{.}

As

B

is a one-to-one linear mapping from

X

to

X\text{,}

which is finite-dimensional, it is also onto by Proposition 8.1.18. Therefore,

B

is invertible. It follows that, in particular,

GL(X)

is open.

Let us prove ii. We must show that the inverse is continuous. Fix an

A \in GL(X)\text{.}

Let

B

be near

A\text{,}

specifically

\snorm{A-B} < \frac{1}{2 \snorm{A^{-1}}}\text{.}

Then (8.2) is satisfied and

B

is invertible. A similar computation as above (using

B^{-1}y

instead of

x

) gives

\begin{equation*} \snorm{B^{-1}y} \leq \snorm{A^{-1}} \, \snorm{A-B} \, \snorm{B^{-1}y} + \snorm{A^{-1}} \, \snorm{y} \leq \frac{1}{2} \snorm{B^{-1}y} + \snorm{A^{-1}}\,\snorm{y} , \end{equation*}

or

\begin{equation*} \snorm{B^{-1}y} \leq 2\snorm{A^{-1}}\,\snorm{y} . \end{equation*}

So

\snorm{B^{-1}} \leq 2 \snorm{A^{-1}} \text{.}

Now

\begin{equation*} A^{-1}(A-B)B^{-1} = A^{-1}(AB^{-1}-I) = B^{-1}-A^{-1} , \end{equation*}

and

\begin{equation*} \snorm{B^{-1}-A^{-1}} = \bnorm{A^{-1}(A-B)B^{-1}} \leq \snorm{A^{-1}}\,\snorm{A-B}\,\snorm{B^{-1}} \leq 2\snorm{A^{-1}}^2 \snorm{A-B} . \end{equation*}

Therefore, as

B

tends to

A\text{,}

\snorm{B^{-1}-A^{-1}}

tends to 0, and so the inverse operation is a continuous function at

A\text{.}

L8.2.7: Matrix-coordinate/operator-norm topology equivalence; full preceding Frobenius estimates.

Subsection 8.2.2 Matrices

Once we fix a basis in a finite-dimensional vector space

X\text{,}

we can represent a vector of

X

as an

n

-tuple of numbers—a vector in

\R^n\text{.}

The same can be done with

L(X,Y)\text{,}

bringing us to matrices, which are a convenient way to represent finite-dimensional linear transformations. Suppose

\{ x_1, x_2, \ldots, x_n \}

and

\{ y_1, y_2, \ldots, y_m \}

are bases for vector spaces

X

and

Y

respectively. A linear operator is determined by its values on the basis. Given

A \in L(X,Y)\text{,}

A x_j

is an element of

Y\text{.}

Define the numbers

a_{i,j}

via

\begin{equation*} A x_j = \sum_{i=1}^m a_{i,j} \, y_i ,\tag{8.3} \end{equation*}

and write them as a matrix, which we, by slight abuse of notation, also call

A\text{,}

\begin{equation*} A = \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{bmatrix} . \end{equation*}

We sometimes write

A

as

[a_{i,j}]\text{.}

We say

A

is an

m

-by-

n

matrix. The

j

th column of the matrix contains precisely the coefficients that represent

A x_j

in terms of the basis

\{ y_1,y_2,\ldots,y_m \}\text{.}

Given the numbers

a_{i,j}\text{,}

then via the formula (8.3), we find the corresponding linear operator, as it is determined by the action on a basis. Hence, once we fix bases on

X

and

Y\text{,}

we have a one-to-one correspondence between

L(X,Y)

and the

m

-by-

n

matrices. When

\begin{equation*} z = \sum_{j=1}^n z_j \, x_j , \end{equation*}

then

\begin{equation*} A z = \sum_{j=1}^n z_j \, A x_j = \sum_{j=1}^n z_j \left( \sum_{i=1}^m a_{i,j}\, y_i \right) = \sum_{i=1}^m \left(\sum_{j=1}^n a_{i,j}\, z_j \right) y_i , \end{equation*}

which gives rise to the familiar rule for matrix multiplication, thinking of

z

as a column vector, that is, an

n

-by-1 matrix. More generally, if

B

is an

n

-by-

r

matrix with entries

b_{j,k}\text{,}

then the matrix for

C = AB

is an

m

-by-

r

matrix whose

(i,k)

th entry

c_{i,k}

is

\begin{equation*} c_{i,k} = \sum_{j=1}^n a_{i,j}\,b_{j,k} . \end{equation*}

A way to remember it is if you order the indices as we do—row, column—and put the elements in the same order as the matrices, then the “middle index” is “summed-out.”

There is a one-to-one correspondence between matrices and linear operators in

L(X,Y)\text{,}

once we fix bases in

X

and

Y\text{.}

If we choose different bases, we get different matrices. This is an important distinction. The operator

A

acts on elements of

X\text{,}

while the matrix is something that works with

n

-tuples of numbers, that is, vectors of

\R^n\text{.}

By convention, we use standard bases in

\R^n

unless otherwise specified, and we identify

L(\R^n,\R^m)

with the set of

m

-by-

n

matrices.

A linear mapping changing one basis to another is represented by a square matrix in which the columns represent vectors of the second basis in terms of the first basis. We call such a linear mapping a change of basis. So for two choices of a basis in an

n

-dimensional vector space, there is a linear mapping (a change of basis) taking one basis to the other, and this corresponds to an

n

-by-

n

matrix which does the corresponding operation on

\R^n\text{.}

Suppose

X=\R^n\text{,}

Y=\R^m\text{,}

and all the bases are just the standard bases. Using the Cauchy–Schwarz inequality, with

c=(c_1,c_2,\ldots,c_n) \in \R^n\text{,}

compute

\begin{equation*} \snorm{Ac}^2 = \sum_{i=1}^m { \left(\sum_{j=1}^n a_{i,j} \, c_j \right)}^2 \leq \sum_{i=1}^m \left( \left(\sum_{j=1}^n {(a_{i,j})}^2 \right) \left(\sum_{j=1}^n {(c_j)}^2 \right) \right) = \left( \sum_{i=1}^m \sum_{j=1}^n {(a_{i,j})}^2 \right) \snorm{c}^2 . \end{equation*}

In other words, we have a bound on the operator norm (note that equality rarely happens)

\begin{equation*} \snorm{A} \leq \sqrt{\sum_{i=1}^m \sum_{j=1}^n {(a_{i,j})}^2} . \end{equation*}

The right-hand side is the euclidean norm on

\R^{nm}\text{,}

the space of all the entries of the matrix. If the entries go to zero, then

\snorm{A}

goes to zero. Conversely,

\begin{equation*} \sum_{i=1}^m \sum_{j=1}^n {(a_{i,j})}^2 = \sum_{j=1}^n \snorm{A e_j}^2 \leq \sum_{j=1}^n \snorm{A}^2 = n \snorm{A}^2 . \end{equation*}

So if the operator norm of

A

goes to zero, so do the entries. In particular, if

A

is fixed and

B

is changing, then the entries of

B

go to the entries of

A

if and only if

B

goes to

A

in operator norm (

\snorm{A-B}

goes to zero). We have proved:

Proposition 8.2.7.

The topology (the set of open sets) on

L(\R^n,\R^m)

is the same whether we consider

L(\R^n,\R^m)

as a metric space using the operator norm, or the euclidean metric of

\R^{nm}\text{.}

In particular, let

S

be a metric space and let

\pi \colon L(\R^n,\R^m) \to \R^{nm}

identify an operator with the

nm

-tuple of entries of the corresponding matrix. Then

f \colon S \to L(\R^n,\R^m)

is continuous if and only if

\pi \circ f \colon S \to \R^{nm}

is continuous. Similarly for

g \colon L(\R^n,\R^m) \to S

and

g \circ \pi^{-1} \colon \R^{nm} \to S\text{.}

L8.2.8: All seven determinant properties; continuity uses P10.1.

Proposition 8.2.8.

$\det(I) = 1\text{.}$
For every $j=1,2,\ldots,n\text{,}$ the function $x_j \mapsto \det\bigl([x_1 ~~~ x_2 ~~~ \cdots ~~~ x_n ]\bigr)$ is linear.
If two columns of a matrix are interchanged, then the determinant changes sign.
If two columns of $A$ are equal, then $\det(A) = 0\text{.}$
If a column is zero, then $\det(A) = 0\text{.}$
$A \mapsto \det(A)$ is a continuous function on $L(\R^n)\text{.}$
$\det\left( \left[\begin{smallmatrix} a & b \\ c &d \end{smallmatrix}\right] \right) = ad-bc\text{,}$ and $\det \bigl( [a] \bigr) = a\text{.}$

Proof.

We go through the proof quickly, as you have likely seen it before. Item i is trivial. For ii, note that each term in the definition of the determinant contains exactly one factor from each column. Item iii follows as switching two columns is switching the two corresponding numbers in every element in

S_n\text{.}

Hence, all the signs are changed. Item iv follows because if two columns are equal, and we switch them, we get the same matrix back. So item iii says the determinant must be 0. Item v follows because the product in each term in the definition includes one element from the zero column. Item vi follows as

\det

is a polynomial in the entries of the matrix and hence continuous (as a function of the entries of the matrix). A function defined on matrices is continuous in the operator norm if and only if it is continuous as a function of the entries (Proposition 8.2.7). Finally, item vii is a direct computation.

L8.2.9: Determinant multiplication, transpose invariance and invertibility criterion.

Proposition 8.2.9.

If

A

and

B

are

n

-by-

n

matrices, then

\det(AB) = \det(A)\det(B)\text{.}

Furthermore,

A

is invertible if and only if

\det(A) \neq 0

and in this case,

\det(A^{-1}) = \frac{1}{\det(A)}\text{.}

Proof.

Let

b_1,b_2,\ldots,b_n

be the columns of

B\text{.}

Then

\begin{equation*} AB = [ Ab_1 \quad Ab_2 \quad \cdots \quad Ab_n ] . \end{equation*}

That is, the columns of

AB

are

Ab_1,Ab_2,\ldots,Ab_n\text{.}

Let

b_{j,k}

denote the elements of

B

and

a_j

the columns of

A\text{.}

By linearity of the determinant,

\begin{equation*} \begin{split} \det(AB) & = \det \bigl([ Ab_1 \quad Ab_2 \quad \cdots \quad Ab_n ] \bigr) = \det \left(\left[ \sum_{j=1}^n b_{j,1} a_j \quad Ab_2 \quad \cdots \quad Ab_n \right]\right) \\ & = \sum_{j=1}^n b_{j,1} \det \bigl([ a_j \quad Ab_2 \quad \cdots \quad Ab_n ]\bigr) \\ & = \sum_{1 \leq j_1,j_2,\ldots,j_n \leq n} b_{j_1,1} b_{j_2,2} \cdots b_{j_n,n} \det \bigl([ a_{j_1} \quad a_{j_2} \quad \cdots \quad a_{j_n} ]\bigr) \\ & = \left( \sum_{(j_1,j_2,\ldots,j_n) \in S_n} b_{j_1,1} b_{j_2,2} \cdots b_{j_n,n} \operatorname{sgn}(j_1,j_2,\ldots,j_n) \right) \det \bigl([ a_{1} \quad a_{2} \quad \cdots \quad a_{n} ]\bigr) . \end{split} \end{equation*}

In the last equality, we sum over the elements of

S_n

instead of all

n

-tuples for integers between 1 and

n\text{,}

because when two columns in the determinant are the same, then the determinant is zero. Reordering the columns to the original ordering obtains the sgn.

The conclusion that

\det(AB) = \det(A)\det(B)

follows by recognizing that the expression in parentheses above is the determinant of

B\text{.}

We obtain this by plugging in

A=I\text{.}

The expression we get for the determinant of

B

has rows and columns swapped, so as a bonus, we have also just proved that the determinant of a matrix and its transpose are equal.

Let us prove the “Furthermore.” If

A

is invertible, then

A^{-1}A = I\text{.}

Consequently

\det(A^{-1})\det(A) = \det(A^{-1}A) = \det(I) = 1\text{.}

If

A

is not invertible, then it is not one-to-one, and so

A

takes some nonzero vector to zero. In other words, the columns of

A

are linearly dependent. Suppose

\begin{equation*} \sum_{k=1}^n \gamma_k\, a_k = 0 , \end{equation*}

where not all

\gamma_k

are equal to 0. Without loss of generality, suppose

\gamma_1\neq 0\text{.}

Take

\begin{equation*} B \coloneqq \begin{bmatrix} \gamma_1 & 0 & 0 & \cdots & 0 \\ \gamma_2 & 1 & 0 & \cdots & 0 \\ \gamma_3 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \gamma_n & 0 & 0 & \cdots & 1 \end{bmatrix} . \end{equation*}

Using the definition of the determinant (there is only a single permutation

\sigma

for which

\prod_{i=1}^n b_{i,\sigma_i}

is nonzero) we find

\det(B) = \gamma_1 \neq 0\text{.}

Then

\det(AB) = \det(A)\det(B) = \gamma_1\det(A)\text{.}

The first column of

AB

is zero, and hence

\det(AB) = 0\text{.}

We conclude

\det(A) = 0\text{.}