Tiny Volt20. Projection matrix
Markov matrices showed another payoff of eigendecomposition: repeatedly applying a transition matrix drives any starting distribution toward the steady state, the eigenvector of eigenvalue . This chapter returns to a geometric question from the dot-product chapter and answers it in full generality.
Back when we learned about the dot product, we projected one vector onto another. Here we ask the more general question: what does it mean to project a vector onto a space of vectors, and is there a single matrix that performs the projection? There is, and it is called the projection matrix.
20.1 Projection of a vector on another vector
Let's revisit the problem we encountered when we learned about the dot product: projection of a vector on another vector.
The figure shows and . Now drop a perpendicular from the tip of onto the line of : .
Before we start out finding a solution, let's try to understand the problem in more detail. Note that we are not projecting on the vector in particular. We are projecting it on any vector which has the same direction as . In other words we are projecting on all possible weighted sums of the vector .
20.2 Projection of a vector on a plane described by two vectors
Now let's say we want to find the projection of the vector on the 2-dimensional xy-plane. Note that this plane can be described by any two independent vectors in that plane: and , or and . Our xy-plane is in fact the set of all possible weighted sums of the two vectors. The projected vector (which is obvious in this case: ) does not depend on which elements are used to describe the space in which we are projecting.
20.3 The idea of vector spaces
This gives us a slightly better picture of what exactly we are projecting a vector onto. The vector space of a set of vectors is the set of all possible weighted sums of those vectors. In other words, it is the set of all possible linear combinations of those vectors.
- The vector space of the vector is the set of all the points (or vectors) on the line . This is a one dimensional space. All vectors in this set have the form for some number .
- The vector space of vectors and , where is a number, is the same as the vector space of . This is because any weighted sum of these two vectors also has the form for some number .
- The vector space of two linearly independent vectors and is a 2D space. These two vectors may have any dimensionality, but the set of all their weighted sums is a 2-dimensional plane (in the n-dimensional space).
20.3.1 Vector subspace
A vector subspace is a vector space which is a subset of another vector space.
- The vector space of is a vector subspace of the vector space of and .
- The vector space of and is a 2-dimensional subspace of the 3-dimensional space that these vectors reside in.
20.3.2 We project a vector on a vector subspace
So when we talk about projecting a vector, we are actually projecting a vector on a subspace, not on a vector or a set of vectors. Let's say the vectors of this subspace are denoted as columns of a matrix . Then we frame the problem as:
- Given an -dimensional vector and a vector subspace of -dimensional space whose vectors are given by a matrix , what is the vector projected onto this subspace?
Let's redraw the earlier picture with this framing. Take , but instead of the single vector , draw , members of the 1-dimensional vector space of . is unchanged: we are projecting on the whole subspace, and every description of that subspace gives the same answer.
Note that this problem makes sense only if we are projecting a vector onto a subspace of the vector space the vector belongs to. If it is not a subspace, the projected vector is the vector itself.
- For example, the projection of the vector onto the vector space of itself is the vector itself.
20.4 Projection on a vector subspace
The projection of a vector on the vector space of a matrix is an element of the vector space of . Let's call the original vector and the projected vector . Note that can be expressed as a weighted sum of the column vectors of . In other words, for some unknown vector .
Once we find out what this vector is, we can calculate easily.
20.4.1 When is the projected vector zero?
When is the projection of a vector on a vector space zero? By zero, we mean the vector where each entry is .
- For a subspace of dimension , a vector has no projection (i.e. the projected vector is a zero vector) when it is perpendicular to every vector in that vector subspace.
- For a subspace of dimension , a vector has no projection when it is perpendicular to each column vector of . This is because if it is perpendicular to a set of vectors, it is also perpendicular to every linear combination of those vectors. E.g. the vector is perpendicular to the subspace of or . The subspace of both these matrices is the xy-plane and the vector is clearly perpendicular to it.
Let's see this on the canvas. Draw again, and , which is perpendicular to since . , the single rose point at the origin.
In general, a vector has a zero projection vector on the subspace of a matrix if is perpendicular to each column vector of .
20.4.2 Vector as a sum of projected vector and normal vector
This simple insight allows us to write down the vector as a sum of two vectors:
Here is the component of that is perpendicular to all the column vectors of , and is the component that is a part of the subspace of .
For the projection of on the 1-dimensional subspace of : draw and , then split into along the subspace and perpendicular to it, drawn tip-to-tail from :
20.5 Understanding the matrix-vector product Aᵀv
Given an -by- matrix where each column vector is denoted as , and an -dimensional vector , we can see that:
Now, if the vector is perpendicular to all the column vectors of the matrix , we have for all columns .
In other words, if is perpendicular to the subspace of .
20.6 The solution
Now let's apply this observation to . Since is normal (aka perpendicular) to the subspace of the column vectors of , we have , which gives us:
But we saw earlier that . This gives us:
Thus the projected vector is:
Note that is also a matrix. We will call it the projection matrix of .
Using the example of and , we get the projection matrix . Indeed, we can see that:
20.7 Projection matrix is idempotent
A matrix is called idempotent if . In other words, is idempotent if , which also implies . It is easy to see that the projection matrix is idempotent:
An example for :
and squaring it gives it back:
If we take the projection of the projection of a vector on a subspace , we get the same thing as the projection of on : the projected vector already lives in the subspace, so projecting it again leaves it unchanged.
20.8 Projection matrix of 1-dimensional subspaces
Let's consider one interesting case: projecting a vector on a 1-dimensional vector space of . Since describes a 1-dimensional space, it only contains one column. In other words, is just a vector. This means that
Thus the projection matrix of is:
Now, if we assume that the vector has unit norm, then , in which case the projection matrix is simply .
In the interactive visual, we project vectors which are points on an ellipse onto a line (aka a 1D vector subspace). First place , then draw , a line through the origin. Each point is sent to , dropping perpendicularly along the grey normal arrows. The live readout shows . Now and watch the projections and the matrix update together, or .
Here's how it is implemented in Python (elementary operations like matrix-matrix product and matrix-vector product are not shown):
import math
angle = 0.4 # this could be any angle
# subspace matrix
matrix = [[math.cos(angle), math.sin(angle)]]
matrix_transpose = [[math.cos(angle)],[math.sin(angle)]]
projection_matrix = get_matrix_matrix_product(matrix, matrix_transpose)
input_vectors = [[1,2],[-3,2],[3,4]] # could be replaced by points on an ellipse
projected_vectors = get_matrix_matrix_product(projection_matrix, input_vectors)
Note that here we set the subspace_vector to be a unit vector of the form so that the projection matrix assumed the much simpler form .
In the next chapter we will encounter (unit) vector products of the form again, in the context of symmetric matrices.
← 19. Markov matrices · 21. Symmetric matrix-vector product →