Singular values of differences of square matrices

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

-
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

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

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

-