3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Feb 25, 2012 at 19:12
  • $\begingroup$ 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. $\endgroup$
    – alex
    Feb 26, 2012 at 4:38

1 Answer 1

5
$\begingroup$

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

$\endgroup$

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.