Interlacing Theorem on Singular Values

Your intuition is wrong; singular values are "nice" that way.

In particular: suppose that $A$ can be divided as $$ A = \pmatrix{A_0 & B\\C & D} $$ The interlacing property compares the singular values of $A$ to the singular values of $A_0$. However, the singular values of $A$ are equal to the non-negative positive eigenvalues of the matrix $$ M = \pmatrix{0 & A^*\\ A & 0} = \pmatrix{0 & 0 & A_0^* & C^*\\0 & 0 & B^* & D^*\\ A_0 & B & 0 & 0\\C & D & 0 & 0}. $$ By applying the interlacing inequality to this larger symmetric matrix and its principal submatrix $$ M_0 = \pmatrix{0 & A_0^*\\A_0 & 0}, $$ we end up with the interlacing inequality for singular values.

I know this question is a few years old, but it pops up as first result on google and I am not completely satisfied with the first answer given, so I'll add the answer I came up with here. Feel free to comment if you think there is a flaw in this one.

So, consider any matrix $A$. Now lets remove one column $b$ from this matrix (for simplicity lets take the last column). So $$A=\begin{pmatrix}A_0 \\ b\end{pmatrix}$$ Now, we have that $$AA^*=\begin{pmatrix}A_0A_0^* & A_0b^* \\ bA_0^* & bb^*\end{pmatrix}$$ So, $A_0A_0^*$ is a submatrix of $AA^*$. Thus the interlacing theorem holds for the eigenvalues of these matrices, and hence also for the singular values of $A$ and $A_0$.

Now you can do the same argument removing a column of $A$ and considering $A^*A$ and $A_0^*A_0$. However, there is a slight difference in my answer compared to the original interlacing theorem. So, the original one states that for a symmetric matrix of size $n\times n$ and a principal submatrix of size $m\times m$ the eigenvalues satisfy (eigenvalues sorted from small to large, i.e., $\alpha_1\leq\alpha_2\leq\ldots$) $$\alpha_j\leq\beta_j\leq\alpha_{n-m+j}.$$ Note, that we are only "punished" once for removing one row/column pair, i.e., the upper bound $\alpha_{n-m+j}$ increases by one eigenvalue per row/column pair removed. In my considerations above the interlacing theorem was applied seperately for removing one row/column, so we would get punished twice here. The resulting formular for singular values of a matrix $A\in\mathbb{C}^{m\times n}$ and its principal submatrix $A_0\in\mathbb{C}^{m_0\times n_0}$ should therefor be $$\alpha_j\leq\beta_j\leq\alpha_{m+n-m_0-n_0+j}.$$

As another side node: Removing rows/columns is actually just a special case, you could apply any orthogonal projection to the rows/columns and the interlacing theorem would hold (Look up e.g., Poincaré separation theorem).