5
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ The interlacing theorem does not apply to only positive definite matrices, but for all symmetric matrices. So the interlacing theorem applies to singular values as well by considering the fact that nonnegative eigenvalues of [0 A*; A 0] are equal to singular values of A (as mentioned by Ben Grossmann) $\endgroup$ May 30, 2022 at 12:12

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Something is wrong with this answer. $\begin{bmatrix} 1&1 \\ 1&-1 \end{bmatrix}$ has singular values $\sqrt{2}$ and $\sqrt{2}$. (Note: Both square roots are the positive one!) We do not have $1 \in [\sqrt{2}, \sqrt{2}]$. $\endgroup$ May 4, 2023 at 15:36
  • 1
    $\begingroup$ @DavidESpeyer Perhaps I should have been more specific about what exactly the the result should be: in general, if $A_0$ is a submatrix of $A$ obtained by deleting $k$ rows and $k$ columns, we have $\sigma_{i+2k}(A) \leq \sigma_i(A_0) \leq \sigma_i(A)$ (with the left bound applying only if $i + 2k \leq n$), which for your example means that we only end up with an upper bound for the singular value. In terms of $M$ and $M_0$, the eigenvalues of $M_0$ are $-1,1$ and the eigenvalues of $M$ are $-\sqrt{2},-\sqrt{2},\sqrt{2},\sqrt{2}$; these eigenvalues interlace as expected. $\endgroup$ May 4, 2023 at 15:45
  • $\begingroup$ Thanks! (I'm working on mathoverflow.net/questions/446147 , so I want bounds for the smallest singular value.) $\endgroup$ May 4, 2023 at 15:56
6
$\begingroup$

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 row $b$ from this matrix (for simplicity lets take the last row). 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 formula 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 therefore 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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .