If we possess the eigendecomposition of a positive definite matrix: $X = U \Sigma U^T$, is there an efficient way to compute the eigendecomposition of $D X D$ where $D$ is a diagonal matrix?

  • $\begingroup$ Unless I'm missing something, the same $U$ works since diagonal matrices commute with everything... $\endgroup$ – Paul Siegel Jul 14 '11 at 2:38
  • 4
    $\begingroup$ Paul, that is only true if the diagonal matrix is scalar. $\endgroup$ – MTS Jul 14 '11 at 3:41
  • $\begingroup$ :) If only it were that easy. Unfortunately a general diagonal matrix will change the eigenvalues and eigenvectors... It seems like there should be a way to update the eigendecomposition but I'm stumped. This is for an implementation of Gaussian belief propagation. First mathoverflow question--thanks for your thoughts. $\endgroup$ – Martin McCormick Jul 14 '11 at 3:54
  • $\begingroup$ Now I'm definitely confused... are we not working over a field? What does positive definite mean over a noncommutative ring? $\endgroup$ – Paul Siegel Jul 14 '11 at 12:49
  • 3
    $\begingroup$ @Paul: diagonal matrices don't commute with everything, even on $\mathbb{Z}$: $\begin{bmatrix}1 & 1\\\\1 & 1 \end{bmatrix}\begin{bmatrix}2 & 0\\\\0 & 1 \end{bmatrix}\neq\begin{bmatrix}2 & 0\\\\0 & 1 \end{bmatrix} \begin{bmatrix}1 & 1\\\\1 & 1 \end{bmatrix}$ $\endgroup$ – Federico Poloni Jul 14 '11 at 13:12

Write $\Sigma$ as $T^2$, for positive definite $T$. Set $Y = U T$.

So the eigenvalues of $X$ are the squares of the singular values of $Y$, and what you want to compute are the singular values of $DY$.

There is no formula which gives the singular values of $DY$ in terms of those of $Y$ and $D$. However, there is a famous set of inequalities relating the three sets of singular values, called the Horn inequalities. See Bhatia's article Linear Algebra to Quantum Cohomology, particularly Section 11, for a gentle introduction.

  • $\begingroup$ Thanks. Yes I came across Horn's stuff. So is this related because if you exponentiate the matrices it is addition of exponents as in the paper? $\endgroup$ – Martin McCormick Jul 14 '11 at 14:08
  • $\begingroup$ No and yes. It is not true that $e^{A} e^{B} = e^{A+B}$ so, if $A+B=C$, it need not be true that the eigenvalues of $e^A e^B$ are the exponentials of the eigenvalues of $e^C$. However, it is true that the set of all possible singular values of $e^A e^B$ is the exponential of the set of all possible eigenvalues for $A+B$. This is a theorem of Klyachko ams.org/mathscinet-getitem?mr=1799623 and it is discussed in section 11 of the refernce I give above. $\endgroup$ – David E Speyer Jul 14 '11 at 17:25
  • $\begingroup$ Excellent, thanks that is very helpful! $\endgroup$ – Martin McCormick Jul 15 '11 at 12:59

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.