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 suffices 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.
Previous Page Next Page