Eigenvalue bounds of a perturbed Hermitian matrix

Question

I am looking for a lower bound of the perturbation of eigenvalues of a Hermitian matrix. More formally: Given a Hermitian matrix $A \in \mathbb{C}^{n \times n}$ with eigenvalues $\lambda_n(A) \leq \ldots \leq \lambda_1(A)$, and a perturbed matrix $A+E \in \mathbb{C}^{n \times n}$ with eigenvalues $\lambda_n(A+E) \leq \ldots \leq \lambda_1(A+E)$, is it possible to find a non-trivial (i.e. not $0$) lower bound for the distance of the eigenvalues of $A$ and the eigenvalues of $A+E$. Weyl's theorem gives me such an upper bound, specifically: $$|\lambda_i(A) - \lambda_i(A-E)| \leq ||E||,$$ where $||\cdot||$ is the two norm (see e.g. here). I am hence looking for a bound like: $$ c||E|| \geq |\lambda_i(A) - \lambda_i(A-E)|,$$ if such a bound is possible to find. In particular the perturbation I am looking at is a permutation of the entries of $A$, which could make a result easier. Any direction or hint how to calculate this bound would be appreciated.

Answer 1

There is no lower bound, since we might not change the eigenvalues at all. For instance, take $$ A = \pmatrix{1&1\\1&1}, \qquad E = \pmatrix{0&-2\\-2&0} $$