Discs of the The Bauer–Fike theorem

Question

The Bauer–Fike theorem states that if $A = VDV^{-1}$ for $D = \operatorname{diag}(\lambda_{1},\ldots,\lambda_{n})$ is a diagonalizable matrix and $\tilde{A}=A+E$ is a perturbed matrix than the eigenvalues of $\tilde{A}$ lie in the union of the discs $D_{i}$ where every $D_{i}$ is centered at $\lambda_{i}$ and has radius $\kappa(V)\|E\|$.

My question is: Is it possible that some disc is empty? That is, can there be an $i$ for which $D_{i}$ contains \emph{no eigenvalues} of $\tilde{A}$?

I think not, but could not prove it.

Answer 1

If you expand the radius by a factor of roughly $2n$ than the answer is indeed that a disc cannot be empty.

The Bauer-Fike theorem tells us that the distance measure $d_1 = \max_{i}\min_{j}|\lambda_{i}-\mu_{j}|$ is small. What I wanted to infer is that the distance measure $d_2 = \min_{\sigma \in S_{n}}\max_{i}|\lambda_{i}-\mu_{\sigma(i)}|$ is small (where $S_n$ is the permutations on $n$ elements).

It turns out that under plausible assumptions, $d_{2} \le 2n d_{1}$, as proved here, by Elsner.

Answer 2

Empty, no; vanishing radius, yes. By definition, $\kappa$ cannot vanish (see here), but a trivial perturbation $E=0$ yields $||E||=0$, and therefore the disks have zero radius. Note that the Bauer-Fike theorem allows the perturbed eigenvalues to lie on the boundary of the disk; in other words, we consider $D_i$ to include its boundary, so to be closed. Any disk $D_i$ contains $\lambda_i$, whatever radius the disk has (including radius zero), so these disks are never empty.

addition, based on edited question: $A$ and $E$ are both $(n \times n)$ matrices, so both the characteristic polynomial of $A$ and the characteristic polynomial of $A+E$ is of order $n$. Therefore, both $A$ and $A+E$ have $n$ eigenvalues, neglecting algebraic multiplicity. The only way a disk $D_i$, centred around $\lambda_i$, could not contain a $\mu_i$, is when the number of eigenvalues $\mu_i$ of $A+E$ would be strictly less than the number of eigenvalues $\lambda_i$ of $A$.