## 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 2010 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.

See also my blog post on this at

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 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.

Edit: on rereading your question I see that this doesn't really answer it at all. Sorry!

-
It's definitely a step towards the answer. No need to apologize. – Peter Shor Jul 11 2010 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 2010 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 2010 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 2010 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 2010 at 0:41