# 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. :) – J. M. 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. ;) – J. M. 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

I am too untrusted to add a comment so i'm spamming this as an answer.

J.M: I think you are considering the converse of the question. If you have two very different-looking matrices it is possible that they have the same spectrum. But if you have two similar-looking matrices, then is it possible that their spectra can be very different?

-
The theorem I remember is "tiny perturbations in matrix entries correspond to tiny perturbations in eigenvalues" for symmetric matrices (for unsymmetric matrices, even a tiny perturbation can cause a matrix to be defective); but since I'm far away from my books, I can't give the rigorous formulation. – J. M. Dec 7 '10 at 2:52
@minel: Instead of spamming the site with answers that should be comments, please earn the reputation needed for commenting by provinding useful answers. – Rasmus Dec 7 '10 at 15:45
@Rasmus: That's a little harsh. – Noah Snyder Dec 7 '10 at 18:19
@Noah Snyder: To my defense led me please notice that this is my third comment on an answer of this kind by minel. The others were at math.stackexchange.com/questions/13318/i-am-so-confused/… and math.stackexchange.com/questions/13308/… . That's we the comment above lacks something like a kind first sentence. I don't think the workaround of posting answers instead of comments should be accepted just because the poster doesn't have enough rep to post comments. – Rasmus Dec 7 '10 at 20:53
@minel: Please excuse if my comment above appears harsh to you. I really meant to submit the sober information in it. – Rasmus Dec 7 '10 at 20:58