1
$\begingroup$

If $A+\epsilon $ (where $\epsilon$ is a perturbation on the order of machine precision,) has an eigenvalue $\lambda$, and $A$ is a normal matrix, then the eigendecomposition of $A$ is $A=Q \Lambda Q^{*}$, where $Q$ is unitary.

Under those conditions, I have seen it written in my textbook that $\|(\lambda I-A)^{-1}\|=\|Q(\lambda I-\Lambda )^{-1} Q^{*}\|$. But I cannot figure out why these two things are equal.

Can someone show me why/how these are equivalent?

Thank you.

The $\|\cdot\|$ denotes the $2$-norm.

$\endgroup$
  • 2
    $\begingroup$ It's a fact that for both the spectral (2-) norm and the Frobenius norm, the norm is invariant under multiplication by an orthogonal matrix. This is not true for most other matrix norms. $\endgroup$ – Brian Borchers Dec 12 '17 at 6:02
  • 2
    $\begingroup$ $A$ has eigenvalue $\lambda$, so $A-\lambda I$ is not injective, so why it is invertible? $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Dec 12 '17 at 6:18
  • $\begingroup$ Ah, really really good point GN Supporter. I think I copied the statement from the textbook wrong....let me check. $\endgroup$ – nundo Dec 12 '17 at 6:36
  • $\begingroup$ @BrianBorchers yes I understand that the Q's do not affect the norm (2-norm, or Fro norm). But then why are we able to stick the $\Lambda$ in there? $\endgroup$ – nundo Dec 12 '17 at 6:36
  • 1
    $\begingroup$ It would help to provide context if you cited the source that you got this from. $\endgroup$ – Brian Borchers Dec 12 '17 at 16:24
1
$\begingroup$

This clearly isn't an exact equation, but rather a relationship that holds in the limit as $\| \epsilon \|$ goes to 0.

There's a notational confusion here, in that $\lambda$ in the statement of the problem is an eigenvalue of the perturbed matrix, and $\Lambda$ is the diagonal matrix of eigenvalues of the original matrix. I'll change the notation to use $\mu$ as an eigenvalue of the perturbed matrix $A+\epsilon$, and restate the proposition as

Assume that $A$ and $A+\epsilon$ are normal matrices, $A$ has been diagonalized as $A=Q\Lambda Q^{*}$ and that $\| \epsilon \|$ is a small perturbation. In the limit as $\| \epsilon \|$ goes to 0, if $\mu$ is an eigenvalue of $A+\epsilon$, then to first order, $\| (\mu I - A)^{-1} \|_{2} \approx \| Q(\mu I - \Lambda)^{-1} Q^{*} \|_{2}$

Since $\mu$ is an eigenvalue of the perturbed matrix, it is close to an eigenvalue $\lambda_{i}$ of the original matrix $A$, with corresponding eigenvector $v_{i}$. The perturbation theory for eigenvalues tells us that to first order,

$\mu \approx \lambda_{i} + v_{i}^{T}\epsilon v_{i}$

Thus the smallest eigenvalue of $\mu I - A$ is to first order,

$\mu_{smallest}(\mu I - A) \approx v_{i}^{T} \epsilon v_{i} $

Then to first order,

$\| (\mu I - A)^{-1} \|_{2} \approx \frac{1}{| v_{i}^{T} \epsilon v_{i} |} $

On the other side, the smallest eigenvalue of $\mu I - \Lambda$ is $\mu - \lambda_{i} \approx v_{i}^{T} \epsilon v_{i}$. Thus to first order,

$\| (\mu I - \Lambda)^{-1} \|_{2} = \| Q(\mu I - \Lambda)^{-1} Q^{*} \|_{2} \approx \frac{1}{| v_{i}^{T} \epsilon v_{i} |}$

You can easily check this in MATLAB by creating random symmetric matrices $A$ and $\epsilon$ with $\| \epsilon \| \ll \| A \|$.

Note that this fails if for some reason $v_{i}^{T}\epsilon v_{i}=0$. I believe that repeated eigenvalues in $A$ can also cause problems.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.