# Eigenvalue Decomposition Explained

Sharing is caring

Eigenvalue decomposition or Eigendecomposition is the process of decomposing a matrix into its eigenvectors and eigenvalues. We can also transform a matrix into an Eigenbasis (the basis matrix where every column is an eigenvector).

### Why is the Eigendecomposition useful?

Matrix operations such as transformations or multiplications are computationally expensive. In applications such as machine learning, you often have thousands or millions of dimensions. Imagine you have to perform matrix transforms repeatedly on matrices in millions of dimensions. Even the best computers quickly reach their limits. But as we discussed before, operations are much simpler on diagonal matrices. So if we can decompose a matrix into a diagonal form before we apply any kind of costly operation, it makes our lives as well as the lives of our computers, much easier. Enter Eigendecomposition.

Remember, that for an eigenvector, multiplication with the transformation matrix A, is equivalent to multiplying with a simple scalar λ. If we expand this idea from vectors to matrices, most matrices can be decomposed into a matrix of column eigenvectors P, and a diagonal matrix D that is filled with eigenvalues on the main diagonal. When we multiply P and D, each column (each eigenvector) would be multiplied with the corresponding scalar (each eigenvalue).

P =  \begin{bmatrix}
v_{11} & v_{21} \\
v_{12} & v_{22}  \\
\end{bmatrix}
\,
D =  \begin{bmatrix}
\lambda_1 & 0 \\
0 & \lambda_2  \\
\end{bmatrix}

We’ve covered previously how to perform a transformation in a different basis. You multiply a vector with the corresponding basis matrix, perform the transform, and finally transform the vector back into its original basis using the identity of the transformation matrix. Similarly, you can use the eigenvector-matrix P to transform a vector to the eigenbasis. Now you can apply the transformation using the much simpler diagonal matrix D. Afterwards, you transform back to your original basis using the inverse of P.

A = PDP^{-1}

What happens if you have to apply the transformation (let’s say a multiplication) several times?

AA = PDP^{-1}PDP^{-1} = PDIDP^{-1} = PD^{2}P^{-1}\\
A^{2} = PD^{2}P^{-1}

As you see, you don’t have to transform back and forth between bases for every multiplication. You only need to transform to the eigenbasis once, then you can apply all the transformations you need to D. Lastly, you transform back to your original basis.

Let’s apply this to a matrix A with a vector v.

A =
\begin{bmatrix}
2 & 1 \\
1 & 2\\
\end{bmatrix} \,,
v =
\begin{bmatrix}
1 \\
1\\
\end{bmatrix}

Recall, that we arrived at the following eigenvalues.

\lambda = 1 \\ \lambda = 3

If you substitute this into our characteristic polynomial, you’ll get x= y for λ=1 and x = -y for λ=3. For the eigenvectors remember that we can pick any value as long as these equations remain true.

e_1 =  \begin{bmatrix}
1 \\
-1\\
\end{bmatrix}\,
e_2 =  \begin{bmatrix}
1 \\
1\\
\end{bmatrix}

Now we can decompose A into a matrix of eigenvectors and eigenvalues.

PDP^{-1} =  \begin{bmatrix}
1 & 1\\
-1 & 1\\
\end{bmatrix}
\begin{bmatrix}
1 & 0\\
0 & 3\\
\end{bmatrix}
\begin{bmatrix}
0.5 & -0.5\\
0.5 & 0.5\\
\end{bmatrix}

If we want to apply the transformation encapsulated by A 2 times, we could do it the classic way.

AA = A^{2} =
\begin{bmatrix}
2 & 1 \\
1 & 2\\
\end{bmatrix}
\begin{bmatrix}
2 & 1 \\
1 & 2\\
\end{bmatrix}
=
\begin{bmatrix}
5 & 4 \\
4 & 5\\
\end{bmatrix}

The other and computationally more efficient way is by using the eigendecomposition.

PD^2P^{-1} =  \begin{bmatrix}
1 & 1\\
-1 & 1\\
\end{bmatrix}
\begin{bmatrix}
1 & 0\\
0 & 9\\
\end{bmatrix}
\begin{bmatrix}
0.5 & -0.5\\
0.5 & 0.5\\
\end{bmatrix}
=
\begin{bmatrix}
5 & 4 \\
4 & 5\\
\end{bmatrix}

As you can see, the result is the same.

## Summary

We’ve learned how to decompose a matrix into its eigenvalues and eigenvectors.

This post is part of a series on linear algebra for machine learning. To read other posts in this series, go to the index.

Sharing is caring