Eigenvalues of A+B where A is symmetric positive definite and B is diagonal - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T10:21:16Z http://mathoverflow.net/feeds/question/34252 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/34252/eigenvalues-of-ab-where-a-is-symmetric-positive-definite-and-b-is-diagonal Eigenvalues of A+B where A is symmetric positive definite and B is diagonal Fumiyo Eda 2010-08-02T12:15:32Z 2010-08-26T13:25:33Z <p>If I have a symmetric positive definite matrix A and a diagonal matrix B, and I know the eigenvalues of both A and B (by iterative numerical computation in A's case and trivially for B), is there any way I can rapidly find the eigenvalues of the matrix M=A+B?</p> <p>(I would be surprised if it helps, but I actually have the stronger condition that A is Laplacian. Unfortunately, the entries of the matrix B are large, and so B cannot be considered a small "perturbation" to A. Finally, I only really have the extremal eigenvalues of A, though I am only hoping to find the extremal eigenvalues of A+B.)</p> http://mathoverflow.net/questions/34252/eigenvalues-of-ab-where-a-is-symmetric-positive-definite-and-b-is-diagonal/34256#34256 Answer by Gerry Myerson for Eigenvalues of A+B where A is symmetric positive definite and B is diagonal Gerry Myerson 2010-08-02T12:42:20Z 2010-08-02T12:42:20Z <p>If $A=\pmatrix{1&amp;0\cr0&amp;9\cr}$ and $B$ is diagonal with eigenvalues 4 and $-4$ then $A+B$ could have eigenvalues 5 and 5 or it could have eigenvalues 13 and $-3$. Doesn't really look like you can get the eigenvalues of $A+B$ from the given information. </p> http://mathoverflow.net/questions/34252/eigenvalues-of-ab-where-a-is-symmetric-positive-definite-and-b-is-diagonal/34263#34263 Answer by Aaron Meyerowitz for Eigenvalues of A+B where A is symmetric positive definite and B is diagonal Aaron Meyerowitz 2010-08-02T14:22:29Z 2010-08-02T14:22:29Z <p>I doubt it. At least it shouldn't be easier than the case where you have the sum of two arbitrary positive definite matrices A',B' with known eigenvalues and eigenvectors. Then you could use an orthogonal basis of eigenvectors for B' and set $A=PA'P^{-1}$ and $B=PB'P^{-1}$. B would be diagonal and AB would have the same eigenvalues as A'B'. Couldn't one even make B=I by choosing an orthonormal basis?</p> http://mathoverflow.net/questions/34252/eigenvalues-of-ab-where-a-is-symmetric-positive-definite-and-b-is-diagonal/34268#34268 Answer by Tracy Hall for Eigenvalues of A+B where A is symmetric positive definite and B is diagonal Tracy Hall 2010-08-02T15:16:43Z 2010-08-02T15:16:43Z <p>The work that you have put into finding the eigenvalues of $A$ is not going to save you time, except that it does give you a bound (together with the maximum eigenvalue of $B$) for how large you have to make $\alpha$ to find the maximum eigenvalue of $\alpha I - A -B$ iteratively--and the row sums would give you a bound on that anyway. In any case finding the extremal eigenvalues of $A+B$ shouldn't be any harder than for $A$, since they are both the same size and equivalently sparse, but if you are repeating this many times with the same $A$ and different $B$ I don't see any shortcuts to iterating each one.</p> http://mathoverflow.net/questions/34252/eigenvalues-of-ab-where-a-is-symmetric-positive-definite-and-b-is-diagonal/36757#36757 Answer by Jiahao Chen for Eigenvalues of A+B where A is symmetric positive definite and B is diagonal Jiahao Chen 2010-08-26T13:00:18Z 2010-08-26T13:00:18Z <p><a href="http://mathoverflow.net/questions/4224/eigenvalues-of-matrix-sums" rel="nofollow">This previous MO question</a> may be relevant.</p> http://mathoverflow.net/questions/34252/eigenvalues-of-ab-where-a-is-symmetric-positive-definite-and-b-is-diagonal/36761#36761 Answer by Denis Serre for Eigenvalues of A+B where A is symmetric positive definite and B is diagonal Denis Serre 2010-08-26T13:25:33Z 2010-08-26T13:25:33Z <p>The ambiguity in your question is the word 'rapidly'.</p> <p>If you want to have an information on the eigenvalues of $A+B$, without any extra information besides those given in the question, then this is the problem raised By H. Weyl in 1912. The answer was conjectured in 1962 by A. Horn, and this conjecture was proved by A. Knutson and T. Tao in 1999. It is one of the works for which Tao received a Fields medal. So, the answer is that the spectrum may be any vector in a polytope in ${\mathbb R}^n$ whose definition is given recursively in terms of the size $n$ of the matrix. A nice expository paper is R. Bhatia, Linear algebra to quantum cohomology: the story of A. Horn’s inequalities. Amer. Math. Monthly, 108 (2001), pp 289–318.</p> <p>Historically, the interest in this question came from Quantum Mechanics. </p>