<< . .

. 5
( : 95)



. . >>

20 1. Foundations of Matrix Analysis

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)

<< . .

. 5
( : 95)



. . >>