Lecture notes on matrix analysis

Mark W. Meckes

April 27, 2019

Contents
1 Linear algebra background 3
1.1 Fundamentals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Matrices and linear maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Rank and eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Matrix factorizations 7
2.1 SVD: The fundamental theorem of matrix analysis . . . . . . . . . . . . . . 7
2.2 A first application: the Moore–Penrose inverse . . . . . . . . . . . . . . . . 9
2.3 The spectral theorems and polar decomposition . . . . . . . . . . . . . . . . 10
2.4 Factorizations involving triangular matrices . . . . . . . . . . . . . . . . . . 14
2.5 Simultaneous factorizations . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Eigenvalues of Hermitian matrices 20

3.1 Variational formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Inequalities for eigenvalues of two Hermitian matrices . . . . . . . . . . . . 22
3.3 Majorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4 Norms 31
4.1 Vector norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 Special classes of norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.3 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.4 Matrix norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.5 The spectral radius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.6 Unitarily invariant norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.7 Duality for matrix norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5 Some topics in solving linear systems 50

5.1 Condition numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.2 Sparse signal recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

6 Positive (semi)definite matrices 55

6.1 Characterizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.2 Kronecker and Hadamard products . . . . . . . . . . . . . . . . . . . . . . . 57
6.3 Inequalities for positive (semi)definite matrices . . . . . . . . . . . . . . . . 58

1
7 Locations and perturbations of eigenvalues 60
7.1 The Geršgorin circle theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 60
7.2 Eigenvalue perturbations for non-Hermitian matrices . . . . . . . . . . . . . 61

8 Nonnegative matrices 64
8.1 Inequalities for the spectral radius . . . . . . . . . . . . . . . . . . . . . . . 64
8.2 Perron’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
8.3 Irreducible nonnegative matrices . . . . . . . . . . . . . . . . . . . . . . . . 71
8.4 Stochastic matrices and Markov chains . . . . . . . . . . . . . . . . . . . . . 73
8.5 Reversible Markov chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
8.6 Convergence rates for Markov chains . . . . . . . . . . . . . . . . . . . . . . 77

9 Spectral graph theory 79

9.1 Eigenvalues of the adjacency matrix . . . . . . . . . . . . . . . . . . . . . . 79
9.2 The graph Laplacian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

2
1 Linear algebra background
If you need to brush up on linear algebra background, the best source is, of course,

Linear Algebra, by Elizabeth S. Meckes and Mark W. Meckes, Cambridge Uni-

versity Press, 2018.

1.1 Fundamentals
We will use F to stand for either the set of real numbers R or the set of complex numbers
C. In this class we will deal only with finite-dimensional vector spaces over R or C.
Basics terms which you should be comfortable with:

• vector space over F

• subspace

• span

• linearly (in)dependent

• basis

• standard basis of Fn

• dimension

• linear transformation/map

• matrix

• identity matrix

• identity map

• invertible matrix

• invertible linear map

• singular matrix

• singular linear map

• inverse matrix

• inverse map

• kernel/null space

• image/range

• determinant

3
 • eigenvector

• eigenvalue

• characteristic polynomial

• inner product

• norm (associated with an inner product)

• standard inner product on Fn

• orthogonal

• orthonormal basis

• unitary map

• unitary matrix

• orthogonal matrix

1.2 Matrices and linear maps

Give a matrix u ∈ V and a basis B = (v1 , . . . , vn ) of V , the matrix representing u with
respect to B is the column matrix x ∈ Mn,1 such that
n
X
u= xi vi .
i=1

Given a linear map T : V → W and bases B1 = (v1 , . . . , vn ) of V and B2 = (w1 , . . . , wm )

of W , the matrix representing T with respect to B1 and B2 is the unique matrix
A ∈ Mm,n such that
m
X
T (vj ) = aij wi
i=1

for each j. Equivalently, the jth column of A is the matrix of T (vj ) with respect to B2 .
If V = W and we consider the same basis B = B1 = B2 in both cases, we speak simply
of the matrix representing T with respect to B.
There are no universally agreed-upon notations for the above notions, and we will not
introduce any since they inevitably lead to a lot of notational clutter. Writing out “the
matrix of T with respect to B1 and B2 ” is pretty cumbersome, too, but we won’t need to
write it that often after this section.

Proposition 1.1. Let B1 be a basis of V and B2 be a basis of W . Let T : V → W be a

linear map, v ∈ V , and write w = T (v). Let A be the matrix of T with respect to B1 and
B2 , x the matrix of v with respect to B1 , and y the matrix of w with respect to B2 . Then
y = Ax.

4
Proposition 1.2. Let B1 be a basis of V , B2 be a basis of W , and B3 be a basis of X. Let
S : V → W and T : W → X be linear maps, let A be the matrix of S with respect to B1
and B2 , and let B be the matrix of T with respect to B2 and B3 . Then the matrix of the
linear map T S : V → X with respect to B1 and B3 is BA.

Corollary 1.3 (Change of basis formula). Let B1 = (v1 , . . . , vn ) and B2 = (w1 , . . . , wn ) be

bases of V , and let S ∈ Mn be the matrix representing the identity map with respect to B1
and B2 . That is, S is the unique matrix such that
m
X
vj = sij wi
i=1

for each j. Then S is invertible; it is called the change of basis matrix.

Let T : V → V be a linear map, and let A be the matrix representing T with respect to
B1 and let B be the matrix representing T with respect to B2 . Then B = S−1 AS.

Definition 1.4. Two matrices A, B ∈ Mn are similar if there exists an invertible matrix
S ∈ Mn such that
A = SBS−1 .
In that case S is called a similarity transformation between A and B.

A minor linguistic clarification may be in order: we may more precisely say that A and
B are similar to each other, or that A is similar to B. It doesn’t mean anything to say that
a single matrix A is similar.
Matrices which are similar (in this technical sense) to each other share many properties.
Two simple but important examples are contained in the following lemma.

Lemma 1.5. If A, B ∈ Mn are similar, then tr A = tr B and det A = det B.

A deeper explanation of the relationship between similar matrices is contained in the

following result, which says, informally, that similar matrices are just different represen-
tations of the same linear map. The proof is a direct application of the change of basis
formula.

Theorem 1.6. Two matrices A, B ∈ Mn are similar if and only if there exist a linear map
T ∈ L(Fn ) and two bases B1 and B2 of Fn such that A is the matrix of T with respect to
B1 and B is the matrix of T with respect to B2 .

Both of the implications in this “if and only if” theorem are important. On the one
hand, it says that any property of matrices which is preserved by similarity is really a
coordinate-independent property of the underlying linear maps. For example, it implies
that the following definitions make sense.

Definition 1.7. Given a linear map T ∈ L(V ), let A be the matrix of T with respect to
any basis of V . Then the trace and determinant of T are defined by

tr T = tr A and det T = det A.

5
 The point is that it doesn’t matter which basis of V is used here — even though different
bases give different matrices A, all the possible matrices are similar, and therefore have the
same trace and determinant. It is possible to define the trace and determinant of an operator
without making reference to bases or matrices (and there are advantages to doing so), but
it is much more complicated.

Proposition 1.8. Let V be an inner product space, let B = (e1 , . . . , en ) be an orthonormal

basis of V , and let v ∈ V . Then the matrix x of v with respect to B is given by

xi = hv, ei i .

Proposition 1.9. Let V and W be inner product spaces, B1 = (e1 , . . . , en ) be an orthonor-

mal basis of V , B2 = (f1 , . . . , fm ) be an orthonormal basis of W , and let T : V → W be a
linear map. Then the matrix A of T with respect to B1 and B2 is given by

aij = hT ej , fi i .

Proposition 1.10. Let V be an inner product space, B an orthonormal basis of V , and

T : V → V a linear map. Then T is a unitary map if and only if the matrix of T with
respect to B is a unitary matrix (in the real case, an orthogonal matrix).

1.3 Rank and eigenvalues

There are several approaches to defining the rank of a linear map or matrix. We will say
that the rank of a linear map is the dimension of its image.

Proposition 1.11. Let A be a matrix. The number of linearly independent columns of A

is equal to the number of linearly independent rows of A.

Corollary 1.12. The rank of a matrix A may be equivalently defined as any of:

• the number of linearly independent columns of A,

• the dimension of the span of the columns of A,

• the number of linearly independent rows of A.

Furthermore rank A = rank AT , and rank A is equal to the rank of any linear map repre-
sented by A.

Proposition 1.13 (Rank-Nullity Theorem). If A ∈ Mm,n , then rank A + dim ker A = n.

If T : V → W is a linear map then rank T + dim ker T = dim V .

Corollary 1.14. The following are equivalent for a square matrix A ∈ M n.

1. A is invertible.

2. rank A = n.

3. dim ker A = 0.

6
 The following are equivalent for a linear map T : V → V .
1. T is invertible.
2. T is surjective.
3. T is injective.
One important application of the last corollary is that it gives a way to talk about
eigenvalues without dealing with the (in general harder) issue of identifying eigenvectors.
Corollary 1.15. Let A ∈ Mn be a square matrix and λ ∈ F. The following are equivalent.
1. λ is an eigenvalue of A.
2. dim ker(A − λI) > 0.
3. rank(A − λI) < n.
4. A − λI is singular.
5. pA (λ) = 0, where pA (z) = det(A − zI) is the characteristic polynomial of A.

