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

Hello,

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?

share|improve this question
    
Unless I'm missing something, the same $U$ works since diagonal matrices commute with everything... –  Paul Siegel Jul 14 '11 at 2:38
3  
Paul, that is only true if the diagonal matrix is scalar. –  MTS Jul 14 '11 at 3:41
    
:) 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. –  Martin McCormick Jul 14 '11 at 3:54
    
Now I'm definitely confused... are we not working over a field? What does positive definite mean over a noncommutative ring? –  Paul Siegel Jul 14 '11 at 12:49
2  
@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}$ –  Federico Poloni Jul 14 '11 at 13:12
show 1 more comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
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? –  Martin McCormick Jul 14 '11 at 14:08
    
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. –  David Speyer Jul 14 '11 at 17:25
    
Excellent, thanks that is very helpful! –  Martin McCormick Jul 15 '11 at 12:59
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.