1
$\begingroup$

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? singular Values of A

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?

$\endgroup$
1
$\begingroup$

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}.$$

$\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.