348 CHAPTER 13. MATRICES AND THE INNER PRODUCT

matrix which has k−1 nonzero entries. Finally, when A is similar to one which hasat most one nonzero entry, this one must also be zero because of the condition on thetrace.

50. ↑An n× n matrix X is a commutator if there are n× n matrices A,B such that X =AB−BA. Show that the trace of any commutator is 0. Next show that if a complexmatrix X has trace equal to 0, then it is in fact a commutator. Hint: Use the aboveproblem to show that it suffices to consider X having all zero entries on the maindiagonal. Then define

A =

1 0

2. . .

0 n

 , Bi j =

{Xi ji− j if i ̸= j

0 if i = j

13.6 Cauchy’s Interlacing Theorem, EigenvaluesRecall that every Hermitian matrix has all real eigenvalues. The Cauchy interlacing theo-rem compares the location of the eigenvalues of a Hermitian matrix with the eigenvalues ofa principal submatrix. It is an extremely interesting theorem.

Theorem 13.6.1 Let A be a Hermitian n×n matrix and let

A =

(a y∗

y B

)where B is (n−1)× (n−1) . Let the eigenvalues of B be µ1 ≤ µ2 ≤ ·· · ≤ µn−1. Then ifthe eigenvalues of A are λ 1 ≤ λ 2 ≤ ·· · ≤ λ n, it follows that λ 1 ≤ µ1 ≤ λ 2 ≤ µ2 ≤ ·· · ≤µn−1 ≤ λ n.

Proof: First note that B is Hermitian because

A∗ =

(a y∗

y B∗

)= A =

(a y∗

y B

)It is easiest to consider the case where strict inequality holds for the eigenvalues for B sofirst is an outline of reducing to this case.

There exists U unitary, depending on B such that U∗BU = D where

D =

µ1 0

. . .

0 µn−1

Now let {εk} be a decreasing sequence of very small positive numbers converging to 0 andlet Bk be defined by

U∗BkU = Dk, Dk ≡

µ1 + εk 0

µ2 +2εk. . .

0 µn−1 +(n−1)εk

