Advanced Calculus Single Variable

B.3 Norms On Linear Maps

To begin with, the notion of a linear map is just a function which is linear. Such a function, denoted by L, and mapping ℝⁿ to ℝ^m is linear means

(\summ ) \summ L xivi = xiLvi i=1 i=1

In other words, it distributes across additions and allows one to factor out scalars. Hopefully this is familiar from linear algebra. If not, there is a short review of linear algebra in the appendix.

Definition B.3.1 We use the symbol ℒ

to denote the space of linear transformations which map ℝⁿ to ℝ^m. For L ∈ℒ

one can always consider it as an m × n matrix A as follows. Let

( ) A = Le1 Le2 \cdot\cdot\cdot Len

where in the above Le_i is the i^th column. Define the sum and scalar multiple of linear transformations in the natural manner. That is, for L,M linear transformations and α,β scalars,

(αL + βM )(x) \equiv αL (x)+ βM (x )

Observation B.3.2 With the above definition of sums and scalar multiples of linear transformations, the result of such a linear combination of linear transformations is itself linear. Indeed, for x,y vectors and a,b scalars,

(αL + βM )(ax+ by) \equiv αL (ax + by)+ βM (ax + by )

= αaL (x )+ αbL(y)+ βaM (x)+ βbM (y)

= a(αL(x) +βM (x))+ b(αL(y)+ βM (y)) = a(αL +βM )(x)+ b(αL +βM )(y )

Also, a linear combination of linear transformations corresponds to the linear combination of the corresponding matrices in which addition is defined in the usual manner as addition of corresponding entries. To see this, note that if A is the matrix of L and B the matrix of M,

(αL + βM )ei \equiv (αA + βB )ei = αAei + βBei

by the usual rules of matrix multiplication. Thus the i^th column of

is the linear combination of the i^th columns of A and B according to usual rules of matrix multiplication.

Proposition B.3.3 For L ∈ℒ

, the matrix defined above satisfies

n Ax = Lx, x \in ℝ

and if any m × n matrix A does satisfy Ax = Lx, then A is given in the above definition.

Proof: Ax = Lx for all x if and only if for x =∑ _i=1ⁿx_ie_i

( x1 ) ( n\sum ) \sumn ( )| x2 | Ax = L xiei = xiL(ei) \equiv Le1 Le2 \cdot\cdot\cdot Len || . || i=1 i=1 ( .. ) xn

if and only if for every x ∈ ℝⁿ,

( ) Ax = Le1 Le2 \cdot\cdot\cdot Len x

which happens if and only if A =

. ■

Definition B.3.4 The norm of a linear transformation of A ∈ℒ

is defined as

||A || \equiv sup{||Ax ||m : ||x||n \leq 1} < \infty. ℝ ℝ

Then

is referred to as the operator norm of the linear transformation A.

It is an easy exercise to verify that

is a norm on ℒ

and it is always the case that

||Ax ||ℝm \leq ||A||||x||ℝn .

Furthermore, you should verify that you can replace ≤ 1 with = 1 in the definition. Thus

||A || \equiv sup{||Ax||ℝm : ||x||ℝn = 1}.

It is necessary to verify that this norm is actually well defined.

Lemma B.3.5 The operator norm is well defined. Let A ∈ℒ

Proof: We can use the matrix of the linear transformation with matrix multiplication interchangeably with the linear transformation. This follows from the above considerations. Suppose lim_k→∞v^k = v in ℝⁿ. Does it follow that Av^k → Av? This is indeed the case with the usual Euclidean norm and therefore, it is also true with respect to any other norm by the equivalence of norms (Theorem B.2.33). To see this,

( m )1∕2 ( m ||n ||2) 1∕2 ||Avk - Av || \equiv \sum ||(Avk ) - (Av )||2 \leq | \sum ||\sum A (vk- v )|| | i=1 i i ( i=1 ||j=1 ij j j|| )

( ) ( ) m ( n )2 1∕2 m ( n ) 2 1∕2 \leq |(\sum (\sum |Aij|||vk- vj||) |) \leq ||vk - v|||( \sum (\sum |Aij|) |) i=1 j=1 j i=1 j=1

Thus A is continuous. Then also v →

