Filetype PDF | Posted on 27 Jan 2023 | 3 years ago
Authentication
digital resources
268x Filetype PDF File size 0.10 MB Source: www.math.uh.edu
Matrix Theory, Math6304
Lecture Notes from October 11, 2012
taken by Da Zheng
4 Variational characterization of eigenvalues, continued
Werecall from last class that given a Hermitian matrix, we can obtain its largest (resp. smallest)
eigenvalue by maximizing (resp. minimizing) the corresponding quadratic form over all the unit
vectors. In fact, due to the following theorem by Courant and Fischer, we can obtain any
eigenvalue of a Hermitian matrix through the ”min-max” or ”max-min” formula.
4.2 The Courant-Fischer Theorem
4.2.1 Theorem (Courant-Fischer). Suppose A ∈ Mn is Hermitian, and for each 1 ≤ k ≤ n,
α n
let {S }α∈I denote the set of all k−dimensional linear subspaces of C . Also, enumerate the n
k k
eigenvalues λ ,··· ,λ (counting multiplicity) in increasing order, i.e. λ ≤ ··· ≤ λ . Then, we
1 n 1 n
have
(i).
min max hAx,xi =λ ,
α∈I x∈Sα\{0} kxk2 k
k k
(ii).
max min hAx,xi = λ .
α∈I x∈Sα \{0} 2 k
n−k+1 n−k+1 kxk
Before starting the proof, we denote an or u ,··· ,u , which is orhonormal, as the eigenvectors
1 n
of A corresponding to λ ,··· ,λ respectively. .
1 n
Proof. (i). First, let W = span{u ,··· ,u }, then dimW = n−k+1. So, for any k−dimensional
1 n
subspace Sα, we should have dim(Sα∩W) ≥ 1. This is because of the equality: dim(Sα+W) =
k k k
dimSα+dimW −dim(Sα∩W), and of course dim(Sα+W)≤n.
k k k
P
Now, choose x ∈ Sα ∩ W \ {0}, note that x = n hx,u iu and Au = u , then it
k j=k j j j j
follows that
hAx,xi Pn λhx,u iu ,x
= j=k j j j
2 2
kxk kxk
1
Pn λhx,u ihu ,xi
j=k j j j
= 2
Pn kxk 2
λ |hx,u i|
= j=k j j
2
Pnkxk 2
|hx,u i|
≥λ j=k j
k kxk2
=λ .
k
Here, we use the fact that λ ≤ λ ≤··· ≤ λ and kxk2 = Pn |hx,u i|2.
k k+1 n j=k j
Thus, for any Sα,
k
sup hAx,xi ≥ λ .
2 k
x∈Sα\{0} kxk
k
Indeed, for any Sα, it is easy to check that
k
sup hAx,xi = sup hAx,xi,
α 2 α
x∈S \{0} kxk x∈S ,kxk=1
k k
and since {x ∈ Sα : kxk = 1} is compact, supremum is attained. So we have
k
max hAx,xi = sup hAx,xi ≥λ .
α 2 2 k
x∈Sk\{0} kxk x∈Sα\{0} kxk
k
On the other hand, consider a particular k−dimensional subspace Sα = span{u ,··· ,u },
k 1 k
then
hAx,xi Pk λ|hx,u i|2
= j=1 j j ≤λ .
2 2 k
kxk kxk
Hence, choosing x = u , we obtain max α hAx,xi = λ .
k x∈S \{0} 2 k
k kxk hAx,xi
This also implies that the minimum of max α over all α ∈ I is also attained, and
x∈S \{0} 2 k
we conclude that k kxk
min max hAx,xi =λ .
α∈I x∈Sα\{0} kxk2 k
k k
(ii). The proof of this formula follows from the same idea as (i), and we shall omit the similar
details. We first choose W = span{u ,··· ,u }, so dimW = k. Then, for any subspace Sα ,
1 k n−k+1
dim(Sα ∩W)≥1.
k
Next, choose any x ∈ Sα ∩W \{0}, hAx,xi ≤ λ , and therefore
n−k+1 2 k
kxk
min hAx,xi ≤ λ .
x∈Sα \{0} 2 k
n−k+1 kxk
Now, we again choose a particular S =span{u ,··· ,u }, and this gives
n−k+1 k n
min hAx,xi = λ .
x∈Sα \{0} 2 k
n−k+1 kxk
2
So finally we conclude that
max min hAx,xi = λ .
α∈I x∈Sα \{0} 2 k
n−k+1 n−k+1 kxk
4.2.2 Remark. We can compare this result with theorem 4.2.11 in Horn and Johnson’s ”Matrix
Analysis”, which uses vectors to prove the ”min-max” and ”max-min” formulae, but the idea is
essentially the same.
4.3 Eigenvalue estimates for sums of matrices
Next, we shall introduce several theorems and corollaries that can be considered as consequences
of the Courant-Fischer’s theorem. The first theorem, by Weyl, allows us to obtain a lower and
upper bound for the kth eigenvalue of A + B.
n n
4.3.3 Theorem (Weyl). Let A,B ∈ M be both Hermitian, and {λ (A)} , {λ (B)} and
n j j=1 j j=1
{λ (A+B)}n denotethesetsofeigenvaluesofA,B,andA+B inincreasingorder,respectively.
j j=1
Then, for any 1 ≤ k ≤ n,
λ (A)+λ (B)≤λ (A+B)≤λ (A)+λ (B).
k 1 k k n
Notice that by symmetry, we naturally also have
λ (B)+λ (A)≤λ (A+B)≤λ (B)+λ (A).
k 1 k k n
Proof. By Rayleigh-Ritz’s theorem, we know that
λ (B) ≤ hBx,xi ≤ λ (B), for x 6= 0.
1 2 n
kxk
Then, by Courant-Fischer’s theorem, for any 1 ≤ k ≤ n,
λ (A+B)=min max h(A+B)x,xi
k α∈I x∈Sα\{0} 2
k k kxk
=min max hAx,xi + hBx,xi
α∈I x∈Sα\{0} 2 2
k k kxk kxk
≥min max hAx,xi +λ (B)
α∈I x∈Sα\{0} 2 1
k k kxk
=λ(B)+min max hAx,xi
1 α∈I x∈Sα\{0} 2
k k kxk
=λ (A)+λ (B).
k 1
For the other inequality, we apply similar argument and immediately obtain λ (A + B) ≤
k
λ (A)+λ (B), and the proof is finished here.
k n
3
4.3.4 Remark. It is interesting to mention that for some special B, both lower and upper bounds
can be attained in the above theorem we have just proved. For example, let {u ,··· ,u } be
1 n
the orthonormal set of eigenvectors of A with Au = λ u for 1 ≤ k ≤ n, and consider
k k k
the rank one projection B = auku∗, where a > 0 or a < 0. Then, A = UDU∗, where
k
D=diag{λ ,··· ,λ }, and we can assume that λ ,··· ,λ is listed in increasing order. Also,
1 n 1 n
it is easy to see that B = UD′U∗, where D′ = diag{0,··· ,0,a,0,··· ,0} (a appears in the
kth place). Then, we immediately have λ (A + B) = λ (A) + λ (B) = λ (A) + a if a > 0;
k k n k
λ (A+B)=λ (A)+λ (B)=λ (A)+a if a<0.
k k 1 k
The following corollary is called the monotonicity theorem, which refines the lower bound in
Weyl’s theorem by assuming B is positive semidefinite.
4.3.5 Definition. B ∈ M is called positive semidefinite, if it is Hermitian and hBx,xi ≥ 0 for
n
n
all x ∈ C .
n
Notice that hBx,xi ≥ 0 for all x ∈ C indeed implies that B is Hermitian. However, for the
real case, we have to impose that B is symmetric.
4.3.6 Corollary (Weyl). Adopt all the assumptions and notations in the above Weyl’s theorem,
if we further that suppose B is positive semideifnite, then
λ (A) ≤ λ (A+B), for all 1 ≤ k ≤ n.
k k
Proof. Since B is positive semidefinite, λ (B) ≥ 0 for all 1 ≤ j ≤ n, so the corollary follows
j
from Weyl’s theorem directly.
The following theorem discusses the relationship between eigenvalues of a Hermitian matrix
and those of the rank one perturbation of it, which is called the interlacing theorem. This is still
an application of Courant-Fischer’s theorem.
n ∗
4.3.7 Theorem. Let A ∈ M be Hermitian, z ∈ C , {λ (A)} and {λ (A ± zz )} be both in
n j j
increasing order, then
(i).
λ (A±zz∗)≤λ (A) ≤ λ (A±zz∗), for 1 ≤ k ≤ n −2,
k k+1 k+2
(ii).
λ (A) ≤ λ (A±zz∗)≤λ (A), for 1≤k≤n−2.
k k+1 k+2
endsection
Proof. By Courant-Fischer’s theorem,
λ (A±zz∗)=min max h(A±zz∗)x,xi
k+2 α∈I x∈Sα \{0} kxk2
k k+2
2
=min max hAx,xi ± |hx,zi|
α∈I x∈Sα \{0} 2 2
k k+2 kxk kxk
≥min max hAx,xi (∗)
α∈I x∈Sα \{0} 2
k k+2 kxk
x⊥z
4
no reviews yet
Please Login to review.
