# Show that every rank-deficient matrix has a full rank matrix arbitrarily close to it

I came across the following exercise in preparation for a test.

Let $$A \in \mathbb{R}^{n \times m}$$ with rank $$r < \min\{n,m\}$$. Use SVD of $$A$$ to show that for every $$\epsilon >0$$ (no matter how small), there existsa full-rank matrix $$A_{\epsilon} \in \mathbb{R}^{n\times m}$$ such that $$|| A - A_\epsilon ||_{2} < \epsilon$$.

I am really puzzled on how to approach this exercise. From my understanding $$A - A_\epsilon = \underset{n\times n}{U} \ \underset{n \times m}{\Sigma} \ \underset{m\times m}{V^{T}} - \underset{n\times n}{U} \ \underset{n \times m}{\Sigma_\epsilon} \ \underset{m\times m}{V^{T}} = U(\Sigma - \Sigma_\epsilon)V^{T}.$$ Then $$\Sigma$$ is diagonal matrix with singular values ranging from $$\sigma_1$$ to $$\sigma_{\min\{n,m\}}$$ and $$\Sigma_\epsilon$$ having singular values from $$\sigma_1$$ to $$\sigma_m$$ since $$A_\epsilon$$ is of rank $$m$$.

Then since $$\min\{n,m\} \le m$$ $$\Sigma - \Sigma_\epsilon = \begin{pmatrix} \sigma_1 & & & \\ & \ddots & \\ & & \sigma_n & \\ & & & 0\end{pmatrix} - \begin{pmatrix} \sigma_1 & & & \\ & \ddots & \\ & & \sigma_{\min\{n,m\}} & \\ & & & 0\end{pmatrix} = \begin{pmatrix} 0& & & \\ & \ddots & \\ & & \sigma_? & \\ & & & 0\end{pmatrix}$$ So since a singular value exists for the matrix difference above, $$|| A - A_\epsilon ||_2 = \sigma_?$$ which has to be small since $$\sigma_1 > \sigma_2 > \dots > \sigma_r$$, and here this $$\sigma_?$$ is among among the last in the sequence.

I am most likely writing non-sense, I am aware of that, I don't know how to proceed, can anyone give me some hint or idea ?

• You don't know that $A_\varepsilon$ has rank $m$. You don't know if $m<n$ or viceversa. You should set $p=min(m,n)$, and think in terms of $p$ rather than $m$ or $n$. Mar 19, 2021 at 18:18

You are very close. The proof needs a couple of ingredients:

• What is the norm of A (say the 2-norm, since they are all equivalent) in terms of $$\Sigma$$? And what's the norm of $$\Sigma$$ in terms of the $$\sigma_i$$'s?
• The simples way to perturb $$\Sigma$$ is to let $$\Sigma_\varepsilon$$ have the first $$r$$ singluar values matching those of $$\Sigma$$.

If you write $$\Sigma_\varepsilon$$ as described above, what would $$\|\Sigma_\varepsilon-\Sigma\|$$ be? And therefore, what aboud $$\|A-A_\varepsilon\|$$?

Edit: read further for more details.

You are free to build $$A_\varepsilon$$ in whatever way you want. The goal is to produce one matrix that is close to A, however peculiar its construction may be. So pick same $$A_\varepsilon=U\Sigma_\varepsilon V^T$$, with $$\Sigma_\varepsilon$$ with the same first $$r$$ singular values as $$\Sigma$$, and $$\sigma_i<\varepsilon$$ for $$i=r+1,...,p$$. (Note: you could pick any values for $$\sigma_{r+1},...,\sigma_p$$, so long as they are all positive, and all smaller than $$\varepsilon$$. Then $$\|\Sigma-\Sigma_\varepsilon\|=\sigma_{r+1}<\varepsilon$$. This proves that $$A_\varepsilon$$ is arbitrarily close to A. The fact that all its singular values are non zero (small as they may be), implies that $$A_\varepsilon$$ is full rank. QED.

• Thank you for answering ; I am not sure for the norm of $A$ in terms of $\Sigma$ but I know there is a theorem that says that $||A||_2 = \max \sigma_i (A)$ , so I suppose that, letting $p := \min\{n,m\}$ , $|| A - A_\epsilon ||_2 = \max \sigma_i (\Sigma - \Sigma_\epsilon)$ ; but here I am not sure what is the difference in length of the sets $\{\sigma\}_i \in \Sigma$ and $\{\sigma\}_i \in \Sigma_\epsilon$. I suppose that doesn't matter since we're taking the maximum anyways ? And since the singular values are decreasing in value as $i$ increases then $|| A - A_\epsilon ||_2 = \sigma_{r+1}$ ? Mar 19, 2021 at 18:38
• Correct. If you pick $\Sigma_\varepsilon$ to have the same first $r$ singular values as $\Sigma$, then $\|\Sigma-\Sigma_\varepsilon\|=\sigma_{r+1}$. Therefore... Mar 19, 2021 at 21:28
• honestly, I am completely clueless as to how to proceed further. How would I even begin to show that $|| A - A_{\epsilon}|| = \sigma_{r+1} < \epsilon$ for $\epsilon$ very small ? Or do I just say; $\sigma_{r+1}$ is very small so $\exists \ 0 < \epsilon < \sigma_{r+1} \ | \ || A - A_{\epsilon}||_{2} < 0$ ? Mar 20, 2021 at 1:03

Note that in the case of square matrices $$(n\times n$$), there is maybe a shorter proof.

$$p(x)=\det(A-xI)$$ is a polynomial in $$x$$ and has at most $$n$$ roots in $$\mathbb C$$.

So let's take $$A_\epsilon=A-\epsilon I$$, we have $$\det(A_\epsilon)=\det(A-\epsilon I)=p(\epsilon)$$

The number of roots of $$p$$ being finite, we can always choose $$\epsilon$$ such that $$p(\epsilon)\neq 0$$, making $$A_\epsilon$$ invertible.