Does the minimum singular value of a matrix smaller than that of its restricted one?

Question

Let $A \in \mathbb{R}^{m \times n}$. Let $\sigma_{min}(A)$ be the minimum singular value of matrix $A$. Let $A_r$ be a restriction of matrix $A$ to some rows. Is $\sigma_{min}(A) \leq \sigma_{min}(A_r)$?

Answer 1

This is true if $A$ is a square or “fat” matrix, and false otherwise.

A counterexample first: let $A=\pmatrix{0\\ 1}$ and $A_r$ be the first row of $A$. Then $\sigma_\min(A_r)=0<1=\sigma_\min(A)$. Note that $A$ is “tall” in this counterexample.

Now suppose $A$ is square or fat. Without loss of generality we may assume that $A_r$ consists of the first $k$ rows of $A$. Then $A^T$ and $A_r^T$ are tall matrices and the latter is composed of the first $r$ columns of the former. Therefore $$ \begin{aligned} \sigma_\min(A) =\sigma_\min(A^T) &=\min_{\substack{u\in\mathbb R^m\\ \|u\|=1}}\|A^Tu\|_2\\ &\le\min_{\substack{v\in\mathbb R^k\\ \|v\|=1}}\left\|A^T\pmatrix{v\\ 0}\right\|_2\\ &=\min_{\substack{v\in\mathbb R^k\\ \|v\|=1}}\|A_r^Tv\|_2\\ &=\sigma_\min(A_r^T)=\sigma_\min(A_r). \end{aligned} $$