Norm bounds on spectral variation and eigenvalue variation

Question

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.

Answer 1

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.

Answer 2

The most elementary case of Weyl's inequality says that, if $\lambda_i(S)$ denote the $i$th eigenvaue of the Hermitian matrix $S$ (increasing order), then $\lambda_i(S)+\lambda_1(T)\le\lambda_i(S+T)\le\lambda_i(S)+\lambda_n(T)$. Since the standard operator norm equals, for Hermitian matrices $T$, $\max\{-\lambda_1(T),\lambda_n(T)\}$, you infer immediately $$\nu(A,B)\le\|B-A\|.$$

Answer 3

This is true for (EDIT: only the Euclidean norm) by the Bauer-Fike theorem, since for a symmetric / normal matrix the eigenvalue matrix is unitary and hence has condition number 1.

Answer 4

For comparison of spectral variations of Hermitian and non-Hermitian matrices and operators I suggest the following book

Gil’, Michael I., Operator functions and operator equations, ZBL06793919.