February 5, 2013 2 Comments
While grading homeworks today, I came across the following bound:
Theorem 1: If A and B are symmetric matrices with eigenvalues and respectively, then .
For such a natural-looking statement, this was surprisingly hard to prove. However, I finally came up with a proof, and it was cool enough that I felt the need to share. To prove this, we actually need two ingredients. The first is the Cauchy Interlacing Theorem:
Theorem 2: If A is an symmetric matrix and B is an principle submatrix of A, then , where is the ith largest eigenvalue of X.
As a corollary we have:
Corollary 1: For any symmetric matrix X, .
Proof: The left-hand-side is just the trace of the upper-left principle submatrix of X, whose eigenvalues are by Theorem 2 bounded by the k largest eigenvalues of X.
The final ingredient we will need is a sort of “majorization” inequality based on Abel summation:
Theorem 3: If and are such that for all k (with equality when ), and , then .
Proof: We have:
where the equalities come from the Abel summation method.
Now, we are finally ready to prove the original theorem:
Proof of Theorem 1: First note that since the trace is invariant under similarity transforms, we can without loss of generality assume that A is diagonal, in which case we want to prove that . But by Corollary 1, we also know that for all k. Since by assumption the are a decreasing sequence, Theorem 3 then implies that , which is what we wanted to show.