Welcome to MathOverflow

Question

2

Suppose $A, B \in \mathbb{R}^{n \times n}$. Let $\sigma_1(A),\ldots,\sigma_n(A)$ be the singular values of $A$, and let $\sigma_1(B),\ldots,\sigma_n(B)$ be the singular values of $B$. If I know these quantities, what can I say about the largest singular value of $C = A - B$?

In particular, if I know that for all $i$, $|\sigma_i(A) - \sigma_i(B)| \leq \epsilon$, does this imply that $|\sigma_1(C)| \leq \epsilon'$ for any $\epsilon'$?

flag	asked Feb 25 2011 at 14:38 Aaron 550●2●8

	Inequalities between eigenvalues for A and B hermitian (not too wild, since you've tagged graph-theory) are given by "linear inequalities of Horn type," which are based on Littlewood-Richardson coefficients. There seem to be similar results for singular values. Take a look at arxiv.org/abs/math/0301307 – John Wiltshire-Gordon Feb 25 2012 at 19:12
	The answer to the question in your final sentence is no. Indeed, consider $A = {\rm diag}(a,-a)$ and $B={\rm diag}(-a,a)$ for some $a \neq 0$. Then $\sigma_1(A)=\sigma_1(B)=a$ and $\sigma_2(A)=\sigma_2(B)=-a$, so you can take $\epsilon$ as small as you wish. However, for $C=A-B={\rm diag}(2a,2a)$, we will have $\sigma_1(C)=2a$, so no $\epsilon'$ can work. – alex Feb 26 2012 at 4:38

S. Sra · Answer 1 · 2012-02-25 18:21:13Z UTC

Update. One more point worth mentioning here is that for positive definite $A$ and $B$, the following inequality can be shown:

\begin{equation*} \sigma_j(A-B) \le \sigma_j(A \oplus B),\qquad j=1,2,\ldots,n, \end{equation*} where $A\oplus B$ denotes the direct sum of $A$ and $B$.

Original answer

The choice $\epsilon' = \sigma_1(A)+\sigma_1(B)$ works, and in general cannot be improved upon: simply take $B=-A$.

By restricting to special classes of matrices, you can probably obtain more interesting upper-bounds.

Some details.

A standard result is: $\sigma_1(X+Y) \le \sigma_1(X)+\sigma_1(Y)$, which implies that $\sigma_1(A-B) \le \sigma_1(A) + \sigma_1(B)$. This inequality suggests the bound on $\epsilon'$ mentioned above.

A lower-bound on $\sigma_1(C) =: \|A-B\|$ is more exciting. For example, the following inequality (see Problem III.6.13, of Matrix Analysis by R. Bhatia) can be shown:

$$(*)\qquad\max_j |\sigma_j(A)-\sigma_j(B)| \le \|A-B\|.$$

Singular values of differences of square matrices

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

Original answer

Some details.

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.