Let $A$ be a $m\times n_1$ matrix, $B$ a $m\times n_2$ matrix and $C=[A B]$ the $m\times(n_1+n_2)$ matrix obtained by concatenating the columns of $A$ and $B$.

I have observed numerically for thousands of examples (taking $A$ and $B$ to be Gaussian random matrices) that, if $m> (n_1+n_2)$, then $\sigma_1(C)<{\rm min}(\sigma_1(A),\sigma_1(B))$ where $\sigma_1$ is the smallest singular value.

Can this be proved?

EDIT: I have found the paper "Principal Submatrices IX: Interlacing Inequalities for Singular Values of Submatrices", by R.C.Thompson, which states the following theorem:

Let $C$ be an $m \times n$ matrix with singular values $\alpha_1\ge \alpha_2\ge...$. Let $B$ be a $p \times q$ submatrix of $C$, with singular values $\beta_1\ge \beta_2\ge...$. Then $\beta_i\ge \alpha_{i+(m-p)+(n-q)}$ for $i\leq {\rm min}(p+q-m,p+q-n)$.

If I take $p=m$ and $i=q$, I have $\beta_q\geq \alpha_n$ which means the smallest singular value of $C$ is smaller than the smallest singular value of $B$, which is what I want.

However, I have only verified this in numerical simulations when $m\gg n$. Why?

  • 1
    $\begingroup$ But the theorem should hold both for $A$ and for $B$... $\endgroup$ – thedude Nov 19 '19 at 18:31

You need $i\le\min(p+q-m,p+q-n)$. When $p=m$, this means $i\le\min(q,\,m+q-n)$. You cannot put $i=q$ unless $q\le m+q-n$ (i.e. unless $n\le m$).

  • $\begingroup$ You are right, with the observation that, in the notation of the original question, it should be $n_1+n_2<m$. $\endgroup$ – thedude Nov 19 '19 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.