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$.
 A: 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}$. 
A: 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?
