Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
What do you mean by "the Laplacian"? Should one understand it as the discretization of the continuous Laplacian in a box? If yes all eigenvalues and eigenvectors can be computed by hand. The answer to your question is "no" in some generic sense. There are obstructions to what you want to do in the limit of infinite matrix size. Maybe the best known one would be that for "B random" the matrix "A + B" exhibits localization, whereas "A" has extended states. So the eigenvectors differ (the eigenvalues also do, since one set obeys clock statistics and the other poisson). –  Helge Aug 2 '10 at 14:42
    
Is B also positive? –  Loick Aug 2 '10 at 14:45
    
"$A$ is Laplacian" --- do you mean it is the Laplacian matrix of some simple graph? –  Laurent Lessard Aug 2 '10 at 17:07
    
Helge: Laplacian means it is the Laplacian matrix of a graph Loick: None of the elements of B are negative, but they are often zero. Laurent: Right, that's what I mean. –  Fumiyo Eda Aug 3 '10 at 11:59
add comment

5 Answers

up vote 4 down vote accepted

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?

share|improve this answer
3  
If you only know the eigenvalues, there are a bunch of linear inequalities constraining the answer. People usually think about the (nonobviously) equivalent problem where the matrices are Hermitian; see front.math.ucdavis.edu/9908.5012 –  Allen Knutson Aug 5 '10 at 20:36
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

This previous MO question may be relevant.

share|improve this answer
add comment

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.

share|improve this answer
2  
I think I have confused you - or maybe I am confused myself! I know not only the eigenvalues of the matrices A and B but the matrices themselves. So, for example, I know that (e.g.) A=diag(1,9) and B=diag(4,-4). Which imply that the eigenvalues of A+B must be 5 and 5. Does that make sense? I'm not trying to solve the more general problem of "I know I have two matrices with the following eigenvalues, now what are the eigenvalues of their sum?" I'm just trying to compute the eigenvalues of the sum A+B rapidly, because there are fast ways to get the eigenvalues of Laplacian and diagonal matrices. –  Fumiyo Eda Aug 2 '10 at 13:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.