Loading editor...

4. Rank and reversibility

A matrix is a function: it maps an input point to an output point . A 2-by-2 matrix maps lines to lines, circles to ellipses, convex shapes to convex shapes — and when its two columns point in the same direction, it squishes the entire 2D plane into a line.

In this chapter we make that squishing precise. We will meet the rank of a matrix, understand when a matrix's action can be reversed, and see why the two ideas are really one.

4.1 Unique values in an array

How can you find the number of unique values in an array of numbers? What if you have an array of vectors of a fixed dimension? Recall that a vector of dimension d is just an array of d numbers. This leads to the question: how is uniqueness defined?

4.1.1 Duplicate numbers: what makes two numbers unique?

The answer is obvious here: two numbers are unique if and only if they are not equal. In this case, the solution may look something like (without worrying about algorithmic complexity):

def get_number_unique_elements(array):
    element_to_count_dict = {}
    for element in array:
        element_to_count_dict[element] = element_to_count_dict.get(element, 0) + 1
    return len(element_to_count_dict)

4.1.2 Duplicate vectors: what makes two vectors unique?

We can think of two vectors to be unique if and only if they point in different directions.

Note that this is not a definition of uniqueness of vectors. But it emphasizes the fact that if two vectors point in the same direction, they are just scaled versions of each other - in that sense, they are not unique.

Consider two arrays and . They point in the same direction so they are not considered unique. However and are considered unique.

Let's see how this looks visually: in the array of vectors [[2,3],[-3,-4.5],[3,4.5],[3,2]] shown on the canvas, , , are all scaled versions of each other, while points in its own direction. So we only have two unique directions i.e. two unique vectors.

4.2 What is the dimension of the space covered by weighted sums of vectors?

Here is a question which may seem unrelated to the previous question initially: given a list of vectors, what is the dimension, r, of the space covered by weighted sums of the vectors?

We define a space as a collection of infinitely many points where each point is a possible output of a weighted sum of vectors. Given vectors , the set of points for all possible values of is the space formed by all possible weighted sums of . Is r the same as the number of unique directions of the vectors being summed? Let's look at some properties of this dimension r first:

4.2.1 It cannot be greater than the dimension of the vectors being added up

This may seem like an obvious fact: you cannot get a 3-dimensional vector by adding two or more 2-dimensional vectors. Thus the dimensionality of the output space cannot be greater than two.

Can it be smaller than two? Absolutely! All weighted sums of a single 2-dimensional vector just cover a line. E.g. the weighted sum of with a weight is . As you change the value of , its tip traces out different points of — a 1-dimensional space:

  • · ·

At the other end, here is a tip-to-tail sum of five 2-dimensional vectors [2,0], [2,3], [-5,-2], [-1,-1], [-1,-3], ending in . No matter how many 2-dimensional vectors we add, we still remain in the 2-d plane.

Even if we have 3 or more unique vectors (i.e. pointing in unique directions), each of dimension 2, we can only cover the entire 2-dimensional space by taking their weighted sums. But this is something we can do with two vectors only (e.g. [1,0] and [0,1]).

4.2.2 It cannot be greater than the number of vectors being added up

This may not be obvious at first but it will start to make sense later: if you add three 100-dimensional vectors weighed (scaled) in all possible manners, you will get a space which is at most three dimensional. Let's consider some examples to understand:

  1. The output space of weighted sums of one 3-dimensional vector is a one-dimensional space — a line in 3-dimensional space. This is easy to visualize - the space is basically just one direction - the direction of the input vector. There is no other unique direction in this space.
  2. The output space of weighted sums of two 3-dimensional vectors which point in the same direction is a one-dimensional space - it is a line in 3-dimensional space. E.g. the sum of w1 * [1,2,2] and w2 * [-2,-4,-4] is [c,2c,2c] where c = w1 - 2*w2. There is only one unique direction in the output space — the direction of the two input vectors.
  3. The output space of weighted sums of two unique 3-dimensional vectors is a two-dimensional space - it is a plane in 3-dimensions. For example, if you add vectors w1 * [1,0,0] and w2 * [0,1,0], the output vector is the space [w1, w2, 0]. No matter how you add these two vectors, you can never get to a vector [1,1,1].
  4. Similarly if you take three vectors of any dimension n > 3, all possible weighted sums of these three vectors will form a 3-dimensional space.

4.3 Rank of a matrix

The dimensionality of all possible weighted sums of vectors in an array is a property of that array of vectors. Note that an array of vectors of the same dimension is nothing but a matrix. We call this property the rank of that matrix. For example, the array of vectors [[2,3],[-3,-4.5],[3,4.5],[3,2]] in the matrix form is:

This has rank 2 as we saw earlier.

Similarly the below matrices have rank 1:

4.4 Linearly (in)dependent vectors

Given vectors , we want to find weights such that the weighted sum . In other words:

Note that we can always find at least one solution: setting all weights to zero. This is called the trivial solution.

  • If this is the only solution for , the vectors are said to be linearly independent.
  • If there exists a non-trivial solution (i.e. at least one of the weights is non-zero), the vectors are said to be linearly dependent.

