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.
1 Answer
$\begingroup$ $\endgroup$
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} $$
- $\begingroup$ 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? $\endgroup$LeoW.– LeoW.2017-03-10 22:47:40 +00:00Commented Mar 10, 2017 at 22:47