Loading editor...

15. Eigendecomposition

A matrix can have up to eigenvectors, the special directions along which it only stretches: . We found them geometrically (the directions where the input-to-output segments lie flat) and algebraically (the values of that make singular). When a matrix has distinct eigenvalues, it has eigenvectors pointing in different directions. This chapter follows that lucky case to its beautiful conclusion.

In this chapter we focus on square () matrices that have distinct eigenvalues and eigenvectors. There is an elegant relationship between such a matrix and the matrix whose columns are the eigenvectors of . As usual we will use matrices for the pictures.

15.1 The relation between and

Consider a rank- matrix with unique eigenvectors and corresponding eigenvalues . Because no two eigenvectors share a direction, the matrix whose columns are these eigenvectors also has rank :

We can navigate the entire -dimensional space with weighted sums of the columns of either or . How are the two matrices related? The relation is surprisingly easy to see. Multiply by one column at a time, and use :

That last matrix is just with each column scaled, which is exactly times a diagonal matrix of the eigenvalues, where has the eigenvalues on its diagonal and zeros everywhere else. Putting the two halves together and multiplying on the right by :

We just decomposed into a product of three matrices. This is the eigendecomposition of .

15.2 But what does it even mean?

Let's understand by tracking what happens to a vector as it passes through , then , then .

  • answers the question: by what amounts must the columns of be scaled and added up to reach ? So holds the coordinates of in the eigenvector basis. In particular, if then : one step along the first eigenvector, and none along the rest.
  • scales each coordinate by its eigenvalue :

  • takes those scaled coordinates and reassembles a vector from the columns of .

So is a three-step pipeline:

  1. Encode in the language of :
  2. Scale each coordinate by its eigenvalue:
  3. Decode back into ordinary coordinates:

Let's watch this happen for the matrix from the previous chapter, whose exact eigendecomposition is

The grey unit circle is our set of input vectors. First look at directly, in one shot. Now let's rebuild that exact ellipse in three steps.

  • : this is the mapping of the identity matrix
  • : the circle is re-expressed in the eigenvector basis, tilting into a first ellipse.
  • : each eigen-coordinate is stretched by its eigenvalue, along one axis and along the other.
  • : the scaled coordinates are reassembled, and the shape lands on an ellipse.

This final ellipse sits exactly where 's ellipse was: encoding, scaling, then decoding reproduces . That is the whole content of .

15.3 Higher powers of a matrix

Why is useful? One especially neat application is computing high powers of . Watch what happens when we multiply the decomposition by itself, and notice the inner cancelling to the identity:

This is a huge shortcut, because is trivial to compute. Since is diagonal, raising it to the -th power just raises each diagonal entry to the -th power:

We can cache and once and reuse them, so the whole cost of collapses to scalar powers on the diagonal. Let's confirm this visually: squaring the eigenvalues should turn 's ellipse into 's ellipse.

Here is , with eigenvalues and . Now reveal , whose eigenvalues are and : the direction that was already stretched grows even more, while the shrinking direction shrinks further. The eigenvectors (the axes of the ellipse) never move; only the eigenvalues change.

Multiply , which is the same as running the step-1/step-2/step-3 pipeline from section 15.2 but scaling by instead of in the middle. Encoding and decoding are unchanged; only the stretch factors are squared.

We will see real applications of matrix powers, such as Fibonacci numbers and Markov chains, in the chapters ahead.

In the next chapter we look at symmetric matrices, whose eigenvectors turn out to be perpendicular to one another, making a rotation matrix and the decomposition even cleaner.

← 14. Eigenvectors and eigenvalues · 16. Eigenvectors of symmetric matrices →