Dhruv's Blog     About     Archive     Feed

Eigenvectors

In the last post, we developed an intuition for matrices. We found that they are just compact representations of linear maps and that adding and multiplying matrices are just ways of combining the underlying linear maps.

In this post, we’re going to dive deeper into the world of linear algebra and cover eigenvectors. Eigenvectors are central to Linear Algebra and help us understand many interesting properties of linear maps including:

  1. The effect of applying the linear map repeatedly on an input.
  2. How the linear map rotates the space. In fact eigenvectors were first derived to study the axis of rotation of planets!

Eigenvectors helped early mathematicians study how the planets rotate. Image Source: Wikipedia.

For a more modern example, eigenvectors are at the heart of one of the most important algorithms of all time - the original Page Rank algorithm that powers Google Search.

Our Goals

In this post we’re going to try and derive eigenvectors ourselves. To really create a strong motivation, we’re going to explore basis vectors, matrices in different bases, and matrix diagonalization. So hang in there and wait for the big reveal - I promise it will be really exciting when it all comes together!

Everything we’ll be doing is going to be in the 2D space R2R^2 - the standard coordinate plane over real numbers you’re probably already used to.

Basis Vectors

We saw in the last post how we can derive the matrix for a given linear map ff:

f(x)f(x) (as we defined it in the previous section) can be represented by the notation [f([10])f([01])]\begin{bmatrix} f(\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}) & f(\textcolor{#228B22}{\begin{bmatrix} 0 \\ 1 \end{bmatrix}}) \end{bmatrix} =[3005] = \begin{bmatrix} \textcolor{blue}{3} & \textcolor{#228B22}{0} \\ \textcolor{blue}{0} & \textcolor{#228B22}{5} \end{bmatrix} This is extremely cool - we can describe the entire function and how it operates on an infinite number of points by a little 4 value table.

But why did we choose [10]\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} and [01]\textcolor{#228B22}{\begin{bmatrix} 0 \\ 1 \end{bmatrix}} to define the columns of the matrix? Why not some other pair like [33]\textcolor{blue}{\begin{bmatrix} 3 \\ 3 \end{bmatrix}} and [00]\textcolor{#228B22}{\begin{bmatrix} 0 \\ 0 \end{bmatrix}}?

Intuitively, we think of [10]\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} and [01]\textcolor{#228B22}{\begin{bmatrix} 0 \\ 1 \end{bmatrix}} as units that we can use to create other vectors. In fact, we can break down every vector in R2R^2 into some combination of these two vectors.

We can reach any point in the coordinate plan by combining our two vectors.

More formally, when two vectors are able to combine in different ways to create all other vectors in R2R^2, we say that those vectors spanspan the space. The minimum number of vectors you need to span R2R^2 is 2. So when we have 2 vectors that span R2R^2, we call those vectors a basis.

[10]\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} and [01]\textcolor{#228B22}{\begin{bmatrix} 0 \\ 1 \end{bmatrix}} are basis vectors for R2R^2.

You can think of basis vectors as the minimal building blocks for the space. We can combine them in different amounts to reach all vectors we could care about.

We can think of basis vectors as the building blocks of the space - we can combine them to create all possible vectors in the space. Image Source: instructables.com.


Other Basis Vectors for R2R^2

Now are there other pairs of vectors that also form a basis for R2R^2?

Let’s start with an example that definitely won’t work.

Bad Example

[10]\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} and [10]\textcolor{#228B22}{\begin{bmatrix} -1 \\ 0 \end{bmatrix}}.

Can you combine these vectors to create [23]{\begin{bmatrix} 2 \\ 3 \end{bmatrix}}? Clearly you can’t - we don’t have any way to move in the yy direction.

No combination of these two vectors could possible get us the vector PP.

Good Example

What about [10]\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} and [11]\textcolor{#228B22}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}}?

Our new basis vectors.

Surprisingly, you can! The below image shows how we can reach our previously unreachable point PP.

Note we can can combine 33 units of [11]{\begin{bmatrix} 1 \\ 1 \end{bmatrix}} and 1-1 units of [10]{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} to get us the vector PP.

I’ll leave a simple proof of this as an appendix at the end of this post so we can keep moving - but it’s not too complicated so if you’re up for it, give it a go! The main thing we’ve learned here is that:

There are multiple valid bases for R2R^2.


Bases as New Coordinate Axes

In many ways, choosing a new basis is like choosing a new set of axes for the coordinate plane. When we when we switch our basis to say B={[10],[11]}B = \{\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}, \textcolor{#228B22}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}}\}, our axes just rotate as shown below:

As our second basis vector changed from [01]\textcolor{#228B22}{\begin{bmatrix} 0 \\ 1 \end{bmatrix}} to [11]\textcolor{#228B22}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}}, our y axis rotates to be in line with [11]\textcolor{#228B22}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}}.


As a result of this, the same notation for a vector means different things in different bases.

In the original basis, [34]{\begin{bmatrix} \textcolor{blue}{3} \\ \textcolor{#228B22}{4} \end{bmatrix}} meant:

  • The vector you get when you compute 3[10]+4[01]\textcolor{blue}{3 \cdot \begin{bmatrix} 1 \\ 0 \end{bmatrix}} + \textcolor{#228B22}{4 \cdot \begin{bmatrix} 0 \\ 1 \end{bmatrix}}.
  • Or just 3\textcolor{blue}{3} \cdot first basis vector plus 4\textcolor{#228B22}{4} \cdot second basis vector.

In our usual notation, [34]{\begin{bmatrix} \textcolor{blue}{3} \\ \textcolor{#228B22}{4} \end{bmatrix}} means 33 units of [10]\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} and 44 units of [01]\textcolor{#228B22}{\begin{bmatrix} 0 \\ 1 \end{bmatrix}}

Now when we use a different basis , the meaning of this notation actually changes.

For the basis is B={[10],[11]}B = \{\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}, \textcolor{#228B22}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}}\}, the vector [34]B\begin{bmatrix} \textcolor{blue}{3} \\ \textcolor{#228B22}{4} \end{bmatrix}_{B} means:

  • The vector you get from: 3[10]+4[11]\textcolor{blue}{3 \cdot \begin{bmatrix} 1 \\ 0 \end{bmatrix}} + \textcolor{#228B22}{4 \cdot \begin{bmatrix} 1 \\ 1 \end{bmatrix}}.

You can see this change below:

In the notation of basis BB, [34]B{\begin{bmatrix} \textcolor{blue}{3} \\ \textcolor{#228B22}{4} \end{bmatrix}}_{B} means 33 units of [10]\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} and 44 units of [11]\textcolor{#228B22}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}} giving us point PBP_{B}.

By changing the underlying axes, we changed the location of PP even though it’s still called (3,4)(3, 4). You can see this below:

The point PP also changes position when we change the basis. It is still 33 parts first basis vector, 44 parts second basis vector. But since the underlying basis vectors have changed, it also changes.

So the vectors [34]{\begin{bmatrix} \textcolor{blue}{3} \\ \textcolor{#228B22}{4} \end{bmatrix}} and [34]B{\begin{bmatrix} \textcolor{blue}{3} \\ \textcolor{#228B22}{4} \end{bmatrix}}_{B} refer to different actual vectors based on basis BB.

Matrix Notation Based on Bases

Similarly the same notation also means different things for matrices based on the basis. Earlier, the matrix FF for the function ff was represented by:

F=[f([10])f([01])]F = \begin{bmatrix} f(\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}) & f(\textcolor{#228B22}{\begin{bmatrix} 0 \\ 1 \end{bmatrix}}) \end{bmatrix}

When I use the basis B={[10],[11]}B = \{\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}, \textcolor{#228B22}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}}\}, the matrix FBF_{B} in basis BB becomes:

FB=[f([10])Bf([11])B]F_{B} = \begin{bmatrix} f(\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}})_{B} & f(\textcolor{#228B22}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}})_{B} \end{bmatrix}

More generally, for a basis B={b1,b2}B = \{b_1, b_2\}, the matrix is:

FB=[f(b1)Bf(b2)B]F_{B} = \begin{bmatrix} f(\textcolor{blue}{b_1})_{B} & f(\textcolor{#228B22}{b_2})_{B} \end{bmatrix}


The Power of Diagonals

We took this short detour into notation for a very specific reason - rewriting a matrix in a different basis is actually a neat trick that allows us to reconfigure the matrix to make it easier to use. How? Let’s find out with a quick example.

Let’s say I have a matrix FF (representing a linear function) that I need to apply again and again (say 5 times) on a vector vv.

This would be:

FFFFFvF \cdot F \cdot F \cdot F \cdot F \cdot v.

Usually, calculating this is really cumbersome.

Can you imagine doing this 5 times in a row? Yeesh. Image Source: Wikipedia.

But let’s imagine for a moment that FF was a diagonal matrix (i.e. something like F=[a00b]F = \begin{bmatrix} a & 0 \\ 0 & b \end{bmatrix} ). If this were the case, then this multiplication would be EASY.

Why? Let’s see what FFF \cdot F is:

FF=[a00b][a00b]F \cdot F = \begin{bmatrix} a & 0 \\ 0 & b \end{bmatrix} \cdot \begin{bmatrix} a & 0 \\ 0 & b \end{bmatrix} FF=[aa+00a0+0b0a+b000+bb]F \cdot F = \begin{bmatrix} a \cdot a + 0 \cdot 0 & a \cdot 0 + 0 \cdot b \\ 0 \cdot a + b \cdot 0 & 0 \cdot 0 + b \cdot b \end{bmatrix} FF=[a200b2]F \cdot F = \begin{bmatrix} a^2 & 0 \\ 0 & b^2 \end{bmatrix}

More generally, Fn=[an00bn]F^{n} = \begin{bmatrix} a^n & 0 \\ 0 & b^n \end{bmatrix} This is way easier to work with! So how can we get FF to be a diagonal matrix?


Which Basis makes a Matrix Diagonal?

Earlier, we saw that choosing a new basis makes us change how we write down the matrix. So can we find a basis B={b1,b2}B = \{b_1, b_2\} that converts FF into a diagonal matrix?

From earlier, we know that FBF_{B}, the matrix FF in the basis BB, is written as:

FB=[f(b1)Bf(b2)B]F_B = \begin{bmatrix} f(\textcolor{blue}{b_1})_{B} & f(\textcolor{#228B22}{b_2})_{B} \end{bmatrix}

For this to be diagonal, we must have:

FB=[f(b1)Bf(b2)B]=[λ100λ2]BF_B = \begin{bmatrix} f(\textcolor{blue}{b_1})_{B} & f(\textcolor{#228B22}{b_2})_{B} \end{bmatrix} = {\begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix}}_{B}

for some λ1\lambda_1 and λ2\lambda_2 (i.e. the the top-right and bottom-left elements are 00).

This implies:

  1. f(b1)B=[λ10]Bf(\textcolor{blue}{b_1})_{B} = {\begin{bmatrix}\lambda_1 \\ 0 \end{bmatrix}}_{B}.
  2. f(b2)B=[0λ2]Bf(\textcolor{#228B22}{b_2})_{B} = {\begin{bmatrix}0 \\ \lambda_2 \end{bmatrix}}_{B}.

Recall our discussion on vector notation in a different basis:

Say my basis is B={[10],[11]}B = \{\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}, \textcolor{#228B22}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}}\}. Then the vector [34]B\begin{bmatrix} \textcolor{blue}{3} \\ \textcolor{#228B22}{4} \end{bmatrix}_{B} means:

  • The vector you get when you compute: 3[10]+4[11]\textcolor{blue}{3 \cdot \begin{bmatrix} 1 \\ 0 \end{bmatrix}} + \textcolor{#228B22}{4 \cdot \begin{bmatrix} 1 \\ 1 \end{bmatrix}}.

So, we know the following additional information:

f(b1)=[λ10]B=λ1b1+0b2f(\textcolor{blue}{b_1}) = {\begin{bmatrix}\lambda_1 \\ 0 \end{bmatrix}}_B = \lambda_1 \cdot \textcolor{blue}{b_1} + 0 \cdot \textcolor{#228B22}{b_2}

f(b1)=λ1b1 f(\textcolor{blue}{b_1}) = \mathbf{\lambda_1 \cdot \textcolor{blue}{b_1}}

Similarly,

f(b2)=[0λ2]B=0b1+λ2b2f(\textcolor{#228B22}{b_2}) = {\begin{bmatrix}0 \\ \lambda_2 \end{bmatrix}}_B = 0 \cdot \textcolor{blue}{b_1} + \lambda_2 \cdot \textcolor{#228B22}{b_2}

f(b2)=λ2b2f(\textcolor{#228B22}{b_2}) = \mathbf{\lambda_2 \cdot \textcolor{#228B22}{b_2}}

Seeing this Visually

What do these vectors look like on our coordinate axis?

We saw earlier that choosing a new basis B={b1,b2}B = \{b_1, b_2\} creates a new coordinate axis for R2R^2 like below:

A new basis B={b1,b2}B = \{b_1, b_2\} gives us new coordinate axis.


Let’s plot f(b1)B=[λ10]Bf(\textcolor{blue}{b_1})_{B} = {\begin{bmatrix}\lambda_1 \\ 0 \end{bmatrix}}_{B}:

In the graph above, we can see that [λ10]B=λ1b1{\begin{bmatrix}\lambda_1 \\ 0 \end{bmatrix}}_{B} = \lambda_1 b_1, so

f(b1)B=λ1b1f(\textcolor{blue}{b_1})_{B} = \lambda_1 b_1


Similarly, let’s plot f(b2)B=[0λ2]Bf(\textcolor{#228B22}{b_2})_{B} = {\begin{bmatrix}0 \\ \lambda_2 \end{bmatrix}}_{B}:

From the above, we see clearly that [0λ2]B=λ2b2{\begin{bmatrix}0 \\ \lambda_2 \end{bmatrix}}_{B} = \lambda_2 b_2, so

f(b2)B=λ2b2f(\textcolor{blue}{b_2})_{B} = \lambda_2 b_2


Rules For Getting a Diagonal

So if we can find a basis BB formed by b1b_1 and b2b_2 such that:

  1. f(b1)=λ1b1f(\textcolor{blue}{b_1}) = \lambda_1 \textcolor{blue}{b_1} and
  2. f(b2)=λ2b2f(\textcolor{#228B22}{b_2}) = \lambda_2 \textcolor{#228B22}{b_2},
then, FF can be rewritten as FBF_{B}, where FB=[λ100λ2]F_{B} = \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix} A nice diagonal matrix!

Enter Eigenvectors

Is there a special name for the vectors above b1b_1 and b2b_2 that magically let us rewrite a matrix as a diagonal? Yes! These vectors are the eigenvectors of ff. That’s right - you derived eigenvectors all by yourself.

You the real MVP.

More formally, we define an eigenvector of ff as any non-zero vector vv such that: f(v)=λvf(v) = \lambda v or Fv=λvF \cdot v = \lambda v

The basis formed by the eigenvectors is known as the eigenbasis. Once we switch to using the eigenbasis, our original problem of finding fffff(v)f\circ f\circ f \circ f \circ f (v) becomes:

FBFBFBFBFBvBF_{B} \cdot F_{B} \cdot F_{B} \cdot F_{B} \cdot F_{B} \cdot v_{B} =[λ1500λ25]B = {\begin{bmatrix} {\lambda_1}^5 & 0 \\ 0 & {\lambda_2}^5 \end{bmatrix}}_{B}

So. Much. Easier.


An Example

Well this has all been pretty theoretical with abstract vectors like bb and vv - let’s make this concrete with real vectors and matrices to see it in action.

Imagine we had the matrix F=[2112]F = \begin{bmatrix}2 & 1 \\ 1 & 2 \end{bmatrix}. Since the goal of this post is not learning how to find eigenvectors, I’m just going to give you the eigenvectors for this matrix. They are:

b1=[11]b_{1} = \begin{bmatrix} 1 \\ -1 \end{bmatrix} b2=[11]b_{2} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}

The eigenbasis is just B={b1,b2}B = \{b_1, b_2\}. What is FBF_{B}, the matrix FF written in the eigenbasis BB?

Since FB=[f(b1)Bf(b2)B]F_B = \begin{bmatrix} f(\textcolor{blue}{b_1})_{B} & f(\textcolor{#228B22}{b_2})_{B} \end{bmatrix}, we need to find :

  • f(b1)Bf(\textcolor{blue}{b_1})_{B} and f(b2)Bf(\textcolor{#228B22}{b_2})_{B}

We’ll break this down by first finding f(b1)f(\textcolor{blue}{b_1}) and f(b2)f(\textcolor{#228B22}{b_2}), and rewrite them in the notation of the eigenbasis BB to get f(b1)Bf(\textcolor{blue}{b_1})_{B} and f(b2)Bf(\textcolor{#228B22}{b_2})_{B}.

Finding f(b1)f(\textcolor{blue}{b_1})

f(b1)f(\textcolor{blue}{b_1}) is:

f(b1)=Fb1=[2112][11] f(\textcolor{blue}{b_1}) = F\cdot \textcolor{blue}{b_1} = \begin{bmatrix}2 & 1 \\ 1 & 2\end{bmatrix} \cdot \begin{bmatrix} 1 \\ -1 \end{bmatrix} f(b1)=[11] f(\textcolor{blue}{b_1}) = \begin{bmatrix} 1 \\ -1 \end{bmatrix}

Finding f(b2)f(\textcolor{#228B22}{b_2})

Similarly,

f(b2)=Fb2=[2112][11] f(\textcolor{#228B22}{b_2}) = F\cdot \textcolor{#228B22}{b_2} = \begin{bmatrix}2 & 1 \\ 1 & 2\end{bmatrix} \cdot \begin{bmatrix} 1 \\ 1 \end{bmatrix} f(b2)=[33] f(\textcolor{#228B22}{b_2}) = \begin{bmatrix} 3 \\ 3 \end{bmatrix}

Rewriting the vectors in the basis BB

We’ve now found f(b1)f(b_1) and f(b2)f(b_2). We need to rewrite these vectors in the notation for our new basis BB.

What’s f(b1)Bf(b_1)_{B}?

f(b1)=[11]=1[11]+0[11]=1b1+0b2f(b_1) = \begin{bmatrix} 1 \\ -1 \end{bmatrix} = \textcolor{blue}{1} \cdot \begin{bmatrix} 1 \\ -1 \end{bmatrix} + \textcolor{#228B22}{0} \cdot \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \textcolor{blue}{1} \cdot b_1 + \textcolor{#228B22}{0} \cdot b_2 f(b1)B=[10]f(b_1)_{B} = \begin{bmatrix} \textcolor{blue}{1} \\ \textcolor{#228B22}{0} \end{bmatrix}

Similarly,

f(b2)=[33]=0[11]+3[11]=0b1+3b2f(b_2) = \begin{bmatrix} 3 \\ 3 \end{bmatrix} = \textcolor{blue}{0} \cdot \begin{bmatrix} 1 \\ -1 \end{bmatrix} + \textcolor{#228B22}{3} \cdot \begin{bmatrix}1 \\ 1 \end{bmatrix} = \textcolor{blue}{0} \cdot b_1 + \textcolor{#228B22}{3} \cdot b_2 f(b2)B=[03]f(b_2)_{B} = \begin{bmatrix} \textcolor{blue}{0} \\ \textcolor{#228B22}{3} \end{bmatrix}

Putting this all together, FB=[f(b1)Bf(b2)B]F_B = \begin{bmatrix} f(\textcolor{blue}{b_1})_{B} & f(\textcolor{#228B22}{b_2})_{B} \end{bmatrix} FB=[1003]F_B = \begin{bmatrix} 1 & 0 \\ 0 & 3 \end{bmatrix} So we get the nice diagonal we wanted!

Geometric Interpretation of Eigenvectors

Eigenvectors also have extremely interesting geometric properties worth understanding. To see this, let’s go back to the definition for an eiegenvector of a linear map ff and its matrix FF.

An eigenvector, is a vector vv such that:

Fv=λvF \cdot v = \lambda v

How are λv\lambda v and vv related? λv\lambda v is just a scaling of vv in the same direction - it can’t be rotated in any way.

Notice how λv\lambda v is in the same direction as vv. Image Source: Wikipedia.

In this sense, the eigenvectors of a linear map ff show us the axes along which the map simply scales or stretches its inputs.

The single best visualization I’ve seen of this is by 3Blue1Brown who has a fantastic youtube channel on visualizing math in general.

I’m embedding his video on eigenvectors and their visualizations below as it is the best geometric intuition out there:

Source: 3Blue1Brown


Google and Eigenvectors

Like we saw at the beginning of this post, eigenvectors are not just an abstract concept used by eccentric mathematicians in dark rooms - they underpin some of the most useful technology in our lives including Google Search. For the brave, here’s Larry Page and Sergey’s original paper on PageRank, the algorithm that makes it possible for us to type in a few letters on a search box and instantly find every relevant website on the internet.

In the next post, we’re going to actually dig through this paper and see how eigenvectors are applied in Google search!

Stay tuned.


Appendix

Proof that [10]\textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} and [11]\textcolor{#228B22}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}} span R2R^2:

  1. We know already that [10]{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} and [01]{\begin{bmatrix} 0 \\ 1 \end{bmatrix}} can be used to reach every coordinate.
  2. We can create [01]{\begin{bmatrix} 0 \\ 1 \end{bmatrix}} by computing:
    • [11][10]=[01]\textcolor{#228B22}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}} - \textcolor{blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} = {\begin{bmatrix} 0 \\ 1 \end{bmatrix}}
  3. Thus we can combine our vectors to obtain both [10]{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} and [01]{\begin{bmatrix} 0 \\ 1 \end{bmatrix}}. By point 1, this means every vector in R2R^2 is reachable by combining [01]\textcolor{blue}{\begin{bmatrix} 0 \\ 1 \end{bmatrix}} and [11]\textcolor{#228B22}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}}.