Proof that $\Delta A := -\sigma_n u_n {v^T}_n$ is the smallest possible perturbation such that $A + \Delta A$ is singular.

Question

I'm studying the peoperties of the SVD decomposition $A = U\Sigma V^T$ and have run into the following statement:

$\Delta A := -\sigma_n u_n {v^T}_n $ is the smallest possible perturbation such that $A + \Delta A$ is singular.

Is there an explanation or proof for this result?

Answer 1

Assume A is $n×n$ of full rank. The problem you want to solve is

$$ \min_{∆A} ‖{∆A}‖_F \qquad\text{such that}\qquad \operatorname{rank}(A+{∆A})=n-1$$

Substituting $B≔A+{∆A}$, this is equivalent to

$$ \min_{B} ‖A-B‖_F \qquad\text{such that}\qquad \operatorname{rank}(B) = n-1$$

which by Eckart-Young has the solution $B=∑_{k=1}^{n-1}σ_iu_iv_i^⊤$, hence ${∆A}=B-A = -σ_nu_nv_n^⊤$.

Answer 2

For any $\Delta A$ that makes $A+\Delta A$ singular, pick a unit vector $x$ in the null space of $A+\Delta A$. Then $Ax=-\Delta Ax$ and we may obtain a lower bound for the norm of $\Delta A$: $$ \sigma_n(A)\le\|Ax\|_2=\|\Delta Ax\|_2\le\|\Delta A\|_2\le\|\Delta A\|_F. $$ Since this lower bound is attained by $\Delta A=-\sigma_n(A)u_nv_n^T$, this choice of $\Delta A$ is the smallest possible perturbation (in terms of induced $2$-norm or Frobenius norm) that makes $A+\Delta A$ singular.