Property 1.11 Let · be a norm of Rn and A ∈ Rn—n be a matrix with

n linearly independent columns. Then, the function · A2 acting from Rn

into R de¬ned as

∀x ∈ Rn ,

x = Ax

A2

is a norm of Rn .

Two vectors x, y in V are said to be orthogonal if (x, y) = 0. This statement

has an immediate geometric interpretation when V = R2 since in such a

case

(x, y) = x y cos(‘),

2 2

where ‘ is the angle between the vectors x and y. As a consequence, if

(x, y) = 0 then ‘ is a right angle and the two vectors are orthogonal in the

geometric sense.

De¬nition 1.18 Two norms · p and · q on V are equivalent if there

exist two positive constants cpq and Cpq such that

¤x ¤ Cpq x ∀x ∈ V.

cpq x q p q

In a ¬nite-dimensional normed space all norms are equivalent. In particular,

if V = Rn it can be shown that for the p-norms, with p = 1, 2, and ∞, the

constants cpq and Cpq take the value reported in Table 1.1.

q=∞ q=∞

cpq q=1 q=2 Cpq q=1 q=2

n1/2

p=1 1 1 1 p=1 1 n

’1/2

n1/2

p=2 n 1 1 p=2 1 1

n’1 ’1/2

p=∞ p=∞

n 1 1 1 1

TABLE 1.1. Equivalence constants for the main norms of Rn

In this book we shall often deal with sequences of vectors and with their

convergence. For this purpose, we recall that a sequence of vectors x(k)

in a vector space V having ¬nite dimension n, converges to a vector x, and

we write lim x(k) = x if

k’∞

(k)

lim xi = xi , i = 1, . . . , n (1.15)

k’∞

(k)

where xi and xi are the components of the corresponding vectors with

respect to a basis of V . If V = Rn , due to the uniqueness of the limit of a

1.11 Matrix Norms 21

sequence of real numbers, (1.15) implies also the uniqueness of the limit, if

existing, of a sequence of vectors.

We further notice that in a ¬nite-dimensional space all the norms are topo-

logically equivalent in the sense of convergence, namely, given a sequence

of vectors x(k) ,

|||x(k) ||| ’ 0 ” x(k) ’ 0 if k ’ ∞,

where ||| · ||| and · are any two vector norms. As a consequence, we can

establish the following link between norms and limits.

·

Property 1.12 Let be a norm in a space ¬nite dimensional space V .

Then

lim x(k) = x ” lim x ’ x(k) = 0,

k’∞ k’∞

where x ∈ V and x(k) is a sequence of elements of V .

1.11 Matrix Norms

De¬nition 1.19 A matrix norm is a mapping · : Rm—n ’ R such that:

1. A ≥ 0 ∀A ∈ Rm—n and A = 0 if and only if A = 0;

2. ±A = |±| A ∀± ∈ R, ∀A ∈ Rm—n (homogeneity);

3. A + B ¤ A + B ∀A, B ∈ Rm—n (triangular inequality).

Unless otherwise speci¬ed we shall employ the same symbol · , to denote

matrix norms and vector norms.

We can better characterize the matrix norms by introducing the concepts

of compatible norm and norm induced by a vector norm.

De¬nition 1.20 We say that a matrix norm · is compatible or consistent

with a vector norm · if

Ax ¤ A ∀x ∈ Rn .

x, (1.16)

More generally, given three norms, all denoted by · , albeit de¬ned on

Rm , Rn and Rm—n , respectively, we say that they are consistent if ∀x ∈ Rn ,

Ax = y ∈ Rm , A ∈ Rm—n , we have that y ¤ A x .

In order to single out matrix norms of practical interest, the following

property is in general required

22 1. Foundations of Matrix Analysis

·

De¬nition 1.21 We say that a matrix norm is sub-multiplicative if

∀A ∈ Rn—m , ∀B ∈ Rm—q

AB ¤ A B. (1.17)