4.4.1 Why the word "dependent"?

Let's say . Then we can write the equation as

Thus the vector can be expressed as a weighted sum of the remaining vectors. We can think of the vector as not being independent of the remaining vectors.

In this scenario, the space of weighted sums of all vectors except is the same as the space of weighted sums of all vectors. In other words, adding the vector does not increase the dimensionality of the space of all possible weighted sums.

But if the trivial solution is the only possible solution, it means that every vector is independent of the remaining vectors. In this case, the dimensionality of the space of all possible weighted sums of vectors is smaller than the dimensionality of the space of all possible weighted sums of vectors by a value of 1.

4.4.2 Relationship between linear independence and rank of a matrix

Given a matrix whose columns are the vectors , the rank of the matrix is equal to the size of the largest subset S of the vectors such that the vectors in S are linearly independent.

Consider the matrix

The largest subset S of such that the columns of S are linearly independent can only contain two vectors. E.g. , or .

Thus the rank of this matrix is 2.

4.5 Building a case for square matrices

Consider the following weighted sum of three 2-dimensional vectors, shown tip-to-tail on the canvas along with :

We can actually get to any point in the output space by using just two vectors. As long as the two vectors are unique (or in other words, as long as the 2-by-2 matrix has rank 2), we can get to any point in the 2d plane using just two vectors. For example, with the weights fixed at ,

  • lands on the point
  • and reaches exactly the same point:

The identity matrix works too, with weights equal to the target coordinates:

In other words, a weighted sum of three or more 2-dimensional vectors can also be represented as a weighted sum of two 2-dimensional vectors (which is a 2-by-2 matrix). Similarly any weighted sum of four or more 3-dimensional vectors can be represented by a weighted sum of three 3-dimensional vectors (which is a 3-by-3 matrix). In this sense, these 2-by-2 and 3-by-3 matrices seem to be "efficient". An n-by-n matrix contains just enough columns to scale-and-add to be able to reach any point in the n-dimensional space.

4.5.1 Input and output vectors of square matrices have the same dimensionality

If we consider the matrix as a function, an n-by-n matrix takes as input an n-dimensional vector and gives as output an n-dimensional vector. In other words, it maps a point in n-dimensional space to another point in n-dimensional space. For example, the matrix maps the point to . This allows us to draw the input and the output points in the same 2-dimensional plane.

4.5.2 Drawing input and output points in the same plane

Since both the input and the output points lie in the same 2d plane, we can draw them in the same plane. We can draw to show the transformation by the matrix .

We can also do this for not just one but a set of input points. Here we sample points on a circle of radius and map each one through the matrix . For , we calculate the , and . The arrows show how the input points on the circle are mapped to points on an ellipse.

4.6 Transforming the output vector back into the input vector

We can ask the question: brings back to ?

Whatever this matrix is, it inverts (which sent the vector to the vector ). We call this matrix the inverse of matrix and write it as (pronounced M inverse).

4.6.1 Matrix inverse is simply inverting the arrows

If we use arrows from input points to output points to visualize these transformations, the effect of an inverse matrix can be seen as simply changing the direction of the arrows:

  • : the teal arrows point from the ellipse back to the circle - maps each output point back to its input point.
  • : back to the gold arrows, mapping the circle to the ellipse.

4.6.2 When is it possible?

A function can have the same output for two different inputs. But it can never have two different outputs for the same input. Remember that a matrix is just a function.

Now, if a matrix sends two input points p1 and p2 to the same output point q, its inverse would have to send that output point q to both p1 and p2. That is not possible since an input point cannot have two different output points. Thus the inverse does not exist.

Now comes the interesting part: if a 2-by-2 matrix has rank 2, it always maps two different input points to two different output points. But if it has rank 1, there exists a set of input points which are all mapped to the same output point.

In fact, a rank-one 2-by-2 matrix squishes the entire 2d plane into a line. The canvas shows the matrix

whose second column is just times its first column — a rank-one matrix. The sampled on a circle all land on . to see the squish in action — and note how the entire transformed grid collapses onto that same line.

  • : the second column stops being a multiple of the first, and the transformed grid spans the whole plane again.
  • : the plane collapses back onto the line.

Thus an inverse does not exist for a rank-one 2-by-2 matrix. In general, for an n-by-n matrix, an inverse exists if and only if the rank of that matrix is n. Also, an inverse can only exist for square matrices. The reason is the same — non-square matrices always map a set of points to a single point.

4.6.3 Inverse of a 2-by-2 matrix

The inverse of a matrix

Thus the inverse of is . You can verify that

4.7 Another term for weighted sums of vectors

We have been and will be using the term weighted sums of vectors quite a lot here. This is to emphasize the fact that a matrix-vector product is just a weighted sum of the columns of the matrix. But in general, this action is more commonly described as taking a linear combination of vectors. We will use both these phrases interchangeably.

In the next chapter, we will use this knowledge of rank and inverse of a matrix to solve an interesting problem — determining whether a point is inside or outside a triangle.

← 3. Matrix as a function · 5. Barycentric coordinates →