I have the matrix
$$A = \begin{bmatrix}
0.501 &1 & & &\\
&0.502& 1& &\\
& & \ddots & \ddots& \\
& & & 0.509& 1\\
& & & &0.6
\end{bmatrix}, A \in \mathbb{R}^{100,100}$$
and its condition is $\kappa(A)=2.2097\cdot 10^{26}$ which is very bad and that is intentional. It is supposed to demonstrate, an ill conditioned matrix can have "nice" eigenvalues. The condidtion is given by $\frac{\sigma_1}{\sigma_n}$, dividing the largest singular value by the smallest. Because its smallest singular value drops very fast in comparison to the others, we get this ill-conditioned situation. But why is it that just the last singular value behaves so oddly?
I have plotted the singular values of $A$ for $n=100$. That is an interesting behaviour. Why does this specific matrix-structure lead to this fast decay of its last singular value?
My Interpretation is that the last eigenspace of $A^TA$, i.e. the one with $\sigma_n$ as an eigenvalue, is "almost" in the kernel. But where in the structure of $A$ is this realized?
Best Answer
Define a vector $v \in \mathbb{R}^{100}$ by $v_1= 1$, and $v_{n+1} = -\dfrac{500+n}{1000}v_n$ for $n = 1,\ldots,99$.
We can compute the entries of $Av$ as follows:
For $m = 1,\ldots,99$, $(Av)_m = \displaystyle\sum_{n = 1}^{100}A_{m,n}v_n = A_{n,n}v_n+A_{n,n+1}v_{n+1} = \dfrac{500+n}{1000}\cdot v_n+1\cdot-\dfrac{500+n}{1000}v_n = 0$
$(Av)_{100} = \displaystyle\sum_{n = 1}^{100}A_{100,n}v_n = A_{100,100}v_{100} = 0.6 \cdot \displaystyle\prod_{n = 1}^{99}\left(-\dfrac{500+n}{1000}\right) \approx -1.03\times 10^{-26}$
So $Av$ is a vector whose first $99$ entries are $0$ and last entry is $\approx -1.03\times 10^{-26}$. So $\|Av\|_2 \approx 1.03 \times 10^{-26}$. You can check that $\|v\|_2 \approx 1.1557$. Hence $v$ is a non-zero vector that is "almost" in the nullspace of $A$, which is why $A$ has a very small singular value.
In particular, we can bound the smallest singular value as follows:
$$\sigma_{100} = \displaystyle\min_{\substack{x \in \mathbb{R}^{100} \\ x \neq 0}}\dfrac{\|Ax\|_2}{\|x\|_2} \le \dfrac{\|Av\|_2}{\|v\|_2} \approx 8.97 \times 10^{-27}.$$