Singular values: smallest perturbation to make a matrix singular

Question

A problem from Gilbert Strang's Linear text, after the section on the singular value decomposition:

Suppose $A$ is $2\times 2$ and invertible (with $\sigma_1 > \sigma_2 > 0$). Change $A$ by as small a matrix as possible to produce a singular matrix $A_0$. Hint: $U$ and $V$ don't change. Use $$A = \left [ \begin {matrix} u_1 & u_2\end {matrix}\right ] \left [ \begin {matrix} \sigma_1 & \\ & \sigma_2 \end {matrix}\right ] \left [ \begin {matrix} v_1 & v_2\end {matrix}\right ]^T.$$

I think we can change $A$ by

$$\left [ \begin {matrix} u_1 & u_2\end {matrix}\right ] \left [ \begin {matrix} 0 & \\ & -\sigma_2 \end {matrix}\right ] \left [ \begin {matrix} v_1 & v_2\end {matrix}\right ]^T.$$

But how can we show this is the smallest possible alteration of $A$ to get a singular matrix?

I think Strang is expecting a somewhat loose answer here, since he's not yet introduced the matrix norm, so it's not clear what he means by "as small as possible." If we were to attempt it in a more rigorous way, I think we'd like two results:

1. A result relating singular values to addition and subtraction, something like $\sigma_n(A) + \sigma_n(B) \geq \sigma_n(A \pm B)\geq \sigma_n(A) - \sigma_1(B)$, where $\sigma_1, \dotsc , \sigma_n$ are arranged in descending order.
2. A result relating singular values to matrix norm. I believe the largest singular value is the value of the 2-norm, but how can we relate this to the operator norm?

Answer 1

I believe the largest singular value is the value of the 2-norm, but how can we relate this to the operator norm?

The largest singular value is the operator norm: $$\sigma_1=\max_{\|x\|=1}\|Ax\|=\|A\| \tag0$$ Here and below I use the Euclidean norm on vectors, and the corresponding operator norm on matrices.

The smallest singular value of $A$, denoted by $\sigma_n$ below, has a description similar to (0): $$\sigma_n=\min_{\|x\|=1}\|Ax\|=\min\{\|A-B\|: \operatorname{rank}B<n \} \tag1$$ Indeed, from the SVD decomposition you see that $$\min_{\|x\|=1}\|Ax\|^2 = \min_{\|y\|=1} \sum_k \sigma_k^2 y_k^2 = \sigma_n^2+ \min_{\|y\|=1} \sum_k (\sigma_k^2-\sigma_n^2) y_k^2$$ where the last sum is minimized by letting $y_n$ be the only nonzero component. I used the fact that the unitaries preserve the vector norm.

By the way, you can prove (0) by modifying the proof above.

As for the second part of (1), the inequality $$\min_{\|x\|=1}\|Ax\|\le \min\{\|A-B\|: \operatorname{rank}B<n \}\tag2$$ follows from the fact that $Bx=0$ for some unit vector $x$. The reverse inequality follows by taking $B=A\circ P$ where $P$ is the projection onto the orthogonal complement of vector $x$ that attains the minimum on the left side of (2). Indeed, $A-A\circ P=A\circ Q$ where $Q$ is the projection onto the span of $x$, hence $\|A\circ Q\|=\|Ax\|$.

In particular, (1) implies that $\sigma_n(A)$ is a $1$-Lipschitz function of $A$ in the operator norm, namely $$|\sigma_n(A)-\sigma_n(B)|\le \|A-B\| \tag3$$ Where the right hand side is $\sigma_1(A-B)$, by (0).

In fact, (3) holds for all singular values, because $\sigma_k$ is the distance from $A$ to the set of operators of rank less than $k$. See Wikipedia: Singular value.

Answer 2

The problem is in "as small a matrix as possible". What does that mean?

Given the suggestion, it is most likely in terms of induced $2$-norm and Frobenius norm, i.e., by $E$ such that $|E|_2$ or $|E|_F$ is minimal. This is shown here.

Try to prove it yourself, and ask if you get stuck.