Loading editor...

6. Matrix-matrix multiplication

A matrix-vector product is a weighted sum of the columns of , and at the same time, is a function that maps the point to the point . In the last chapter we used the inverse , the function that undoes , to check whether a point lies inside a triangle.

In this chapter we multiply a matrix with another matrix, and meet the powerful idea of composing and decomposing transformations.

6.1 The two lenses of matrix-vector multiplication

We introduced matrix-vector multiplication by taking a weighted sum of vectors. Then we changed our perspective to view a matrix as a function that eats a vector and outputs another vector. Viewing through this lens allowed us to say things like "a matrix maps point A to point B" or "a matrix transforms a circle into an ellipse".

We will follow a similar approach here - we will look at a way to multiply two matrices. Then we will look at matrix-matrix multiplication through an entirely different lens which will enable us to see some insightful (and pretty!) visuals.

6.1.1 Let's bring in some notation

We will use an upper case letter like to denote a matrix, and a lower case letter like to denote a vector. If we are dealing with more than one matrices or vectors, we will either use different names like or use subscripts and

The matrix-vector product of and will be written as .

Remember that is a vector, not a matrix. Similarly is also a vector - it is the product of the matrix and the vector .

6.1.2 Remember that matrix-vector multiplication is linear

It follows the two rules of linearity:

  1. : Adding vectors in the input space followed by a matrix transformation is the same as adding the vectors transformed by the matrix.
  2. : Scaling a vector in the input space followed by a matrix transformation is the same as doing the matrix transformation first and then scaling the output vector by the same amount.

Let's write down some functions to perform matrix-vector multiplication:

Vector = [float]
Matrix = [[float]]
    
def scale_vector(scale:float, vector:Vector) -> Vector:
    return [i*scale for i in vector]

def add_vectors(array_of_vectors:Matrix) -> Vector:
    dimensionality = len(array_of_vectors[0])
    output = [0]*dimensionality
    for vector in array_of_vectors:
        output = [i+j for (i,j) in zip(output, vector)]
    return output

def get_matrix_vector_product(matrix:Matrix, vector:Vector) -> Vector:
    scaled_vectors = [scale_vector(scale, vector) 
        for (scale, vector) in zip(vector, matrix)]
    return add_vectors(scaled_vectors)

6.2 Definition: what is matrix multiplication?

Let be a matrix and be two vectors. Note that the matrix-vector products and are also vectors. Let us invent a new format to show these two matrix-vector multiplications in a single expression:

To make it clearer that are column vectors, we can modify the expression as shown below (the vertical lines denote that each entry is a column):

But a matrix is just an array or an ordered collection of vectors. This means that both and are matrices. Let's name them X and Y. This gives us: . There we have it, a matrix-matrix multiplication!

Once you have the function to calculate a matrix-vector product, get_matrix_vector_product, it is really easy to implement a matrix-matrix product using it:

def get_matrix_matrix_product(A:Matrix, B:Matrix) -> Matrix:
    return [get_matrix_vector_product(A,v) for v in B]

Note that this function is meant to illustrate what matrix-matrix multiplication is - it is not an efficient implementation. You should use the native functions to multiply two matrices (especially if they are large matrices).

6.2.1 Generalizing it to any number of vectors

We can use the same format to show matrix-vector multiplications in a single expression:

Thus a matrix-matrix multiplication is just a collection of many matrix-vector multiplications, and the matrix-matrix product is just a collection of many matrix-vector products. Now some observations which should be obvious by now:

  1. The dimensionality of each vector in the right matrix needs to be the same as the number of columns in the left matrix M.
  2. The number of columns (or vectors) in the product is the same as the number of columns in the right matrix (n in the example above).
  3. The number of rows (or dimensionality of each output vector) in the product is the same as the number of rows in the left matrix.

6.3 Some properties of matrix-matrix multiplication

6.3.1 Matrix-matrix multiplication is associative

That is, . Note that are matrices whereas are vectors.

