2
$\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 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .