Sum of Singular Values of (A+B)

How we can prove that:

$$\sum_{i=1}^n\sigma_i(A+B)\leq\sum_{i=1}^n\sigma_i(A)+\sum_{i=1}^n\sigma_i(B)$$

Where $\sigma_i$s are singular values $\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_n\geq0$ .

Solution 1:

$$ \sum_{i=1}^n \sigma_i(A) = \sup\{|\text{trace}(AU)| : \text{$U$ is unitary}\} .$$ To see this, note by SVD that $A = V_1 \Sigma V_2$ where $V_1$ and $V_2$ are unitary, and $\Sigma$ is the diagonal matrix of singular values. Note also that $\text{trace}(XY) = \text{trace}(YX)$, and so $$ \sup\{|\text{trace}(AU)| : \text{$U$ is unitary}\} = \sup\{|\text{trace}(\Sigma U)| : \text{$U$ is unitary}\} .$$ To get the $\le$ use $U = I$. To get the $\ge$ multiply it out and see $ |\text{trace}(\Sigma U)| \le \text{trace}(\Sigma)$.

Hence \begin{aligned} \sum_{i=1}^n \sigma_i(A+B) &= \sup\{|\text{trace}((A+B)U)| : \text{$U$ is unitary}\} \\&\le \sup\{|\text{trace}(AU)| + |\text{trace}(BU)| : \text{$U$ is unitary}\} \\&\le \sup\{|\text{trace}(AU)| : \text{$U$ is unitary}\} + \sup\{|\text{trace}(BU)| : \text{$U$ is unitary}\} .\end{aligned}

Solution 2:

As we know the sum of singular values is equivalent to unitarily invariant norms. Matrix Analysis Book So instead of proving the $$\sum_{i=1}^n\sigma_i(A+B)\leq\sum_{i=1}^n\sigma_i(A)+\sum_{i=1}^n\sigma_i(B)$$ you can show $\||A+B|\|\leq \||A|\|+\||B|\|$ and the latter one is true because of norm property.