# Singular values of matrix sums

This is a follow-up question to this one about eigenvalues of matrix sums. Suppose you have matrices $A$ and $B$, and know their singular values. What can you say about the singular values of $A+B$?

For Hermitian matrices and eigenvalues, this question was answered by a famous theorem of Knutson and Tao, but I don't know of anything similar for the more general case of singular values. This result would have come in useful for an estimate that I needed. I was able to obtain the estimate in a differenr way, but now I'm curious about the question.

-
The natural question for singular values turns out to be "what can you say about the singular values of AB?" not "A+B". The inequalities are exactly the same as in the Hermitian sum case, except on the logs of the singular values. Not that this answers your question, of course. – Allen Knutson Jul 12 '10 at 3:29

The singular values of a $n \times m$ matrix A are more or less the eigenvalues of the $n+m \times n+m$ matrix $\begin{pmatrix} 0 & A \\\ A^* & 0 \end{pmatrix}$. By "more or less", I mean that one also has to throw in the negation of the singular values, as well as some zeroes. Using this, one can deduce inequalities for the singular values from that of the Hermitian matrices problem. This may even be the complete list of inequalities, though I don't know if this has already been proven in the literature.

http://terrytao.wordpress.com/2010/01/12/254a-notes-3a-eigenvalues-and-sums-of-hermitian-matrices/

-
There is a very nice work-in-progress by Alekseev-Podkopaeva-Szenes about this. Anton Alekseev rported on this work in a great talk: youtube.com/watch?v=nt-RE2IZJ8w&feature=plcp – DamienC Aug 16 '12 at 7:39

Edit: as pointed out below in comments, what I wrote originally is wrong. I will try to come back later and repair this, but if someone else has a better answer before then, I may just delete this "answer".

Since the $k$th singular value is the distance to matrices of rank $\leq k-1$, one clearly has $s_k(A+B)\leq s_k(A)+s_k(B)$. This ought to be sharp in the sense that one ought to be able to find matrices $A$ and $B$ where equality is attained for all singular values $s_1,s_2,\dots$ (and the examples can be positive and commuting, I think, but I haven't thought about this too much).

As for trying to find inequalities in the other direction, I think taking $A=-B$ kills the most naive attempts.

-
It's definitely a step towards the answer. No need to apologize. – Peter Shor Jul 11 '10 at 23:39
I don't understand the justification for the inequality $s_k(A+B) \leq s_k(A)+s_k(B)$. The matrices $A=diag(1,0)$, $B=diag(0,1)$ appear to form a counterexample. If you want in addition $k\geq 1$, as implied by your first sentence, then $A=diag(1,0,0)$, $B=diag(0,1,0)$ is a counterexample. – angela Jul 11 '10 at 23:46
I'm using the convention that an $n\times n$ matrix has $n$ singular values of which $s_1$ is the largest and $s_n$ the smallest. Also, I should have said that $s_k(M)$ is the minimum value of $\Vert M-F\Vert$ where $F$ runs over all matrices of rank at most $k-1$ (a silly mistake in my original version, which I've now corrected.) Does that help at all? – Yemon Choi Jul 12 '10 at 0:06
so if $A=diag(1,0,0)$ and $B=diag(0,1,0)$, then $s_2(A)=s_2(B)=0$, $s_2(A+B)=1$, so the inequality we are discussing gives $1 \leq 0+0$. – angela Jul 12 '10 at 0:24
@angela: yes, you're right, I was being stupid. I'll edit the post accordingly and have a think later as to what the correct statement is (certainly one knows that $(s_1^p+\dots s_n^p))^{1/p}$ is subadditive for any $1\leq p <\infty$, so that indicates something should be true...) – Yemon Choi Jul 12 '10 at 0:41

There are many kinds of inequalities one can obtain: In fact, the following quite general statement holds:

Let $n,m \in \mathbb{N}$, and let $q=min(n,m)$. For any norm $\| \cdot \|$ on $\mathbb{R}^q$ which is invariant under signed permutations*, and any two real $n \times m$ matrices $A,B$:$$\|s_1(A+B),\dots,s_q(A+B) \|\le \|s_1(A),\dots,s_q(A) \| + \|s_1(B),\dots,s_q(B) \|$$

This is holds since one can prove every such norm induces an orthogonally-invariant norm on the space of $n \times m$ matrices in a natural way. (see here for details).

In particular the quantity $(s_1^p+\dots s_q^p)^{1/p}$ is subadditive for any $1 \le p \le \infty$ (as mentioned also by Yemon Choi).

*such a norm is called a symmetric gauge function

-