Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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'$?

share|improve this question
    
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 '12 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 '12 at 4:38

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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