# Eigenvalue bounds of a perturbed Hermitian matrix

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.

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}$$
• Thanks, I agree on this. This is of course also the case for permutations with similar entries. I need to reformulate the question a bit. The permutations are only allowed between certain parts. Considering that the matrix is stored in a tree structure, then only permutations which would switch subtrees would be allowed (one such permutation at a time). Here also the lower bound is $0$ if e.g. two entries are equal, but assuming non-uniform entries, can this be bound as well? – LeoW. Mar 10 '17 at 22:47