Eigenvalue decomposition of the sum: A (symmetric) + D (diagonal)

Suppose $A$ is a real symmetric matrix and its eigenvalue decomposition $V \Lambda V^T$ is given. It is easy to see what happens with the eigenvalues of the sum $A + cI$ where $c$ is a scalar constant (see this question). Can we draw any conclusion in the general case $A + D$ where $D$ is an arbitrary diagonal matrix? Thanks.

Regards,

Ivan

• You may get better answers if you specify what type of conclusions you're interested in. – David Ketcheson Jul 25 '12 at 13:37
• @DavidKetcheson, yes, you are absolutely right. Actually, I am trying to find an efficient way of computing a sequence of matrix exponentials of the form $e^{A + D_i}$ where $A$ is fixed and $D_i$ are diagonal matrices. I was hoping to perform the eigenvalue decomposition of $A$ only once and then use it somehow to account for the correction introduced by diagonal matrices. Unfortunately, $A$ and $D_i$ are not commuting in general, so $e^{A + D_i} \neq e^A e^{D_i}$. I would be grateful if you could share any ideas about it. Thanks. – Ivan Jul 26 '12 at 6:35
• This is related to scicomp.stackexchange.com/questions/503/… – Geoffrey Irving Mar 11 '13 at 3:02

One can say very little, except for generalities such as that the eigenvalues change continuously with the entries of $D$.

You can see by symbolic computation in the 2 by 2 case that nothing strong can be expected.

• Thank you for the reply, I knew I would hear something like this. May I please ask you to have a look at my comment above. – Ivan Jul 26 '12 at 6:39
• the complexity of computing a matrix exponential and that of computing a spectral factorization is about the same. So no, there is no simple solution. What you can do, however, in case your diagonal matrices lie in a lowD subspace, to compute the relevant part of the exponential (or indeed, whatever you want to compute from it) for a number of specific choices well-distributed in your space of desired values, and then use an interpolation algorithm to approximate all others. – Arnold Neumaier Jul 26 '12 at 13:01
• Yes, I know that spectral decompositions are not cheap, what I meant is that if such a decomposition was needed to be performed only once for $A$ (having done this, $e^A$ is simply $V e^\Lambda V^T$) and all exponents with $A + D_i$ could be somehow derived from this single decomposition, then it would be reasonable to employ it. Otherwise, I am quite positive that it is a waste of time. Thanks for the suggestion about interpolation, I need to read a little bit about it. – Ivan Jul 26 '12 at 17:02
• I had meant to say if there were a cheaper way to compute the exponential when $D$ changes, there would also be one for the eigenvalue problem. But there isn't one. – Arnold Neumaier Jul 26 '12 at 17:11

Ming Gu and Stanley C. Eisenstat have studied this problem before, see the link: http://www.cs.yale.edu/publications/techreports/tr916.pdf

This paper solves the rank-one permutation problem, which cannot solve the problem here. If anyone meet the rank-one permutation problem, it helps.

• Adding a diagonal matrix is not a rank one correction, so I'm not sure how this paper helps in this case. – Christian Clason Mar 12 '13 at 17:58
• @ChristianClason: Right! I just realize it. Thanks for pointing it out! – skyuuka May 6 '13 at 3:28