33
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 12, 2010 at 3:29

3 Answers 3

30
$\begingroup$

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/

$\endgroup$
1
1
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ It's definitely a step towards the answer. No need to apologize. $\endgroup$
    – Peter Shor
    Jul 11, 2010 at 23:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – angela
    Jul 11, 2010 at 23:46
  • $\begingroup$ 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? $\endgroup$
    – Yemon Choi
    Jul 12, 2010 at 0:06
  • 1
    $\begingroup$ 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$. $\endgroup$
    – angela
    Jul 12, 2010 at 0:24
  • $\begingroup$ @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...) $\endgroup$
    – Yemon Choi
    Jul 12, 2010 at 0:41
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Is there a way to use subadditivity to show that $\lVert s_1(A+B),\dots,s_q(A+B)\rVert\geq \lVert s_1(A),\dots,s_q(A)\rVert$ if $A$ and $B$ are orthogonal with respect to Hilbert-Schmidt inner product? $\endgroup$
    – LFH
    Mar 23, 2018 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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