# eigenvalue error

Let $A$ and $B$ be two symmetric matrices of the same size, and let $\alpha_k$ and $\beta_k$ be the $k$th largest eigenvalues of $A$ and $B$ respectively. What can we say about $|\beta_k - \alpha_k|$ in terms of $||B - A||_2$? To be clearer, I want the tightest possible upper bound on $|\beta_k - \alpha_k|$ using only the stated assumptions, and computed as a function of $||B - A||_2$.

-
Can you then at least say why you want this? Maybe there is a different approach. –  Jonas Teuwen Dec 6 '10 at 18:30
Jonas T: I want this because I am doing a math research and the question is too noob for mathoverflow. I've been looking at theorems like Weyl and like Bauer-Fike and I'm wondering if there is a theorem that very specifically addresses my question. If not then I can piece it together from other theorems I can find on the google. –  mathcast Dec 6 '10 at 18:32
If you are subtly asking whether this is homework then the answer is no. –  mathcast Dec 6 '10 at 18:36
No, I'm not wondering if it is homework or not, your question just is not very "well-posed" in a mathematical sense. –  Jonas Teuwen Dec 6 '10 at 18:38
Which matrix norm do you mean by $\|B-A\|_2$? –  Willie Wong Dec 7 '10 at 4:21

I am slightly unsure about the following approach, so you should double check if that is correct. I'll use $\|\cdot\|_2$ to denote the spectral norm as above, and $\|\cdot \|_F$ for the Frobenius norm.

It is well known that for $n\times n$ matrices, $\|\cdot \|_F \leq \sqrt{n} \|\cdot\|_2$ is sharp from just the definition of the norms. Now, I claim that

$$|\beta_k - \alpha_k| \leq \|B - A\|_F$$

is also sharp. Fix the eigenvalues $\beta_k$ and $\alpha_k$. Consider orthogonal transformations of the symmetric matrix $B$ by $Q$. It suffices to compute the minimum

$$\inf_{Q\in O(n)} \| QBQ^T - A\|_F$$

But using the definition of the Frobenius norm as an inner product, you see that

$$\| QBQ^T - A\|_F^2 = \mathop{Tr}\left[ (QBQ^T - A)(QBQ^T - A) \right] = \|B\|_F^2 + \|A\|_F^2 - 2 A\cdot_F (QBQ^T)$$

It's an exercise to see that $A\cdot_F (QBQ^T)$ is maximized when all the $k$th eigenspace of $A$ lines up with that of $QBQ^T$ (some sort of Cauchy-Schwarz plus re-arrangement inequality). When the eigen-spaces line up, you have that

$$\| QBQ^T - A\|_F^2 = \sum_{k = 1}^n |\beta_k - \alpha_k|^2$$

and so the desired inequality holds, and is attained with the eigenvalues only differ in one position.

Unfortunately, the composition of these two inequalities is not automatically sharp, since the bound of $|\beta_k-\alpha_k|$ by $\|B-A\|_F$ is only sharp with $B-A$ has rank 1, while the first bound can be sharpened $\|C\|_F \leq \sqrt{\mathop{rank}(C)} \|C\|_2$. But it is clear that the most general sharp bound should be

$$|\beta_k-\alpha_k| \leq s\|B-A\|_2$$

with $1 \leq s \leq \sqrt{n}$.

-
So far, it looks sound, but I'm too tired to try and "break" your bounds... maybe after a good night's rest. P.S. Usually $Q$ is used for denoting orthogonal matrices since $O$ is too easily confused with zero. A mere quibble, of course. :) –  Ｊ. Ｍ. Dec 7 '10 at 18:14
@J.M. fixed to your liking. :) –  Willie Wong Dec 7 '10 at 18:32
I upvoted it before commenting, just so you know. ;) –  Ｊ. Ｍ. Dec 7 '10 at 18:34
No, seriously, that was a valid point. I've by habit written $O$ for orthogonal matrices, but have quite often seen textbooks where $Q$ is used. I never really paid thought to why they used $Q$ instead of $O$, and now I know. –  Willie Wong Dec 7 '10 at 19:20