42 1. Preparatory material

1.3.2. Minimax formulae. The

ith

eigenvalue functional A → λi(A) is

not a linear functional (except in dimension one). It is not even a convex

functional (except when i = 1) or a concave functional (except when i = n).

However, it is the next best thing, namely it is a minimax expression of

linear

functionals13.

More precisely, we have

Theorem 1.3.2 (Courant-Fischer minimax theorem). Let A be an n × n

Hermitian matrix. Then we have

(1.57) λi(A) = sup

dim(V )=i

inf

v∈V :|v|=1

v∗Av

and

(1.58) λi(A) = inf

dim(V )=n−i+1

sup

v∈V :|v|=1

v∗Av

for all 1 ≤ i ≤ n, where V ranges over all subspaces of

Cn

with the indicated

dimension.

Proof. It suﬃces to prove (1.57), as (1.58) follows by replacing A by −A

(noting that λi(−A) = −λn−i+1(A)).

We first verify the i = 1 case, i.e., (1.53). By the spectral theorem, we

can assume that A has the standard eigenbasis e1,...,en, in which case we

have

(1.59)

v∗Av

=

n

i=1

λi|vi|2

whenever v = (v1,...,vn). The claim (1.53) is then easily verified.

To prove the general case, we may again assume A has the standard

eigenbasis. By considering the space V spanned by e1,...,ei, we easily see

the inequality

λi(A) ≤ sup

dim(V )=i

inf

v∈V :|v|=1

v∗Av,

so we only need to prove the reverse inequality. In other words, for every

i-dimensional subspace V of

Cn,

we have to show that V contains a unit

vector v such that

v∗Av

≤ λi(A).

Let W be the space spanned by ei,...,en. This space has codimension i−1,

so it must have non-trivial intersection with V . If we let v be a unit vector

in V ∩ W , the claim then follows from (1.59).

13Note that a convex functional is the same thing as a max of linear functionals, while a

concave functional is the same thing as a min of linear functionals.