Singular values of differences of square matrices - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T06:20:54Z http://mathoverflow.net/feeds/question/56634 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56634/singular-values-of-differences-of-square-matrices Singular values of differences of square matrices Aaron 2011-02-25T14:38:06Z 2012-02-25T18:21:13Z <p>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$?</p> <p>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'$?</p> http://mathoverflow.net/questions/56634/singular-values-of-differences-of-square-matrices/56650#56650 Answer by suVRit for Singular values of differences of square matrices suVRit 2011-02-25T17:13:49Z 2012-02-25T18:21:13Z <p><strong>Update.</strong> One more point worth mentioning here is that for positive definite $A$ and $B$, the following inequality can be shown:</p> <p>\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$.</p> <h2>Original answer</h2> <p>The choice $\epsilon' = \sigma_1(A)+\sigma_1(B)$ works, and in general cannot be improved upon: simply take $B=-A$.</p> <p>By restricting to special classes of matrices, you can probably obtain more interesting upper-bounds.</p> <h2>Some details.</h2> <p>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.</p> <p>A lower-bound on $\sigma_1(C) =: \|A-B\|$ is more exciting. For example, the following inequality (see Problem III.6.13, of <em>Matrix Analysis</em> by R. Bhatia) can be shown:</p> <p>$$(*)\qquad\max_j |\sigma_j(A)-\sigma_j(B)| \le \|A-B\|.$$</p>