# Eigenvalue Bounds

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.

Nice! However, I would like to correct a tiny thing in your proof. Theorem 3 needs $\sum_1^n x_i = \sum_1^n y_i$. Fortunately, this condition is also satisfied when you apply Theorem 3 in your proof as $\sum_1^n B_{ii} = Trace(B) = \sum_1^n \mu_i$.

tmbtw

Yes, good catch! I will edit.