2 Matrix factorizations
2.1 SVD: The fundamental theorem of matrix analysis
Theorem 2.1 (Singular value decomposition). 1. Let A ∈ Mm,n , and denote p = min{m, n}.
Then there exist U ∈ Um , V ∈ Un , and real numbers σ1 ≥ · · · ≥ σp ≥ 0 such that
A = U ΣV ∗ , (1)
where Σ ∈ Mm,n has entries [Σ]jj = σj for 1 ≤ j ≤ p, and all other entries are 0. If
A ∈ Mm,n (R), then U and V can be taken to be orthogonal.
We also have
p
X
A= σj uj vj∗ , (2)
j=1
where uj and vj denote the columns of U and V , respectively.
The numbers σ1 , . . . , σp are called the singular values of A, and are uniquely defined
by A.
2. Suppose that V and W are finite dimensional inner product spaces and that T : V →
W is a linear map. Write n = dim V , m = dim W , and p = min{m, n}. Then
there exist orthonormal bases e1 , . . . , en of V and f1 , . . . , fm of W , and real numbers
σ1 ≥ · · · ≥ σp ≥ 0 such that
(
σj fj if 1 ≤ j ≤ p,
T ej = (3)
0 if j > p.

The numbers σ1 , . . . , σp are called the singular values of T , and are uniquely defined
by T .

7
Proof. The first step is to observe that the two parts of the theorem are exactly equivalent
to each other.
We will prove the existence statement by induction on p, switching freely between the
two viewpoints. The basis case p = 1 is trivial. Suppose now that the theorem is known for
all smaller values of p.
The function f : Fn → R defined by f (x) = kAxk is continuous. By a theorem from
multivariable calculus, it achieves its maximum value on the closed, bounded set S =
{x ∈ Fn | kxk = 1}, say at x0 . That is, kx0 k = 1, and kAxk ≤ kAx0 k whenever kxk = 1.
Note that if kAx0 k = 0, then A = 0 and the result is trivial, so we may assume that
σ = kAx0 k > 0.
I claim that if hu, x0 i = 0, then hAu, Ax0 i = 0 as well. For t ∈ C, define
g(t) = kA(x0 + tu)k2 = hA(x0 + tu), A(x0 + tu)i = σ 2 + 2 Re t hAx0 , Aui + |t|2 kAuk2 .
On the one hand,
g(t) ≥ σ 2 + 2 Re t hAx0 , Aui .
On the other hand,
  2
2 x0 + tu
g(t) = kx0 + tuk A ≤ σ 2 kx0 + tuk2 = σ 2 hx0 + tu, x0 + tui = σ 2 (1+|t|2 kuk2 ).
kx0 + tuk
Together, these inequalities imply that
2 Re t hAx0 , Aui ≤ |t|2 σ 2 kuk2
for every t ∈ C. Setting t = hAu, Ax0 i ε for ε > 0, we obtain that
2 |hAx0 , Aui|2 ≤ |hAx0 , Aui|2 σ 2 kuk2 ε
for every ε > 0, which is only possible if hAx0 , Aui = 0.
Switching now to the linear map perspective, it follows that T (x⊥ ⊥
0 ) ⊆ (T x0 ) . Note
⊥ ⊥
that V1 := x0 ( V and W1 := (T x0 ) ( W . We can therefore apply the induction
hypothesis to the linear map T |V1 : V1 → W1 . The induction hypothesis states that there
exist orthonormal bases e1 , . . . , en−1 of V1 and f1 , . . . , fm of W1 such that
(
σj fj if 1 ≤ j ≤ p − 1,
T ej =
0 if j > p = 1.
Now define e0 = x0 , σ0 = σ = kAx0 k, and f0 = Ax
σ0 . Then e0 is orthonormal to e1 , . . . , en−1
0

and the claim above implies that f0 is also orthonormal to f1 , . . . , fm−1 . After reindexing,
the claim follows.
For uniqueness, note that if A = U ΣV ∗ , then A∗ A = V Σ2 V ∗ , and that
Σ2 = diag(σ12 , . . . , σp2 , 0, . . . 0) ∈ Mn .
Therefore σ1 , . . . , σp are the square roots of the first p eigenvalues of A∗ A, and are therefore
uniquely determined by A.
Corollary 2.2. If A ∈ Mm,n , then rank A is equal to the number of nonzero singular values
of A.
Proof. Again switching to the linear map perspective, the range of T is spanned by those
fj for which σj > 0.

8
2.2 A first application: the Moore–Penrose inverse
Suppose that m = n, and that A ∈ Mn has SVD
A = U ΣV ∗ = U diag(σ1 , . . . , σn )V ∗ .
By Corollary 2.2, A is invertible iff σn > 0. In that case,
A−1 = V Σ−1 U ∗ = V diag(σ1−1 , . . . , σn−1 )U ∗ .
More generally, for A ∈ Mm,n we have an SVD
 
D 0 ∗
A=U V , (4)
0 0
where D ∈ Mr has positive diagonal entries and r = rank A. We define
 −1 
† D 0 ∗
A =V V . (5)
0 0

We call A† the Moore–Penrose inverse or pseudoinverse of A. (Note that if m 6= n

then the 0 blocks in (4) and in (5) have different sizes. The block matrix on the right side
of (4) is m × n, but the one in (5) is n × m; this determines the sizes of all the 0 blocks.)
Lemma 2.3. The Moore–Penrose inverse of A ∈ Mm,n satisfies the following.
1. If m = n and A is invertible, then A† = A−1 .
2. AA† A = A.
3. A† AA† = A† .
4. (AA† )∗ = AA† .
5. (A† A)∗ = A† A.
Consider an m × n linear system Ax = b. When m = n = rank A, this has the
unique solution x = A−1 b. Now consider the underdetermined but full-rank case, when
rank A = m < n. The system then always has a solution, but not a unique one.
Proposition 2.4. If A ∈ Mm,n and rank A = m < n, then A(A† b) = b for each b ∈ Fm .
Moreover, if x ∈ Fm and Ax = b, then A† b ≤ kxk.
We therefore say that A† b is the least-squares solution of Ax = b.

Proof. Since rank A = m, given b ∈ Fm , there exists some x ∈ Fn such that Ax = b.

Therefore
AA† b = AA† Ax = Ax = b.
Furthermore,  
† † Im 0 ∗
A b = A Ax = V V x .
0 0
Writing y = V ∗ x,  
†Im 0
Ab = y ≤ kyk = kxk .
0 0

9
 If the system is overdetermined, there will usually be no solution at all. In that case we
may wish to find the closest possible thing to a solution: an x that minimizes kAx − bk.
Proposition 2.5. If A ∈ Mm,n and rank A = n < m, then for any x ∈ Fn and b ∈ Fm ,

A(A† b) − b ≤ kAx − bk .

We again call A† b a least-squares solution of Ax = b, but note that in this case A† b

may not actually be a solution of Ax = b.
 
D
Proof. In this case we can write the SVD of A as A = U V ∗ , where D ∈ Mn is diagonal
0
with positive diagonal entries σ1 , . . . , σn . If we write c = U ∗ b and y = V ∗ x, then
v
u n n
      uX
D ∗ D Dy X
kAx − bk = U V x−b = y−c = − c = t (σj yj − cj )2 + c2j .
0 0 0
j=1 j=m+1

For a given b (hence given c), this is clearly smallest when yj = σj−1 cj for j = 1, . . . , n. That
is,  −1 
D
y= c,
0
and so
D−1
 
x=Vy =V U ∗ c = A† b.
0
Propositions 2.4 and 2.5 can be combined into a single result, which also covers the
non-full rank case, as you will see in homework.

2.3 The spectral theorems and polar decomposition

Recall that a matrix A ∈ Mn is called Hermitian if A∗ = A. Note that a real matrix A is
Hermitian if and only if it is symmetric, that is, if AT = A.
Recall also that the adjoint of a linear map T : V → W between inner product spaces
is the unique linear map T ∗ : W → V such that

hT v, wi = hv, T ∗ wi

for every v ∈ V and w ∈ W . This corresponds to conjugate transpose of matrices: if

A ∈ Mm,n , then for every x ∈ Cn and y ∈ Cm , we have

hAv, wi = w∗ (Av) = w∗ (A∗ )∗ v = (A∗ w)∗ v = hv, A∗ wi .

A linear map T : V → V is called self-adjoint or Hermitian if T ∗ = T .

The next two results have corresponding versions for self-adjoint linear maps (which we
will use in the proof of Theorem 2.8 below), but for simplicity we will state and prove them
only in the matrix versions.
Lemma 2.6. If A is Hermitian, then every eigenvalue of A is real.

10
Proof. Suppose that Ax = λx. Then

hAx, xi = x∗ Ax = x∗ (λx) = λx∗ x = λ kxk2 ,

but also
hAx, xi = x∗ Ax = x∗ A∗ x = (Ax)∗ x = (λx)∗ x = λ kxk2 .
Therefore if x is an eigenvector of A with eigenvalue λ, then λ kxk2 = λ kxk2 . Dividing by
kxk2 , we see that λ = λ, and so λ ∈ R.

Lemma 2.6 is a first hint of a broad general analogy in which certain types of matrices
are like certain types of complex numbers. One aspect of this analogy is that the conjugate
transpose operation on matrices corresponds to complex conjugation of numbers; another
is that the eigenvalues of a class of matrices belong to the corresponding class of complex
numbers. So we see in two different ways that Hermitian matrices are analogous to real
numbers: both because the equation A∗ = A is analogous to λ = λ, and because eigenvalues
of Hermitian matrices are automatically real numbers. More manifestations of this analogy
will come up below.
Recall that eigenvectors of a matrix corresponding to distinct eigenvalues are necessarily
linearly independent. It turns out that more is true for Hermitian matrices.

Lemma 2.7. If A ∈ Mn (F) is Hermitian, then A has an eigenvector in Fn .

Proof. Let A = U ΣV ∗ be an SVD of A. Then

A2 = A∗ A = V Σ2 V ∗ .

Each column vj of V is therefore an eigenvector of A2 with corresponding eigenvalue σj2 .

Therefore
0 = (A2 − σj2 In )vj = (A + σj In )(A − σj In )vj .
Now if (A − σj In )vj = 0, then vj is an eigenvector of A with eigenvalue σj . On the other
hand, if (A − σj In )vj 6= 0, then (A − σj In )vj is an eigenvector of A with eigenvalue −σj .

Theorem 2.8 (The spectral theorem for Hermitian matrices). 1. If A ∈ Mn (F) is Her-
mitian, then there exists U ∈ Un and a diagonal matrix Λ ∈ Mn (R) such that
A = U ΛU ∗ . If F = R then U can be taken to be real orthogonal.

2. If T : V → V is self-adjoint, then there exists an orthonormal basis of V consisting

of eigenvectors of T .

Proof. As with Theorem 2.1, the first step is to observe that the two parts are equivalent
to one another.
Again we will proceed by induction, this time on n = dim V . The case n = 1 is trivial.
Suppose now that the theorem is known for spaces of dimension < n.
By Lemma 2.7, T has an eigenpair v and λ. I claim that if u ∈ V and hu, vi = 0, then
hT u, vi = 0 as well. Since T is self-adjoint,

hT u, vi = hu, T ∗ vi = hu, T vi = hu, λvi = λ hu, vi = 0.

11
So if we define V1 = v ⊥ , it follows that T (V1 ) = V1 .
So the linear map T |V1 maps V1 → V1 , and is furthermore still self-adjoint. The induction
hypothesis implies that there is an orthonormal basis (e1 , . . . , en−1 ) of V1 consisting of
v
eigenvectors of T . If we define en = kvk , then (e1 , . . . , en ) will now be an orthonormal basis
of V consisting of eigenvectors of T .

Continuing the analogy between matrices and complex numbers described above, we
might ask which matrices correspond to nonnegative real numbers. Three possibilities to
consider are:

• matrices with nonnegative eigenvalues,

• matrices of the form A = B 2 for some Hermitian matrix B (analogous to the fact that
λ ≥ 0 iff λ = x2 for some x ∈ R), or

• matrices of the form A = B ∗ B for some matrix B (analogous to the fact that λ ≥ 0
iff λ = |z|2 = zz for some z ∈ C).

Using Theorem 2.8 we can show that these three possibilities are all equivalent, and are
equivalent to a fourth positivity condition.

Theorem 2.9. Suppose that A ∈ Mn (F) is Hermitian. Then the following are equivalent:

1. Each eigenvalue of A is nonnegative.

2. There exists a Hermitian matrix B ∈ Mn (F) such that A = B 2 .

3. There exists a matrix B ∈ Mm,n (F) for some m such that A = B ∗ B.

4. For every x ∈ Fn , hAx, xi ≥ 0.

A Hermitian matrix satisfying the conditions of Theorem 2.9 is called a positive

semidefinite matrix. (The closely related notion of a positive definite matrix will appear
in homework.)

Proof. (1) ⇒ (2): By the spectral theorem (Theorem 2.8), we can write A = U ΛU ∗ for a
unitary matrix U ∈ Mn (F) and a diagonal matrix Λ = diag(λ1 , . . . , λn ), where the
p λj
are all eigenvalues of A. By assumption, λj ≥ 0, so it has a real square root λj .
Define p p
B = U diag( λ1 , . . . , λn )U ∗ .
Then B ∗ = B and
p p p p
B 2 = U diag( λ1 , . . . , λn )U ∗ U diag( λ1 , . . . , λn )U ∗ = A.

(2) ⇒ (3): This follows immediately.

(3) ⇒ (4): If A = B ∗ B, then for each x ∈ Fn , hAx, xi = hB ∗ Bx, Bxi = hBx, Bxi =
kBxk2 ≥ 0.

12
(4) ⇒ (1): Suppose that λ is an eigenvalue of A with corresponding eigenvector v. Then

0 ≤ hAv, vi = hλv, vi = λ hv, vi = λ kvk2 .

Since kvk > 0, this implies that λ ≥ 0.

The first part of the proof of Theorem 2.9 illustrates the basic philosophy of how the
spectral theorem is usually applied: many things are simple to do for diagonal matrices, and
the spectral theorem lets us pass from diagonal matrices to Hermitian matrices for many
purposes.
Theorem 2.8 raises the question of which matrices can be factorized as A = U ΛU ∗ for
U unitary and Λ diagonal. If Λ has real entries, then A has to be Hermitian, since in that
case
A∗ = (U ΛU ∗ )∗ = U Λ∗ U ∗ = U ΛU ∗ = A.
If we don’t insist that Λ have real entries, this is no longer the case, since Λ∗ 6= Λ for a
complex diagonal matrix. But it is still true that ΛΛ∗ = diag(|λ1 |2 , . . . , |λn |2 ) = Λ∗ Λ. So
if A = U ΛU ∗ , then we must have that

AA∗ = U ΛU ∗ U Λ∗ U ∗ = U ΛΛ∗ U ∗ = U Λ∗ ΛU ∗ = A∗ A.

We call a matrix A ∈ Mn (C) a normal matrix if AA∗ = A∗ A. It turns out that this is
also a sufficient condition for a decomposition as in Theorem 2.8, as we will see in Theorem
2.11 below.
Recall next that if z = x + iy is a complex number with x, y ∈ R, then the real and
imaginary parts of z are
z+z z−z
Re z = x = , Im z = y = .
2 2i
(Note that the imaginary part is actually a real number.) In analogy with this, we define
for A ∈ Mn (C),
A + A∗ A − A∗
Re A = , Im A = .
2 2i
We define Re T and Im T for a linear map T : V → V on an inner product space similarly.
Lemma 2.10. Suppose that A ∈ Mn (C). Then:
1. Re A and Im A are Hermitian.

2. A = (Re A) + i(Im A).

3. A is normal if and only if (Re A)(Im A) = (Im A)(Re A).

Note that even if A ∈ Mn (R), Im A will typically have nonreal entries.
Theorem 2.11 (The spectral theorem for normal matrices). 1. If A ∈ Mn (C) is nor-
mal, then there exists U ∈ Un and a diagonal matrix Λ ∈ Mn (C) such that A = U ΛU ∗ .

2. If T : V → V is normal and V is a complex inner product space, then there exists an

orthonormal basis of V consisting of eigenvectors of T .

13
Proof. We will prove the second part of the theorem, which as usual is equivalent to the
first. For brevity we write Tr = Re T and Ti = Im T .
First note that if v is an eigenvector of Tr with eigenvalue λ, then by Lemma 2.10,

Tr Ti v = Ti Tr v = λTi v.

It follows that Ti v is also an eigenvector of Tr with eigenvalue λ. Thus Ti maps the eigenspace
ker(Tr − λI) to itself.
Now by the spectral theorem for Hermitian matrices (Theorem 2.8), for each eigenvalue
λ of Tr , there exists an orthonormal basis of ker(Tr − λI) consisting of eigenvectors of Ti ,
which must also be eigenvectors of Tr . Moreover, Theorem 2.8 implies that the eigenvectors
of Tr span all of V , and that the distinct eigenspaces of Tr are orthogonal to each other, so
that combining these orthonormal bases of the eigenspaces yields an orthonormal basis of
all of V .

The last factorization in this section is the matrix analogue of the fact that a complex
number can be written in the form z = rω where r = |z| ≥ 0 and |ω| = 1. Since we can
furthermore write ω = eiθ = cos θ + i sin θ this amounts to polar coordinates in the complex
plane, which explains the name of the following result. (The fact that unitary matrices are
analogous to complex numbers with absolute value 1 will be justified by various results we’ll
see, both in homework and in class.)

Theorem 2.12 (The polar decomposition). Let A ∈ Mn (F). Then there exists a U ∈ Un
(which can be taken to be orthogonal if F = R) and positive semidefinite matrices P, Q ∈
Mn (F) such that A = P U = U Q.

Proof. Let A = W ΣV ∗ be an SVD for A. Then

A = W ΣW ∗ W V ∗ = W V ∗ V ΣV ∗ .

Define U = W V ∗ , P = W ΣW ∗ , and Q = V ΣV ∗ .

Observe that in this case P 2 = AA∗ and Q2 = A∗ A. This means that both P and Q
have a claim to be analogous to the “absolute value” of A.

2.4 Factorizations involving triangular matrices

Recall the following fundamental result about orthonormalization:

Proposition 2.13 (Gram–Schmidt process). Let (v1 , . . . , vn ) be a linearly independent list

of vectors in an inner product space V . Define e1 = v1 / kv1 k, and for each j = 2, . . . , n,
define recursively
j−1
X
uj = vj − hvj , ek i , ej = uj / kuj k .
k=1

Then (e1 , . . . , en ) is orthonormal, and for each j,

span(e1 , . . . , ej ) = span(v1 , . . . , vj ).

14
 The Gram–Schmidt process can be basically restated as a matrix factorization result:

Theorem 2.14 (The QR decomposition). If A ∈ Mn (F), there exist a unitary matrix

Q ∈ Un (orthogonal if F = R) and an upper triangular matrix R ∈ Mn (F) such that
A = QR.

Proof of Theorem 2.14 when A is nonsingular. Let a1 , . . . , an ∈ Fn be the columns of A.

If A is nonsingular, then (a1 , . . . , an ) forms a basis of Fn . We apply the Gram–Schmidt
process to obtain an orthonormal basis (q1 , . . . , qn ) of Fn . The matrix Q with these columns
is unitary. If we define R = Q∗ A, then R has entries

rjk = qj∗ ak = hak , qj i .

Since ak is in the span of (q1 , . . . , qk ), and the qj are orthonormal, this implies that rjk = 0
if j > k. Thus R is upper triangular.

We can extend Theorem 2.14 to singular matrices with a little more algebraic work,
but because this is a class on matrix analysis, we will instead use an analytic approach, for
which we need the following analytic fact:

Proposition 2.15. If Ω is a closed, bounded subset of RN , and {ωk | k ∈ N} is a sequence

of points in Ω, then there is a subsequence of {ωk | k ∈ N} that converges to a point in Ω.

Observe also that Un and On are closed and bounded sets: closed since if {Uk | k ∈ N}
is a sequence in Un or On with Uk → U , then

U ∗ U = lim Uk∗ Uk = lim In = In ;

k→∞ k→∞

and bounded since each column of U is a unit vector, and so |uij | ≤ 1 for every i, j.

Proof of Theorem 2.14 when A is singular. Given A, then matrix A + εIn is nonsingular as
long as −ε is not an eigenvalue of A. We define Ak = A + k1 In . Then if − k1 is greater than
the largest negative eigenvalue of A (if there are any at all), then Ak is nonsingular.
For all such k, let Ak = Qk Rk be a QR decomposition, which we have already seen
exists since Ak is nonsingular. Then there is a subsequence of the sequence {Qk | k ∈ N}
which converges to a matrix Q ∈ Un (in On if F = R). Writing this subsequence as Qkm for
m ∈ N, we have that
R := lim Rkm = lim Q∗km Akm = Q∗ A
m→∞ m→∞

exists. Furthermore, the limit of a sequence of upper triangular matrices is upper triangular.
From this we have that A = QR.

The next theorem is one of the most powerful tools for studying eigenvalues of arbitrary
(especially non-normal) matrices. Be careful to notice that it requires working over C, even
if the original matrix A has real entries.

Theorem 2.16 (Schur factorization). If A ∈ Mn (C), then there exist U ∈ Un and an upper
triangular T ∈ Mn (C) such that A = U T U ∗ .

15
Proof. We proceed by induction on n, the base case n = 1 being trivial.
By the Fundamental Theorem of Algebra, every polynomial with complex coefficients
has a complex root. Applied to the characteristic polynomial of A, this implies that A has
an eigenvalue λ1 with a corresponding eigenvector v1 . Extend v1 to a basis (v1 , . . . , vn ) of
Cn , and let S ∈ Mn be the invertible matrix with columns v1 , . . . , vn . Since Av1 = λv1 , it
follows that
λ1 w T
 
−1
S AS =
0 B
for some w ∈ Cn−1 and B ∈ Mn−1 (C). By the induction hypothesis, B = S1 T1 S1−1 for some
invertible S1 ∈ Mn−1 (C) and upper triangular T1 ∈ Mn−1 (C). This implies that
−1
wT 1 0 λ 1 xT 1 0
    
−1 λ1
S AS = = ,
0 S1 T1 S1−1 0 S1 0 T1 0 S1

where xT = wT S1 . Thus
−1
λ 1 xT 1 0
  
1 0
A=S S −1 = S2 T2 S2−1
0 S1 0 T1 0 S1

for an invertible S2 ∈ Mn (C) and upper triangular T2 ∈ Mn (C). Now let S2 = QR be a QR

decomposition for S2 . Then A = Q(RT2 R−1 )Q∗ , where Q is unitary and RT2 R−1 is upper
triangular, since the inverse of an upper triangular matrix is upper triangular. Letting
U = Q and T = RT2 R−1 proves the theorem.

Observe also that in the first step, we could pick any eigenvalue of A to be λ1 . It follows
that there exist Schur decompositions of A in which the eigenvalues of A appear on the
diagonal of T in any chosen order.
Recall that the Frobenius norm of a matrix A ∈ Mm,n (C) is given by
v
√ um X n
uX
kAkF = tr A A = ∗ t |ajk |2 .
j=1 k=1

That is, it is the norm of A when we identify A with a vector in Cm×n . The following basic
property will be used many times in this course.

Lemma 2.17. Suppose that A ∈ Mm,n (C), U ∈ Um , and V ∈ Un . Then kU AV kF = kAk.

Proof. kU AV k2F = tr(U AV )∗ (U AV ) = tr V ∗ A∗ U ∗ U AV = tr V ∗ A∗ AV = tr V V ∗ A∗ A =

tr A∗ A = kAk2F .

Corollary 2.18. For each A ∈ Mn (C) and ε > 0, there exists a diagonalizable matrix
B ∈ Mn (C) such that kA − Bk < ε.

In analytic language, Corollary 2.18 says that the set of diagonalizable matrices is dense
in Mn (C).

16
Proof. Let A = U T U ∗ be a Schur decomposition for A. Pick numbers λ1 , . . . , λn which are
distinct from each other, such that |λj − tjj | < √εn for each j. Define T1 to be the upper
triangular matrix whose jj entry is λj , and all other entries are the same as T , and then
define B = U T1 U ∗ . Then B is diagonalizable, because it has distinct eigenvalues λ1 , . . . , λn ,
and v
u n
uX
kA − BkF = kU (T − T1 )U ∗ kF = kT − T1 kF = t |λj − tjj |2 < ε.
j=1

The following result can also be proved in a more algebraic way, but Corollary 2.18
allows for a simple analytic proof.

Corollary 2.19 (Cayley–Hamilton theorem). Let p be the characteristic polynomial of

A ∈ Mn (C). Then p(A) = 0.

Proof. Suppose first that A is diagonalizable, and that A = SDS −1 for a diagonal matrix
D. Then D = diag(λ1 , . . . , λn ), where λj are the eigenvalues of A, and we can factor
p(x) = (x − λ1 ) · · · (x − λn ). It follows that

p(D) = (D − λ1 In ) · · · (D − λn In ) = 0,

since the j th factor here is a diagonal matrix whose j th entry is 0, and then p(A) =
Sp(D)S −1 = 0.
For the general case, by Corollary 2.18 we can find a sequence {Ak | k ∈ N} of diagonal-
izable matrices such that Ak → A. If pk denotes the characteristic polynomial of Ak , then
coefficient of pk converges to the corresponding coefficient of p. Therefore

p(A) = lim pk (Ak ) = 0

k→∞

by the above argument.

Corollary 2.20. The eigenvalues of a matrix A ∈ Mn (C) depend continuously on A. That

is, given A ∈ Mn (C) with eigenvalues λ1 , . . . , λn and ε > 0, there exists a δ > 0 such
that whenever B ∈ Mn (C) and kA − BkF < δ, it follows that we can write the eigenvalues
µ1 , . . . , µn of B in some order so that |λj − µj | < ε for each j.

Proof. Suppose the claim is not true. Then there exists an ε > 0 such that for every
k ∈ N we can find a Bk ∈ Mn (C) such that kA − Bk kF ≤ k1 but for every ordering of the
(m) (k)
eigenvalues µj of Bk , we have maxj λj − µj ≥ ε.
Let Bk = Uk Tk Uk∗ be Schur factorizations, in which the diagonal entries of Tk are ordered
in this way. There exists a subsequence of {Uk | k ∈ N} that converges to some U ∈ Un ;
say Ukm → U . Then
m→∞
Tkm = Uk∗m Bkm Ukm −−−−→ U ∗ AU,
which implies that T := U ∗ AU is upper triangular, with diagonal entries equal to the
eigenvalues of A in some order. But now this implies that, perhaps after reordering the
(k ) m→∞
eigenvalues of A, maxj λj − µj m −−−−→ 0, which is a contradiction.

17
2.5 Simultaneous factorizations
Theorem 2.21. Let A ⊆ Mn (F) be a family of diagonalizable matrices. The following are
equivalent:

1. A is simultaneously diagonalizable. That is, there exists a single invertible matrix

S ∈ Mn (F) such that S −1 AS is diagonal for every A ∈ A.

2. A is commuting. That is, for every A, B ∈ A, we have AB = BA.

Lemma 2.22. If A = A1 ⊕ · · · ⊕ Ak is diagonalizable, then each block Aj is diagonalizable.

Proof. It suffices to assume that k = 2. Suppose that C = A ⊕ B for A ∈ Mm and

B ∈ Mn , and that S −1 CS = diag(λ1 , . . . , λm+n ). We need to show that A and B are each
diagonalizable.
Write  
x1 · · · xm+n
S=
y1 · · · ym+n
for xj ∈ Fm and yj ∈ Fn . Then CS = S diag(λ1 , . . . , λm+n ) implies that Axj = λj xj and
Byj = λj yj for j = 1, . . . , m + n. Now since S has rank m + n, it follows that
   
rank x1 · · · xm+n = m and rank y1 · · · ym+n = n

(since otherwise the number of linearly independent rows of S would be smaller than m+n).
Therefore there exist m linearly independent xj , which form a basis of Fm consisting of
eigenvectors of A, so A is diagonalizable, and similarly B is diagonalizable.

Proof of Theorem 2.21. 1 ⇒ 2 is trivial. We prove 2 ⇒ 1 by induction on n, the case n = 1

being trivial.
The result is moreover trivial if every matrix in A is a scalar matrix (that is, of the
form λIn for some λ ∈ F). So suppose that A ∈ A is one fixed nonscalar matrix. Since B
is diagonalizable, there exists a nonsingular S such that SAS −1 is diagonal. By permuting
the columns of S if necessary, we may assume that

S −1 AS = (λ1 In1 ) ⊕ · · · ⊕ (λk Ink )

for distinct λ1 , . . . , λk , with k ≥ 2 and n1 + · · · + nk = n.

Since A is commuting, for each B, C ∈ A, (S −1 BS)(S −1 CS) = (S −1 CS)(S −1 BS). If
we write SBS −1 in block form as
 
B11 · · · B1k
S −1 BS =  ... .. .. 

. . 
Bk1 · · · Bkk

with Bij ∈ Mni ,nj (F), then AB = BA implies that λi Bij = λj Bij for each i, j. Since the
λi are distinct, this implies that Bij = 0 for i 6= j, and so SBS −1 = B11 ⊕ · · · ⊕ Bkk is
block-diagonal.

18
 By Lemma 2.22, each Bjj is diagonalizable for every B ∈ A, and furthermore Aj =
{Bjj | B ∈ A} is a commuting family. By the induction hypothesis, there exist invertible
matrices Sj ∈ Mnj (F) such that Sj−1 Bjj Sj is diagonal for each j and every B ∈ A. Letting

Se = S(S1 ⊕ · · · ⊕ Sk ),
it follows that Se−1 B Se is diagonal for every B ∈ A.
Theorem 2.23. If A ⊆ Mn (C) is commuting, then there exists a single matrix U ∈ Un
such that U ∗ AU is upper triangular for every A ∈ A.
Proof. As in the previous proof, we proceed by induction on n, assuming without loss of
generality that there exists a nonscalar A ∈ A.
Let λ be an eigenvalue of A, let v1 , . . . , vm be an orthonormal basis of the range of
A − λIn , extend it to an orthonormal basis v1 , . . . , vn of all of Cn , and let V ∈ Un be the
matrix with columns vj . For each B ∈ A and x ∈ Cn ,
B(A − λIn )x = (A − λIn )Bx.
It follows that V ∗ BV has the block triangular form
 
∗ B11 B12
V BV =
0 B22
with B11 ∈ Mm and B22 ∈ Mn−m . Since A is commuting, if B, C ∈ A, then
     
B11 B12 C11 C12 C11 C12 B11 B12
= ,
0 B22 0 C22 0 C22 0 B22
which implies that B11 C11 = C11 B11 and B22 C22 = C22 B22 . Therefore, the families
A1 = {B11 | B ∈ A} and A2 = {B22 | B ∈ A}
are commuting.
By the induction hypothesis, there exist V1 ∈ Um and V2 ∈ Un−m such that Vj∗ Bjj Vj is
upper triangular for every B ∈ A and j = 1, 2. If we now define U = V (V1 ⊕ V2 ), it follows
that for each B ∈ A,
 ∗   ∗
V1 B11 V1 V1∗ B12 V2
  
∗ V1 0 B11 B12 V1 0
U BU = =
0 V2∗ 0 B22 0 V2 0 V2∗ B22 V2
is upper triangular.
Corollary 2.24. Let A ⊆ Mn (C) be a family of normal matrices. The following are
equivalent:
1. There exists a single matrix U ∈ Un such that U ∗ AU is diagonal for every A ∈ A.
2. A is commuting.
Proof. As you saw in homework, an upper triangular normal matrix is diagonal, so that
this follows immediately from Theorem 2.23.
This is the finite-dimensional case of the commutative Gelfand–Naimark theorem from
the theory of operator algebras.

19
3 Eigenvalues of Hermitian matrices
If A ∈ Mn (C) is Hermitian, then we know that the n eigenvalues of A (counted with
multiplicity) are all real. By default we will put them in nondecreasing order and write
them as λ1 (A) ≤ λ2 (A) ≤ · · · ≤ λn (A) (omitting the A when there is no ambiguity). We
will also sometimes write λmin and λmax for the smallest and largest eigenvalues. Observe
that, as with the Schur decomposition, we can always arrange to have the eigenvalues appear
on the diagonal part of any spectral decomposition of A in any chosen order.

3.1 Variational formulas

Theorem 3.1 (Rayleigh–Ritz theorem). Suppose that A ∈ Mn (F) is Hermitian. Then for
every x ∈ Fn ,
λmin kxk2 ≤ hAx, xi ≤ λmax kxk2 .
Moreover,
hAx, xi
λmin = minn = minn hAx, xi
x∈F kxk2 x∈F
x6=0 kxk=1

and
hAx, xi
λmax = maxn = maxn hAx, xi .
x∈F kxk2 x∈F
x6=0 kxk=1

Proof. Let A = U ΛU ∗ be a spectral decomposition of A. Then for each x ∈ Fn , writing

y = U ∗ x we have
n
X n
X
2
∗
hAx, xi = hU ΛU x, xi = hΛy, yi = λj |yj | ≤ λmax |yj |2 = λmax kyk2 = λmax kxk2 .
j=1 j=1

hAx,xi
This immediately implies that λmax ≥ kxk2
for every nonzero x, and in particular λmax ≥
hAx, xi whenever kxk = 1. Thus λmax is greater than or equal to both of the max expres-
sions. Moreover, if x = U en (so that y = en ), then

hAx, xi = hΛen , en i = λn = λmax .

Thus λmax is also less than or equal to both of the max expressions.
The proofs for λmin are similar.

The following corollary is immediate.

Corollary 3.2. Suppose that A ∈ Mn (F) is Hermitian, and that α = hAx, xi kxk2 for some
x 6= 0. Then A has at least one eigenvalue in [α, ∞) and at least one eigenvalue in (−∞, α].
Theorem 3.3 (Courant–Fischer theorem). If A ∈ Mn (F) is Hermitian, then
hAx, xi hAx, xi
λk (A) = min max 2 = dim S=n−k+1
max min ,
dim S=k 06=x∈S kxk 06 =x∈S kxk2
where in both cases S varies over subspaces of Fn of the stated dimension.

20
Lemma 3.4. If U and V are subspaces of an n-dimensional vector space, then

dim(U ∩ V ) ≥ dim U + dim V − n.

In particular, if dim U + dim V > n, then U ∩ V contains nonzero vectors.

Proof. Writing k = dim U ∩ V , ` = dim U , and m = dim V , let w1 , . . . , wk be a basis of

U ∩ V , and extend it to bases w1 , . . . , wk , u1 , . . . , u`−k of U and w1 , . . . , wk , v1 , . . . , vm−k of
V . I claim that the combined list

w1 , . . . , wk , u1 , . . . , u`−k , v1 , . . . , vm−k

is linearly independent. Indeed, if

a1 w1 + · · · + ak wk + b1 u1 + · · · + b`−k u`−k + c1 v1 + · · · + cm−k vm−k = 0,

then the vector

c1 v1 + · · · + cm−k vm−k = −(a1 w1 + · · · + ak wk + b1 u1 + · · · + b`−k u`−k )

is in U ∩ V (considering the two sides of the equation separately). Therefore

c1 v1 + · · · + cm−k vm−k = d1 w1 + · · · dk wk

for some d1 , . . . , dk ∈ F, and so

(a1 + d1 )w1 + · · · + (ak + dk )wk + b1 u1 + · · · + b`−k u`−k = 0.

Since w1 , . . . , wk , u1 , . . . , u`−k is linearly independent, it follows that b1 = · · · = b`−k = 0. A

similar argument shows that c1 = · · · = cm−k = 0. It then follows that a1 w1 +· · ·+ak wk = 0,
and therefore a1 = · · · = ak = 0 as well. Thus the combined list of k + (` − k) + (m − k) =
` + m − k vectors is linearly independent.
It follows that ` + m − k ≤ n, which is equivalent to the claim.

Proof of Theorem 3.3. Let A = U ΛU ∗ be a spectral decomposition of A. Then λk (A) =

λk (Λ), and making the substitution y = U ∗ x,

hAx, xi hΛy, yi
min max 2 = dim
min max
dim S=k 06=x∈S kxk S=k 06=y∈S kyk2

since the subspace {U y | y ∈ S} has the same dimension as S.

Given a k-dimensional subspace S, Lemma 3.4 implies there exists a nonzero z ∈ S ∩
span(ek , . . . , en ). It follows that
Pn 2 Pn 2
hΛy, yi hΛz, zi j=k λj |zj | j=k |zj |
max ≥ = ≥ λk 2 ≥ λk ,
06=y∈S kyk2 kzk2 n 2 n
P P
j=k |zj | j=k |zj |

and therefore
hΛy, yi
λk ≤ min max .
dim S=k 06=y∈S kyk2

21
On the other hand, if S = span(e1 , . . . , ek ), then for any 0 6= y ∈ S, we have
Pk 2
λk kj=1 |yj |2
P
hΛy, yi j=1 λj |yj |
= Pk ≤ Pk = λk ,
kyk2 j=1 |yj |
2
j=1 |yj |
2

with equality if y = ek . Thus

hΛy, yi
λk = max ,
06=y∈span(e1 ,...,ek ) kyk2

and so
hΛy, yi
λk ≥ min max .
dim S=k 06=y∈S kyk2
The max-min expression can be proved similarly, or can be deduced by replacing A with
−A.

The following version of the Courant–Fischer theorem for singular values can be proved
in a similar way, but it can also be deduced directly from Theorem 3.3.

Corollary 3.5. If A ∈ Mm,n (F), then

kAxk kAxk
σk (A) = min max = max min ,
dim S=n−k+1 06=x∈S kxk dim S=k 06=x∈S kxk

where in both cases S varies over subspaces of Fn of the stated dimension.

Proof. Recall that σk2 = λn−k+1 (A∗ A) (noting that we have chosen to list singular values
in nonincreasing order, but eigenvalues in nondecreasing order). The result now follows
immediately from the Courant–Fischer theorem applied to the Hermitian matrix A∗ A.

3.2 Inequalities for eigenvalues of two Hermitian matrices

Theorem 3.6 (Weyl’s inequalities). If A, B ∈ Mn are Hermitian, then for each 1 ≤ k ≤ n,

λk (A + B) ≤ λk+j (A) + λn−j (B)

for j = 0, . . . , n − k, and

λk−j+1 (A) + λj (B) ≤ λk (A + B)

for j = 1, . . . , k.

Proof. By the Courant–Fischer theorem (Theorem 3.3), there exist subspaces SA and SB
of Fn such that dim SA = k + j, dim SB = n − j, and

λk+j (A) = max hAx, xi ,

x∈SA ,
kxk=1
(6)
λn−j (B) = max hBx, xi .
x∈SB ,
kxk=1

22
By Lemma 3.4, we have dim(SA ∩ SB ) ≥ k. Applying the Courant–Fischer theorem to
A + B, we now have that
λk (A + B) = min max h(A + B)x, xi
dim S=k x∈S
kxk=1

≤ min max (hAx, xi + hBx, xi)

dim S=k, x∈S,
S⊆SA ∩SB kxk=1
!
≤ min max hAx, xi + max hBx, xi
dim S=k, x∈S, x∈S,
S⊆SA ∩SB kxk=1 kxk=1

= λk+j (A) + λn−j (B),

where the last equality follows from (6).
The second inequality in the theorem follows similarly from the max-min version of the
Courant–Fischer theorem.
Weyl’s inequalities are useful for bounding the effect on eigenvalues of various types of
perturbations of Hermitian matrices. An immediate consequence is the following.
Corollary 3.7. If A, B ∈ Mn are Hermitian, then
λk (A) + λ1 (B) ≤ λk (A + B) ≤ λk (A) + λn (B).
Corollary 3.7 says that if B is small in the sense that all its eigenvalues are small, then
the eigenvalues of A + B are close to those of A. A further consequence of Corollary 3.7 is
the following.
Corollary 3.8 (Weyl’s monotonicity theorem). If A ∈ Mn is Hermitian and B ∈ Mn is
positive semidefinite, then
λk (A) ≤ λk (A + B)
for each 1 ≤ k ≤ n.
Another natural question is what the effect is on the eigenvalues of perturbing a fixed
matrix A by a matrix B which is small in the sense of having small rank.
Corollary 3.9. If A, B ∈ Mn and rank B = r, then
λk (A + B) ≤ λk+r (A)
for 1 ≤ k ≤ n − r and
λk (A + B) ≥ λk−r (A)
for r + 1 ≤ k ≤ n.
Proof. Since rank B = r, B has exactly r nonzero eigenvalues. Therefore λn−r (B) ≤ 0 ≤
λr+1 (B). Weyl’s inequalities then imply that
λk (A + B) ≤ λk+r (A) + λn−r (B) ≤ λk+r (A)
for 1 ≤ k ≤ n − r and
λk (A + B) ≥ λk−r (A) + λr+1 (B) ≥ λk−r (A)
for r + 1 ≤ k ≤ n.

23
 Our last consequence of Weyl’s inequalities, which follows immediately from the last
two results is an example of an interlacing theorem.
Corollary 3.10. If A ∈ Mn is Hermitian, and B ∈ Mn is positive semidefinite with rank
r, then
λk−r (A + B) ≤ λk (A) ≤ λk (A + B),
with the first inequality valid for r+1 ≤ k ≤ n, and the second inequality valid for 1 ≤ k ≤ n.
When r = 1, Corollary 3.10 says in particular that
λ1 (A) ≤ λ1 (A + B) ≤ λ2 (A) ≤ λ2 (A + B) ≤ · · · ≤ λn−1 (A + B) ≤ λn (A) ≤ λn (A + B).
The next result is the most famous interlacing theorem for eigenvalues.
Theorem 3.11 (Cauchy interlacing theorem). Suppose that A ∈ Mn is Hermitian and has
the block form  
B C
A= ,
C∗ D
where B ∈ Mm , C ∈ Mm,n−m , and D ∈ Mn−m . Then for each 1 ≤ k ≤ m,
λk (A) ≤ λk (B) ≤ λk+n−m (A).
Proof. Observe first that if y ∈ Fm and x = (y1 , . . . , ym , 0, . . . , 0) ∈ Fn , then hAx, xi =
hBy, yi, and moreover kxk = kyk. By the Courant–Fischer theorem,
λk (A) = minn max hAx, xi ≤ min max hAx, xi
S⊆F x∈S S⊆span(e1 ,...,em )⊆Fn x∈S
dim S=k kxk=1 dim S=k kxk=1

= minm max hBy, yi = λk (B)

S⊆F y∈S
dim S=k kyk=1

and
λk+n−m (A) = max min hAx, xi ≥ max min hAx, xi
S⊆Fn x∈S S⊆span(e1 ,...,em )⊆Fn x∈S
dim S=m−k+1 kxk=1 dim S=m−k+1 kxk=1

= max min hBy, yi = λk (B).

S⊆Fm y∈S
dim S=n−k+1 kyk=1

When m = n − 1, Theorem 3.11 says in particular that

λ1 (A) ≤ λ1 (B) ≤ λ2 (A) ≤ λ2 (B) ≤ · · · ≤ λn−1 (A) ≤ λn−1 (B) ≤ λn (A).
This is the best possible description of the relationship between the eigenvalues of a Her-
mitian matrix and those of a principal (n − 1) × (n − 1) submatrix, in a sense made precise
by the following result (stated here without proof).
Theorem 3.12. Suppose that λ1 , . . . , λn and µ1 , . . . , µn−1 are real numbers such that
λ1 ≤ µ1 ≤ λ2 ≤ µ2 ≤ · · · ≤ µn−1 ≤ λn .
Then there exists a Hermitian matrix A such that λk = λk (A) and µk = λk (B), where B is
the (n − 1) × (n − 1) upper-left principle submatrix of A.

24
 A similar converse holds for Corollary 3.10.
One important application of Cauchy’s interlacing theorem is the following variational
formula for a sum of eigenvalues.
Theorem 3.13 (Fan’s maximal principle). If A ∈ Mn (F) is Hermitian, then
m
X
λk (A) = min tr(U ∗ AU )
U ∈Mn,m (F)
k=1 U ∗ U =Im

and
n
X
λk (A) = max tr(U ∗ AU ).
U ∈Mn,m (F)
k=n−m+1 U ∗ U =Im
Proof. If U ∈ Mn,m and U ∗ U = Im , then the columns of U are orthonormal. We extend
that list of columns to an orthonormal basis of Fn , and form the unitary matrix V ∈ Mn (F)
with those basis vectors as its columns. Then U ∗ AU ∈ Mm is the m × m upper-left
principal submatrix of V ∗ AV . By Cauchy’s interlacing theorem (Theorem 3.11), λk (A) =
λk (V ∗ AV ) ≤ λk (U ∗ AU ), and so for each such U we obtain
m
X m
X
λk (A) ≤ λk (U ∗ AU ) = tr(U ∗ AU ).
k=1 k=1

On the other hand, suppose that A = V diag(λ1 , . . . , λn )V ∗ is a spectral decomposition,

and let U ∈ Mn,m consist of the first m columns of V . Then U ∗ U = Im , and
m
X
∗
tr(U AU ) = tr diag(λ1 , . . . , λn ) = λk (A).
k=1
The proof of the other half is similar.
Corollary 3.14. If A, B ∈ Mn are Hermitian, then
n
X n
X n
X
λk (A + B) ≤ λk (A) + λk (B)
k=m k=m k=m
for each 1 ≤ m ≤ n, with equality for m = 1.
Proof. By Theorem 3.13,
n
X
λk (A + B) = max tr(U ∗ (A + B)U )
U ∈Mn,n−m+1
k=m U ∗ U =In−m+1

tr(U ∗ AU ) + tr(U ∗ BU )
 
= max
U ∈Mn,n−m+1
U ∗ U =In−m+1

≤ max tr(U ∗ AU ) + max tr(U ∗ BU )

U ∈Mn,n−m+1 U ∈Mn,n−m+1
U ∗ U =In−m+1 U ∗ U =In−m+1
X n n
X
= λk (A) + λk (B).
k=m k=m

If m = 1, the claim reduces to tr(A + B) = tr A + tr B.

25
3.3 Majorization
Given x = (x1 , . . . , xn ) ∈ Rn , we write x↓ and x↑ for the nonincreasing and nondecreasing
rearrangements of x. That is, x↓j is the j th largest entry of x, and x↑j is the j th smallest
entry of x.
Let x, y ∈ Rn . If
Xk k
X
xi ≤ yi for each 1 ≤ k ≤ n,
i=1 i=1
Pn
then we say that x is weakly majorized by y, written x ≺w y. If moreover i=1 xi =
P n
i=1 yi , then we say that x is majorized Pby y, written x ≺ y.
For example, if xi ≥ 0 for each i and ni=1 xi = 1, then
 
1 1
,..., ≺ x ≺ (1, 0, . . . , 0).
n n

A more significant example follows from Corollary 3.14 above. We write λ(A) ∈ Rn for
the vector of eigenvalues of a Hermitian matrix A ∈ Mn .

Corollary 3.15 (Fan’s majorization theorem). Let A, B ∈ Mn be Hermitian. Then

λ↓ (A + B) ≺ λ↓ (A) + λ↓ (B).

Proof. By Corollary 3.14, for each 1 ≤ k ≤ n,

k k n
↓
λ↓i (A
X X  ↓ ↓  X  ↓
+ B) ≤ λi (A) + λi (B) = λ (A) + λ↓ (B) i ,
i=1 i=1 i=1

with equality throughout if k = n.

Theorem 3.16 (Lidskii’s majorization theorem). Let A, B ∈ Mn be Hermitian. Then

λ↓ (A + B) − λ↓ (A) ≺ λ↓ (B).

It is important to note that this does not follow from Corollary 3.15 simply by sub-
tracting λ↓ (A) from both sides: majorization is not necessarily preserved by addition and
subtraction of vectors.

Proof. Majorization is preserved by addition of a constant vector (c, . . . , c). We can there-
fore replace B with B − λ↓k (B)In , and thereby assume without loss of generality that
λ↓k (B) = 0.
Under this assumption (as you will show in homework), we can write B = B+ − B− ,
where B+ and B− are both positive semidefinite, λ↓j (B+ ) = λ↓j (B) for j ≤ k, and λ↓j (B+ ) = 0
for j ≥ k.
Then
k k n
λ↓j (B) = λ↓j (B+ ) = λ↓j (B+ ) = tr B+ .
X X X

j=1 j=1 j=1

26
Therefore we need to show that
k
X  ↓ ↓
λ (A + B − B− ) − λ↓ (A) j ≤ tr B+ .
j=1

Since B+ and B− are both positive semidefinite, Weyl’s monotonicity theorem (Corollary
3.8) implies that λ↓j (A + B+ − B− ) ≤ λ↓j (A + B+ ) and λ↓j (A) ≤ λ↓ (A + B+ ). Therefore

k k
X  ↓ ↓ X ↓
λ (A + B − B− ) − λ↓ (A) j ≤
 ↓
λ (A + B) − λ↓ (A) j
j=1 j=1
n
X ↓
λ↓ (A + B) − λ↓ (A)

≤ j
j=1

= tr(A + B+ ) − tr A = tr B+ .

When k = n, we get equality since both sides are equal to tr B.

A different connection between majorization and matrix theory is provided by Proposi-

tion 3.17 below, for which we need another definition.
A matrix A ∈ Mn (R) is called doubly stochastic if aij ≥ 0 for each i and j,
n
X
aij = 1
j=1

for each i, and

n
X
aij = 1
i=1
for each j.
The following examples will all be important:
• Every permutation matrix is doubly stochastic.

• More
PN generally, if PP1 , . . . , PN ∈ Mn are permutation matrices, t1 , . . . , tN ≥ 0, and
N
k=1 tk = 1, then k=1 tk Pk is doubly stochastic.

• Still
PN more generally, Pif A1 , . . . , AN ∈ Mn are doubly stochastic, t1 , . . . , tN ≥ 0, and
N
k=1 tk = 1, then k=1 tk Ak is doubly stochastic.

• If P and Q are permutation matrices and A is doubly stochastic, then P AQ is also

doubly stochastic.

• More generally, if A and B are both doubly stochastic, then AB is also doubly stochas-
tic. This can be proved by direct computation, but also follows easily from Birkhoff’s
theorem below.

• If U ∈ Mn (R) is orthogonal and A ∈ Mn (R) is defined by aij = u2ij , then A is doubly

stochastic. Such a doubly stochastic matrix is called orthostochastic.

27
 • More generally, if U ∈ Mn (C) is unitary and A ∈ Mn (C) is defined by aij = |uij |2 , then
A is doubly stochastic. Such a doubly stochastic matrix is called unitary-stochastic.
Proposition 3.17. Let x, y ∈ Rn . Then x ≺ y if and only if there exists a doubly stochastic
matrix A such that x = Ay.
Proof. Suppose first that x = Ay for a doubly stochastic matrix A. There exist permutation
matrices P and Q such that x↓ = P x and y ↓ = Qy. Then x↓ = (P AQT )y ↓ , and P AQT is
also doubly stochastic. It therefore suffices to assume that x = x↓ and y = y ↓ .
Fix k. We have
k k X n n k
!
X X X X
xi = aij yj − aij yj .
i=1 i=1 j=1 j=1 i=1
Pk
Define tj = i=1 aij . Then 0 ≤ tj ≤ 1 and
n
X k X
X n
tj = aij = k,
j=1 i=1 j=1

which implies that

k
X n
X
(tj − 1) + tj = 0.
j=1 j=k+1

Therefore
k
X k
X n
X k
X k
X n
X
xi − yi = tj yj − yj = (tj − 1)yj + tj yj
i=1 i=1 j=1 j=1 j=1 j=k+1
k
X n
X
= (tj − 1)(yj − yk ) + tj (yj − yk ) ≤ 0.
j=1 j=k+1

If k = n, then we would have tj = 1 for each j, and obtain equality above.

Now suppose that x ≺ y. By a similar argument to above, we may assume without loss
of generality that x = x↓ and y = y ↓ . We will proceed by induction on n, the case n = 1
being trivial.
The majorization x ≺ y implies that yn ≤ x1 ≤ y1 . Therefore there exists a k ≥ 1 such
that yk ≤ x1 ≤ yk−1 (or x1 = y1 if k = 1). Let t ∈ [0, 1] be such that

x1 = ty1 + (1 − t)yk ,

and define
x0 = (x2 , . . . , xn ) ∈ Rn−1
and
y 0 = (y2 , . . . , yk−1 , (1 − t)y1 + tyk , yk+1 , . . . , yn ) =: (y20 , . . . , yn0 ) ∈ Rn−1 .
Then x0 is in nonincreasing order,
m
X m
X
xj ≤ yj
j=2 j=2

28
for 2 ≤ m ≤ k − 1 simply because each xj ≤ yj in this range, and for k ≤ m ≤ n we have
m
X m
X m
X m
X
xj = xj − x1 ≤ yj − x 1 = yj − ty1 − (1 − t)yk
j=2 j=1 j=1 j=1
k−1
X m
X m
X
yj0 ,
 
= yj + (1 − t)y1 + tyk + yj =
j=1 j=k+1 j=2

with equality if m = n. Now y 0 need not be in nonincreasing order, but in any case m 0
P
j=2 yj
is at most the sum of the m − 1 largest entries of y 0 , and so it follows that x0 ≺ y 0 .
Now by the induction hypothesis there is a doubly stochastic B ∈ Mn−1 (R) such that
x0 = By 0 . Define  
1 0
C= ∈ Mn (R)
0 B
and observe that x = C(x1 , y 0 ). Now

(x1 , y 0 ) = (ty1 + (1 − t)yk , y2 , . . . , yk−1 , (1 − t)y1 + tyk , yk+1 , . . . , yn ) = tIn + (1 − t)P y,

 

where P is the permutation matrix that th

  transposes the first and k entries. It follows that
x = Ay, where A = C tIn + (1 − t)P is doubly stochastic.

Theorem 3.18 (Schur’s majorization theorem). If A ∈ Mn is Hermitian, then (a11 , . . . , ann ) ≺

λ(A).

Proof. Let A = U ΛU ∗ be a spectral decomposition. Then

n
X n
X
ajj = ujk λk (A)ujk = |ujk |2 λk (A).
k=1 k=1

That is, (a11 , . . . , ann ) = Bλ(A), where B is the unitary-stochastic matrix bjk = |ujk |2 . The
result now follows from Proposition 3.17.

Similarly to the situation with Cauchy’s interlacing theorem, Theorem 3.18 is an optimal
result, as shown by the following converse (stated here without proof).

Theorem 3.19 (Horn’s theorem). Suppose that (d1 , . . . , dn ) ≺ (λ1 , . . . , λn ). Then there
exists a symmetric matrix A ∈ Mn (R) with diagonal entries d1 , . . . , dn and eigenvalues
λ1 , . . . , λ n .

For further applications of majorization theorems to matrix analysis, we will need the
following additional characterization of majorization.

Proposition 3.20. For x, y ∈ Rn , x ≺ Py if and only if there

Pexist permutations σ1 , . . . , σN
and numbers t1 , . . . , tN ≥ 0 such that N
i=1 it = 1 and x = N
i=1 i σi (1) , . . . , yσi (n) ).
t (y

29
Proof. We first note that the proposition can be equivalently stated as sayingP that x ≺ y
iff there exist permutation matrices P1 , . . . , PN and t1 , . . . , tN ≥ 0 such that Ni=1 ti = 1
PN PN
and x = i=1 ti Pi y. Since i=1 ti Pi is doubly stochastic, the “if” direction follows from
Proposition 3.17.
We can deduce the “only if” from a formally stronger statement. We will call a matrix
of the form T = tIn + (1 − t)P a T -matrix if t ∈ [0, 1] and P is a permutation matrix. A
close inspection of our proof of Proposition 3.17 shows that it actually proves the following
statement: if x ≺ y, then there exist some T -matrices T1 , . . . , Tm such that x = T1 · · · Tm y.
It is easy to check that a product of T -matrices is a permutation matrix, so the proposition
then follows.

Propsitions 3.17 and 3.20 immediately suggest the following result, which is indeed true:

Theorem 3.21 (Birkhoff’s theorem). A matrix A ∈ Mn (R) is doubly stochastic if and

only if there exist permutation matrices P1 , . . . , PN and numbers t1 , . . . , tN ≥ 0 such that
P N PN
i=1 ti = 1 and A = i=1 ti Pi .

Indeed, Birkhoff’s theorem implies that Propositions 3.17 and 3.20 are equivalent to
each other; however, the proof of Birkhoff’s theorem requires more overhead than the direct
proof of Proposition 3.20 given above. We will leave Birkhoff’s theorem unproved for the
time being.
The next result is a substantial strengthening, for Hermitian matrices, of the fact that
the eigenvalues of a matrix depend continuously on the matrix itself.

Corollary 3.22 (Hoffman–Wielandt inequality for Hermitian matrices). If A, B ∈ Mn are

Hermitian, then
λ↓ (A) − λ↓ (B) ≤ kA − BkF .

Proof. By Lidskii’s majorization theorem (Theorem 3.16),

λ↓ (A) − λ↓ (B) ≺ λ↓ (A − B).

By Proposition 3.20, this impliesPthat there exist permutation matrices P1 , . . . , PN and

numbers t1 , . . . , tN ≥ 0 such that N
i=1 ti = 1 and

N
X
↓ ↓
λ (A) − λ (B) = ti Pi (λ↓ (A − B)).
i=1

It follows from the triangle inequality that

N
X N
X
↓ ↓ ↓
λ (A) − λ (B) = ti Pi (λ (A − B)) ≤ ti Pi (λ↓ (A − B))
i=1 i=1
N
X
= ti λ↓ (A − B) = λ↓ (A − B) .
i=1

30
4 Norms
4.1 Vector norms
A norm on a real or complex vector space V is a function k·k : V → R such that:

• For each v ∈ V , kvk ≥ 0.

• If kvk = 0, then v = 0.

• For each v ∈ V and c ∈ F, kcvk = |c| kvk.

• For each v, w ∈ V , kv + wk ≤ kvk + kwk (the triangle inequality).

If all but the second condition are satisfied, then we call k·k a seminorm.
The quantity which we have been accustomed to calling the norm on Fn is just one
example of a norm. To avoid ambiguity, from now on we will denote it k·k2 and call it the
`2 norm.
The Frobenius norm k·kF is of course also a norm on the vector space Mm,n (F), since it
amounts to the `2 norm when we identify Mm,n (F) with Fmn .
The `2 norm is part of a larger family: for 1 ≤ p < ∞, we define the `p norm on Fn by
 1/p
Xn
kxkp =  |xj |p  .
j=1

For p = ∞, we have the limiting case

kxk∞ = max |xj | .

1≤j≤n

Except for the extreme cases p = 1, ∞, it is not obvious that these “norms” satisfy the
triangle inequality. (Recall that it’s not obvious for p = 2, either — the proof uses the
Cauchy–Schwarz inequality.) To prove that we will need some preliminaries.

Lemma 4.1 (The arithmetic–geometric mean inequality). If a, b ≥ 0 and 0 < t < 1, then
at b1−t ≤ ta + (1 − t)b.

Proof. First observe that the function f (t) = log t satisfies f 00 (t) < 0. This implies that f
is concave, i.e., that
f (tx + (1 − t)y) ≥ tf (x) + (1 − t)f (y)
for all x, y > 0 and 0 < t < 1. The claim is trivial if either a = 0 or b = 0; if both are
positive then we have

log(ta + (1 − t)b) ≥ t log a + (1 − t) log b,

and so
ta + (1 − t)b = elog(ta+(1−t)b) ≥ et log a+(1−t) log b = at b1−t .

31
 1 1
Proposition 4.2 (Hölder’s inequality). Suppose that 1 ≤ p, q ≤ ∞ and p + q = 1 (where
1
we interpret ∞ as 0). Then for any x, y ∈ Cn ,

|hx, yi| ≤ kxkp kykq .

Proof. The proof is easy in the case that p = 1 and q = ∞ (or vice-versa), so we assume
that 1 < p, q < ∞. We may also assume that x, y 6= 0, so that kxkp , kykq > 0. Define

|xj |p |yj |p
aj = and bj = ,
kxkpp kykpp

and write t = p1 , so 1 − t = 1q . By the arithmetic geometric mean inequality,

|xj yj | = kxkp kykq atj b1−t

j ≤ kxkp kykq (taj + (1 − t)bj ) .

Therefore
 
n
X n
X n
X n
X
|hx, yi| = x j yj ≤ |xj yj | ≤ kxkp kykq t aj + (1 − t) bj  = kxkp kykq .
j=1 j=1 j=1 j=1

Corollary 4.3 (Minkowski’s inequality). Let 1 ≤ p ≤ ∞. For x, y ∈ Cn ,

kx + ykp ≤ kxkp + kykq .

Proof. As noted above, this result is easy if p = 1, ∞, so we will assume that 1 < p < ∞
p
and let q = p−1 (so p1 + 1q = 1. For each j, by the triangle inequality for absolute values,

|xj + yj |p = |xj + yj | |xj + yj |p−1 ≤ |xj | + |yj | |xj + yj |p−1 .

Now by Hölder’s inequality,

n
X n
X n
X
kx + ykp = |xj + yj |p ≤ |xj | |xj + yj |p−1 + |yj | |xj + yj |p−1
j=1 j=1 j=1
 1/q
  n
X  
(p−1)q 
≤ kxkp + kykp  |xj + yj | = kxkp + kykp kx + ykp/q
p ,
j=1

where the last equality follows from the fact that (p − 1)q = p. It follows that
p− pq
kx + ykp = kx + yk ≤ kxkp + kykp .

Minkowski’s inequality shows that the `p norms do satisfy the triangle inequality, and
therefore really are norms.
We will not prove the following theorem, or use it below, but it provides an important
piece of perspective.

32
Theorem 4.4. Suppose that V is a real or complex finite dimensional vector space, and
that k·k and k·k0 are both norms on V . Then there exist constants c, C > 0 such that for
every v ∈ V we have
c kvk ≤ kvk0 ≤ C kvk .

Theorem 4.4 roughly says that any two norms are almost the same as each other, up
to a constant multiple. For certain purposes, this means that any one norm on a finite
dimensional vector space is as good as any other. For example, a sequence of vectors {vn }
in V is said to converge to v ∈ V with respect to a norm k·k if

lim kv − vn k = 0.
n→∞

Theorem 4.4 says that if {vn } converges to v with respect to one norm, then it also converges
to v with respect to any other norm.
However, Theorem 4.4 is of rather limited importance in practical terms, since the
constants c and C may be very different from each other. In particular, even for very nice,
familiar norms (like the `p norms), these constants may be forced to be very far apart when
the dimension of V is large.

4.2 Special classes of norms

Give x ∈ Cn , we define |x| ∈ Rn to be the coordinate-wise absolute value of x: |x| =
(|x1 | , . . . , |xn |). We also write x ≤ y for x, y ∈ Rn if xj ≤ yj for each j.
A norm k·k on Fn is called monotone if, whenever |x| ≤ |y|, we have kxk ≤ kyk. A
norm k·k on Fn is called absolute if kxk = k|x|k for each x ∈ Fn . For example, the `p
norms are both monotone and absolute.

Proposition 4.5. A norm on Fn is monotone if and only if it is absolute.

Proof. Suppose that k·k is a monotone norm. Given x ∈ Fn , let y = |x|. Then |y| = |x|,
and therefore monotonicity implies that both kxk ≤ kyk and kyk ≤ kxk. Therefore k·k is
absolute.
Now suppose that k·k is an absolute norm. Let x ∈ Rn . For each j and t ∈ [−1, 1],
txj = 1+t 1−t
2 xj + 2 (−xj ). By the absolute norm property, it follows that

1+t 1−t
k(x1 , . . . , txj , . . . , xn )k = x+ (x1 , . . . , −xj , . . . , xn )
2 2
1+t 1−t
≤ kxk + k(x1 , . . . , −xj , . . . , xn )k = kxk .
2 2
Iterating this implies that k·k satisfies the monotone norm property on Rn . If F = C
the result follows since k·k is absolute, so it depends only on the absolute values of the
components of a vector.

A norm k·k on Fn is called a symmetric gauge function if it is an absolute norm

and also kxk = kP xk for each x ∈ Fn and permutation matrix P . Thus for example the `p
norms are symmetric gauge functions.

33
Proposition 4.6. Suppose that k·k is a symmetric gauge function on Fn . If x, y ∈ Rn and
x ≺ y, then kxk ≤ kyk.
PN
Proof. By Proposition 3.20, we can write x =
PN i=1 ti Pi y for some t1 , . . . , tN ≥ 0 with
t
i=1 i = 1 and permutation matrices P 1 , . . . , P N Then since k·k is a symmetric gauge
.
function,
XN XN
kxk ≤ ti kPi yk = ti kyk = kyk .
i=1 i=1

As a first application of Proposition 4.6, we obtain the following result, which simul-
taneously generalizes Corollary 3.7 (the `∞ case) and the Hoffman–Wielandt inequality
(Corollary 3.22, the `2 case).

Corollary 4.7. Suppose that k·k is a symmetric gauge function on Rn . If A, B ∈ Mn are

Hermitian, then
λ↓ (A) − λ↓ (B) ≤ kλ(A − B)k .

Proof. This follows immediately from Lidskii’s majorization theorem (3.16) and Proposition
4.6.

The majorization hypothesis in Proposition 4.6 can be weakened to weak majorization

for nonnegative vectors.

Proposition 4.8. Suppose that k·k is a symmetric gauge function on Rn . If x, y ∈ Rn+ and
x ≺w y, then kxk ≤ kyk.

Proof. Without loss of generality we may assume that x = x↓ and y = y ↓ . Let r =

min {xi | xi > 0}, s = min {yi | yi > 0}, and
n
X n
X
u= yi − xi ≥ 0.
i=1 i=1

Pick m ∈ N such that m u

≤ min{r, s}. Define x0 , y 0 ∈ Rn+m by
 u u
x0 = x1 , . . . , x n , , . . . , and y 0 = (y1 , . . . , yn , 0, . . . , 0).
m m
PN
Then x0 ≺ y 0 , so by Proposition 3.20, there exist t1 , . . . , tN ≥ 0 with i=1 ti = 1 and
PN
permutation matrices P1 , . . . , PN ∈ Mn+m such that x0 = t
i=1 i i P y 0 . It follows that
PN
x = i=1 ti Q i y, where Q i is the n × n upper-left submatrix of Pi . The components of
each Qi y are some subcollection of the components of y, possibly in a different order,
together with some 0 components. Since k·k is both permutation-invariant and monotone,
kQi yk ≤ kyk for each i, and so
N
X N
X
kxk ≤ ti kQi yk ≤ ti kyk = kyk .
i=1 i=1

34
Corollary 4.9. Let p = min{m, n}, and suppose that k·k is a symmetric gauge function on
Rp . If A, B ∈ Mm,n , then

s↓ (A + B) ≤ s↓ (A) + s↓ (B) ≤ s↓ (A) + s↓ (B) .

Proof. This follows immediately from Proposition 4.8 and problem 2 from the February 18
homework.

Another specific family of symmetric gauge functions will be important later. If 1 ≤

k ≤ n, we define the k-norm
k
|x|↓i
X
kxk(k) =
i=1

for x ∈ Cn , where |x|↓i denotes the ith largest component of |x| ∈ Rn+ . It is not hard
to check that k·k(k) is indeed a symmetric gauge function. Note that kxk(1) = kxk∞ , and
kxk(n) = kxk1 ; other than these special cases, these k-norms are different from the `p norms.
The special role of the k-norms is due to the following result.

Proposition 4.10. Let x, y ∈ Rn . The following are equivalent.

1. |x| ≺w |y|.

2. kxk(k) ≤ kyk(k) for each k = 1, . . . , n.

3. kxk ≤ kyk for every symmetric gauge function k·k on Rn .

Proof. The equivalence of statements 1 and 2 follows directly from the definition of the k-
norms. Statement 1 implies statement 3 by Proposition 4.8. Statement 3 implies statement
2 because each k-norm is a symmetric gauge function.

4.3 Duality
Given a norm k·k on Fn , its dual norm is defined by

|hx, yi|
kxk∗ = maxn |hx, yi| = maxn = maxn Re hx, yi .
y∈F 06=y∈F kyk y∈F
kyk≤1 kyk≤1

The equality of the three maxima above is left as an exercise. The use of max here implicitly
relies on the fact that a continuous function on a closed, bounded set achieves its maximum
value. The fact that {y ∈ Fn | kyk ≤ 1} is closed and bounded follows from Theorem 4.4.

Proposition 4.11. If k·k is a norm on Fn , then k·k∗ is also a norm on Fn .

Proof. It is obvious that kxk∗ ≥ 0. If kxk∗ = 0, then |hx, yi| = 0 for every y with kyk ≤ 1.
x kxk22
If x 6= 0, we could then let y = kxk and obtain that kxk = 0, whence kxk2 = 0, thus
contradicting that x 6= 0.
The homogeneity property is obvious.

35
 If x, y ∈ Fn , then

kx + yk∗ = max |hx + y, zi| ≤ max (|hx, zi| + |hy, zi|)

kzk≤1 kzk≤1

≤ max |hx, zi| + max |y| z = kxk∗ + kyk∗ .

kzk≤1 kzk≤1

The second maximum expression given for the dual norm gives the following interpre-
tation: for every x, y ∈ Fn
|hx, yi| ≤ kxk∗ kyk .
Moreover, given x ∈ Fn , kxk∗ is the smallest constant C such that |hx, yi| ≤ C kyk for every
y ∈ Fn .
1
Proposition 4.12. Suppose that 1 ≤ p, q ≤ ∞ and p + 1q = 1 (where we interpret 1
∞ as 0).
Then k·k∗p = k·kq .

Proof. By Hölder’s inequality, for every x, y ∈ Fn we have

|hx, yi| ≤ kxkp kykq ;

this immediately implies that k·k∗p ≤ k·kq .

For the remainder of the proof we assume that 1 < p < ∞; the other cases are, as usual,
easier and are left as an exercise.
Given x ∈ Fn , define y ∈ Fn by
( |x |p
j
xj if xj 6= 0,
yj =
0 if xj = 0.

Then
 1/q  1/q  1·p
n n n p q
X X X
kykq =  |yj |q  = |xj | (p−1)q  = p
|xj |  = kxkpp−1
j=1 j=1 j=1

and
n
X
|hx, yi| = |xj |p = kxkpp = kxkp kykq .
j=1

From this it follows that k·k∗p ≥ k·kq .

The following basic properties are left as exercises:

• If k·kα and k·kβ are two norms such that kxkα ≤ kxkβ for every x ∈ Fn , then kxk∗β ≤
kxk∗α for every x ∈ Fn .

• For c > 0, (c k·k)∗ = 1

c k·k∗ .

The next result highlights the special role held by the `2 norm.

Proposition 4.13. If k·k is a norm on Fn and k·k∗ = k·k, then k·k = k·k2 .

36
Proof. For any x ∈ Fn , kxk22 = |hx, xi| ≤ kxk∗ kxk = kxk2 . Therefore kxk2 ≤ kxk. It then
follows that kxk = kxk∗ ≤ kxk22 = kxk2 .

Proposition 4.14. If k·k is an absolute norm on Fn , then k·k∗ is also an absolute norm.
If k·k is a symmetric gauge function, then k·k∗ is also a symmetric gauge function.
Proof. For any x, y ∈ Fn ,
n
X
|hx, yi| ≤ |xj | |yj | = h|x| , |y|i ,
j=1

with equality when xj yj ≥ 0 for each j. Therefore if k·k is an absolute norm, then
kxk∗ = max |hx, yi| = max |h|x| , |y|i| ,
kyk≤1 k|y|k≤1

which implies that k·k∗ is absolute.

Now suppose that P ∈ Mn is a permutation matrix. Then, making the substitution
z = P ∗ y,
kP xk∗ = max |hP x, yi| = max |hx, P ∗ yi| = max |hx, zi| = max |hx, zi| = kxk∗ .
kyk≤1 kyk≤1 kP zk≤1 kzk≤1

Theorem 4.15. If k·k is a norm on Fn , then k·k∗∗ = k·k.

Proof. For any x ∈ Fn ,
kxk∗∗ = max
∗
|hx, yi| ≤ max
∗
kxk kyk∗ = kxk .
kyk ≤1 kyk ≤1

For the opposite inequality, it suffices to assume that kxk∗∗ = 1 and prove that kxk ≤ 1.
The set B = {z ∈ Fn | kzk ≤ 1} is a closed, bounded, convex set. A basic result from
convexity theory says that B is equal to the intersection of the family of closed half-spaces
Hy,t = {z ∈ Fn | Re hy, zi ≤ t} which contain B. Since 0 ∈ B, we need only consider t ≥ 0
here.
Now B ⊆ Hy,t iff Re hy, zi ≤ t whenever kzk ≤ 1, hence iff kyk∗ ≤ t. Since kxk∗∗ ≤ 1,
we have Re hy, xi ≤ 1 whenever kyk∗ ≤ 1; by homogeneity Re hy, xi ≤ t whenever kyk∗ ≤ t.
Thus x ∈ B.

Corollary 4.16. For each x ∈ Fn ,

|hx, yi|
kxk = maxn |hx, yi| = maxn = maxn Re hx, yi .
y∈F 06=y∈F kyk∗ y∈F
kyk∗ ≤1 ∗
kyk ≤1

4.4 Matrix norms

The space of matrices Mm,n (F) is a vector space, so we can consider norms on it. For
example, we can consider `p norms via the obvious identification of Mm,n (F) with Fmn :
 1/p
Xm X n
kAkp =  |ajk |p  or kAk∞ = max |ajk | .
1≤j≤m
j=1 k=1 1≤k≤n

37
When working with matrices we typically are interested in using norms that interact in
some natural way with the action of matrices as linear maps on Fn , or with the product
structure on Mn (F).
A norm k·k on Mn (F) is called submultiplicative if kABk ≤ kAk kBk for every A, B ∈
Mn (F). A submultiplicative norm on Mn (F) is often called a matrix norm, in contrast to
a “vector norm”, which is merely a norm on the vector space Mn (F).1
For example, the `1 norm on Mn (F) is submultiplicative:
n
X n
X n
X n
X
kABk1 = aj` b`k ≤ |aj` | |b`k | ≤ |aj` | |bmk | = kAk1 kBk1 ,
j,k=1 `=1 j,k,`=1 j,k,`,m=1

and so is the `2 norm (same as the Frobenius norm):

n n 2 n n
! n
!
X X X X X
kABk2F = aj` b`k ≤ |aj` | 2 2
|b`k | = kAk2F kBk2F ,
j,k=1 `=1 j,k=1 `=1 `=1

where the inequality follows from the Cauchy–Schwarz inequality. On the other hand, the
`∞ norm on Mn (F) is not submultiplicative (examples are easy to come by), although n k·k∞
is.
A large class of submultiplicative norms arises from the following construction. Suppose
that k·kα is a norm on Fn and k·kβ is a norm on Fm . For A ∈ Mm,n (F), we define2

kAxkβ
kAkα→β = maxn kAxkβ = max n .
x∈F 06=x∈F kxkα
kxkα ≤1

That is, kAkα→β is the smallest constant C > 0 such that kAxkβ ≤ C kxkα for every x ∈ Fn .

Proposition 4.17. Suppose that k·kα is a norm on Fn and k·kβ is a norm on Fm . Then
k·kα→β is a norm on Mm,n (F).

The proof of Proposition 4.17 is essentially the same as the proof of Proposition 4.11
above, which it generalizes.
For example, if A ∈ Mm,n (F), then

kAk2→2 = σ1 (A).

This is easy to prove directly from the singular value decomposition, and is also a special case
of Corollary 3.5; it also follows from the proof we gave of the singular value decomposition.
1
Terminological warning: the term “matrix norm” is used by some authors to mean any norm on a space
of matrices.
2
Notational warning: If k·kα is a norm on Fn , then the norm on Mn (F) that we denote by k·kα→α here is
often denoted k·kα . Note that this conflicts with the common practice of writing, say kAkp for the `p norm
of the entries of A. Later we will introduce yet another family of norms on matrices denoted by kAkp . So it
is vital, any time you read something about norms on matrices, to figure out what the author’s notational
conventions are!

38
 It is seldom easy to express an induced norm in terms of the entries of a matrix. Two
prominent exceptions are
Xm
kAk1→1 = max |ajk |
1≤k≤n
j=1
and
n
X
kAk∞→∞ = max |ajk | ,
1≤j≤m
k=1
which are also referred to as the maximum column sum and maximum row sum norms of
A. To prove the first of these, for any x ∈ Fn ,
m X
X n m X
X n
kAxk1 = ajk xk ≤ |ajk | |xk |
j=1 k=1 j=1 k=1
 
n
X Xm m
X
= |xk |  |ajk | ≤ kxk1 max |ajk | .
1≤k≤n
k=1 j=1 j=1

On the other hand, suppose that the k th column of A has the largest `1 norm of the columns
of A. Then
Xm m
X
max |ajk | = |ajk | = kAek k1 .
1≤k≤n
j=1 j=1
The expression for kAk∞→∞ can be proved similarly, but also follows from the the expression
for kAk1→1 using Corollary 4.21 below.
Proposition 4.18. Suppose that k·kα is a norm on Fn , k·kβ is a norm on Fm , and k·kγ is
a norm on Fp . Then
kABkα→γ ≤ kAkβ→γ kBkα→β
for every A ∈ Mp,m (F) and B ∈ Mm,n (F).
Proof. For any x ∈ Fn ,
kABxkγ ≤ kAkβ→γ kBxkβ ≤ kAkβ→γ kBkα→β kxkα .
Corollary 4.19. If k·kα is any norm on Fn , then k·kα→α is a submultiplicative norm on
Mn (F).
The following is an immediate reformulation of the definition of an induced norm, using
the definition of a dual norm.
Proposition 4.20. Suppose that k·kα is a norm on Fn and k·kβ is a norm on Fm . Then
kAkα→β = max |hAx, yi| .
kxkα ≤1
kyk∗β ≤1

Proposition 4.20 and Theorem 4.15 immediately imply the following.

Corollary 4.21. Suppose that k·kα is a norm on Fn and k·kβ is a norm on Fm . Then
kAkα→β = kA∗ kβ ∗ →α∗ ,
where k·kβ ∗ →α∗ denotes the induced norm induced by k·k∗β on Fm and k·k∗α on Fn .

39
4.5 The spectral radius
Given A ∈ Mn (C), we call the set σ(A) of eigenvalues (in C) of A the spectrum of A, and
the number
ρ(A) = max |λ|
λ∈σ(A)
 
0 1
the spectral radius of A. Note that ρ is not a norm on Mn (C). For example, ρ =
0 0
0. However, it is closely related to matrix norms.
A first simple observation is that if k·kα is any norm on Cn and Ax = λx for x 6= 0, then

kAxkα = kλxkα = |λ| kxkα ,

which implies that |λ| ≤ kAkα→α , and so ρ(A) ≤ kAkα→α . This result can be generalized
to arbitrary submultiplicative norms:

Theorem 4.22. If k·k is a submultiplicative norm on Mn (C), then ρ(A) ≤ kAk for every
A ∈ Mn (C).

Proof. Suppose that Ax = λx for x 6= 0. Define X ∈ Mn (C) to be the matrix whose

columns are all equal to x. Then AX = λX, and so

|λ| kXk = kAXk ≤ kAk kXk .

Therefore |λ| ≤ kAk.

Corollary 4.23. Suppose A ∈ Mn (C) and that k·k is any submultiplicative norm on Mn (C).
If kAk < 1 then In − A is nonsingular.

Proof. By Theorem 4.22, ρ(A) < 1. The eigenvalues of In − A are 1 − λj (A), so they are
all nonzero, and thuse In − A is nonsingular.

As an application, we get the following easy-to-check sufficient condition for invertibility.

We say that A ∈ Mn (C) is strictly diagonally dominant if for each j,
X
|ajj | > |akj | .
k6=j

Corollary 4.24 (Levy–Desplanques theorem). If A ∈ Mn (C) is strictly diagonally domi-

nant, then A is nonsingular.

Proof. Let D = diag(a11 , . . . , ann ). Then D is nonsingular, and we define B = I − D−1 A.

The entries of B are ( a
− ajk if j 6= k,
bjk = jj

0 if j = k.
Then kBk∞→∞ < 1 since A is strictly diagonally dominant, so In − B = D−1 A is nonsin-
gular, and hence A is as well.

40
Lemma 4.25. Let A ∈ Mn (C) and ε > 0 be given. Then there exists a submultiplicative
norm (depending on both A and ε) such that kAk ≤ ρ(A) + ε. That is,

ρ(A) = inf {kAk | k·k is a submultiplicative norm on Mn (C)} .

Proof. You proved in homework (problem 3 from February 1) that there exists a nonsingular
S and upper triangular T such that A = ST S −1 and |tjk | < ε/n for j < k. Define k·k by

kBk = S −1 BS 1→1
.

Then k·k is submultiplicative, and

n
X

kAk = kT k1→1 = max |tjk | ≤ max |tkk | + ε = ρ(A) + ε.
1≤k≤n 1≤k≤n
j=1

k→∞
Theorem 4.26. Let A ∈ Mn (C). Then Ak −−−→ 0 if and only if ρ(A) < 1.

Proof. Suppose that Ak → 0, and that Ax = λx for x 6= 0. Then Ak x = λk x, which implies

that λk x → 0, and therefore λk → 0, so |λ| < 1.
Now suppose that ρ(A) < 1. By Lemma 4.25 there exists a submultiplicative norm k·k
on Mn (C) such that kAk < 1. Then Ak ≤ kAkk , and kAkk → 0, so Ak → 0.

Corollary 4.27 (The Gelfand formula). Let k·k be any submultiplicative norm on Mn (C).
1/k
Then ρ(A) ≤ Ak for each k ∈ N, and
1/k
ρ(A) = lim Ak .
k→∞

1/k
Proof. By Theorem 4.22, ρ(A)k = ρ(Ak ) ≤ Ak , and so ρ(A) ≤ Ak .
1 ρ(A) k→∞
Now given ε > 0, let B = ρ(A)+ε A. Then ρ(B) = ρ(A)+ε < 1, so B k −−−→ 0 by Theorem
4.26. Therefore there exists a K such that for all k ≥ K, Bk < 1. Equivalently, for all
1/k
such k, Ak ≤ ρ(A) + ε.

Since there exist submultiplicative norms that are straightforward to compute or esti-
mate from the entries of a matrix (the Frobenius norm or the maximum row- or column-sum
norms), Corollary 4.27 can be a very useful tool for estimate the spectral radius of a matrix.
A fundamental fact about infinite series of real or P complex numbers is that every P∞ ab-
∞
solutely convergent series is convergent. That is, if k=0 |ak | converges, then k=0 ak
converges as well. This fact extends to any finite dimensional normed space (and further to
any complete normed space): if ∞
P P∞
k=0 kv k k converges, then v
k=0 k converges.
power series ∞ k with coefficients a ∈ C has
P
Another fundamental fact is that a P k=0 ak z k
a radius of convergence R ∈ [0, ∞]: ∞ k=0 ka z k converges whenever |z| < R and diverges

whenever |z| > R.

41
 P∞ k
Proposition 4.28. Suppose that the power series k=0 ak z has radius of convergence R.
Then the matrix-valued series
∞
X
ak Ak
k=0

converges for every matrix A ∈ Mn (C) with ρ(A) < R, and diverges for every A with
ρ(A) > R.

Proof. If ρ(A) < R, then there exists a submultiplicative norm k·k on Mn (C) such that
kAk < R. It follows that
X∞ ∞
X
ak Ak ≤ |ak | kAkk
k=0 k=0
P∞
converges, so k=0 ak Ak converges.
If ρ(A) > R, then there is a λ ∈ σ(A) with |λ| > R. Let x be a corresponding eigenvector.
Then
N N
! !
X X
k k
ak A x = ak λ x,
k=0 k=0
P∞ P∞
and we know k=0 ak λk diverges, so this series must also diverge, and hence k=0 ak A
k

diverges.
1 P∞ k
The following is a matrix analogue of the formula 1−x = k=0 x for the sum of a
geometric series.

Corollary 4.29. Let A ∈ Mn (C). If ρ(A) < 1, then In − A is nonsingular, and

∞
X
(In − A)−1 = Ak .
k=0

Proof. The eigenvalues of In − A are 1 − λj (A), so if ρ(A) < 1 then all the eigenvalues of
In − A are nonzero, hence In − A is P
nonsingular.
Now the radius of convergence of ∞ k
P∞ k
k=0 z is 1, so Proposition 4.28 implies that k=0 A
converges, say to B. We have
N
X
(In − A) Ak = In − An+1 ,
k=0

and taking the limit N → ∞ yields, by Theorem 4.26, that (In − A)B = In .

Replacing A with In − A in Corollary 4.29 yields the following.

Corollary 4.30. Let A ∈ Mn (C). If σ(A) ⊆ (0, 2), then

∞
X
−1
A = (In − A)k .
k=0

42
4.6 Unitarily invariant norms
A norm k·k on Mm,n (C) is called unitarily invariant if kU AV k = kAk for every A ∈
Mm,n (C), U ∈ Um , and V ∈ Un .
We have already seen two examples of unitarily invariant norms: the Frobenius norm
k·kF and the standard operator norm k·k2→2 .
If A = U ΣV ∗ is a singular value decomposition and k·k is unitarily invariant, then
kAk = kΣk. Therefore a unitarily invariant norm depends only on the singular values of A.
For example, as we have seen previously,
v
u p
uX
kAkF = t σj (A)2 and kAk2→2 = σ1 (A).
j=1

It turns out that any unitarily invariant norm on Mm,n (C) can be described in terms of a
norm of the sequence of singular values s(A) ∈ Rp , where p = min{m, n}. More precisely,
unitarily invariant norms on Mm,n (C) are in one-to-one correspondence with symmetric
gauge functions on Rp :3

Theorem 4.31. Suppose that k·k is a unitarily invariant norm on Mm,n (C). There is a
symmetric gauge function on Rp , again denoted k·k, such that kAk = ks(A)k.
Conversely, given a symmetric gauge function on Rp , the formula kAk = ks(A)k defines
a unitarily invariant norm on Mm,n (C).

Proof. Suppose that k·k is a unitarily invariant norm on Mm,n (C). For simplicity, we assume
that m ≤ n, the proof in the case m > n being similar.
Given x ∈ Rm , we define kxk as follows: let
 
x1 0 · · · 0 0 · · · 0
 0 x2 · · · 0 0 · · · 0
M (x) =  . ..  ∈ Mm,n (C),
 
. .. . . .. ..
. . . . . .
0 0 · · · xm 0 · · · 0

and set kxk = kM (x)k. All the properties of a norm follow easily (this essentially amounts
to observing that the restriction of a norm to a subspace is still a norm).
Given x ∈ Rm , define D ∈ Mm to be the diagonal matrix D = diag(d1 , . . . , dm ), where
(
1 if x ≥ 0,
dj =
−1 if x < 0.

Then D is unitary, and so

k|x|k = kM (|x|)k = kDM (x)k = kM (x)k = kxk

by unitary invariance. Therefore k·k on Rm is an absolute norm.

3
As you already saw in homework, symmetric gauge functions on Rp and Cp are essentially the same
thing.

43
 Now let P ∈ Mm be a permutation matrix. Define Q ∈ Mn to have the block decompo-
sition  
P 0
Q= ,
0 In−m
so Q is also a permutation matrix, and P and Q are both unitary. Then

kP xk = kM (P x)k = kP M (x)Q∗ k = kM (x)k = kxk .

Therefore k·k on Rm is a symmetric gauge function.

Now suppose that k·k is a symmetric gauge function on Rp , and define kAk = ks(A)k
for A ∈ Mm,n (C). It follows immediately that kAk ≥ 0 and kAk = 0 iff A = 0. If c ∈ C,
then so s(cA) = |c| s(A), and so kcAk = |c| kAk. The triangle inequality for k·k on Mm,n (C)
follows from Corollary 4.9.
Finally, if A ∈ Mm,n (C), U ∈ Um , and V ∈ Un are given, then s(U AV ) = s(A), and so
k·k on Mm,n (C) is unitarily invariant.

Using Theorem 4.31, we get additional examples of unitarily invariant norms:

• For 1 ≤ p < ∞, the Schatten p-norm of A ∈ Mm,n (C) is given by

 1/p
min{m,n}
X
kAkp =  σj (A)p  ,
j=1

and for p = ∞, the Schatten ∞-norm is

kAk∞ = max σj (A) = σ1 (A).

1≤j≤min{m,n}

Note that kAk2 = kAkF and kAk∞ = kAk2→2 . The other Schatten norms are new to
us. One other that is frequently singled out is the Schatten 1-norm, which is sometimes
called the trace norm k·ktr (for reasons that will be explored in homework).

• For 1 ≤ k ≤ n, the Fan k-norm of A ∈ Mm,n (C) is given by

k
X
kAk(k) = σj (A).
j=1

Note that kAk(1) = kAk∞ = kAk2→2 , and that kAkmin{m,n} = kAk1 = kAktr .

The Fan k-norms play an important role in the general theory of unitarily invariance
norms, thanks to the following result, which follows immediately from Theorem 4.31 and
Proposition 4.10.

Theorem 4.32 (Fan dominance principle). Let A, B ∈ Mm,n (C). If kAk(k) ≤ kBk(k)
foer each 1 ≤ k ≤ min{m, n}, then kAk ≤ kBk for every unitarily invariant norm k·k on
Mm,n (C).

44
 We next address the question of when which unitarily invariant norms fit into other
special classes of norms we have considered.

Theorem 4.33. A norm k·k on Mm,n (C) is unitarily invariant if and only if

kABCk ≤ kAk2→2 kBk kCk2→2

for every A ∈ Mm , B ∈ Mm,n , and C ∈ Mn .

Proof. Suppose first that k·k is unitarily invariant. The Courant–Fischer theorem for sin-
gular values (Corollary 3.5) implies that σj (ABC) ≤ kAk2→2 σj (B) kCk2→2 for each j,
and so s(ABC) ≤ kAk2→2 kCk2→2 s(B) coordinate-wise. The symmetric gauge function on
Rmin{m,n} corresponding to k·k is an absolute, and hence monotone norm, and so

kABCk = ks(ABC)k ≤ kkAk2→2 kCk2→2 s(B)k

= kAk2→2 kCk2→2 ks(B)k = kAk2→2 kCk2→2 kBk .

Now suppose that k·k has the stated property. Given A ∈ Mm,n (C), U ∈ Um , and
V ∈ Un , we have
kU AV k ≤ kU k2→2 kAk kV k2→2 = kAk
and
kAk = kU ∗ U AV V ∗ k ≤ kU ∗ k2→2 kU AV k kV ∗ k2→2 = kU AV k . .

Corollary 4.34. Suppose that k·k is a unitarily invariant norm on Mn (C), and let E11 =
diag(1, 0, . . . , 0) ∈ Mn (C). If kE11 k = 1, then k·k is submultiplicative.

Proof. Let k·k also denote the corresponding symmetric gauge function on Rn . The nor-
malization assumption implies that ke1 k = 1, which further implies that for any x ∈ Rn ,

kxk = |x|↓ ≥ kkxk∞ e1 k = kxk∞ ,

where the inequality above follows by monotonicity. It follows that kAk2→2 ≤ kAk for any
A ∈ Mn (C). The claim now follows immediately from Theorem 4.33.

Lemma 4.35. If k·kα is a norm on Fn , k·kβ is a norm on Fm , and x ∈ Fm , y ∈ Fn , then

kxy ∗ kα→β = kxkβ kyk∗α .

The proof of Lemma 4.35 is left as an exercise.

Theorem 4.36. Suppose that k·kα is a norm on Cn and k·kβ is a norm on Cm , and that
the induced norm k·kα→β on Mm,n (C) is unitarily invariant. Then there exist a, b > 0 such
that
b
k·kα = a k·k2 , k·kβ = b k·k2 , and k·kα→β = k·k2→2 .
a
In particular, if an induced norm k·kα→α on Mn (C) is unitarily invariant, then k·kα→α =
k·k2→2 .

45
Proof. Let x ∈ Cm , y ∈ Cn , U ∈ Um , and V ∈ Un . Then by unitary invariance and Lemma
4.35,
kxkβ kyk∗α = kxy ∗ kα→β = kU xy ∗ V ∗ kα→β = kU xkβ kV yk∗α .
Therefore
kU xkβ kV yk∗α
=
kxkβ kyk∗α
for all nonzero x and y. In particular, the value C of this ratio is independent of x, y, U ,
and V . Setting U = Im or V = In implies that C = 1.
So kU xkβ = kxkβ for every x ∈ Cm and U ∈ Um . Given x 6= 0, let v = kxk x
. There is a
2
U ∈ Um such that U v = e1 . It follows that

kxkβ = kvkβ kxk2 = kU vkβ kxk2 = ke1 kβ kxk2

for every x ∈ Cm .
Similarly, kyk∗α = ke1 k∗α kyk2 for every y ∈ Cn , and therefore k·kα = k·k∗∗ ∗ −1
α = (ke1 kα ) k·k2 .

Theorem 4.37. Suppose that k·k is a unitarily invariant and absolute norm on Mm,n (C).
Then there is a constant c > 0 such that k·k = c k·kF .
Proof. Without loss of generality we may assume that kE11 k = 1. Let A ∈ Mm,n (C). We
will prove that kAk = kAkF by induction on rank A. The case rank A = 0 is trivial; if
rank A = 1 then the singular value decomposition of A has the form A = U (σ1 E11 )V ∗ , so
kAk = kσ1 E11 k = σ1 = kAkF .
Now suppose that r = rank A ≥ 2, and that the result is known for matrices of rank
smaller than r. Let σj = σj (A), we define
p p
σ12 + σr2 + σ1 − σr σ12 + σr2 − σ1 + σr
r
σ1 σr
a= , b= , and c= ,
2 2 2
and then define
 
a b 0 ··· 0 0 ··· 0
 b ±c 0 · · · 0 0 · · · 0
 
0 0 σ2 · · · 0 0 · · · 0
 
. . . . . . .
. . . . . . .

. . . . . . .
A± =  ..  ∈ Mm,n (C).
 
..
0 0
 0 · · · σr−1 . .
0 0
 0 · · · · · · 0 · · · 0 

 .. .. .. .. . . .. 
. . . . . .
0 0 0 ··· ··· 0 ··· 0
 
a b
The matrices are real symmetric, with eigenvalues σ1 and −σr in the − case, and
b ±c
p
2 2
σ1 + σr and 0 in the + case. It follows that s(A− ) = s(A), and
q
s(A+ ) = ( σ12 + σr2 , σ2 , . . . , σr−1 , 0, . . . , 0).

46
Therefore
kAk = kA− k = kA+ k = kA+ kF = kAkF ,
by (in order) unitary invariance, the fact that k·k is absolute, the induction hypothesis, and
the expression for k·kF in terms of singular values.

Recall that Corollary 4.7 showed that if A, B ∈ Mn are Hermitian, then

λ↓ (A) − λ↓ (B) ≤ kλ(A − B)k

for each symmetric gauge function k·k on Rn . Using Theorem 4.31, we can rephrase this as
follows.
Theorem 4.38 (Mirsky’s inequality). Let k·k denote both a symmetric gauge function on
Rn and the corresponding unitarily invariant norm on Mn . Then

λ↓ (A) − λ↓ (B) ≤ kA − Bk

for any Hermitian matrices A, B ∈ Mn .

This states in a very precise, quantitative, and general way that the eigenvalues of
a Hermitian matrix depend in a continuous fashion on the matrix itself. Note that this
includes as special cases both Weyl’s perturbation theorem (Corollary 3.7, when k·k =
k·k∞ ) and the Hoffman–Wielandt inequality for Hermitian matrices (Corollary 3.22, when
k·k = k·k2 ).
For general (non-Hermitian, possibly non-square) matrices, there is a similar theorem
for singular values.
Corollary 4.39. Let k·k denote both a symmetric gauge function on Rp and the corre-
sponding unitarily invariant norm on Mm,n , with p = min{m, n}. Then

s↓ (A) − s↓ (B) ≤ kA − Bk

for any A, B ∈ Mm,n .

 
0 A
Proof. Recall from homework that the eigenvalues of are ± the singular values of
A∗ 0
A, plus some 0s. Lidskii’s majorization theorem (Theorem 3.16) implies that
     
0 A 0 B 0 A−B
λ↓ − λ ↓
≺ λ↓
.
A∗ 0 B∗ 0 (A − B)∗ 0
Note that the nonzero entries of the left hand side of the majorization above are ± |σj (A) − σj (B)|.
Then for 1 ≤ k ≤ p,
k k     ↓ X k
X X 0 A 0 B ↓
↓ ↓
σj (A − B) ≥ λ ∗ − λ ∗ ≥ s↓ (A) − s↓ (B) .
A 0 B 0 j j
j=1 j=1 j=1

If A = UA ΣA VA∗ and B = UB ΣB VB∗ are singular value decompositions, then the inequality
above states that kA − Bk(k) ≥ kΣA − ΣB k(k) for every 1 ≤ k ≤ p. By Fan’s dominance
principle (Theorem 4.32), this implies that kA − Bk ≥ kΣA − ΣB k for every unitarily in-
variant norm k·k, which is equivalent to the claim.

47
 Corollary 4.39 is a powerful tool for determining how well a matrix of one kind can be
approximated by another kind of matrix, with respect to unitarily invariant norms.
Corollary 4.40. Let k·k denote both a symmetric gauge function on Rp and the corre-
Mm,n , with p = min{m, n}. Suppose that A ∈ Mm,n
sponding unitarily invariant norm on P
has singular value decomposition A = pj=1 σj uj vj∗ and B ∈ Mm,n has rank k. Then

kA − Bk ≥ k(0, . . . , 0, σk+1 , . . . , σp )k ,
Pk ∗
with equality when B = j=1 σj uj vj .

Proof. By Corollary 4.39, if rank B = k then

kA − Bk ≥ k(σ1 (A) − σ1 (B), . . . , σk (A) − σk (B), σk+1 (A), . . . , σp (A))k .

The right-hand-side above is greater than the right-hand-side in the statement of the corol-
lary since k·k is absolute and monotone on Rp . The equality case is immediate.

A special case worth

Pn noting is that if A ∈ Mn is nonsingular with singular value de-
composition A = σ u v ∗ , then the closest singular matrix B with respect to any
j=1 j j j
Pn−1
unitarily invariant norm is B = j=1 σj uj vj∗ , and then kA − Bk = σn ke1 k. (Compare this
to problem 4 from the March 1 homework.)

4.7 Duality for matrix norms

Duality was defined above specifically for norms on Fn , but the definition obviously extends
to any space with a fixed inner product. Here we will extend the definition to Mm,n (F) with
the Frobenius inner product hA, BiF = tr AB ∗ (which we recall is the same as the standard
inner product when we identify Mm,n (F) with Fmn in the obvious way). The definition of
the dual norm to a given norm k·k on Mm,n (F) becomes
|tr AB ∗ |
kAk∗ = max |tr AB ∗ | = max = max Re tr AB ∗ .
B∈Mm,n (F) 06=B∈Mm,n (F) kBk B∈Mm,n (F)
kBk≤1 kBk≤1

Because of the appearance of traces here, this is sometimes referred to as trace duality.
Theorem 4.41. Suppose that k·k is a submultiplicative norm on Mn (F). Then

kABk∗ ≤ min {kA∗ k kBk∗ , kAk∗ kB ∗ k}

for all A, B ∈ Mn (F). In particular, if kA∗ k ≤ kAk∗ for every A ∈ Mn (F), then k·k∗ is
submultiplicative.
Proof. If A, B, C ∈ Mn (F), then

tr(AB)C ∗ = tr A(CB ∗ )∗ ≤ kAk∗ kCB ∗ k ≤ kAk∗ kCk kB ∗ k ,

where the first inequality follows from the definition of the dual norm k·k∗ , and the second
inequality from the submultiplicativity of k·k. This implies that kABk∗ ≤ kAk∗ kB ∗ k. The
inequality kABk∗ ≤ kA∗ k kBk∗ is proved similarly.

48
Corollary 4.42. Let k·kα be a norm on Fn . Then k·k∗α→α is a submultiplicative norm on
Mn (F).
Proof. By Corollary 4.21 and Proposition 4.20,

kA∗ kα→α = kAkα∗ →α∗ = max

∗
|hAx, yi| = max
∗
|y ∗ Ax| = max
∗
|tr Axy ∗ |
kxkα ≤1 kxkα ≤1 kxkα ≤1
kykα ≤1 kykα ≤1 kykα ≤1

≤ max
∗
kAk∗α→α kyx∗ kα→α ≤ kAk∗α→α ,
kxkα ≤1
kykα ≤1

where the last inequality follows from Lemma 4.35. The result now follows from Theorem
4.41.

Recall that Proposition 4.14 shows that the dual norm of a symmetric gauge function
is again a symmetric gauge function. It is therefore obvious to guess that the dual of a
unitarily invariant norm is again unitarily invariant, and that the corresponding symmetric
gauge functions are dual as well. This guess turns out to be correct; we will need a technical
preliminary result.
PnA matrix A ∈ Mn (R) is P called doubly substochastic if aij ≥ 0 for each i, j and,
n
i=1 a ij ≤ 1 for each j, and j=1 aij ≤ 1 for each i.

Lemma 4.43. If A ∈ Mn (R) is doubly substochastic, then there exists a doubly stochastic
matrix B ∈ Mn (R) such that A ≤ B entrywise.
Proof. Note that the sum of the column sums of A is equal to the sum of the row sums of
A, so if row sum is < 1 then some column sum is < 1 as well. Pick the smallest i such that
the ith row sum is < 1 and the smallest j such that the ith column sum is < 1. Increase
aij until one of these row/column sums is 1. This decreases the total number of row and
column sums which are < 1. Iterate this procedure; the process must eventually terminate
because there are only finitely many rows and columns. At the end we obtain a matrix
whose entries are greater than or equal to the entries of A, and whose row and column sums
are all equal to 1.

Theorem 4.44. Let k·k be a unitarily invariant norm on Mm,n (C), corresponding to the
symmetric gauge function k·kv on Rp , where p = min{m, n}. Then k·k∗ is the unitarily
invariant norm corresponding to the symmetric gauge function k·k∗v .
Proof. First observe that if U ∈ Um and V ∈ Un , then

kU AV k∗ = max |tr U AV B ∗ | = max |tr A(U ∗ BV ∗ )∗ | = max |tr AC ∗ | = kAk∗ ,

kBk≤1 kBk≤1 kCk≤1

where we have made the substitution C = U ∗ BV ∗ . Thus k·k∗ is unitarily invariant.

Suppose for now that m = n. Let A = UA ΣA VA∗ and B = UB ΣB VB∗ be singular value
decompositions, and define U = UB∗ UA and V = VA∗ VB . Then

n
X n
X n
X
|tr AB ∗ | = |tr ΣA V ΣB U | = σj (A)vjk σk (B)ukj ≤ σj (A) |vjk ukj | σk (B).
j,k=1 j=1 k=1

49
Let wjk = |vjk ukj |. By the Cauchy–Schwarz inequality, for each k we have
v v
n
u n u n
X uX uX
wjk ≤ t |vjk |2 t |ukj |2 = 1
j=1 j=1 j=1
Pn
since V and U are both unitary. Similarly k=1 wjk ≤ 1 for each j. Therefore W is
substochastic, and by Lemma 4.43 there exists a doubly stochastic matrix C such that
W ≤ C entrywise. We then have
|tr AB ∗ | ≤ hs(A), W s(B)i ≤ hs(A), Cs(B)i .
Now Cs(B) ≺ s(B) by Proposition 3.17, and so by Proposition 3.20, Cs(B) = N
P
i=1 ti Pi s(B)
for some ti ≥ 0 with N
P
t
i=1 i = 1 and permutation matrices P i . It follows that
N
X
|tr AB ∗ | ≤ ti hs(A), Pi s(B)i .
i=1

Now if m 6= n, we can add rows or columns of 0s as necessary to make A and B square;

this adds 0s to the vectors s(A) and s(B). If we call the resulting extended vectors se(A) =
(s(A), 0, . . . , 0) and se(B) similarly, then the argument above yields
N
X
∗
|tr AB | ≤ ti he
s(A), Pi se(B)i .
i=1

For each i, we could further permute the entries of Pi se(B) so that all the nonzero entries
appear among the first p; we obtain that there are permutation matrices Qi ∈ Mp such that
he
s(A), Pi se(B)i = hs(A), Qi s(B)i. Therefore
N N
ti ks(A)k∗v kQi s(B)kv
X X
|tr AB ∗ | ≤ ti he
s(A), Qi se(B)i ≤
i=1 i=1
N
ti ks(A)k∗v ks(B)kv = ks(A)k∗v kBk ,
X
=
i=1

which implies that kAk ≤ ks(A)k∗v .

∗

Finally, given A with singular value decomposition A = U ΣV ∗ , pick x ∈ Rp such that

|hs(A), xi| = ks(A)k∗v kxkv , and define M (x) ∈ Mm,n as before and B = U M (x)V ∗ . Then
kM (x)k = kxkv and
tr AB ∗ = tr ΣM (x)∗ = hs(A), xi ,
which implies that kAk∗ ≥ ks(A)k∗ .

5 Some topics in solving linear systems

5.1 Condition numbers
Consider a linear system of equations, written in matrix form as Ax = b. We will restrict
attention here to an n × n system, so A ∈ Mn and b ∈ Fn are fixed, and we wish to find the

50
unknown vector x ∈ Fn . Assuming that A is nonsingular, we could do this by computing
A−1 and then x = A−1 b. (This isn’t necessarily the best way to find x, depending on what
constitutes “best” for our purposes, but we will assume that approach for now.)
Now suppose that the vector b is not precisely known, due to measurement error, round-
off error in an earlier calculation, or any number of other real-world issues. That is, in place
of the true vector b, we are actually using b + ∆b, where ∆b ∈ Fn represents the error or
uncertainty in b. Then our computed value of x is not A−1 b but instead

A−1 (b + ∆b) = A−1 b + A−1 (∆b).

That is, we get an error ∆x = A−1 (∆b) in the computed value.

We can use norms to quantify the size of the error. Let k·kα be a norm on Fn . Then

k∆xkα = A−1 (∆b) α

≤ A−1 α→α
k∆bkα .

More relevant for many purposes is the relative size of the error:

k∆xkα A−1 α→α k∆bkα kbkα k∆bkα k∆bkα

≤ = A−1 ≤ A−1 kAkα→α .
kxkα kA−1 bkα α→α kA−1 bkα kbkα α→α kbkα

We define the condition number of A ∈ Mn with respect to the submultiplicative

norm k·k to be (
kAk A−1 if A is nonsingular,
κk·k (A) =
∞ if A is singular.
Note that κk·k (A) ≥ kIn k ≥ 1 by submultiplicativity. When k·k is the operator norm k·kα→α
induced by the norm k·kα on Fn , we write κα . The particular case κ2 with respect to the
`2 norm is usually simply called the condition number of A; note that κ2 (A) = σσn1 (A)
(A) .
We have just seen that in solving Ax = b with an error ∆b in the right hand side, using
the known value of A−1 ,
k∆xkα k∆bkα
≤ κα (A) .
kxkα kbkα
That is, the condition number bounds how much the size of the relative error (with respect
to the norm k·kα ) is increased.
Now suppose that there is some uncertainty or error in the matrix A itself. How will
that error propagate to the computed inverse matrix A−1 ? It turns out that condition
numbers control the relative error here as well.

Proposition 5.1. Let k·k be a submultiplicative norm on Mn and write κ = κk·k . Suppose
that A ∈ Mn is nonsingular, and that A−1 k∆Ak = κ(A) k∆Ak
kAk < 1. Then A + ∆A is
nonsingular, and
A−1 − (A + ∆A)−1 κ(A) k∆Ak
kAk
−1
≤ .
kA k 1 − κ(A) k∆Ak
kAk

x
Note that 1−x = x + x2 + x3 + · · · ≈ x for small x. Thus the upper bound in the
inequality in Proposition 5.1 is about κ(A) k∆Ak
kAk when this quantity is small.

51
Proof. Let B = A + ∆A = A(In + A−1 ∆A). By submultiplicativity and the hypothesis,
A−1 ∆A ≤ A−1 k∆Ak < 1, so by Corollary 4.29, In + A−1 ∆A is nonsingular, and hence
B is nonsingular as well. Now

A−1 − B −1 = A−1 (B − A)B −1 = A−1 (∆A)B −1 ,

so
A−1 − B −1 ≤ A−1 ∆A B −1 .
By the triangle inequality,

B −1 = A−1 − A−1 (∆A)B −1 ≤ A−1 + A−1 ∆A B −1 ,

which implies that

A−1
B −1 ≤ .
1 − kA−1 ∆Ak
It follows that
A−1 − B −1 A−1 ∆A
≤ .
kA−1 k 1 − kA−1 ∆Ak
Since A−1 ∆A ≤ A−1 k∆Ak = κ(A) k∆Ak
kAk , this proves the claim.

5.2 Sparse signal recovery

Consider an m × n linear system Ax = b. If rank A < n (in particular, if m > n) and a
solution x exists, then there will be infinitely many solutions. We saw in section 2.2 that
singular value decomposition, via the Moore–Penrose pseudoinverse, gives a way to pick out
one particular solution: the least squares solution, which is the solution to the optimization
problem:
Minimize kxk2 among all x ∈ Rn such that Ax = b. (7)
For different purposes, we might wish to pick out a different solution. In many signal
processing applications, it is particularly useful to find sparse solutions, that is, solutions
such that xj = 0 for most j. In particular, we would often like to solve the optimation
problem:
Minimize # {j | xj 6= 0} among all x ∈ Rn such that Ax = b. (8)
Unfortunately, solving (8) is much more difficult computationally; it essentially requires
searching through exponentially many subspaces, making it in general a computationally
intractable problem for large matrices.
One way to attack this problem is to replace the combinatorial quantity # {j | xj 6= 0}
with something that has nicer analytic properties. For example, if f : Rn → R is a convex
function, then there are good computational tools for solving optimation problems of the
form
Minimize f (x) among all x ∈ Rn such that Ax = b.
Notice in particular that (7) is of this form, using f (x) = kxk2 . Superficially it might appear
that (7) could be a reasonable substitute for (8), since, after all, k·k2 is a monotone norm,

52
so less sparse matrices have larger norm. However, this fact doesn’t interact well with the
restriction Ax = b.
Suppose for example that the solution space of Ax = b consists of the line x + 2y = 1.
The two sparsest solutions are (1/2, 0) and (0, 1), but the solution with least `2 norm is
(1/5, 2/5). In fact, in this two-dimensional setting the solution with least `2 norm will never
be a sparsest solution unless the solution space is either a horizontal or vertical line.
A next thought might be to replace k·k2 with a different norm that behaves more like
# {j | xj 6= 0}. The most obvious candidate is the `1 norm, so we consider the optimization
problem
Minimize kxk1 among all x ∈ Rn such that Ax = b. (9)
In the example above, for instance, (1/2, 0) minimizes the `1 norm on the line x+2y = 1. In
fact, on any line in R2 , the `1 norm is minimized by a point lying on one of the coordinate
axes, and uniquely minimized by such a point unless the line has slope ±1. (Note that those
situations are as exceptional as the situations in which the `2 norm is minimized by a point
on one of the coordinate axes.)
It turns out that (9) is indeed a useful substitute for (8). To state a precise result along
these lines we will need a little more terminology.
First, for x ∈ Rn , we define kxk0 = # {j | xj 6= 0}. Note that k·k0 is not a norm. Next,
we say that A ∈ Mm,n satisfies the restricted isometry property (RIP) with parameters
α, β > 0 and s if
α kxk2 ≤ kAxk2 ≤ β kxk2
whenever kxk0 ≤ s. That is, A approximately preserves the `2 norm, up to a scalar multiple,
when we restrict it to acting on sufficiently sparse vectors.

Theorem 5.2. Suppose that A ∈ Mm,n satisfies the RIP with parameters α, β, and (1+λ)s,
with λ > (β/α)2 . Then, whenever kxk0 ≤ s and Ax = b, x is the solution of the optimization
problem (9).

Theorem 5.2 implies that the (computationally tractable) convex optimization problem
(9) will find the solution of the hard combinatorial optimization problem (8), as long as the
matrix A satisfies the RIP with suitable parameters, relative to the sparsity of the solution
of (8).
The difficulty now is how to tell whether A satisfies the RIP. Unfortunately, for a given
matrix A this is not much easier than solving (8) directly. On the other hand, it is known
that many natural ways of generating a large matrix randomly have a very high probability
of producing a matrix that satisfies the RIP. Here we will not deal with these issues, and
merely proof Theorem 5.2.

Proof of Theorem 5.2. Assume that kxk0 ≤ s and that Ax = b. Let xb be a solution of the
optimization problem (9). We wish to show that x b − x, so that we need to
b = x. Let h = x
show h = 0. Note that
Ah = Ab x − Ax = b − b = 0.
We start by decomposing the the set of indices, and decomposing h in a corresponding
way. For a subset I ⊆ {1, . . . , n} and y ∈ Rn , we write yI ∈ Rn for the vector with

53
components (
yj if j ∈ I,
(yI )j = .
0 if j ∈
/ I.
Let
I0 = {j | xj 6= 0} ,
so that #I0 = kxk0 ≤ s. Let I1 denote the indices for the λs largest (in absolute value)
entries of hI0c , let I2 denote the indices for the λs next largest entries, and so on; say It is
the last of these (which may have fewer than λs elements). (If there are entries of equal
magnitude, we can order them arbitrarily.) We also write I0,1 = I0 ∪ I1 .
We first observe that kb xk1 ≥ kxk1 by definition of x
b. On the other hand,

xk1 = kx + hk1 = kx + hI0 k1 + hI0c

kb 1
≥ kxk1 − khI0 k1 + hcI0 1

by the triangle inequality. Therefore

hcI0 1
≤ khI0 k1 .

Next, by the triangle inequality,

0 = kAhk2 = A(hI0,1 + hI0,1

c ) ≥ AhI0,1 2
− AhI0,1
c .
2 2
Pt
Now hI0,1 0 ≤ #I0 + #I1 ≤ (1 + λ)s, khIk k0 ≤ λs for k ≥ 2, and hI0,1
c = k=2 hIk .
Therefore by the RIP hypothesis and the triangle inequality
t
X t
X
α hI0,1 2
≤ AhI0,1 2
≤ Ah c
I0,1 ≤ kAhIk k2 ≤ β khIk k2 .
2
k=2 k=2

To further bound the right hand side of this, note that by the definition of Ik , for k ≥ 2
we have
1 X 1
khIk k∞ ≤ min |hj | ≤ |hj | = hIk−1 1 .
j∈Ik−1 λs λs
j∈Ik−1
√
It follows that khIk k2 ≤ λs khIk k∞ ≤ √1 khIk k1 , and therefore
λs

t t t
X 1 X 1 X 1 1
khIk k2 ≤ √ hIk−1 1
≤√ khIk k1 = √ hI0c 1
≤ √ khI0 k1 .
k=2
λs k=2
λs k=1 λs λs

We now have that

β β β
α hI0,1 2
≤ √ khI0 k1 ≤ √ khI0 k2 ≤ √ hI0,1 2
.
λs λ λ

Since λ > (β/α)2 , this implies that hI0,1 2

= 0, so that hI0,1 = 0, and therefore h = 0.

54
6 Positive (semi)definite matrices
6.1 Characterizations
Recall the notion of a positive semidefinite matrix, which can be characterized in several
equivalent ways (Theorem 2.9). As you saw in homework, positive definite matrices have
several analogous characterizations, including as nonsingular positive semidefinite matrices.
One immediate consequence of the characterizations in terms of inner products hAx, xi
is the following fact, which we will often use without comment.

Lemma 6.1. If A ∈ Mn is positive (semi)definite, then every principal submatrix of A is

positive (semi)definite.

Another characterization of positive definite matrices is a special case of yet another

homework problem.

Theorem 6.2 (Sylvester’s criterion). A Hermitian matrix A is positive definite if and only
if the determinant of each upper-left principal submatrix of A is positive.

Proof. As you showed in homework, the determinant criterion implies that all the eigenval-
ues of A are positive, which implies that A is positive semidefinite.
Conversely, if A is positive definite then each of its principal submatrices is positive
definite, and hence determinant (the product of the eigenvalues) of each of those submatrices
is positive.

Theorem 6.3. If A ∈ Mn (F) is positive (semi)definite, then A has a unique positive

(semi)definite k th root (that is, a matrix B such that B k = A) for each k ∈ N.

Proof. Existence is proved just as in Theorem 2.9, which included the case k = 2: let A =
1/k 1/k
U diag(λ1 , . . . , λn )U ∗ be a spectral decomposition, and define B = U diag(λ1 , . . . , λn )U ∗ .
For uniqueness, given any distinct x1 , . . . , xn and y1 , . . . , yn ∈ R, there exists a poly-
nomial p(x) such that p(xj ) = yj for each j (for example, by the Lagrange interpolation
formula). Therefore, if λ1 , . . . , λn are the eigenvalues of A, there is a polynomial p such
1/k
that p(λj ) = λj for each j. It follows that p(A) = B for B defined as above.
Now suppose that C is positive semidefinite and C k = A. Then B = p(A) = p(C k ).
This implies that B and C commute. Since B and C are both Hermitian and therefore
diagonalizable, Theorem 2.21 implies that they are simultaneously diagonalizable:

B = SD1 S −1 and C = SD2 S −1

for some nonsingular S ∈ Mn (F) and diagonal D1 , D2 ∈ Mn (F). Then

SD1k S −1 = B k = A = C k = SD2k S −1 ,

which implies that D1k = D2k . The diagonal entries of D1 and D2 are the eigenvalues of B
and C, and therefore nonnegative, so this implies that D1 = D2 , and therefore B = C.

55
 For an arbitrary A ∈ Mn , the absolute value of A is the unique positive semidefinite
square root |A| of the positive semidefinite matrix A∗ A. (We could alternatively define
it using AA∗ ; this is not the same matrix when A is non-normal, but the difference is
only a matter of convention.) We can describe |A| explicitly in terms of a singular value
decomposition A = U ΣV ∗ as A = V ΣV ∗ . Thus the singular values of A are the same as
the eigenvalues of |A|. This implies that we can write the Schatten 1-norm (or Ky Fan
(n)-norm) of A as
kAk1 = tr |A| .
For this reason, the Schatten 1-norm is sometimes called the trace norm.
We have also encountered the matrix absolute value before in the polar decomposition
(Theorem 2.12), which we can now be state by saying that A = U |A| for some unitary
matrix U .

Proposition 6.4. Suppose that B ∈ Mm,n . Then:

1. ker B ∗ B = ker B.

2. rank B ∗ B = rank B.

3. B ∗ B is positive definite if and only if rank B = n.

Proof. If Bx = 0 then clearly B ∗ Bx = 0. If B ∗ Bx = 0, then

0 = hB ∗ Bx, xi = hBx, Bxi ,

and therefore Bx = 0. This proves the first statement. The second statement follows from
the rank–nullity theorem, and the third statement follows from the second statement and the
fact that a positive semidefinite matrix is positive definite if and only if it is nonsingular.

Proposition 6.5 (Cholesky factorization). A Hermitian matrix A ∈ Mn (F) is positive

semidefinite if and only if there exists a lower triangular matrix L ∈ Mn (F) such that
A = LL∗ .

Proof. If A = LL∗ then A is positive semidefinite. Conversely, if A is positive semidefinite,

then A = B ∗ B for some B ∈ Mn . Let B = QR be a QR decomposition. Then

A = B ∗ B = R∗ Q∗ QR = R∗ R.

Thus we can let L = R∗ .

Suppose that V is an inner product space. The Gram matrix of a list of vectors
v1 , . . . , vn is the matrix A ∈ Mn with entries ajk = hvk , vj i.

Theorem 6.6. 1. A matrix A ∈ Mn is positive semidefinite if and only if it the the

Gram matrix of some list of vectors in some inner product space.

2. A matrix A ∈ Mn is positive definite if and only if it the the Gram matrix of some
linearly independent list of vectors in some inner product space.

56
Proof. Suppose that A is the Gram matrix of v1 , . . . , vn . Given x ∈ Fn ,
2
n
X n
X n
X
hAx, xi = hvk , vj i xk xj = hxk vk , xj vj i = xj vj ≥ 0,
j,k=1 j,k=1 j=1

Pn thus A is positive semidefinite. Furthermore, this shows that hAx, xi = 0 if and only if
and
j=1 xj vj = 0. If v1 , . . . , vn is a linearly independent list, then this is the case if and only
if x = 0.
Now suppose that A is positive semidefinite. Then A = B ∗ B for some B ∈ Mn . This
implies that ajk = b∗j bk = hbk , bj i, where bj are the columns of B. Therefore A is the Gram
matrix of b1 , . . . , bn ∈ Fn . If A is positive definite then rank B = n, and so b1 , . . . , bn are
linearly independent.

Corollary 6.7. A list of vectors v1 , . . . , vn in an inner product space is linearly independent

if and only if their Gram matrix is nonsingular.

6.2 Kronecker and Hadamard products

If A ∈ Mm1 ,n1 and B ∈ Mm2 ,n2 , the Kronecker product A ⊗ B ∈ Mm1 m2 ,n1 n2 is defined
by the block presentation
 
a11 B · · · a1n1 B
A ⊗ B =  ... .. ..
.
 
. .
am1 1 B · · · am1 n1 B

Straightforward computations show that

(A ⊗ B)(C ⊗ D) = (AC) ⊗ (BD)

when all of these products are defined, that (A ⊗ B)∗ = A∗ ⊗ B ∗ . If follows that if U and
V are unitary matrices (not necessarily of the same size) then U ⊗ V is also unitary, and if
A and B are Hermitian then so is A ⊗ B.
Proposition 6.8. 1. Suppose that A ∈ Mm has eigenvalues λ1 , . . . , λm and B ∈ Mn
has eigenvalues µ1 , . . . , µn (with multiplicity). Then A ⊗ B has eigenvalues λj µk for
1 ≤ j ≤ m and 1 ≤ k ≤ n.

2. Suppose that A ∈ Mm1 ,n1 has singular values σ1 , . . . , σp1 and B ∈ Mm2 ,n2 has singular
values τ1 , . . . , τp2 , where pi = min{mi , ni }. Then A ⊗ B has singular values σj τk for
1 ≤ j ≤ p1 and 1 ≤ k ≤ p2 , possibly with additional 0s.
Proof. 1. Let A = U T1 U ∗ and B = V T2 V ∗ be Schur decompositions. Then

A ⊗ B = (U ⊗ V )(T1 ⊗ T2 )(U ∗ ⊗ V ∗ ) = (U ⊗ V )(T1 ⊗ T2 )(U ⊗ V )∗ .

Since U ⊗ V is unitary, the eigenvalues of A ⊗ B are the eigenvalues of the triangular

matrix T1 ⊗ T2 , which are precisely as given in the statement of the proposition.

57
 2. Let A = U1 Σ1 V1∗ and B = U2 Σ2 V2∗ be singular value decompositions. Then

A ⊗ B = (U1 ⊗ U2 )(Σ1 ⊗ Σ2 )(V1 ⊗ V2 )∗

is a singular value decomposition, in which the singular values are precisely as given
in the statement of the proposition.

Corollary 6.9. If A ∈ Mm and B ∈ Mn are both positive (semi)definite, then so is A ⊗ B.

If A, B ∈ Mm,n , the Hadamard product A ◦ B ∈ Mm,n is defined to have entries

[A ◦ B]jk = ajk bjk . Note that A ◦ B is a submatrix of A ⊗ B, and is a principal submatrix
when A, B ∈ Mn . With this observation in mind, the next result follows immediately from
Corollary 6.9.

Corollary 6.10 (Schur product theorem). If A, B ∈ Mn are both positive (semi)definite,

then so is A ◦ B.

6.3 Inequalities for positive (semi)definite matrices

If A, B ∈ Mn are Hermitian, we write A  B if B − A is positive semidefinite, and A ≺ B
if B − A is positive definite.

Proposition 6.11. The relation  is a partial order on the set of n×n Hermitian matrices.
That is:

1. A ≺ A for every A.

2. If A ≺ B and B ≺ C, then A ≺ C.

3. If A ≺ B and B ≺ A, then A = B.

The proof of Proposition 6.11 is left as an exercise.

The following result follows immediately from the Weyl monotonicity theorem (Corollary
3.8).

Proposition 6.12. If A  B then λ↓j (A) ≤ λ↓j (B) for every 1 ≤ j ≤ n.

The following corollary is immediate.

Corollary 6.13. If A  B then tr A ≤ tr B. If 0  A  B then det A ≤ det B.

Recall the following result from the January 28 homework, sometimes

Qn known as Hadamard’s
inequality: if A ∈ Mn has columns a1 , . . . , an , then |det A| ≤ j=1 kaj k2 . This has the fol-
lowing consequence, which often goes by the same name.

Theorem 6.14 (Hadamard’s inequality for positive semidefinite matrices). If A ∈ Mn is

positive semidefinite, then det A ≤ nj=1 ajj .
Q

58
Proof. Write A = B 2 for a Hermitian matrix B with columns bj = Bej . Then

ajj = hAej , ej i = B 2 ej , ej = hBej , Bej i = kbj k22 .

Therefore, by the earlier Hadamard’s inequality applied to B,

n
Y n
Y
det A = (det B)2 ≤ kbj k22 = ajj .
j=1 j=1
 
A B
Theorem 6.15 (Fischer’s inequality). Suppose that H = is positive semidefinite
B∗ C
with A and C square.

Proof. Let A = U ΛU ∗ and C = V ΓV ∗ be spectral decompositions, and define W = U ⊕ V .

Then
U ∗ BV
 
∗ Λ
W HW =
V ∗ BU Γ
By Hadamard’s inequality (Theorem 6.14),
n
Y
det H = det(W ∗ HW ) ≤ λj γj = (det Λ)(det Γ) = (det A)(det C).
j=1

Theorem 6.16. If A ∈ Mn is positive definite, then

 
1/n 1
(det A) = min tr(AB) B ∈ Mn is positive definite with det B = 1 .
n

Proof. Let A = U ΛU ∗ be a spectral decomposition. Then det A = det Λ and tr(AB) =

tr(ΛU ∗ BU ). It therefore suffices to assume that A = Λ. By the arithmetic geometric mean
inequality (Lemma 4.1) and Hadamard’s inequality (Theorem 6.14),
 1/n  1/n
n n n
1 1 X Y Y
tr(ΛB) = λj bjj ≥  λj   bjj  ≥ (det A)1/n (det B)1/n
n n
j=1 j=1 j=1

for any positive definite B. In particular, if det B = 1 then

1
(det A)1/n ≤ tr(AB).
n

Moreover, we have equality here if B = (det A)1/n A−1 .

Corollary 6.17 (Minkowski’s determinant inequality). If A, B ∈ Mn are positive definite

then 1/n
≥ (det A)1/n + (det B)1/n .

det(A + B)

59
Proof. By Theorem 6.16,
 
 1/n 1
det(A + B) = min tr(A + B)C C  0, det C = 1
n
 
1
≥ min tr(AC) C  0, det C = 1
n
 
1
+ min tr(BC) C  0, det C = 1
n
= (det A)1/n + (det B)1/n .

7 Locations and perturbations of eigenvalues

7.1 The Geršgorin circle theorem
P
Theorem 7.1 (Geršgorin’s theorem). Let A ∈ Mn , and define Rj (A) = k6=j |ajk | and

Dj (A) = {z ∈ C | |z − ajj | ≤ Rj (A)} .

Then each eigenvalue of A lies in at least one Dj (A).

The sets Dj (A) are sometimes called the Geršgorin discs of A. Note that Theorem 7.1
does not say that each disc Dj (A) contains an eigenvalue.

Proof. Suppose that Ax = λx for x 6= 0, and pick an index p such that |xp | = kxk∞ .
Considering the pth entry of (Ax − λx) = 0, we have
X
(λ − app )xp = apk xk ,
k6=p

and therefore
|λ − app | ≤ Rp (A) kxk∞ = Rp (A) |x|p .

Recall that A is called strictly diagonally dominant if |ajj | > Rj (A) for each j.
Geršgorin’s theorem gives us a new proof of the Levy–Desplanques theorem (Corollary
4.24), which states that a strictly diagonally dominant matrix is nonsingular:

Second proof of Corollary 4.24. If A is strictly diagonally dominant, then for each j, 0 ∈ /
Dj (A). By Theorem 7.1, this implies that 0 is not an eigenvalue of A and so A is nonsingular.

Conversely, the Levy–Desplanques theorem implies Geršgorin’s theorem. Since we al-

ready have an independent proof of the Levy–Desplanques theorem, this gives a second
approach to proving Geršgorin’s theorem.
This is one manifestation of a general phenomenon: any result about locations of eigen-
values gives a sufficient condition for invertibility (whatever condition forces 0 not to be an

60
eigenvalue). And conversely, any sufficient condition for invertibility implies a result about
locations of eigenvalues (since σ(A) = {z ∈ C | A − zIn is singular}).4
Geršgorin’s theorem can be generalized and extended in many ways. P A first obvious
observation is that columns can be used just as well as sums: if Ck (A) = j6=k |ajk |, then
each eigenvalue of A lies in some disc

{z ∈ C | |z − akk | ≤ Ck (A)} .

This can be proved analogously, or deduced directly from Geršgorin’s theorem since σ(AT ) =
σ(A). More subtle analogues exist which consider both the rows and sums of A at the same
time.
Another easy way to extend Geršgorin’s theorem is to note that σ(S −1 AS) = σ(A) for
any nonsingular S, and apply Geršgorin’s theorem to S −1 AS. If we let S = diag(d1 , . . . , dn )
with dj > 0 for each j, we get the following.
Corollary 7.2. Suppose that d1 , . . . , dn > 0 and A ∈ Mn . Then each eigenvalue of A lies
in one of the discs  
 1 X 
z ∈ C |z − ajj | ≤ dk |ajk |
 dj 
k6=j

for j = 1, . . . , n.

7.2 Eigenvalue perturbations for non-Hermitian matrices

Recall Mirsky’s inequality (Theorem 4.38), which states that

λ↓ (A) − λ↓ (B) ≤ kA − Bk

for any corresponding pair of a symmetric gauge function and unitarily invariant norm, and
any Hermitian matrices A, B ∈ Mn . This result refines, in precise, quantitative form, the
fact that eigenvalues depend continuously on the matrix (Corollary 2.20) — but only for
Hermitian matrices.
For general matrices, the first obstacle is that since the eigenvalues need not be real, and
it’s not clear how to quantify how similar two sets of complex numbers are to each other
absent a natural ordering. In fact there are many ways to do this, and different eigenvalue
perturbation theorems involve different ones.
We will first prove two results for normal matrices. Despite the fact that eigenvalues
of normal matrices can be any complex numbers, eigenvalues of normal matrices are still
better behaved as functions of the matrix than in the completely general case.
Given two closed, bounded sets X, Y ⊆ C, the Hausdorff distance between them is
defined to be  
dH (X, Y ) = max max min |x − y| , max min |x − y| .
x∈X y∈Y y∈Y x∈X

4
A very careful reader might note that our first proof of the Levy–Desplanques theorem was based on
applying Corollary 4.23 with the maximum row sum norm, and that Corollary 4.23 itself was proved by
this strategy: deduce invertibility of In − A by considering where the eigenvalues of A are. So this second
suggested proof of the Levy–Desplanques theorem uses all the same ideas as the first one.

61
That is, dH (X, Y ) is the farthest that a point from one of the two sets can be from the
other set.
Theorem 7.3 (Bauer–Fike theorem). Suppose that A, B ∈ Mn are normal. Then
dH (σ(A), σ(B)) ≤ kA − Bk2→2 .
Proof. We will prove a stronger fact: if A ∈ Mn is normal and B ∈ Mn is arbitrary, then
max min |λ − µ| ≤ kA − Bk2→2 .
µ∈σ(B) λ∈σ(A)

Suppose that Bx = µx with kxk2 = 1, and let A = U ΛU ∗ be a spectral decomposition.

Then, with the substitution y = U ∗ x,
kA − Bk2→2 ≥ k(A − B)xk2 = kAx − µxk2 = kU (Λ − µIn )U ∗ xk2
v
u n
uX
= k(Λ − µIn )yk2 = t |λj − µ|2 |yj |2 ≥ min |λj − µ| ,
1≤j≤n
j=1
Pn 2
since j=1 |yj | = kyk22 = 1.
The Hausdorff distance measures a kind of “worst case scenario” for comparing two sets
of complex numbers. The following result, which generalizes Corollary 3.22, considers a
kind of average comparison.
Theorem 7.4 (Hoffman–Wielandt inequality for normal matrices). Suppose that A, B ∈
Mn are both normal. The eigenvalues {λj } of A and {µj } of B can be ordered so that
v
u n
uX
t |λj − µj |2 ≤ kA − BkF .
j=1

To prove this, we need to deal with some leftovers from before. Suppose that V is a
finite-dimensional real vector space and that K ⊆ V is a closed convex set. A point x ∈ K
is called an extreme point of K if, whenever x = ty + (1 − t)z for y, z ∈ K and 0 < t < 1,
we must have x = y = z.
Proposition 7.5. Let Kn ⊆ Mn be the set of n × n doubly stochastic matrices. If A ∈ Kn
is an extreme point of Kn , then A is a permutation matrix.
Proof. We will show that if A ∈ Kn is not a permutation matrix, then A is not an extreme
point of Kn .
If A is not a permutation matrix, it has some row with two positive entries; choose one
such entry ai1 ,j1 ∈ (0, 1). Then there is an entry ai2 ,j1 ∈ (0, 1) for some i2 6= i1 , and then
some ai2 ,j2 ∈ (0, 1) for some j2 6= j1 . We continue picking entries in (0, 1) in this way until
the first time an entry aij is picked twice.
Let a be the value of the smallest entry picked from the first to the second time aij
occurs. Define B ∈ Mn to have 1 in the position of the first entry in this sequence, −1
in the position of the second entry, and so on, with all other entries 0. Then the row and
column sums of B are all 0. We then have that A+ = A + aB and A− = A − aB are
nonnegative with row and column sums all equal to 1, so A± ∈ Kn , and A = 12 A+ + 12 A− .
Therefore A is not an extreme point of Kn .

62
 A basic fact from convexity is that a closed, bounded, convex set is the convex hull of
its extreme points; thus Proposition 7.5 implies Birkhoff’s theorem (Theorem 3.21).

Proof of Theorem 7.4. Let A = U ΛU ∗ and B = V ΓV ∗ be spectral decompositions, and let

W = U ∗ V . Then
n
X
kA − Bk2F = kΛW − W Γk2F = |λj − γk |2 |wjk |2 .
j,k=1
h i
The matrix |wjk |2 is unitary stochastic, hence doubly stochastic. So by Birkhoff’s theo-
rem, it can be written as N
P
PN i=1 ti Pi for permutation matrices P1 , . . . , PN and t1 , . . . , tN ≥ 0
with i=1 ti = 1. Writing pijk for the entries of Pi , this implies

N
X n
X n
X
kA − Bk2F = ti |λj − γk |2 pijk ≥ min |λj − γk |2 pijk .
1≤i≤N
i=1 j,k=1 j,k=1

Let π : {1, . . . , n} → {1, . . . , n} be the permutation corresponding to Pi , so that pijk = 1 if

π(j) = k, and other entries are 0. Then we have
n
2
X
kA − Bk2F ≥ λj − γπ(j) ,
j=1

so we can let µj = γπ(j) .

For non-normal matrices, the dependence of eigenvalues on the matrix can be much
more irregular. Consider the matrix
 
0 1 0 ··· ··· 0
 .. .. 
. 0 1 ... .

 .. .. 

.. .. ..
Aε =  . . . . . ∈ Mn

 .. ..
.

. 1 0
 
0 0 1
ε 0 ··· ··· ··· 0

for ε ≥ 0. Since A0 is triangular, we can tell immediately that its only eigenvalue is
0. It can be shown (in homework!) that the eigenvalues of Aε all have modulus ε1/n .
1/n
Thus dH (σ(Aε ), σ(A0 )) = ε1/n = kAε − A0 k2→2 . The same holds for the distances in the
Hoffman–Wielandt inequality.
The following theorem shows roughly that the example above is the worst things can
get.

Theorem 7.6. If A, B ∈ Mn , then

1 1/n
dH σ(A), σ(B) ≤ (kAk2→2 + kBk2→2 )1− n kA − Bk2→2 .

63
Proof. Let µ be an eigenvalue of B and let λ1 , . . . , λn be the eigenvalues of A. Then
n
Y
min |λj − µ| ≤ |λj − µ|1/n = |det(A − µIn )|1/n .
1≤j≤n
j=1

Let v1 , . . . , vn be an orthonormal basis of Cn such that Bv1 = µv1 , and let V be the unitary
matrix with those columns. Then
n
Y
|det(A − µIn )| = |det(A − µIn )V | ≤ k(A − µIn )vj k2
j=1

by Hadamard’s inequality. Now

k(A − µIn )v1 k2 = kAv1 − µv1 k2 = k(A − B)v1 k2 ≤ kA − Bk2→2 ,

and for j ≥ 2,

k(A − µIn )vj k2 ≤ kAvj k2 + kµvj k2 ≤ kAk2→2 + kBk2→2 .

Combining the above estimates proves the claim.

8 Nonnegative matrices
8.1 Inequalities for the spectral radius
We now turn to another special class of matrices: nonnegative matrices, by which we mean
matrices which have only nonnegative real entries, and the subclass of positive matrices,
those with only positive entries. It is important to be careful of the distinction between
positive matrices and positive (semi)definite matrices (likewise between nonnegative matri-
ces and nonnegative definite matrices, another term for positive semidefinite) — especially
since some authors use the term positive matrix to mean a positive (semi)definite matrix.
Nevertheless, we will see that many of the results for positive (semi)definite matrices,
or Hermitian matrices more generally, have analogues for nonnegative or positive matrices.
However, the methods tend to be quite different. In particular, in working with Hermi-
tian matrices we tend (with some notable exceptions) either to avoid thinking about the
individual matrix entries, or only think about them after invoking the spectral theorem
in order to reduce attention to diagonal entries. On the other hand, when working with
nonnegative matrices we work with matrix entries quite a lot — unsurprisingly, given that
the assumption of nonnegativity is entirely about matrix entries.
One major difference is that whereas Hermitian matrices have real eigenvalues, the
eigenvalues of a nonnegative matrix need not be real. Since many of the important results
about Hermitian matrices take the form of inequalities involving eigenvalues, this limits how
closely results about nonnegative matrices can resemble results for Hermitian matrices. The
spectral radius ρ(A), which of course is always a nonnegative real number, turns out to play
a central role in the theory of nonnegative matrices, similar to eigenvalues themselves in
the theory of Hermitian matrices.
Throughout this section |A| will refer to the entrywise absolute value of a matrix, as
opposed to the postive semidefinite absolute value introduced in section 6.1 above.

64
Theorem 8.1. Suppose that A ∈ Mn (C) and B ∈ Mn (R). If |A| ≤ B, then ρ(A) ≤
ρ(|A|) ≤ ρ(B).
In particular, if 0 ≤ A ≤ B, then ρ(A) ≤ ρ(B).

Compare this to the fact that if A, B ∈ Mn (C) are Hermitian and A  B, then λ↓j (A) ≤
λ↓j (B) for each j. In particular, if 0  A  B, then ρ(A) ≤ ρ(B).

Proof. For any m ∈ N and i, j we have

n
X
|[Am ]ij | = aik1 ak1 k2 · · · akm−2 km−1 akm−1 j
k1 ,...,km−1 =1
n
X
≤ |aik1 | |ak1 k2 | · · · akm−2 km−1 akm−1 j = [|Am |]ij
k1 ,...,km−1 =1
X n
≤ bik1 bk1 k2 · · · bkm−2 km−1 bkm−1 j = [B m ]ij .
k1 ,...,km−1 =1

Now let k·k be any absolute submultiplicative norm on Mn (C) (for example, the Frobenius
norm or the maximum column sum norm). It follows that

kAm k ≤ k|A|m k ≤ kB m k .

The claim now follows from the Gelfand formula (Corollary 4.27) ρ(A) = limm→∞ kAm k1/m .

From now on, unless otherwise specified, matrices are in Mn (R).

Corollary 8.2. If A ≥ 0 and B is a principal submatrix of A, then ρ(B) ≤ ρ(A). In

particular, ajj ≤ ρ(A) for each j.

Compare this to the fact (a consequence of the Rayleigh–Ritz theorem) that if A is

Hermitian and B is a principal submatrix of A, then ρ(B) ≤ ρ(A), and in particular
|ajj | ≤ ρ(A) for each j. (From now on we will mostly not comment on these analogies.)

Proof. Let A
e be the matrix obtained by replacing those entries of A not in B with 0. Then
0≤A e ≤ A, and ρ(A)
e = ρ(B). The result now follows from Theorem 8.1.

We will frequently find it convenient to refer to e = ni=1 ei = (1, . . . , 1).

P

Lemma 8.3. If A ≥ 0 and all the rows of A have the same sum r, then ρ(A) = r =
kAk∞→∞ .
If A ≥ 0 and all the columns of A have the same sum c, then ρ(A) = c = kAk1→1 .

Proof. By Theorem 4.22, ρ(A) ≤ kAk∞→∞ for any matrix. If all the rows of A ≥ 0 have the
same sum r, this implies that ρ(A) ≤ r. Moreover, Ae = re, which implies that ρ(A) ≥ r.
The second statement follows by applying the first statement to AT .

65
Theorem 8.4. If A ≥ 0, then
n
X n
X
min aij ≤ ρ(A) ≤ max aij
1≤i≤n 1≤i≤n
j=1 j=1

and
n
X n
X
min aij ≤ ρ(A) ≤ max aij .
1≤j≤n 1≤j≤n
i=1 i=1
Pn Pn
Proof. Let r = min1≤i≤n j=1 aij and R = max1≤i≤n j=1 aij . Define B ∈ Mn (R) as
follows:
bi1 = min{ai1 , r},
bi2 = min{ai2 , max{r − ai1 , 0}},
..
.
  
  n−1
X 
bin = min ain , max r − aij , 0 .
  
j=1

That is, in each row, the entries of B match those of A until the row sum of A exceeds r
(if ever); at that point B has whatever is necessary to make the row sum of B equal to r
and then 0 for the rest of the row. Then 0 ≤ B ≤ A, and B has all row sums equal to r.
By Theorem 8.1 and Lemma 8.3, this implies that r = ρ(B) ≤ ρ(A).
Now define C ∈ Mn (R) by cij = aij for 1 ≤ j ≤ n − 1 and
n−1
X
cin = R − aij .
j=1

Then A ≤ C and C has all row sums equal to R. By Theorem 8.1 and Lemma 8.3, this
implies that ρ(A) ≤ ρ(C) = R.
The second claim can be proved similarly, or follows by applying the first to AT .

Corollary 8.5. If A ≥ 0 and each row of A contains at least one nonzero entry, or each
column of A contains at least one nonzero entry, then ρ(A) > 0.
In particular, if A > 0 entrywise, then ρ(A) > 0.

We can extend Theorem 8.4 by conjugating A by a diagonal matrix, similar to the way
Geršgorin’s theorem was extended to Corollary 7.2.

Corollary 8.6. If A ≥ 0 and x1 , . . . , xn > 0, then

n n
1 X 1 X
min aij xj ≤ ρ(A) ≤ max aij xj .
1≤i≤n xi 1≤i≤n xi
j=1 j=1

Corollary 8.7. If A ≥ 0, x > 0, and αx ≤ Ax ≤ βx for some α, β ≥ 0, then α ≤ ρ(A) ≤ β.

If αx < Ax, then α < ρ(A), and if Ax < βx, then ρ(A) < β.

66
Proof. The first claim follows immediately from Corollary 8.6. For the second, if αx < Ax,
then there exists some α0 > α such that αx < α0 x < Ax, and so ρ(A) ≥ α0 > α; the other
part follows similarly.

Corollary 8.8. Let A ≥ 0. If A has a positive eigenvector x, then Ax = ρ(A)x.

Proof. Suppose that Ax = λx. Since x > 0 and A ≥ 0, this implies that λ ≥ 0. Now since
λx ≤ Ax ≤ λx, Corollary 8.7 implies that ρ(A) = λ.

The final result of this section can be thought of as a counterpart of the Rayleigh–Ritz
theorem for the spectral radius of a nonnegative matrix.

Corollary 8.9. If A ≥ 0 has a positive eigenvector, then

n n
1 X 1 X
ρ(A) = max min aij xj = min max aij xj .
x>0 1≤i≤n xi x>0 1≤j≤n xi
j=1 j=1

In the following sections we will see sufficient conditions for a nonnegative matrix to
have a positive eigenvector.

Proof. Suppose that y is a positive eigenvector of A. By Corollary 8.8, Ay = ρ(A)y, and so

n
1 X
ρ(A) = aij yj
yi
j=1

for each i. Together with Corollary 8.6 this implies the claim.

8.2 Perron’s theorem

This section is devoted to proving the following theorem, which is the fundamental result
about the spectral radius of a positive matrix.

Theorem 8.10 (Perron’s theorem). Suppose that A > 0. Then:

1. ρ(A) > 0.

2. ρ(A) is an eigenvalue of A with multiplicity 1.

3. There is a positive eigenvector x > 0 of A with eigenvalue ρ(A), which is unique

up to scalar multiples. With the normalization kxk1 = 1, this is called the Perron
eigenvector of A.

4. If λ ∈ σ(A) and λ 6= ρ(A), then |λ| < ρ(A).

5. Let x be the Perron eigenvector of A, and let y > 0 be an eigenvector of AT with

eigenvalue ρ(A) normalized so that hx, yi = 1. Then
 m
1
lim A = xy T .
m→∞ ρ(A)

67
 We will prove Theorem 8.10 a bit at a time. The first part has already been proved in
Corollary 8.5.

Lemma 8.11. Suppose that A > 0, Ax = λx for x 6= 0, and that |λ| = ρ(A). Then
A |x| = ρ(A) |x|, and |x| > 0.

Proof. Note first that

ρ(A) |x| = |λ| |x| = |Ax| ≤ |A| |x| = A |x| ,

and that A |x| > 0 since A > 0 and |x| ≥ 0. Now if A |x| − ρ(A) |x| =
6 0, we would have

0 < A(A |x| − ρ(A) |x|) = A(A |x|) − ρ(A)(A |x|),

which implies that ρ(A)(A |x|) < A(A |x|). Since A |x| > 0, Corollary 8.7 would then imply
that ρ(A) > ρ(A), which is impossible. Therefore we must have A |x| − ρ(A) |x| = 0.
Finally, since ρ(A) |x| = A |x| > 0, we must have |x| > 0.

Proposition 8.12. If A > 0 then ρ(A) is an eigenvalue of A with a positive eigenvector.

Proof. This follows immediately from Lemma 8.11.

Proposition 8.12 implies the first half of part 2 (without the multiplicity 1 part) and the
first half of part 3 (without the uniqueness) of Theorem 8.10.

Lemma 8.13. Suppose that A > 0, Ax = λx for x 6= 0, and that |λ| = ρ(A). Then
x = eiθ |x| for some θ ∈ R.

Proof. By Lemma 8.11,

|Ax| = |λx| = ρ(A) |x| = A |x| .
Pn Pn
Therefore for each i, j=1 aij xj = j=1 aij |xj |, which implies that the numbers aij xj all
have the same argument. Since aij > 0, this implies that the xj all have the same argument,
which is equivalent to the claim.

Proposition 8.14. Suppose that A > 0, λ ∈ σ(A), and that λ 6= ρ(A). Then |λ| < ρ(A).

Proof. By Lemma 8.13, if x is an eigenvector associated to an eigenvalue λ with |λ| = ρ(A),

then some scalar multiple w of x is positive. Corollary 8.8 then implies that λ = ρ(A).

Proposition 8.14 proves part 4 of Theorem 8.10.

Proposition 8.15. If A > 0, then ρ(A) has geometric multiplicity one as an eigenvalue of
A. That is, the eigenspace ker(A − ρ(A)In ) is one-dimensional.

Proof. Suppose that x, y ∈ Cn are both eigenvectors of A with eigenvalue ρ(A). By Lemma
8.13 we may assume that x, y ≥ 0, and by Lemma 8.11 we then have that x, y > 0. Let
y
β = min1≤j≤n xjj . Then z := y − βx ≥ 0 has at least one zero entry, and Az = ρ(A)z.
Therefore Az has at least one zero entry, which implies Az = 0, and so z = 0.

68
 Proposition 8.15 completes the proof of part 3 of Theorem 8.10. Note that part 2 of
Theorem 8.10 is actually a stronger statement than Proposition 8.15 (since the (algebraic)
multiplicity of an eigenvalue is at least as large as its geometric multiplicity). However, we
will use Proposition 8.15 in part to prove that statement.
Lemma 8.16. Suppose that A ∈ Mn , x, y ∈ Cn , Ax = λx, AT y = λy and xT y = 1. Let
L = xy T . Then:
1. Lx = x and LT y = y.
2. Lm = L for all m ∈ N.
3. Am L = LAm = λn A for all m ∈ N.
4. L(A − λL) = 0.
5. (A − λL)m = Am − λm L for all m ∈ N.
6. If 0 6= µ ∈ σ(A − λL) then µ ∈ σ(A).
7. If 0 6= λ ∈ σ(A) has geometric multiplicity 1, then λ ∈
/ σ(A − λL), so λIn − (A − λL)
is nonsingular.
Moreover, if λ has geometric multiplicty 1 and is the only eigenvalue of A with absolute
value ρ(A), then:
8. ρ(A − λL) ≤ |λn−1 | < ρ(A).
m→∞
9. (λ−1 A)m = L + (λ−1 A − L)m −−−−→ L.
Proof. The first three parts are immediate, the fourth follows from the second and third,
and the fifth follows from the fourth by an easy induction.

6. Suppose w is an eigenvector of A − λL with nonzero eigenvalue µ. Then µLw =

L(A − λL)w = 0 by part 4, so Lw = 0, and therefore µw = (A − λL)w = Aw.
7. Suppose 0 6= λ ∈ σ(A) has geometric multiplicity 1. Then every eigenvector of A with
eigenvalue λ is a scalar multiple of x. Suppose now that λ is an eigenvalue of A − λL
with eigenvector w. The proof above of part 6 showns that Aw = λw, and so w = αx
for some α ∈ C. Then
λw = (A − λL)w = α(A − λL)x = 0,
and so w = 0, which is a contradiction.
8. By part 6, either ρ(A − λL) = |µ| for some µ ∈ σ(A), or else ρ(A − λL) = 0. By part
7, in the former case µ 6= λ, and so |µ| < ρ(A).
9. By parts 5 and 2,
(λ−1 A − L)m = (λ−1 A)m − Lm = (λ−1 A)m − L.
m→∞
By part 8, ρ(λ−1 A−L) = |λ|−1 ρ(A−λL) < 1, which implies that (λ−1 A−L)m −−−−→
0 by Theorem 4.26.

69
 Propositions 8.14 and 8.15 and Lemma 8.16 imply part 5 of Theorem 8.10.
It remains to prove part 2 of Theorem 8.10:

Proposition 8.17. If A > 0 then ρ(A) has (algebraic) multiplicity 1 as an eigenvalue of

A.

Proof. Let A = U T U ∗ be a Schur decomposition of A, with ρ = ρ(A) as the first k diagonal

entries of T . By Proposition 8.14, |tjj | < ρ for j > k. Then U ∗ (ρ−1 A)m U m = (ρ−1 T )m has
the first k entries equal to 1 for each m. By part 5 of Theorem 8.10, U ∗ (ρ−1 A)m U converges
as m → ∞ to a matrix with rank 1. It follows that k = 1.

Only one part of Perron’s theorem (Theorem 8.10) extends to nonnegative matrices
without adding additional assumptions:

Theorem 8.18. Suppose that A ≥ 0. Then ρ(A) is an eigenvalue of A with a nonnegative

eigenvector.

We will give two proofs of Theorem 8.18. The first fits neatly with recurring themes of
this course.
k→∞
First proof of Theorem 8.18. Let Ak be a sequence of positive matrices such that Ak −−−→
A (for example, [Ak ]ij = max{aij , k1 }). Let xk > 0 be the Perron eigenvector of Ak , so that
kxk k1 = 1 and Ak xk = ρ(Ak )xk for each k. The set {x ∈ Rn | x ≥ 0, kxk1 = 1} is closed
and bounded, so there is a subsequence xkm which converges to some x ≥ 0 with kxk1 = 1.
m→∞
Moreover, we have Akm −−−−→ A and, by the continuity of eigenvalues, ρ(Akm ) → ρ(A). It
follows that
Ax = lim Akm xkm = lim ρ(Akm )xkm = ρ(A)x.
m→∞ m→∞

The second proof of Theorem 8.18 illustrates a new idea: using nontrivial topological
theorems. We will need the following result, which is typically proved using homology
theory.

Theorem 8.19 (Brouwer’s fixed point theorem). Suppose that C ⊆ Rn is closed, bounded,
and convex. Then each continuous function f : C → C has a fixed point. That is, there
exists an x ∈ C such that f (x) = x.

Second proof of Theorem 8.18. The set

C = {x ∈ Rn | x ≥ 0, kxk1 = 1, Ax ≥ ρ(A)x}

is closed, bounded, and convex. If λ ∈ σ(A) satisfies |λ| = ρ(A) and Av = λv, then

A |v| ≥ |Av| = |λv| = ρ(A) |v| .

|v|
It follows that kvk ∈ C, and therefore C 6= ∅.
1
Define f : C → Rn by
Ax
f (x) = .
kAxk1

70
Clearly f (x) ≥ 0 and kf (x)k1 = 1. Furthermore,

1 1
Af (x) = AAx ≥ Aρ(A)x = ρ(A)f (x).
kAxk1 kAxk1

Therefore f maps C into C. By Theorem 8.19, there exists a y ∈ C such that f (y) = y.
We then have
Ay = kAyk1 y ≥ ρ(A)y,
where the inequality follows since y ∈ C. Thus y ≥ 0 is an eigenvector of A with positive
eigenvalue kAyk1 ≥ ρ(A); it follows that in fact the eigenvalue is ρ(A).

8.3 Irreducible nonnegative matrices

To state a generalization of Perron’s theorem, we will need another piece of terminology.
A matrix A ∈ Mn is called reducible if there exists a permutation matrix P ∈ Mn such
that P −1 AP has the block form
 
−1 B C
P AP =
0n−r,r D

where 0n−r,r denotes an (n − r) × r block of 0’s with 1 ≤ r ≤ n − 1. Equivalently, some

proper subset of the standard basis vectors spans an invariant subspace for A. If A is not
reducible, then A is called irreducible. Note that any strictly positive matrix is clearly
irreducible.
Theorem 8.4 immediately implies:

Proposition 8.20. If A ≥ 0 is irreducible, then ρ(A) > 0.

We will need the following reformulation of irreducibility for nonnegative matrices.

Proposition 8.21. Suppose that A ∈ Mn , A ≥ 0. Then A is irreducible if and only if

(In + A)n−1 > 0.

Proof. We clearly have (In + A)n−1 ≥ 0. We therefore need to show that A is reducible if
and only if some entry of (In + A)n−1 is 0.
 Suppose
 that A is irreducible. Without loss of generality, we may assume that A =
B C
with square blocks B and D. It follows that
0 D

n−1 n−1 
X n − 1 k X n − 1 Bk ∗
  
n−1
(In + A) = A =
k k 0 Dk
k=0 k=0

for some value of ∗, and so (In + A)n−1 has a 0 entry.

Now suppose that [(In + A)n−1 ]pq = 0. Then
n
X
[In + A]p,i1 [In + A]i1 ,i2 · · · [In + A]in−1 ,q = 0.
i1 ,...,in−1 =1

71
Each factor of each of the summands of the left hand side above is nonnegative, and so
each summand is 0, so for each choice of i1 , . . . , in−1 at least one of the factors [In + A]p,i1 ,
[In + A]i1 ,i2 , . . . , [In + A]in−1 ,q is 0.
Let J1 = {k | [In + A]p,k 6= 0} and iteratively define

Ji = {k | [In + A]m,k 6= 0 for some m ∈ Ji−1 }

for 2 ≤ i ≤ n. Note that since [In + A]jj ≥ 1 for each j, Ji−1 ⊆ Ji for each i. The argument
above shows that q ∈ / Jn . Note that [In + A]jk = 0, and hence ajk = 0, whenever j ∈ Jn
and k ∈/ Jn . Therefore, if P is a permutation matrix that reorders {1,. . . , n}to put the
B C
indices in J after all the indices in J c , then P AP −1 has the block form , and so A
0 D
is reducible.

Theorem 8.22 (Perron–Frobenius theorem). Suppose that A ≥ 0 is irreducible. Then

ρ(A) > 0 is an eigenvalue of A with multiplicity 1, and there is a corresponding positive
eigenvector.

Proof. We have already seen that ρ(A) > 0 (in Proposition 8.20) and that ρ(A) is an
eigenvalue of A with a nonnegative corresponding eigenvector x (Theorem 8.18). Then

(In + A)x = (1 + ρ(A))x = ρ(In + A)x

since ρ(A) is an eigenvalue of A. By Proposition 8.21, it follows that

0 < (In + A)n−1 x = (1 + ρ(A))n+1 x,

and so x > 0.
Finally, by Perron’s theorem, ρ(In + A)n−1 has multiplicity 1 as an eigenvalue of the
positive (by Proposition 8.21) matrix (In +A)n−1 . This implies that 1+ρ(A) = ρ(In +A) has
multiplicity 1 as an eigenvalue of In + A, and thus ρ(A) has multiplicity 1 as an eigenvalue
of A.

To generalize the last part of Perron’s theorem, we need yet another condition. A matrix
A ≥ 0 is called primitive if A is irreducible and ρ(A) is the unique eigenvalue of A with
modulus ρ(A). The same argument as in the proof of Lemma 8.16 proves the following:

Theorem 8.23. Suppose that A ≥ 0 is primitive. Let x > 0 and y > 0 satisfy Ax = ρ(A)x
and AT y = ρ(A)y be normalized so that kxk1 = 1 and hx, yi = 1. Then
 m
1
lim A = xy T .
m→∞ ρ(A)

Note that the existence of x and y as in the statement above is guaranteed by the
Perron–Frobenius theorem.
Since we have essentially made a hypothesis of one of the key conclusions of Perron’s
theorem here, it is desirable to have another characterization of primitivity. The following
is useful.

72
Proposition 8.24. A matrix A ≥ 0 is primitive if and only if Am > 0 for some m ∈ N.
1

m
Proof. Suppose that A is primitive. By Theorem 8.23, ρ(A) A → xy T , which is strictly
positive. Thus for some m, Am > 0.  
m −1 B C
Now suppose that A > 0. If we could write P AP = for some permutation
0 D
 m 
B ∗
matrix P , we would have P Am P −1 = , which is false; thus A is irreducible.
0 Dm
By Perron’s theorem (Theorem 8.10), ρ(Am ) = ρ(A)m is the unique eigenvalue of Am with
modulus ρ(A)m , with multiplicity 1. It follows that ρ(A) is the unique eigenvalue of A with
modulus ρ(A).

8.4 Stochastic matrices and Markov chains

A matrix P ∈ Mn (R) is called stochastic if P ≥ 0 and every row of P adds up to 1. (Note
that P is doubly stochastic if and only if both P and P T are stochastic.) We can state
the latter condition as P e = e, where e = (1, . . . , 1); this makes it easy to check that every
power of a stochastic matrix is again stochastic.
Stochastic matrices have a natural interpretation in terms of probability. Let Ω =
{x1 , . . . , xn } be some set with n elements, and fix a stochastic matrix P ∈ Mn (R). Then P
can be used to describe a Markov chain on Ω, that is, a sequence X0 , X1 , . . . of random
points in ΩPwith the property that if Xt = xi , then Xt+1 will be xj with probability pij . The
fact that nj=1 pij = 1 means that this completely describes the probability distribution
of Xt+1 given Xt . (The initial point X0 might be given explicitly, or it might be chosen
at random according to some probability distribution on Ω; we will return to this below.)
The matrix P is called the transition matrix of the Markov chain. A Markov chain is
typically thought of as a “random walk without memory”.
More generally, if we write P[A|B] for the probability that A is true, given that we know
B, then

P[Xt+s = xj |Xt = xi ]
Xn
= P[Xt+1 = xk1 |Xt = xi ]P[Xt+2 = xk2 |Xt+1 = xk1 ] · · · P[Xt+s = xj |Xt+s−1 = xks−1 ]
k1 ,...,ks−1 =1
X n
= pi,k1 pk1 ,k2 · · · pks−1 ,j = [P s ]i,j .
k1 ,...,ks−1 =1

Suppose that π ≥ 0 is an n-dimensional row vector with ni=1 πi = 1. Again, we can

P
state the latter condition as πe = 1. We can interpret π as a probability distribution on Ω:
πi is the probability of picking xi . Below we will always consider probability distributions
to be row vectors.
If P is a stochastic matrix, then πP ≥ 0, and (πP )e = π(P e) = πe = 1, so πP is again a
probability distribution. Specifically, it describes the distribution of X1 , if X0 is distributed
according to π. We call π a stationary distribution for P is πP = π.

Lemma 8.25. If P is a stochastic matrix, then P has a stationary distribution π.

73
Proof. By Lemma 8.3, ρ(P T ) = 1. Theorem 8.18 implies that P T has a nonnegative
eigenvalue y with P T y = y. By renormalizing if necessary we can set kyk1 = 1. Then
π = y T is a stationary distribution for P .

The following is the fundamental result about the convergence of Markov chains.

Theorem 8.26. If P is an irreducible stochastic matrix, then P has a unique stationary

distribution π, and π > 0. If P is moreover primitive, then for any probability distribution
µ,
lim µP t = π.
t→∞

The probabilistic interpretation of the convergence statement is the following: no matter

how the initial step X0 of a Markov chain with a primitive transition matrix is chosen, for
large t the distribution of Xt is approximately given by the stationary distribution π.

Proof. Note first that P is irreducible or primitive if and only if P is. By the Perron–
Frobenius theorem 8.22, P T has a unique eigenvector with eigenvalue 1 (up to scalar multi-
ples), which is moreover positive; its transpose is therefore the unique stationary distribution
π.
If P is also primitive, then Theorem 8.23 applies to A = P T with x = π T and y = eT ,
and implies that limt→∞ P t = eπ. It follows that if µ is any probability distribution, then

lim µP t = µ(eπ) = (µe)π = π.

t→∞

As a first example, consider simple random walk on the discrete circle: given n, let
Ω = {x1 , . . . , xn } consist of n equally spaced points on the unit circle. We consider the
stochastic matrix P with
(
1/2 if j = i ± 1, or if {i, j} = {1, n},
pij =
0 otherwise.

That is, the random walk moves either clockwise or counterclockwise one space, with equal
probability. It is easy to check that the uniform probability distribution π = n1 , . . . , n1 is

a stationary distribution for P ; in fact P is irreducible, and so the stationary distribution

is unique.
However, if n is even then P is not primitive, and the convergence in Theorem 8.26 does
not hold. For this reason, it is often convenient to consider the lazy version of the random
walk: 
1/2 if i = j,

pij = 1/4 if j = i ± 1, or if {i, j} = {1, n}, (10)

0 otherwise.


That is, the random walk stays put with probability 1/2; if it moves, it moves one step in
either direction with equal probability. The lazy random walk is irreducible and primitive,
so that the uniform distribution is its unique stationary distribution.
For a second example (which generalizes the first), consider a graph G = (V, E) consist-
ing of a set of vertices V = {x1 , . . . , xn } and edges connecting pairs of vertices. We write

74
xi ∼ xj if there is an edge connecting xi and xj . The degree of a vertex xi , written deg(xi )
is the number of vertices connected to xi . The simple random walk on G has transition
matrix (
1
if xi ∼ xj ,
pij = deg(xi ) (11)
0 otherwise.
Then
deg(xi )
πi = (12)
2#E
defines a stationary distribution for P . Again P is not necessarily primitive, but can be
modified to be primitive by making it “lazy”.
An important aspect of Markov chains is their “local” behavior: given Xt , picking Xt+1
only requires knowing pxt ,j for 1 ≤ j ≤ n. That is, you never need to use the entire matrix
P , and don’t need to know the entire matrix a priori. In the context of random walk on a
graph, for example, given a node Xt , to pick Xt+1 at random you only need to be able to
see which vertices are connected to Xt . Now if P is primitive, then by Theorem 8.26 we
know that for large t, the probability of being at xi ∈ Ω at a given step is approximately πi
— regardless of how the Markov chain was started.
This observation is the starting point of Markov chain Monte Carlo techniques: in order
to choose a random element from Ω according to a probability distribution π, you can run
a primitive Markov chain with stationary distribution π. Moreover, you can do this even
without complete knowledge of the transition matrix or of π itself.
To return to random walk on a graph, suppose we wish to estimate the number of edges
in G. Assuming the transition matrix is primitive, if we run random walk for a long time,
then
deg(xi )
P[Xt = xi ] ≈ .
2#E
Thus we can estimate
deg(xi )
#E ≈ ;
2P[Xt = xi ]
the right hand side of this can be estimated by observing just how often Xt turns out to be
a give xi .
A last example is furnished by the PageRank algorithm, made famous by its use as a
key component of Google’s search algorithm for the World Wide Web. We start with the
directed graph G = (V, E) whose vertices are all the web pages containing a given search
term, and with edges representing links from one page to another. The goal is to rank these
pages in some useful way. The basic idea is that useful pages are likely to be ones that are
linked to by many other useful pages. (Superficially this sounds circular, but it is really no
more so than an eigenvector problem — which, in fact, it is an example of.) This suggests
considering a random walk on G: the random walk is most likely to end up at these useful
pages. So the invariant measure π for the random walk should give a good measure of
usefulness.
The trouble with this basic idea is that there may be many dead ends in the directed
graph G, resulting in a reducible transition matrix. One simple way around this is to

75
add edges from each dead end to every other vertex. That is, we start with the modified
adjacency matrix A given by

1
 if xi → xj ,
aij = 1 if xi is a dead end, .

0 otherwise.


We then normalize the rows to get a transition matrix P :

aij
pij = Pn .
k=1 aik

There is still no guarantee that this transition matrix is primitive, so we modify it slightly
by setting Q = (1 − ε)P + nε J for some small ε > 0, where J is the matrix whose entries
are all 1. Probabilistically, this represents a Markov chain where, given Xt , the random
walker goes to a completely random page with probability ε; and otherwise choose a page
that Xt links to at random, assuming there are any; and otherwise again picks a completely
random page. Since Q > 0, Q is primitive. It therefore has a unique stationary distribution
π, which can be approximated by, say, eT1 Qm for large m. We rank web pages xi according
to the size of πi .
The last key observation is that eT1 Qm can be computed quickly in practice, even though
the size n = #V of the matrix is often huge. The point is that a given page typically has
a small number of links, but is also unlikely to have no links. Therefore P is a very sparse
matrix. On the other hand, J = eeT , so if µ is any probability distribution, then µJ = eT .
It follows that
ε
µQ = (1 − ε)µP + eT
n
can be computed very quickly, allowing eT1 Qm ≈ π to be quickly computed for large m.

8.5 Reversible Markov chains

A stochastic matrix P is called reversible with respect to a probability distribution π if

πi pij = πj pji (13)

for every i, j. The equation (13) is sometimes called the detailed balance equation.
Probabilistically, it says that if X0 is distributed according to π, then

P[X0 = xi and X1 = xj ] = P[X0 = xj and X1 = xi ].

Since P is stochastic, (13) implies that

n
X n
X
[πP ]j = πi pij = πj pji = πj ;
i=1 i=1

that is, πP = π, and so π is a stationary distribution for P . Note that if P is also

irreducible, then it has a unique stationary distribution by Theorem 8.26, and therefore it
can be reversible with respect to at most one probability distribution.

76
 For example,
if P is a symmetric stochastic matrix, then P is reversible with respect to
π = n1 , . . . , n1 . Also, for simple random walk on a graph, from (11) and (12) we have
(
1
if xi ∼ xj ,
πi pij = 2#E
0 otherwise,

which implies that (13) holds.

On the other hand, not every stochastic matrix is reversible with respect to its stationary
distribution. If ε ∈ (0, 1), the biased random walk on the discrete circle has the transition
matrix 
ε
 if j = i + 1 or i = n and j = 1,
pij = 1 − ε if j = i − 1 or i = 1 and j = n,

0 otherwise.


Then P is irreducible and has π = n1 , . . . , n1 as its unique stationary distribution, but if

ε 6= 1/2 then P is not symmetric, and so P is not reversible with respect to π.

Assuming that π > 0 (which, by Theorem 8.26, holds if P is irreducible), q (13)  equiv-
√ √ πi
alently says that if we define S = diag( π1 , . . . , πn ), then SP S −1 = πj pij is a
symmetric matrix. This observation implies the following.
Proposition 8.27. If P is the transition matrix for an irreducible Markov chain, then all
the eigenvalues of P are real.
The symmetry of SP S −1 of course implies more: SP S −1 is orthogonally diagonalizable.
We will see one way to exploit that fact in this context in the next section.

8.6 Convergence rates for Markov chains

Theorem 8.26 assures us that if P is a primitive stochastic matrix with stationary distri-
m→∞
bution π, then µP t −−−−→ π for any probability distribution µ. A potentially important
question for applications is: how fast does this convergence happen?
That is, we would like to bound µP t − π , as a function of t, for some norm k·k. We
note first that it suffices to consider µ = eTi for i = 1, . . . , n (probabilistically: to assume
that X0 = xi with probability 1 for some i):
n
X n
X
t
µi eTi P t µi eTi P t − π ≤ max eTi P t − π .


µP − π = −π ≤
1≤i≤n
i=1 i=1

Note that [eTi P t ]j = P[Xt = xj |X0 = xi ].

For the purposes of probability theory, one particularly natural choice is the `1 norm
(for reasons that will be explored in the homework). But as we know well, it is frequently
easier to work with quantities related to `2 norms. Given two probability distributions µ
and π with π > 0, we define the χ2 distance by
n  n
2 X
2
X µi 1
χ (µ, π) = πi −1 = (µi − πi )2 .
πi πi
i=1 i=1

77
 √ √
If S = diag( π1 , . . . , πn ) as in the previous section, then
2
χ2 (µ, π) = (µi − πi )S −1 2
. (14)
Note that χ2 (µ, π) 6= χ2 (π, µ) in general.
Lemma 8.28. If µ and π are probability distributions with π > 0, then
p
kµ − πk1 ≤ χ2 (µ, π).
Proof. By the Cauchy–Schwarz inequality,
n n r
X X 1 √
kµ − πk1 = |µi − πi | = |µi − πi | πi
πi
i=1 i=1
v v
u n u n
uX 1 uX p
≤t (µi − πi )2 t πi = χ2 (µ, π).
πi
i=1 i=1

The following is a basic example of how the rate of convergence of a Markov chain can
be bounded using spectral information.
Theorem 8.29. Suppose that P is a primitive stochastic matrix which is reversible with
respect to π. Let C = maxλ∈σ(P )\{1} |λ| and κ = min1≤i≤n πi . Then C < 1, and for each
i = 1, . . . , n and each t ∈ N, we have
1 2t 1
χ2 (eTi P t , π) ≤ C and eTi P t − π 1
≤ √ C t.
κ κ
Theorem 8.29 shows that, under these hypotheses, eTi P t converges exponentially quickly
to π. One commonly used (but rather arbitrary) way state such a result is in terms of the
mixing time, defined as the smallest τ such that eTi P t − µ 1 ≤ 1/2 for all t ≥ τ . Theorem
√
log( κ/2)
8.29 implies in particular that the mixing time is at most log C .

Proof. Since P is primitive and stochastic, ρ(P ) = 1 and C < 1 by the definition of
primitive.
√ √
Since P is reversible with respect to π, if S = diag( π1 , . . . , πn ), then A = SP S −1 is
real symmetric. We also have πP = π, so that A(πS −1 )T = (πS −1 )T ; note that πS −1 =
√ √
( π1 , . . . , πn ) is a unit vector. Then by the spectral theorem A = U ΛU T for an orthogonal
U ∈ Mn (R) and Λ = diag(1, λ2 , . . . , λn ), with |λj | ≤ C for 2 ≤ j ≤ n, and we can take
the first column of U to be (πS −1 )T . That is, U e1 = (πS −1 )T , so eT1 U T = πS −1 , and thus
πS −1 U = eT1 .
We now have
2 2 2
χ2 (eTi P t , π) = (eTi P t − π)S −1 2
= (eTi − π)P t S −1 2
= (eTi − π)S −1 At 2
2 2
= (eTi − π)S −1 U Λt U T 2 = (eTi − π)S −1
U Λt 2
n
X  T −1 2
= (ei S U − eT1 )λtj ej
j=1
n

X 2
= eTi S −1 U e1 − 1 +
 T −1
ei S U ej λtj
j=2

78
Now S −1 U e1 = S −2 π T = e, so eTi S −1 U e1 = 1. Using this and the definition of S,
n
1 X T 2 C 2t T 2 C 2t
χ2 (eTi P t , π) = ei U ej λ2t
j ≤ ei U 2
= .
πi κ κ
j=2

Finally, the `1 bound follows from the χ2 bound via Lemma 8.28.

We illustrate this result with the example of the lazy random walk on the discrete circle,
with transition matrix given by (10).
This transition matrix is an example of a circulant matrix, so we can compute its
eigenvalues and eigenvectors explicitly: for k = 0, 1, . . . , n − 1, the vector vk ∈ Cn with
entries [vk ]j = e2πijk/n is an eigenvector with eigenvalue
 
1 1 2πik/n 1 −2πik/n 1 2πk
λk = + e + e = 1 + cos .
2 4 4 2 n
Then λ0 = 1 is the trivial eigenvalue that we already know about. The others are all
between 0 and 1 with the largest being when k = 1 or n − 1. So here we can apply Theorem
8.29 with κ = n1 and  
1 2π
C= 1 + cos .
2 n
To be a bit more explicit, by Taylor’s theorem with a remainder,
x2 1 3
cos x ≤ 1 − + x ,
2 6
2π
so if, say, n ≥ 7 (so that n < 1), then
4π 2
C ≤1− .
6n2
Theorem 8.29 now implies that
t
√ 4π 2

eTi P t −π 1
≤ n 1− 2 .
6n
As you will see in homework, it’s possible to do much better in this example, in particular
because we can identify all the eigenvalues explicitly.

9 Spectral graph theory

9.1 Eigenvalues of the adjacency matrix
In this final section we will see some examples of how properties of graphs are related to
eigenvalues of matrices related to the graph. We will focus first on the adjacency matrix.
Given a (simple, undirected) graph G = (V, E) with V = {x1 , . . . , xn }, the adjacency
matrix A ∈ Mn (R) is given by
(
1 if xi ∼ xj ,
aij =
0 otherwise.

79
Note that A is both symmetric and nonnegative.
Before considering eigenvalues explicitly, let’s see how some basic information about G
can be extracted from A. Of course, A contains all the information about G; the point
here is that we want to relate graph-theoretic information about G to matrix-theoretic
information about A.
We first need a little terminology. A graph G = (V, E) is disconnected if V = V1 ∪ V2
with V1 , V2 6= ∅ and whenever v1 ∈ V1 and v2 ∈ V2 , we have v1 6∼ v2 . A graph is connected
if it is not disconnected.

Lemma 9.1. A graph is connected if and only if its adjacency matrix is irreducible.

The proof of Lemma 9.1 is an exercise in remembering the definition of irreducibility.

A triangle in G is a set of three distinct vertices v1 , v2 , v3 such that v1 ∼ v2 , v2 ∼ v3 ,
and v3 ∼ v1 .

Proposition 9.2. Let G = (V, E) be a graph with adjacency matrix A. Then tr A2 = 2#E
and tr A3 is 6 times the number of triangles in G.

Proof. Since A is real symmetric,

n
X
tr A2 = a2ij = # {(i, j) | xi ∼ xj } = 2#E,
i,j=1

since the set above counts each edge twice. Similarly,

n
X
tr A3 = aij ajk aki = # {(i, j, k) | xi ∼ xj , xj ∼ xk , xk ∼ xi } .
i,j,k=1

Each triangle is counted in this set 6 times.

PnNote that although Proposition 9.2 does not mention eigenvalues explicitly, tr Ak =
k
i=1 λi (A) for each k.
We next observe which facts can be deduced with little or no extra effort from results
we know about nonnegative matrices or about real symmetric matrices.
The degree of a vertex in G is the corresponding row sum of A:
n
X
deg(xi ) = aij .
j=1

We denote by

δ(G) = min deg(xi ) and ∆(G) = max deg(xi )

1≤i≤n 1≤i≤n

the minimal and maximal degrees of G.

Theorem 8.4 immediately implies the following.

Proposition 9.3. If A is the adjacency matrix of a graph G, then δ(G) ≤ ρ(A) ≤ ∆(G).

80
 From the Rayleigh–Ritz theorem (Theorem 3.1) we can further deduce the following
refinement of Proposition 9.3.

Proposition 9.4. If A is the adjacency matrix of a graph G with vertices V = {x1 , . . . , xn },

then n1 ni=1 deg(xi ) ≤ λmax (A) ≤ ∆(G).
P

Proof. The upper bound follows from Proposition 9.3. The lower bound follows by applying
the Theorem 3.1 with x = e:
Pn n
hAe, ei i,j=1 aij 1X
λmax (A) ≥ = = deg(xi ).
kek2 n n
i=1

A graph G is called regular if δ(G) = ∆(G).

Proposition 9.5. Suppose G is connected. Then ∆ = ∆(G) is an eigenvalue of A if and

only if G is regular.

Proof. If G is regular with degree ∆, then Ae = ∆e. (Note that this implication does not
need connectedness.)
Now suppose that ∆ is an eigenvalue of A. By Proposition 9.3, ρ(A) = ∆. Since G is
connected, A is irreducible by Lemma 9.1, so the Perron–Frobenius theorem applies. If y is
the Perron eigenvector of A, then we have Ay = ∆y. Adding the components of this vector,
we obtain
n n Xn n n n
!
X X X X X
∆= ∆yi = aij yj = aij yj = deg(xj )yj ,
i=1 i=1 j=1 j=1 i=1 j=1

and so nj=1 (∆ − deg(xj ))yj = 0. Since each term of this sum is nonnegative, we must have
P
∆ = deg(xj ) for each j.

We will present one more substantial example result about the eigenvalues of the adja-
cency matrix. The chromatic number of a graph G = (V, E), denoted χ(G), is the minimal
number k of subsets in a partition V = V1 ∪ · · · ∪ Vk such that each edge in G connects
vertices in two different subsets Vi . Such a partition is called a k-coloring of G, which
accounts for the term “chromatic number”.
In the following, note that tr A = 0, so λmin (A) < 0.

Theorem 9.6. If G is a graph with at least one edge and adjacency matrix A, then

λmax (A)
1+ ≤ χ(G) ≤ 1 + λmax (A).
−λmin (A)

Proof. We begin with the upper bound. We first put the vertices of G in a convenient order.
By Proposition 9.4, G has at least one vertex with degree at most λmax (A); we choose
one and designate it vn . We now consider the graph Gn−1 with vertex set V \ {vn } and
every edge in G which does not connect to vn . Its adjacency matrix An−1 is a submatrix of
A, and therefore λmax (An−1 ) ≤ λmax (A). Proposition 9.4 now implies that Gn−1 contains
a vertex vn−1 of degree (in Gn−1 ) at most λmax (A).

81
 Continuing in this way, we get an ordering v1 , . . . , vn of the vertices of G such that each
vj is connected to at most λmax (A) of the vertices vi with i < j. We can then assign colors
to the vertices in order, making sure always to give each vertex a color shared by none of
its neighbors, and using at most 1 + λmax (A) colors.
Now suppose that G has a k-coloring with color classes V1 , . . . , Vk . For each 1 ≤ m ≤ k,
let Um be the subspace of Rn spanned by {ei | xi ∈ Vm }. By assumption, if xi , xj ∈ Vm , we
have xi 6∼ xj , and therefore aij = hAej , ei i = 0. It follows that hAu, ui = 0 for any u ∈ Um
and any m.
Now let Py = (y1 , . . . , yn ) ∈ Rn be an eigenvector of P
A with eigenvalue λmax = λmax (A).
k
Let ym = y
xi ∈Vm i ie , so that y m ∈ U m and y = m=1 ym . Write ym = cm um for
cm = kym k2 and um ∈ Um a unit vector (note ym may be 0). Extend u1 , . . . , uk to an
orthonormal basis of Rn and let U be the orthogonal matrix with columns ui . Then the
k × k upper left submatrix of U ∗ AU is S ∗ AS, where S ∈ Mn,k has columns u1 , . . . , uk . By
the Cauchy interlacing principle (Theorem 3.11), λmin (S ∗ AS) ≥ λmin (U ∗ AU ) = λmin (A),
and λmax (S ∗ AS) ≤ λmax (A) similarly. Furthermore
   
c1 c1
∗  ..  ∗ ∗  .. 
S AS  .  = S Ay = λmax (A)S y = λmax (A)  .  ,
ck ck

so in fact λmax (S ∗ AS) = λmax (A).

Also, for each 1 ≤ i ≤ k, hS ∗ ASei , ei i = hAui , ui i = 0, so tr S ∗ AS = 0. It follows that
k k
λ↓i (S ∗ AS) ≥ λmax (A) + (k − 1)λmin (A),
X X
∗
0= λi (S AS) = λmax (A) +
i=1 i=2

λmax (A)
which implies (since λmin (A) < 0 as noted above) that k ≥ 1 + −λmin (A) .

We end this section by remarking that the practical significance of a result like Theorem
9.6 is that the chromatic number of a graph is computationally expensive to compute ex-
actly, but there are efficient algorithms to approximate extremal eigenvalues of a symmetric
matrix. Theorem 9.6 furnishes relatively easy-to-compute upper and lower bounds on an
important quantity which is hard to find directly.

9.2 The graph Laplacian

Let G = (V, E) be a graph with V = {x1 , . . . , xn } as above, and let A be the adjacency
matrix of G. Define D = diag(deg(x1 ), . . . , deg(xn )). The (nonnormalized or combina-
torial) Laplacian matrix of G is the matrix L = D − A.
If G is regular, then D = ∆In , and the eigenvalues of L are just ∆ − λj (A); in that case
the Laplacian is essentially an equivalent tool to the adjacency matrix. For non-regular
graphs, however, the Laplacian and its variations turn out to play a more important role
in applications than the adjacency matrix.
We can see that L is positive semidefinite using Geršgorin’s theorem (as in Exercise 3
from the March 27 homework). Moreover, Le = De − Ae = 0, so L is not positive definite.
Alternatively, we can observe these facts from the following perspective on the quadratic

82
form associated with L. Here we choose to write a vector in Rn as f , associating it with a
function f : G → R given by f (xi ) = fi . We have
n
X n
X X
hLf, f i = (δij deg(xi ) − aij )fi fj = deg(xi )fi2 − fi fj
i,j=1 i=1 i,j:xi ∼xj
(15)
1 X X
= (fi2 2
− 2fi fj + fj ) = 2
(fi − fj ) .
2
i,j:xi ∼xj {xi ,xj }∈E

It follows immediately from (15) that hLf, f i ≥ 0, and that hLf, f i = 0 whenever f is
constant. In fact, (15) implies that hLf, f i = 0 if and only if f is constant on each connected
component of G, and thus:

Proposition 9.7. The multiplicity of 0 as an eigenvalue of L is equal to the number of

connected components of G.

The Laplacian
P gets its name because it is analogous in certain ways to the Laplacian
∂2
operator ∆ = ni=1 ∂x n
2 for smooth functions on R , and its generalizations to Riemannian
i
manifolds. For instance, multivariable integration by parts implies that if f : Rn → R is a
smooth function which decays sufficiently quickly, then
Z Z
k∇f (x)k22 dx,


∆f (x) f (x) dx = −
Rn Rn

which (up to the minus sign — L is actually analogous to −∆) is formally similar to (15).
For the remainder of this section we will write λ1 ≤ · · · ≤ λn for the eigenvalues of L.
Proposition 9.7 implies that λ1 = 0 always, and that λ2 > 0 if and only if G is connected.
When G is connected, λ2 can be used to quantify how difficult it is to cut G into pieces.
We will need the following lemma.

Lemma 9.8. If L is the Laplacian of a graph, then

( )
hLf, f i
λ2 = min f 6= 0 and hf, ei = 0 .
kf k22

This can be proved either using the Courant–Fischer theorem, or directly from the
spectral theorem by the same method as the Courant–Fischer theorem; the key point is
that e is an eigenvector associated to λ1 = 0.
Given a graph G = (V, E) and a subset S ⊆ V , the cut associated to S is the set ∂S ⊆ E
of all edges in G with one end in S and the other end in V \ S. In the following result, we
use |X| to denote the cardinality of a set X.

Theorem 9.9. Let G = (V, E) be a graph. For any S ⊂ V , we have

|S| |V \ S|
|∂S| ≥ λ2 .
|V |

83
Proof. Let k = |S|, n = |V |, and define f ∈ Rn by
(
n − k if xi ∈ S,
fi =
−k if xi ∈ V \ S.

Then hf, ei = 0 and kf k22 = kn(n − k). By (15) we have

hLf, f i = n2 |∂S| .

Lemma 9.8 then implies that

hLf, f i n |∂U |
λ2 ≤ 2 = k(n − k) .
kf k2
Many algorithmic problems can be put in the framework of finding cuts which are
“efficient” in some sense. Theorem 9.9 says that λ2 bounds how well this can be done. In
particular, given any way of dividing V into two subsets of roughly comparable size, there
are on the order of λ2 |V | edges between them.
Moreover, the proof of Theorem 9.9 suggests a strategy for finding cuts with few edges:
divide V into two subsets according to the signs of entries of a vector which achieves (or
comes close to achieving) the minimum in Lemma 9.8. That is, using an eigenvector of L
with eigenvalue λ2 . This turns out to be almost but not quite the right idea (except in
the case when G is regular). In general, we first need to replace L with a slightly different
notion of Laplacian.
The matrix
L = D−1/2 LD−1/2 = In − D−1/2 AD−1/2
is called the normalized or analytic Laplacian of G. (We will assume for convenience
that G has no isolated vertices, that is, no vertices with degree 0, but the definition can be
modified easily to handle that case.) We will write µ1 ≤ · · · ≤ µn for the eigenvalues of L.
Note that D1/2 e ∈ ker L, so µ1 = 0.
Lemma 9.10. If L is the normalized Laplacian of a graph G = (V, E), then
(P 2
)
{x1 ,x2 }∈E (fi − fj )
µ2 = min Pn 2 6 0 and hf, Dei = 0 .
f=
i=1 fi deg(xi )

Proof. As with Lemma 9.8, we have

( )
hLg, gi D E
µ2 = min g 6= 0 and g, D1/2 e = 0 .
kgk22

By the definition of L and (15), if we substitute f = D−1/2 g,

2
P
hLg, gi LD−1/2 g, D−1/2 g hLf, f i {x1 ,x2 }∈E (fi − fj )
= = = n .
kgk22 kgk22 2 2
P
D1/2 f 2 i=1 fi deg(xi )

Finally, g, D1/2 e = hf, Dei.

84
 The volume of a subset S ⊆ V of the set of vertices of a graph is
X
vol(S) = deg(xi ).
xi ∈S

Using this notion of the size of a set of vertices, we have the following analogue of Theorem
9.9.
Theorem 9.11. Let G = (V, E) be a graph. For any S ⊂ V , we have
min{vol(S), vol(V \ S)}
|∂S| ≥ µ2 .
2
Proof. Define f ∈ Rn by (
1
vol(S) if xi ∈ S,
fi =
− vol(V1 \S) if xi ∈ V \ S.
Then
n
X
hf, Dei = fi deg(xi ) = 0,
i=1
n
X 1 1
fi2 deg(xi ) = + ,
vol(S) vol(V \ S)
i=1
and  2
X
2 1 1
(fi − fj ) = + |∂S| .
vol(S) vol(V \ S)
{x1 ,x2 }∈E

Lemma 9.10 then implies that

 
1 1
µ2 ≤ + |∂S|
vol(S) vol(V \ S)
which proves the claim.

The following can be viewed as a partial converse to Theorem 9.11.

Theorem 9.12 (Cheeger’s inequality). There exists a S ⊆ V such that
|∂S| p
≤ 2µ2 .
vol(S) vol(V \ S)
In fact one proof of Theorem 9.11 (omitted here) gives a construction for a good S
which is much more computationally feasible than an exhaustive search through subsets of
V . Namely, let f be an eigenvector of L with eigenvalue µ2 . Order V = {v1 , . . . , vn } so
that f (vi ) is nondecreasing in i, and let Si = {v1 , . . . , vi }. Then it can be shown that
|∂Si | p
min ≤ 2µ2 .
1≤i≤n vol(Si ) vol(V \ Si )

Thus a near-optimal S can be found by solving an eigenvector problem for L and then
checking n subsets of V , as opposed to the obvious brute-force approach of trying 2n subsets
of V .

85