3
$\begingroup$

From Strang's Introduction to Linear Algebra (p375), there is a paragraph on the instability of eigenvalues in relation to the stability of singular values when $A$ is altered slightly. Moreover, it says, that the instability of eigenvalues is only if $AA^T$ is far from $A^TA$, but if those are very similar, the eigenvalues are also stable. The book goes on to present a $4\times4$ example with one value altered by $1/60000$ which changes the eigenvalues by $1/10$ but singular value change is only $1/60000$.

To put what I understood from this claim and the example in definite terms, the eigenvalues of $A$ are seriously unstable if $A^TA$ is significantly different $AA^T$, i.e. on altering $a_{ij}$ in $A$ by $\Delta a_{ij}$, the $\lambda_A$ change by values much greater ($\Delta \lambda_A >> \Delta a_{ij}$) but singular values change in the same order ($\Delta \sigma_A \approx\Delta a_{ij}$).

The overarching question I have is, I do not understand, intuitively or mathematically, how this came to be

My attempts:

I tried to characterize $\Delta \lambda_A$ by looking at how the coefficient of the polynomial $det(A-\lambda_A I) = 0$ change when $a_{ij}$ becomes $a_{ij} + \Delta a_{ij}$. But if I were to compare this to the singular value case, I would be looking at the change in coefficients of the polynomial $det(A^TA - \sigma_A^2I) = 0$, but in $A^TA$, the $\Delta a_{ij}$ term would be actually present at more than one entries and it would seem that it would actually lead to a greater change in the coefficients! I also am not sure how would a change in coefficients be related to the change in the zeros of the polynomial.

Furthermore, why would the relation between $AA^T$ and $A^TA$ affect $\Delta \lambda_A$ rather than $\Delta \sigma_A$, as one would expect since the singular value is quite strongly associated with the eigenvectors of $AA^T$ and $A^TA$, but the eigenvalues of $A$ appears to not have a direct relation with them.

Any more clarity on the intuition of the three bold statements would be appreciated.

$\endgroup$
0
$\begingroup$

Let $A\in M_n(\mathbb{R})$ and $\lambda$ be a SIMPLE real eigenvalue of $A$. Let $Ax=\lambda x$ where $||x||^2=1$. Then $x^Tx=1,x^T(\Delta x)=0$.

$(\Delta A)x+A(\Delta x)=(\Delta \lambda)x+\lambda (\Delta x)$ implies that

(*) $x^T(\Delta A)x+x^TA(\Delta x)=\Delta \lambda$ and

(*bis) $x^T(\Delta A)x=\Delta \lambda$ when $AA^T=A^TA$.

Let $AA^T=S$ (a symmetric matrix) and $Sy=\sigma y$, where $||y||^2=1$. Then

$(\Delta S)y+S(\Delta y)=(\Delta \sigma)y+\sigma (\Delta y)$ implies that

(**) $y^T(\Delta S)y=\Delta \sigma$.

Then $\Delta \sigma$ has same order as $\Delta S=(\Delta A)A^T+A(\Delta A)^T$, that is, same order as $\Delta A$.

On the other hand, $\Delta \lambda$ has same order as $\max(order(\Delta A),order(\Delta x))$ and as $order(\Delta A)$ when $AA^T=A^TA$.

Finally a matrix $A$ with instable eigenvalue $\lambda$ is obtained when $\Delta x$ is very large. The Strang's example is

$A=\begin{pmatrix}0&1&0&0\\0&0&2&0\\0&0&0&3\\0&0&0&0\end{pmatrix}$ and $\Delta A=\begin{pmatrix}0&0&0&0\\0&0&0&0\\0&0&0&0\\1/60000&0&0&0\end{pmatrix}$.

Note that $0$ is not a simple eigenvalue; yet instability is further caused by the magnitude of $\Delta x$ (the unique eigenvector of $A$ explodes in $4$ eigenvectors that are far from the first one -when we change $a_{4,1}=0$ into $1/60000$-).

EDIT. To get the simplicity of the eigenvalues (as I suppose it), just choose $a_{4,1} = 10^{-10}$ (then there are $4$ distinct eigenvalues) and change it to $a_{4,1}=1/60000$.

Then check that the eigenvector associated with the $> 0$ eigenvalue "moves" quickly. It's your business.

$\endgroup$
3
  • $\begingroup$ Sorry for being slow, but can you expand/explain a bit on some of the statements and how they came about, and how one implies the other (I understood some but not most)? Especially the first statement with $\Delta$s? $\endgroup$ Mar 29 '20 at 9:37
  • $\begingroup$ It's the standard derivation; for example $\dfrac {\partial A}{\partial a_{i,j}}\approx \dfrac{\Delta A}{\Delta a_{i,j}}$; moreover , I write only the numerators -it is a notation widely used in physics- $\endgroup$
    – user91684
    Mar 29 '20 at 11:13
  • $\begingroup$ Can you expand on how $xT(\Delta A)x+xTA(\Delta x)=\Delta λ$ and $yT(\Delta S)y+yTS(\Delta y)=\Delta σ$ lead to different conclusions despite having similar forms? (in the former, in general, we do not remove the contribution of $\Delta x$ while in the latter we remove the contribution of $\Delta y$)? And by a simple eigenvalue, what do you mean? $\endgroup$ May 9 '20 at 9:06

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.