Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This shouldn't be too difficult but I can't find a satisfactory proof.

Show that a real, symmetric matrix A satisfying the eigenvector equation $Au_{i} = \lambda u_{i}$ cam be expressed as an expansion of its eigenvalues in the following way:

$$A = \sum_{i}^{D}\lambda_{i}u_{i}u_{i}^{T}$$ and similarly, the inverse $A^{-1}$ can be expressed as

$$A^{-1} = \sum_{i}^{D}\frac{1}{\lambda_{i}}u_{i}u_{i}^{T}$$

I suppose this is an alternative form of eigendecomposition. I know this can be proved using $AU = U\Lambda$ where $\Lambda$ is a diagonal matrix and $U$ an orthogonal matrix, but it's a somewhat tedious procedure.

An additional question: Do I need to assume a real, symmetric matrix?

Thanks a lot

share|improve this question
2  
Symmetry is to guarantee that the eigenvalues are real, and consequently eigenvectors of different eigenvalues are orthogonal. –  Easy Mar 16 '13 at 6:29
    
Robert, did you get this question from the Machine Learning book from Christopher Bishop? :) In any case, what I still don't understand is how $$ \sum_{k}{(\lambda_{k}u_{k}^{T}x)u_{k}} = \sum_{k}{\lambda_{k}u_{k}u_{k}^{T}x} $$ I worked it out by manually expanding 2x1 $u$ and $x$ vectors. But, I can't figure out the general proof. Thanks. –  Phoeniyx Sep 27 '13 at 19:52
    
Yes, it was from Bishop's book. By the way, you should have added this as a comment, not as another answer. You can change the order of the terms there because you're dealing with values, not with matrices. Therefore, there are no issues with the ordering of terms. –  Robert Smith Sep 27 '13 at 20:28
add comment

1 Answer

up vote 3 down vote accepted

The proof using $AU = U\Lambda$ is not tedious. Since the $U$ is orthogonal, you have $U^{-1} = U^T$, so $A = U \Lambda U^T$. Then $$Ax = U \Lambda U^T x = U \Lambda \begin{bmatrix} u_1^T x \\ \vdots \\ u_n^T x \end{bmatrix} = U \begin{bmatrix} \lambda_1 u_1^T x \\ \vdots \\ \lambda_n u_n^T x \end{bmatrix} = \sum_k (\lambda_k u_k^T x) u_k = \sum_k \lambda_k u_k u_k^T x = (\sum_k \lambda_k u_k u_k^T)x$$

Hence $A=\sum_k \lambda_k u_k u_k^T$.

Since $AU = U\Lambda$, inverting both sides gives $U^T A^{-1} = \Lambda^{-1} U^T$, and hence $A^{-1} = U\Lambda^{-1} U^T$. Applying the above result to $A^{-1}$, noting that $\Lambda^{-1}$ is just the diagonal matrix of the inverses of the diagonal elements of $\Lambda$, we have $A^{-1} = \sum_k \frac{1}{\lambda_k} u_k u_k^T$.

To address your other question, the same result holds for Hermitian matrices ($A^* = A$), with the proviso that the $U$ will be unitary rather than orthogonal (ie, may be complex).

A normal matrix ($A A^* = A^* A$) can also be expressed as above, except the eigenvalues may be complex (and eigenvectors, of course)

The matrix $\begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix} $ is real, but not symmetric, but does not have a basis of eigenvectors (hence it cannot be expressed as above).

The matrix $\begin{bmatrix} 0 & i \\ i & 0 \end{bmatrix} $ is symmetric but not real (it is normal). It can be unitarily diagonalized, but the eigenvalues and eigenvectors are complex.

share|improve this answer
    
Excellent answer. In the first part, you're using partitioned matrices, right? I'm not too comfortable using them, so I had to expand the products. By the way, do you really need $x$ in $Ax$? In the sum $\sum_{k} (\lambda_{k}u_{k}^{T}x)u_{k}$, why did you multiply $u_{k}$ on the right? –  Robert Smith Mar 16 '13 at 7:10
    
I don't know what you mean by partitioned matrices in this context. Yes, you need the $x$; the point of the $x$ was so that the terms $(\lambda u_k^T x) u_k$ could be written as $(\lambda u_k u_k^T) x$. When you have a product $By$ this is equal to $\sum_k y_k b_k$, where $b_k$ is the $k$th column of $B$, and $y_k$ is the $k$th component of $y$, a scalar. This is why the $u_k$ are on the right. –  copper.hat Mar 16 '13 at 7:26
    
Maybe you know them as block matrices, e.g. $U^{T}$ contains rows with eigenvectors of $A$, but instead of writing every vector, we just use $\begin{bmatrix} u_1^T \\ \vdots \\ u_n^T \end{bmatrix}$. Then in your third step you have $[u_{1} \cdots u_{n}]$ where each $u_{i}$ is a column vector, so you multiply that $1XN$ matrix by a $NX1$ matrix. –  Robert Smith Mar 16 '13 at 7:33
    
Well, they are $n \times n$, but arranged as $n$ columns or rows as the case may be. The proof is basically just multiplying the matrices out in a convenient format. –  copper.hat Mar 16 '13 at 7:36
    
Now that I have read your edit, your procedure makes perfect sense. Last thing, where do I find more information about the representation $AU = U\Lambda$ of the eigenvector equation? –  Robert Smith Mar 16 '13 at 7:40
show 3 more comments

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.