Welcome to MathOverflow

Question

4

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?

flag	asked Jul 14 2011 at 1:02 Martin McCormick 43●2

Unless I'm missing something, the same $U$ works since diagonal matrices commute with everything... – Paul Siegel Jul 14 2011 at 2:38

3

Paul, that is only true if the diagonal matrix is scalar. – MTS Jul 14 2011 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 2011 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 2011 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 2011 at 13:12

show 1 more comment

David Speyer · Accepted Answer · 2011-07-14 12:53:01Z UTC

5

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.

answered Jul 14 2011 at 12:53

David Speyer
55k●3●102●236

	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 2011 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 2011 at 17:25
	Excellent, thanks that is very helpful! – Martin McCormick Jul 15 2011 at 12:59

Eigendecomposition after multiplying by diagonal matrix

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.