8
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – Helge
    Aug 2, 2010 at 14:42
  • $\begingroup$ Is B also positive? $\endgroup$
    – Loick
    Aug 2, 2010 at 14:45
  • $\begingroup$ "$A$ is Laplacian" --- do you mean it is the Laplacian matrix of some simple graph? $\endgroup$ Aug 2, 2010 at 17:07
  • $\begingroup$ 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. $\endgroup$
    – Fumiyo Eda
    Aug 3, 2010 at 11:59

5 Answers 5

4
$\begingroup$

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?

$\endgroup$
2
  • 3
    $\begingroup$ 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 $\endgroup$ Aug 5, 2010 at 20:36
  • 1
    $\begingroup$ @AllenKnutson the updated link to Fulton's paper Eigenvalues, invariant factors, highest weights, and Schubert calculus is arxiv.org/abs/math/9908012 $\endgroup$
    – David Roberts
    Sep 26, 2021 at 0:49
8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

This previous MO question may be relevant.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Fumiyo Eda
    Aug 2, 2010 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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