Singular value inequality for sum of 2 matrices

Question

I found a theorem mentioned in a couple of places, but could not find a proof. The theorem states the following:

Let $A, B \in \mathbb{F^{m,n}}$, $p=min(m,n)$ with singular values $\sigma_1(A) \geqslant...\geqslant \sigma_p(A)$ and $\sigma_i(B) \geqslant...\geqslant \sigma_p(B)$ respectively, then $\sigma_{i+j-1}(A+B) \leqslant \sigma_i(A) + \sigma_j(B)$.

I am looking for a proof of the above. Thanks in advance.

Answer 1

Answering my own question (taking cue from the comment of zimbra314).

This can be proved using Courant-Fischer min-max theorem:

$\sigma_{k+1} = \underset{V \subseteq \mathbb{F}^m,dimV=m-k}{min} \ \ \underset{v \in V,\Vert v \Vert = 1}{max} \Vert Mv \Vert$, where $M \in \mathbb{F}^{n,m}$ and $\sigma_i$ is the $i$-th singular value in decreasing order.

Using the theorem, we get:

$ \sigma_{i+j+1}(A+B) = \underset{V \subseteq \mathbb{F}^m,dimV=m-i-j}{min} \ \ \underset{v \in V,\Vert v \Vert = 1}{max} \Vert (A+B)v \Vert \tag{1}\label{1} $

Let $V_1,V_2 \subseteq \mathbb{F}^m,\ dimV_1=m-i,\ dimV_2=m-j$ are chosen so that $$\underset{v \in V_1,\Vert v \Vert = 1}{max}\Vert Av \Vert=\sigma_{i+1}(A)\ and\ \underset{v \in V_2,\Vert v \Vert = 1}{max}\Vert Bv \Vert=\sigma_{j+1}(B)$$ This is possible again due to the min-max theorem.

Now, let $W = V_1 \cap V_2$ $$ \begin{align} \underset{v \in W, \Vert v \Vert = 1}{max} \Vert (A+B)v \Vert &\leqslant \underset{v \in W, \Vert v \Vert = 1}{max} \left(\Vert Av \Vert + \Vert Bv \Vert \right) \\ &\leqslant \underset{v \in W, \Vert v \Vert = 1}{max} \Vert Av \Vert + \underset{v \in W, \Vert v \Vert = 1}{max} \Vert Bv \Vert \\ &\leqslant \underset{v \in V_1, \Vert v \Vert = 1}{max} \Vert Av \Vert + \underset{v \in V_2, \Vert v \Vert = 1}{max} \Vert Bv \Vert \\ &=\sigma_{i+1}(A) + \sigma_{j+1}(B) \tag{2}\label{2} \end{align} $$

Note that $dimW \geqslant m-i-j$, and by restrictig the choice of $v$ in $(\ref{2})$ to a subset $V \subseteq W$ with $dimV=m-i-j$, we can write $$ \underset{v \in V, \Vert v \Vert = 1}{max} \Vert (A+B)v \Vert \leqslant \sigma_{i+1}(A) + \sigma_{j+1}(B) $$

We have proved the upper-bound for some example of $V \in \mathbb{F}^m, dimV=m-i-j$, so clearly this holds for the minimum over all $V$, i.e. we can write $$ \underset{V \subseteq \mathbb{F}^m,dimV=m-i-j}{min} \ \ \underset{v \in V,\Vert v \Vert = 1}{max} \Vert (A+B)v \Vert \leqslant \sigma_{i+1}(A) + \sigma_{j+1}(B)\\ \implies \sigma_{i+j+1}(A+B) \leqslant \sigma_{i+1}(A) + \sigma_{j+1}(B)\ [using\ (\ref{1})] $$ Writing $i=i-1$ and $j=j-1$, we get the desired result.