Distance from an invertible matrix to the singular matrices

Idea. The matrix closest to $A$ among the singular ones is obtained by "killing" the weakest direction of $A$, namely the one with the smallest singular value.

Step 1: $\sigma_{\min}=1/\|A^{-1}\|$. If $A=P\Sigma Q^T$ is an SVD ($P,Q$ orthogonal, $\Sigma=\operatorname{diag}(\sigma_1\ge\dots\ge\sigma_n>0)$), then $A^{-1}=Q\Sigma^{-1}P^T$ has operator norm $\max_i\sigma_i^{-1}=1/\sigma_n$ by the orthogonal invariance of the norm.

Step 2: lower bound. Let $B$ be singular. If $\|A-B\|<1/\|A^{-1}\|$, the stability problem would make $B$ invertible. Hence $\|A-B\|\ge1/\|A^{-1}\|=\sigma_n$. Since $\|X\|_F\ge\|X\|$ we also have $\|A-B\|_F\ge\sigma_n$.

Step 3: attainment. Write $A=\sum_i\sigma_iu_iv_i^T$ with $u_i,v_i$ the columns of $P,Q$, and set
$$B=A-\sigma_nu_nv_n^T=\sum_{i<n}\sigma_iu_iv_i^T.$$
Then $B$ has rank $n-1$, so it is singular, and $A-B=\sigma_nu_nv_n^T$ is rank one with
$$\|A-B\|=\|A-B\|_F=\sigma_n\,|u_n||v_n|=\sigma_n.$$
(For a rank-one matrix $uv^T$: $\|uv^T\|_F^2=\sum_{i,j}u_i^2v_j^2=|u|^2|v|^2$, and $|uv^Tx|=|u||v^Tx|\le|u||v||x|$ with equality at $x=v/|v|$, so both norms equal $|u||v|$.)

Conclusion. The distance is exactly $\sigma_n=1/\|A^{-1}\|$ in both norms.

Example. For $A=\begin{pmatrix}2&0\\0&\tfrac12\end{pmatrix}$, $1/\|A^{-1}\|=\frac12$ and $B=\operatorname{diag}(2,0)$ is the nearest singular matrix. In particular a matrix can have a large norm ($\|A\|=2$) and be extremely close to a singular matrix.

Remark. This is a special case of the Eckart-Young theorem: the best rank-$r$ approximation of $A$ (in operator or Frobenius norm) is obtained by truncating the SVD. The quantity $\kappa(A)=\|A\|\|A^{-1}\|$ measures, relative to $\|A\|$, how close $A$ is to being singular.