Kenneth Kuttler

350 CHAPTER 13. MATRICES AND THE INNER PRODUCT

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 13.12 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−3 and 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 347), and so, passing to the limit, gives the desired result in which itmay be necessary to replace < with ≤. ■

Definition 13.6.2 Let A be an n×n matrix. An (n− r)×(n− r) matrix is called a principalsubmatrix of A if it is obtained by deleting from A the rows i1, i2, · · · , ir and the columnsi1, i2, · · · , ir.

Now the Cauchy interlacing theorem is really the following corollary.

Corollary 13.6.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 40 on Page 99. 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 Theorem13.6.1. ■

350 CHAPTER 13. MATRICES AND THE INNER PRODUCTNotice 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 2; are strictly increasing in i, it follows from 13.12 thatq(fi;) 4 ran <0. However, since each |z;| 4 0, none of the g(fi;) can equal 0 and soq(f;)q (A;.1) <0. Hence, from the intermediate value theorem of calculus, there is a rootof q(A) in each of the disjoint open intervals (f1;,fi;,,). There are n — 2 of these intervalsand so this accounts for n — 2 roots of g(A).n—-1 n—1 _———~—_.q(A) =(A—a) (A fis) ~ Ye bei (A= Ba) A= Ai) (A Bena)iaWhat of q((i,)? Its sign is the same as (—1)""? and also q(fi,,_;) <0. Therefore, thereis a root to qg(A) which is larger than ft,,_,. Indeed, limy_,..qg(A) = © so there exists aroot of qg(A) strictly larger than fi,_,. This accounts for n — | roots of g (A). Now considerq(fl,). Suppose first that n is odd. Then you have q(ft,) > 0. Hence, there is a root ofq(A) which is no larger than fi, because in this case, lim,_,_..g(A) = —o9. If n is even,then q(ft,) < 0 and so there is a root of g (4) which is smaller than f1, because in this case,limy_,_.4q (A) =. This accounts for all roots of g(A). Hence, if the roots of q(A) areAy <Az <+++ <Any, it follows thatAy < fly <A2 < pln < +++ < yy <AnTo get the complete result, simply take the limit as k — oo. Then limy_,.. fl, = , andA; — A and so the eigenvalues of A, converge to the corresponding eigenvalues of A (SeeProblem 47 on Page 347), and so, passing to the limit, gives the desired result in which itmay be necessary to replace < with <.Definition 13.6.2 Let A be ann Xn matrix. An (n—r) x (n—r) matrix is called a principalsubmatrix of A if it is obtained by deleting from A the rows i,i2,--+ ,i, and the columnsiy, 12,° ttyl p.Now the Cauchy interlacing theorem is really the following corollary.Corollary 13.6.3 Let A be ann x n Hermitian matrix and let B be an (n—1) x (n—1)principal submatrix. Then the interlacing inequality holds A, < Wy <A < by <0 <H,—1 <An where the 1; 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 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 40 on Page 99. 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 Theorem13.6.1. Hf