Kenneth Kuttler

6.11. CAUCHY’S INTERLACING THEOREM FOR EIGENVALUES 187

= (λ− a)

3∏i=1

(λ− µ̂i)−

(|z1|2 (λ− µ̂2) (λ− µ̂3) + |z2|2 (λ− µ̂1) (λ− µ̂3)

+ |z3|2 (λ− µ̂1) (λ− µ̂2)

)Notice how, when you expand the 3× 3 determinants along the first column, you have onlyone non-zero term and the sign is adjusted to give the above claim. Clearly, it works thesame for any size matrix. Since the µ̂i are strictly increasing in i, it follows from 6.27 thatq (µ̂i) q

(µ̂i+1

)≤ 0. However, since each |zi| ̸= 0, none of the q (µ̂i) can equal 0 and so

q (µ̂i) q(µ̂i+1

)< 0. Hence, from the intermediate value theorem of calculus, there is a root

of q (λ) in each of the disjoint open intervals(µ̂i, µ̂i+1

). There are n − 2 of these intervals

and so this accounts for n− 2 roots of q (λ).

q (λ) = (λ− a)

n−1∏i=1

(λ− µ̂i)−n−1∑i=2

|zi|2 (λ− µ̂1) · · · ̂(λ− µ̂i) · · ·(λ− µ̂n−1

)What of q (µ̂1)? Its sign is the same as (−1)

n−3and also q

(µ̂n−1

)< 0 . Therefore, there

is a root to q (λ) which is larger than µ̂n−1. Indeed, limλ→∞ q (λ) = ∞ so there exists aroot of q (λ) strictly larger than µ̂n−1. This accounts for n− 1 roots of q (λ) . Now considerq (µ̂1) . Suppose first that n is odd. Then you have q (µ̂1) > 0. Hence, there is a root ofq (λ) which is no larger than µ̂1 because in this case, limλ→−∞ q (λ) = −∞. If n is even,then q (µ̂1) < 0 and so there is a root of q (λ) which is smaller than µ̂1 because in this case,limλ→−∞ q (λ) = ∞. This accounts for all roots of q (λ). Hence, if the roots of q (λ) areλ1 ≤ λ2 ≤ · · · ≤ λn, it follows that

λ1 < µ̂1 < λ2 < µ̂2 < · · · < µ̂n−1 < λn

To get the complete result, simply take the limit as k → ∞. Then limk→∞ µ̂k = µk andAk → A and so the eigenvalues of Ak converge to the corresponding eigenvalues of A (SeeProblem 47 on Page 184), and so, passing to the limit, gives the desired result in which itmay be necessary to replace < with ≤. ■

Definition 6.11.2 Let A be an n × n matrix. An (n− r) × (n− r) matrix is called aprincipal submatrix of A if it is obtained by deleting from A the rows i1, i2, · · · , ir and thecolumns i1, i2, · · · , ir.

Now the Cauchy interlacing theorem is really the following corollary.

Corollary 6.11.3 Let A be an n × n Hermitian matrix and let B be an (n− 1) × (n− 1)principal submatrix. Then the interlacing inequality holds λ1 ≤ µ1 ≤ λ2 ≤ µ2 ≤ · · · ≤µn−1 ≤ λn where the µi are the eigenvalues of B listed in increasing order and the λi arethe eigenvalues of A listed in increasing order.

Proof: Suppose B is obtained from A by deleting the ith row and the ith column. Thenlet P be the permutation matrix which switches the ith row with the first row. It is anorthogonal matrix and so its inverse is its transpose. The transpose switches the ith column

with the first column. See Problem 33 on Page 128. Thus PAPT =

(a y∗

y B

)and it

follows that the result of the multiplication is indeed as shown, a Hermitian matrix becauseP, PT are orthogonal matrices. Now the conclusion of the corollary follows from Theorem6.11.1. ■

6.11. CAUCHY’S INTERLACING THEOREM FOR EIGENVALUES 187~(\-a — 2. la? (= fig) (A= tg) + 22]? (A = ty) C= fig)ater aes ( + |23|° (A= fy) (A — fg)Notice how, when you expand the 3 x 3 determinants along the first column, you have onlyone non-zero term and the sign is adjusted to give the above claim. Clearly, it works thesame for any size matrix. Since the fi, are strictly increasing in 7, it follows from 6.27 thatq(ft;) @ (fin1) < 0. However, since each |z;| 4 0, none of the q (ji;) can equal 0 and soqa (ft;) @ (fi41) < 0. Hence, from the intermediate value theorem of calculus, there is a rootof q(A) in each of the disjoint open intervals (ji;, /4;,,). There are n — 2 of these intervalsand so this accounts for n — 2 roots of q (A).i=1n—-1g(a) = (A-a) J] ( A — jt;) -Sat (A = fy) (A= fiz) + (A= fin-1)i=lWhat of q(ji,)? Its sign is the same as (—1)""° and also q (fn—-1) <0. Therefore, thereis a root to q(A) which is larger than j,,_,. Indeed, lim,-,.. g(A) = co so there exists aroot of qg(A) strictly larger than ji,,_,. This accounts for n — 1 roots of g (A). Now considerq (jt;). Suppose first that n is odd. Then you have q(ji,) > 0. Hence, there is a root ofq(A) which is no larger than ji, because in this case, lim,_,-. q(A) = —oo. If n is even,then gq (ji,) < 0 and so there is a root of q(A) which is smaller than fj, because in this case,lim). g(A) = oo. This accounts for all roots of g(A). Hence, if the roots of g(A) areAy < Ag < +++ < Ang, it follows thatMt < fly < AQ < flg < +++ < fly < AnTo get the complete result, simply take the limit as k — oo. Then limz.0 ft, = pj, andA; — A and so the eigenvalues of A; converge to the corresponding eigenvalues of A (SeeProblem 47 on Page 184), and so, passing to the limit, gives the desired result in which itmay be necessary to replace < with <. HfDefinition 6.11.2 Let A be ann xn matriz. An (n—r) x (n—r) matrix is called aprincipal submatrix of A if it is obtained by deleting from A the rows 71,12,--+ ,t, and thecolumns 41, 12,++° yt.Now the Cauchy interlacing theorem is really the following corollary.Corollary 6.11.3 Let A be ann x n Hermitian matrix and let B be an (n — 1) x oe —1)principal submatriz. Then the interlacing inequality holds 44 < py < A2 < pg Se <Myn—1 < An where the pu; are the eigenvalues of B listed in increasing order and the A; arethe eigenvalues of A listed in increasing order.Proof: Suppose B is obtained from A by deleting the i*” row and the i*” column. Thenlet P be the permutation matrix which switches the i’? row with the first row. It is anorthogonal matrix and so its inverse is its transpose. The transpose switches the i” columnwith the first column. See Problem 33 on Page 128. Thus PAP? = “ and ityfollows that the result of the multiplication is indeed as shown, a Hermitian matrix becauseP,P® are orthogonal matrices. Now the conclusion of the corollary follows from Theorem6.11.1.