This property is not satis¬ed by any matrix norm. For example (taken from

[GL89]), the norm A ∆ = max |aij | for i = 1, . . . , n, j = 1, . . . , m does

not satisfy (1.17) if applied to the matrices

1 1

A=B= ,

1 1

since 2 = AB ∆ > A ∆ B ∆ = 1.

Notice that, given a certain sub-multiplicative matrix norm · ± , there

always exists a consistent vector norm. For instance, given any ¬xed vector

y = 0 in Cn , it su¬ces to de¬ne the consistent vector norm as

x ∈ Cn .

x = xyH ±

As a consequence, in the case of sub-multiplicative matrix norms it is no

longer necessary to explicitly specify the vector norm with respect to the

matrix norm is consistent.

Example 1.7 The norm

n

|aij |2 = tr(AAH )

A = (1.18)

F

i,j=1

2

is a matrix norm called the Frobenius norm (or Euclidean norm in Cn ) and is

compatible with the Euclidean vector norm · 2 . Indeed,

2

n n n n n

¤ |aij | |xj |2

2 2 2

x 2.

Ax = aij xj =A

2 F 2

i=1 j=1 i=1 j=1 j=1

√

•

Notice that for such a norm In = n.

F

In view of the de¬nition of a natural norm, we recall the following theorem.

Theorem 1.1 Let · be a vector norm. The function

Ax

A = sup (1.19)

x

x=0

is a matrix norm called induced matrix norm or natural matrix norm.

1.11 Matrix Norms 23

Proof. We start by noticing that (1.19) is equivalent to

A = sup Ax . (1.20)

x =1

Indeed, one can de¬ne for any x = 0 the unit vector u = x/ x , so that (1.19)

becomes

A = sup Au = Aw with w = 1.

u =1

This being taken as given, let us check that (1.19) (or, equivalently, (1.20)) is

actually a norm, making direct use of De¬nition 1.19.

1. If Ax ≥ 0, then it follows that A = sup Ax ≥ 0. Moreover

x =1

Ax

= 0 ” Ax = 0 ∀x = 0

A = sup

x

x=0

and Ax = 0 ∀x = 0 if and only if A=0; therefore A = 0 ” A = 0.

2. Given a scalar ±,

±A = sup ±Ax = |±| sup Ax = |±| A .

x =1 x =1

3. Finally, triangular inequality holds. Indeed, by de¬nition of supremum, if

x = 0 then

Ax

¤A ’ Ax ¤ A x,

x

so that, taking x with unit norm, one gets

(A + B)x ¤ Ax + Bx ¤ A + B ,

from which it follows that A + B = sup (A + B)x ¤ A + B .

x =1

3

Relevant instances of induced matrix norms are the so-called p-norms de-

¬ned as

Ax p

A = sup

p

xp

x=0

The 1-norm and the in¬nity norm are easily computable since

m n

|aij |, |aij |

A = max A = max

∞

1

j=1,... ,n i=1,... ,m

i=1 j=1

and they are called the column sum norm and the row sum norm, respec-

tively.

Moreover, we have A 1 = AT ∞ and, if A is self-adjoint or real sym-

metric, A 1 = A ∞ .

A special discussion is deserved by the 2-norm or spectral norm for which

the following theorem holds.

24 1. Foundations of Matrix Analysis

Theorem 1.2 Let σ1 (A) be the largest singular value of A. Then

ρ(AH A) = ρ(AAH ) = σ1 (A).

A = (1.21)

2

In particular, if A is hermitian (or real and symmetric), then

A = ρ(A), (1.22)

2

while, if A is unitary, A = 1.

2

Proof. Since AH A is hermitian, there exists a unitary matrix U such that

UH AH AU = diag(µ1 , . . . , µn ),

where µi are the (positive) eigenvalues of AH A. Let y = UH x, then

(AH Ax, x) (UH AH AUy, y)

A = sup = sup

2

(x, x) (y, y)

x=0 y=0

n n

µi |yi | / |yi |2 = max |µi |,

2

= sup

i=1,... ,n

y=0

i=1 i=1

