# Stability of eigenvalues/singular values on altering the matrix

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.

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.

• 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? Mar 29 '20 at 9:37
• 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-
– user91684
Mar 29 '20 at 11:13
• 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? May 9 '20 at 9:06