Interlacing Theorem on Singular Values Does the Cauchy's interlacing theorem hold for "singular values" of matrices too? I saw on this publication first Theorem that it does. It states that singular values of a matrix interlace the singular values of its principal sub-matrices. I would have thought given the original (celebrated) Cauchy's interlacing theorem that is on the "eigenvalues" of symmetric matrices and their sub-matrices, that to make interlacing statements about singular values we would need a restriction on positivity of the matrix. Is my intuition wrong? 
 A: 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.
A: 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).
