11
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ You may get better answers if you specify what type of conclusions you're interested in. $\endgroup$ – David Ketcheson Jul 25 '12 at 13:37
  • $\begingroup$ @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. $\endgroup$ – Ivan Jul 26 '12 at 6:35
  • $\begingroup$ This is related to scicomp.stackexchange.com/questions/503/… $\endgroup$ – Geoffrey Irving Mar 11 '13 at 3:02
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ivan Jul 26 '12 at 6:39
  • $\begingroup$ 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. $\endgroup$ – Arnold Neumaier Jul 26 '12 at 13:01
  • $\begingroup$ 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. $\endgroup$ – Ivan Jul 26 '12 at 17:02
  • $\begingroup$ 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. $\endgroup$ – Arnold Neumaier Jul 26 '12 at 17:11
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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