Eigenvalues of A+B where A is symmetric positive definite and B is diagonal 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?
(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.)
 A: The ambiguity in your question is the word 'rapidly'.
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.
Historically, the interest in this question came from Quantum Mechanics. 
A: 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?
A: 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.
A: This previous MO question may be relevant.
A: If $A=\pmatrix{1&0\cr0&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. 
