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

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

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

$$A^{-1} = \sum_{i=1}^{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

  • 2
    $\begingroup$ Symmetry is to guarantee that the eigenvalues are real, and consequently eigenvectors of different eigenvalues are orthogonal. $\endgroup$ – Easy Mar 16 '13 at 6:29
  • 1
    $\begingroup$ 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. $\endgroup$ – Phoeniyx Sep 27 '13 at 19:52
  • $\begingroup$ 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. $\endgroup$ – Robert Smith Sep 27 '13 at 20:28
  • $\begingroup$ @Phoeniyx this is Exercise 2.19 of the Christopher Bishop's book $\endgroup$ – rtrtrt Apr 22 '19 at 16:32

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.

  • $\begingroup$ 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? $\endgroup$ – Robert Smith Mar 16 '13 at 7:10
  • $\begingroup$ 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. $\endgroup$ – copper.hat Mar 16 '13 at 7:26
  • $\begingroup$ 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. $\endgroup$ – Robert Smith Mar 16 '13 at 7:33
  • $\begingroup$ 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. $\endgroup$ – copper.hat Mar 16 '13 at 7:36
  • 1
    $\begingroup$ Copper.hat, this is such a superb answer. I was looking for the answer to this question for a whole day on Google! $\endgroup$ – Phoeniyx Sep 27 '13 at 19:52

The official solution (from the Tutor's edition of the solutions manual) is as follows (the matrix is called $\Sigma$ instead of $A$):

We can rewrite the r.h.s. of (2.48) in matrix form as $$\sum_{i=1}^D \lambda_i \mathbf{u}_i \mathbf{u}_i^T = \mathbf{U} \mathbf{\Lambda} \mathbf{U}^T = \mathbf{M}$$

where $\mathbf{U}$ is a $D \times D$ matrix with the eigenvectors $\mathbf{u}_1, \dots, \mathbf{u}_D$ as its columns and $\mathbf{\Lambda}$ is a diagonal matrix with the eigenvalues $\lambda_1, \dots, \lambda_D$ along its diagonal.

Thus we have

$$ \mathbf{U}^T \mathbf{M} \mathbf{U} = \mathbf{U}^T \mathbf{U} \mathbf{\Lambda} \mathbf{U}^T \mathbf{U} = \mathbf{\Lambda}$$

However, from (2.45)-(2.47), we also have that

$$ \mathbf{U}^T \mathbf{\Sigma} \mathbf{U} = \mathbf{U}^T \mathbf{\Lambda} \mathbf{U} = \mathbf{U}^T \mathbf{U} \mathbf{\Lambda} = \mathbf{\Lambda}$$

and so $\mathbf{M} = \mathbf{\Lambda}$ and (2.48) holds.

Moreover, since $\mathbf{U}$ is orthonormal, $\mathbf{U}^{-1} = \mathbf{U}^T$ and so:

$$ \mathbf{\Sigma}^{-1} = (\mathbf{U} \mathbf{\Lambda} \mathbf{U}^T)^{-1} = (\mathbf{U}^T)^{-1} \mathbf{\Lambda}^{-1} \mathbf{U}^{-1} = \mathbf{U} \mathbf{\Lambda}^{-1} \mathbf{U}^T = \sum_{i=1}^D \dfrac{1}{\lambda_i} \mathbf{u}_i \mathbf{u}_i^T $$

Where (2.45) is

$$ \mathbf{\Sigma} \mathbf{u}_i = \lambda_i \mathbf{u}_i $$

So that $ \mathbf{\Sigma} \mathbf{U} = \mathbf{\Lambda} \mathbf{U} $ is the eigenvector equation


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.