Let and let , with each colored to match the column of it scales. Then we have

6.3.2 Matrix-matrix multiplication is also linear

This can easily be seen from the fact that a matrix-matrix product is a "collection" of multiple matrix-vector products. And we have seen earlier that matrix-vector multiplication is linear. You can try to find a rigorous (and proper) proof yourself.

Just like scaling a vector, scaling a matrix means multiplying each entry inside the matrix by the scale.

6.3.3 Usually AB != BA

You can check this by looking at the output of the matrix function AB and the matrix function BA for the same input x. As an example, we will use 2-by-2 matrices:

We can see that

They are not equal. In the sections below we will visualize this difference in greater detail.

6.4 Visualizing matrix-matrix multiplication

We have already seen some visual examples of how 2-by-2 matrices transform the input space (points, lines, circles etc). Note that if A and B are 2-by-2 matrices, their products AB and BA are also 2-by-2 matrices. Thus we can visualize how these matrices AB and BA transform the input space.

Since AB(x) = A(Bx), we can see how an input vector x is mapped to Bx first and then how the vector Bx is mapped to ABx. This allows us to decompose the transformation by the matrix AB into two transformations: B then A.

In the product , the matrix acts on the input first, and then acts on the result - the product is read right-to-left.

For the visualizations we use

This gives us

The canvas shows , which starts as the identity matrix (so the grid is undistorted). is the first column of the current matrix - the image of the vector [1,0] - and is the second column, the image of [0,1]. The current matrix itself is shown in the bottom-left corner.

Let's decompose the transformation by AB into two steps:

  • : the grid is now transformed by .
  • : the grid is now transformed by .

Now let's apply the two matrices in the opposite order:

  • first.
  • : the grid is now transformed by .
  • : the grid is now transformed by .

The end result is different from AB - a visual confirmation that . You can flip between and to compare them directly.

6.5 The idea of "factorizing" a matrix into a product of two matrices

In many cases, decomposing the transformation of a matrix M into two or more transformations A, B, C, ... makes it easier to understand how M transforms the input space. This is especially the case if the matrix transformations A, B, C, ... are simpler to understand. We can simply compose multiple simple transformations to get a complicated transformation.

In other words, for a given matrix M we want to find matrices A, B, C, ... such that M = ABC.... Let's look at some decompositions of the matrix

This is the same matrix as BA from the previous section, but let's call it M for the sake of simplicity.

6.5.1 Different decompositions of M

Note that

Let and . In other words, .

Also note that itself can be factorized:

Let and . In other words, .

Each of these factors is a very simple transformation: stretches the plane vertically by 2, flips it horizontally, and is a vertical shear (it slides each point vertically in proportion to its x-coordinate). Let's compose them on the canvas and watch the complicated transformation M emerge from simple steps:

  • : a horizontal flip plus a vertical stretch.
  • : the grid is now transformed by .

And with the finer decomposition , applied right-to-left in three steps:

  • first.
  • : a vertical stretch by 2.
  • : a horizontal flip - the grid is now transformed by .
  • : the shear - the grid is now transformed by .

A key takeaway from this section is that decomposition of a matrix into other matrices is a useful tool. We will explore this tool in greater detail later when we cover a particular decomposition: Singular Value Decomposition.

6.5.2 Another simple decomposition

is equal to a square matrix whose diagonal elements are 1 and non-diagonal elements are 0. This is also called the Identity Matrix. If A is a 2-by-2 matrix then

This can be understood by noticing that just does the opposite of . So if maps a vector a to b, will map b to a. Thus the net effect of is that the output vector is the same as the input vector. The same logic can be applied to .

6.6 Algebraic equations involving matrices

If two matrices X and C are equal, we can multiply both sides by another matrix:

Now let's say and . This gives us:

Thus, if , we have . Using a similar argument, we have .

We will use these equations later on.

In the next chapter, we will take a closer look at what makes a transformation linear.

← 5. Barycentric coordinates · 7. Linear transformations →