_ℝ^m is a continuous function by the triangle inequality. Indeed,

|||Av ||ℝm - ||Au||ℝm | \leq ||Av - Au||ℝm

Now let D be the closed ball of radius 1 in V . By Theorem B.2.32, this set D is compact and so

max {||Av || : ||v|| \leq 1} \equiv ||A|| < \infty.■ ℝm ℝn

Then we have the following theorem.

Theorem B.3.6 Let ℝⁿ and ℝ^m be finite dimensional normed linear spaces of dimension n and m respectively and denote by

the norm on either ℝⁿ or ℝ^m. Then if A is any linear function mapping ℝⁿ to ℝ^m, then A ∈ℒ

and

is a complete normed linear space of dimension nm with

||Ax || \leq ||A||||x||.

Also if A ∈ℒ

and B ∈ℒ

where ℝⁿ, ℝ^m, ℝ^p are normed linear spaces,

∥BA∥ \leq ∥B∥ ∥A∥

Proof: It is necessary to show the norm defined on linear transformations really is a norm. Again the triangle inequality is the only property which is not obvious. It remains to show this and verify

< ∞. This last follows from the above Lemma B.3.5. Thus the norm is at least well defined. It remains to verify its properties.

||A+ B || \equiv sup{||(A + B)(x)|| : ||x|| \leq 1}

\leq sup{||Ax|| : ||x|| \leq 1}+ sup{||Bx || : ||x || \leq 1} \equiv ||A||+||B||.

Next consider the assertion about the dimension of ℒ

. This is fairly obvious because a basis for the space of m × n matrices is clearly the matrices E_ij which has a 1 in the ij^th position and a 0 everywhere else. By Theorem B.2.33

is complete. If x≠0,

1 |||| x |||| ||Ax ||----= ||||A ----|||| \leq ||A || ||x|| ||x||

Thus

≤

Consider the last claim.

∥BA ∥ \equiv sup ∥B (A (x ))∥ \leq ∥B ∥ sup ∥Ax ∥ = ∥B ∥∥A∥ ■ ∥x∥\leq1 ∥x∥\leq1

What does it mean to say that A^k → A in terms of this operator norm? In words, this happens if and only if the ij^th entry of A^k converges to the ij^th entry of A for each ij.

Proposition B.3.7 lim_k→∞

= 0 if and only if for every i,j

lim ||Ak - A || = 0 k\to \infty ij ij

Proof: If A is an m×n matrix, then A_ij = e_i^TAe_j. Suppose now that

→ 0. Then in terms of the usual Euclidean norm and using the Cauchy Schwarz inequality,

| k | |T ( k ) | |Aij - Aij| = |ei A - A ej| =

|( ( ) )| |( ) | || || | ei, Ak - A ej | \leq |ei|| Ak - A ej| \leq ||Ak - A|| (2.10)

(2.10)

If the operator norm is taken with respect to

, some other norm than the Euclidean norm, then the right side of the above after ≤

||( k ) || ||||( k ) |||| |||| k |||| A - A ej \leq Δ A - A ej \leq Δ A - A ||ej||

Thus convergence in operator norm implies pointwise convergence of the entries of A^k to the corresponding entries of A.

Next suppose the entries of A^k converge to the corresponding entries of A. If

≤ 1, and to save notation, let B^k = A^k − A. Then

||( k ) || ||( \sum k \sum k \sum )T|| A - A v = | jB1jvj jB 2jvj \cdot\cdot\cdot jBmjvj |

( ( ) 2)1∕2 ( ( ) 2) 1∕2 \sum \sum | | \sum \sum | | = |( ( |Bkij||vj|) |) \leq |v||( ( |Bkij|) |) i j i j

By equivalence of norms,

( ( ) 2)1∕2 |||| k |||| | \sum ( \sum || k||) | δ B v \leq Δ ||v||( Bij ) i j

and so if

≤ 1,

( )1∕2 \sum ( \sum ) 2 δ||||Bkv |||| \leq Δ |( ( ||Bkij||) |) i j

and so

( ( ) 2)1∕2 ||||Bk|||| \leq Δ-|\sum ( \sum ||Bk ||) | δ ( i j ij )

the quantity on the right converging to 0. ■