Let $A$ and $B$ be two matrices of eigenvalues $\lambda\_i$ and $\mu\_i$, respectively. 


The *spectral variation* of $B$ w.r.t. $A$ and the *eigenvalue variation* of $B$ and $A$ are, respectively,
\begin{align} s\_B(A)&=\max\_i\min\_j\vert\lambda\_i-\mu\_j\vert, \\
v(A,B)&=\min\_{\pi}\max\_i\vert\lambda\_i-\mu\_{\pi(i)}\vert;\end{align}
where in the latter the minimum is to be taken over all permutations $\pi$ of the indices.



> 
> **Question 1.** If $A$ and $B$ are Hermitian matrices, then for which norms is this true?
>  $$s\_B(A)\leq\Vert A-B\Vert.$$
> 
> 
> **Question 2.** If $A$ and $B$ are normal matrices (more generally for fully symmetric operators), then for which norms is this true?
>  $$v(A,B)\leq\Vert A-B\Vert.$$
> 
> 
> 


I would appreciate any reference to the state-of-the-art in this matter.



Norm bounds on spectral variation and eigenvalue variation
The Hermitian case is more like a state-of-art answer. A good review of results in given in [Holbrook].


$\nu(A,B)\leq\|A-B\|$ for the operator norm. This is a direct consequence from Weyl's inequality. 


This problem about spectral variation bound is fully discussed in [Bhatia] Chap 3&4(with a supplement in Chap7&8 if you got the 2006 ed.) 



> 
> “The spectral variation problem for the class of Hermitian matrices
>  has been completely solved in the following sense. For any two
>  Hermitian matrices a tight upper bound for the distance between their
>  eigenvalues is known. Such bounds are known when the distance is
>  measured in any *unitarily-invariant norm*.”[Bhatia]p.34
> 
> 
> 


Later development including marjorization inequalities used in controlling covariance matrices in statistics as motivation [Marshall&Olkin], as described in[Bhatia] 3.9


(This is quite clear once you know the reference, probably that is why it gets downvotes.)


**Reference**


[Holbrook]Holbrook, John A. "Spectral variation of normal matrices." Linear algebra and its applications 174 (1992): 131-144.


[Bhatia]Bhatia, Rajendra. Perturbation bounds for matrix eigenvalues. Society for Industrial and Applied Mathematics, 2007.


[Marshall&Olkin]Marshall, Albert W., Ingram Olkin, and Barry C. Arnold. Inequalities: theory of majorization and its applications. Vol. 143. New York: Academic press, 1979.


