You Could Have Come Up With Eigenvectors - Here's How
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:
- The effect of applying the linear map repeatedly on an input.
- 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.
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 - the standard coordinate plane over real numbers you’re probably already used to.
We saw in the last post how we can derive the matrix for a given linear map :
(as we defined it in the previous section) can be represented by the notation 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 and to define the columns of the matrix? Why not some other pair like and ?
Intuitively, we think of and as units that we can use to create other vectors. In fact, we can break down every vector in 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 , we say that those vectors the space. The minimum number of vectors you need to span is 2. So when we have 2 vectors that span , we call those vectors a basis.
and are basis vectors for .
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
Now are there other pairs of vectors that also form a basis for ?
Let’s start with an example that definitely won’t work.
Can you combine these vectors to create ? Clearly you can’t - we don’t have any way to move in the direction.
No combination of these two vectors could possible get us the vector .
What about and ?
Our new basis vectors.
Surprisingly, you can! The below image shows how we can reach our previously unreachable point .
Note we can can combine units of and units of to get us the vector .
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 .
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 , our axes just rotate as shown below:
As a result of this, the same notation for a vector means different things in different bases.
In the original basis, meant:
- The vector you get when you compute .
- Or just first basis vector plus second basis vector.
In our usual notation, means units of and units of
Now when we use a different basis , the meaning of this notation actually changes.
For the basis is , the vector means:
- The vector you get from: .
You can see this change below:
In the notation of basis , means units of and units of giving us point .
By changing the underlying axes, we changed the location of even though it’s still called . You can see this below:
The point also changes position when we change the basis. It is still parts first basis vector, parts second basis vector. But since the underlying basis vectors have changed, it also changes.
Matrix Notation Based on Bases
Similarly the same notation also means different things for matrices based on the basis. Earlier, the matrix for the function was represented by:
When I use the basis , the matrix in basis becomes:
More generally, for a basis , the matrix is:
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 (representing a linear function) that I need to apply again and again (say 5 times) on a vector .
This would be:
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 was a diagonal matrix (i.e. something like ). If this were the case, then this multiplication would be EASY.
Why? Let’s see what is:
More generally, This is way easier to work with! So how can we get 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 that converts into a diagonal matrix?
From earlier, we know that , the matrix in the basis , is written as:
For this to be diagonal, we must have:
for some and (i.e. the the top-right and bottom-left elements are ).
Recall our discussion on vector notation in a different basis:
Say my basis is . Then the vector means:
- The vector you get when you compute: .
So, we know the following additional information:
Seeing this Visually
What do these vectors look like on our coordinate axis?
We saw earlier that choosing a new basis creates a new coordinate axis for like below:
Let’s plot :
In the graph above, we can see that , so
Similarly, let’s plot :
From the above, we see clearly that , so
Rules For Getting a Diagonal
So if we can find a basis formed by and such that:
Is there a special name for the vectors above and that magically let us rewrite a matrix as a diagonal? Yes! These vectors are the eigenvectors of . That’s right - you derived eigenvectors all by yourself.
You the real MVP.
More formally, we define an eigenvector of as any non-zero vector such that: or
The basis formed by the eigenvectors is known as the eigenbasis. Once we switch to using the eigenbasis, our original problem of finding becomes:
So. Much. Easier.
Well this has all been pretty theoretical with abstract vectors like and - let’s make this concrete with real vectors and matrices to see it in action.
Imagine we had the matrix . 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:
The eigenbasis is just . What is , the matrix written in the eigenbasis ?
Since , we need to find :
We’ll break this down by first finding and , and rewrite them in the notation of the eigenbasis to get and .
Rewriting the vectors in the basis
We’ve now found and . We need to rewrite these vectors in the notation for our new basis .
Putting this all together, 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 and its matrix .
An eigenvector, is a vector such that:
How are and related? is just a scaling of in the same direction - it can’t be rotated in any way.
Notice how is in the same direction as . Image Source: Wikipedia.
In this sense, the eigenvectors of a linear map 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:
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!
Proof that and span :
- We know already that and can be used to reach every coordinate.
- We can create by computing:
- Thus we can combine our vectors to obtain both and . By point 1, this means every vector in is reachable by combining and .