from which (1.21) follows, thanks to (1.10).

If A is hermitian, the same considerations as above apply directly to A.

Finally, if A is unitary

2

= (Ax, Ax) = (x, AH Ax) = x 2

Ax 2 2

3

so that A = 1.

2

As a consequence, the computation of A 2 is much more expensive than

that of A ∞ or A 1 . However, if only an estimate of A 2 is required,

the following relations can be pro¬tably employed in the case of square

matrices

max|aij | ¤ A ¤ n max|aij |,2

i,j i,j

√

A ∞ ¤ A 2 ¤ n A ∞,

1

√

n

√

A 1 ¤ A 2 ¤ n A 1,

1

√

n

¤

A A A ∞.

2 1

For other estimates of similar type we refer to Exercise 17. Moreover, if A

is normal then A 2 ¤ A p for any n and all p ≥ 2.

Theorem 1.3 Let ||| · ||| be a matrix norm induced by a vector norm ·.

Then

1. Ax ¤ |||A||| x , that is, ||| · ||| is a norm compatible with ·;

1.11 Matrix Norms 25

2. |||I||| = 1;

3. |||AB||| ¤ |||A||| |||B|||, that is, ||| · ||| is sub-multiplicative.

Proof. Part 1 of the theorem is already contained in the proof of Theorem 1.1,

while part 2 follows from the fact that |||I||| = sup Ix / x = 1. Part 3 is simple

x=0

3

to check.

Notice that the p-norms are sub-multiplicative. Moreover, we remark that

the sub-multiplicativity property by itself would only allow us to conclude

that |||I||| ≥ 1. Indeed, |||I||| = |||I · I||| ¤ |||I|||2 .

1.11.1 Relation between Norms and the Spectral Radius of a

Matrix

We next recall some results that relate the spectral radius of a matrix to

matrix norms and that will be widely employed in Chapter 4.

·

Theorem 1.4 Let be a consistent matrix norm; then

ρ(A) ¤ A ∀A ∈ Cn—n .

Proof. Let » be an eigenvalue of A and v = 0 an associated eigenvector. As a

·

consequence, since is consistent, we have

|»| v = »v = Av ¤ A v

so that |»| ¤ A . 3

More precisely, the following property holds (see for the proof [IK66], p.

12, Theorem 3).

Property 1.13 Let A ∈ Cn—n and µ > 0. Then, there exists a consistent

matrix norm · A,µ (depending on µ) such that

¤ ρ(A) + µ.

A A,µ

As a result, having ¬xed an arbitrarily small tolerance, there always exists

a matrix norm which is arbitrarily close to the spectral radius of A, namely

ρ(A) = inf A , (1.23)

·

the in¬mum being taken on the set of all the consistent norms.

For the sake of clarity, we notice that the spectral radius is a sub-

multiplicative seminorm, since it is not true that ρ(A) = 0 i¬ A = 0.

As an example, any triangular matrix with null diagonal entries clearly has

spectral radius equal to zero. Moreover, we have the following result.

26 1. Foundations of Matrix Analysis

Property 1.14 Let A be a square matrix and let · be a consistent norm.

Then

lim Am 1/m

= ρ(A).

m’∞

1.11.2 Sequences and Series of Matrices

∈ Rn—n is said to converge to a matrix

A(k)

A sequence of matrices

A ∈ Rn—n if

lim A(k) ’ A = 0.

k’∞

The choice of the norm does not in¬‚uence the result since in Rn—n all norms

are equivalent. In particular, when studying the convergence of iterative

methods for solving linear systems (see Chapter 4), one is interested in the

so-called convergent matrices for which

lim Ak = 0,

k’∞

0 being the null matrix. The following theorem holds.

Theorem 1.5 Let A be a square matrix; then

lim Ak = 0 ” ρ(A) < 1. (1.24)

k’∞

∞

Ak is convergent i¬ ρ(A) < 1. In such a

Moreover, the geometric series

k=0

case

∞

Ak = (I ’ A)’1 . (1.25)