Smallest singular value of full column rank matrix

Question

For any matrix $M$, denote by $\sigma_{\min}(M)$ the smallest non-zero singular value of $M$. Now given a matrix $A=[A1,A2]$ and assume that $A$ has full column rank. Is it always true that $\sigma_{\min}(A)\leq\sigma_{\min}(A_1)$? I tried several examples on Matlab and all turned to be true. But I cannot prove it yet. Thanks in advance!

Answer 1

Adding a column $z$ to a matrix $A\in \mathbb{R}^{m \times n}$, $m>n$, will cause the min singular value ($\sigma_{min})$ to decrease or stay the same i.e., $$\sigma_{min}([A | z]) \leq \sigma_{min}(A)$$

because:

Taking $A = U\Sigma V^T$ (the SVD) and $x$ as the last column of $V$, which corresponds to the singular vector for $\sigma_{min}$, and $\hat{A} = [A|z]$, we have

\begin{align} \sigma_{min}(A)& = \|Ax\|_2 && \text{b/c $x:=$ last column of $V$}\\ &= \|\hat{A}\begin{bmatrix}x\\0\end{bmatrix}\|_2 \ \geq \ \sigma_{min}(\hat{A})\cdot\|\begin{bmatrix}x\\0\end{bmatrix}\|_2 && \text{b/c $\|Ax\|_2 \geq \sigma_{min} \|x\|_2 $ and $ \|x\|_2=1$} \\ &= \sigma_{min}(\hat{A}) \cdot 1 && \text{} \end{align} Thus, $$\sigma_{min}(\hat{A}) \leq \sigma_{min}(A)$$

This is for the case of adding a column; I am not sure if your A2 is a matrix or vector, but the derivation should be similar. For reference, I took a similar approach from Golub's Matrix Computations 4th edition section 2.4.2