5.1. Matrix Operations - EECS 245 Course Notes

Introduction¶

In Chapter 4, we focused on understanding the subspace of $\mathbb{R}^n$ spanned by a set of vectors. I’ve been alluding to the fact that to solve the regression problem in higher dimensions, we’d need to be able to project a vector onto the span of a set of vectors. (To be clear, we haven’t done this yet.) Matrices will allow us to achieve this goal elegantly. It will take a few sections to get there:

In Chapter 5.1, we’ll define matrices and learn to perform basic operations on them.
In Chapter 5.3, we’ll define the column space, row space, null space, and rank of a matrix, while introducing the CR decomposition along the way.
In Chapter 6.1, we’ll understand matrix-vector multiplication as a transformation of the vector, and in Chapter 6.2 we’ll learn how to invert a matrix and compute its determinant.
In Chapter 6.3, we’ll learn to project a vector onto the span of the columns of a matrix, closing the loop with Chapter 3.4.

Just remember that all of this is for machine learning.

For now, let’s consider the following three vectors in $\mathbb{R}^4$ :

\vec v_1 = \begin{bmatrix} 3 \\ 2 \\ 0 \\ 2 \end{bmatrix}, \quad \vec v_2 = \begin{bmatrix} 1 \\ 1 \\ -1 \\ -2 \end{bmatrix}, \quad \vec v_3 = \begin{bmatrix} 4 \\ 9 \\ 0 \\ 0 \end{bmatrix}

If we stack these vectors horizontally, we produce a matrix:

\begin{bmatrix} \mid & \mid & \mid \\ \vec v_1 & \vec v_2 & \vec v_3 \\ \mid & \mid & \mid \end{bmatrix} = \begin{bmatrix} 3 & 1 & 4 \\ 2 & 1 & 9 \\ 0 & -1 & 0 \\ 2 & -2 & 0 \end{bmatrix}

$A$ is a matrix with 4 rows and 3 columns, so we might say that $A$ is a $4 \times 3$ matrix, or that $A \in \mathbb{R}^{4 \times 3}$ .

It’s common to use the notation $A_{ij}$ to denote the entry in the $i$ -th row and $j$ -th column of $A$ , e.g. $A_{23} = 9$ .

In numpy, you can access the entry in the 2nd row and 3rd column of the 2D matrix A using A[1, 2], once we account for the fact that numpy uses 0-based indexing.

Activity 1

In the cell above, try and find the bottom-right entry of A, first using positive indexing and then using negative indexing.

I’ve introduced matrices in a very particular way, because I’d like for you to think of them as a collection of vectors, sometimes called column vectors. We’ll come back to this in just a moment. You can also think of a matrix as a collection of row vectors; the example $A$ defined above consists of four row vectors in $\mathbb{R}^3$ stacked horizontally.

When we introduced vectors, $n$ was typically the placeholder we’d use for the number of components of a vector. With matrices, I like using $n$ for the number of rows, and $d$ for the number of columns. This means that, in general, a matrix is of shape $n \times d$ and is a member of the set $\mathbb{R}^{n \times d}$ . This makes clear that when we’ve collected data, we store each of our $n$ observations in a row of our matrix. Just be aware that using $n \times d$ to denote the shape of a matrix is a little unorthodox; most other textbooks will use $m \times n$ to denote the shape of a matrix. Of course, this is all arbitrary.

Suppose $A$ has $n$ rows and $d$ columns, i.e. $A \in \mathbb{R}^{n \times d}$ .

If $n > d$ , we say that $A$ is tall.
If $n = d$ , we say that $A$ is square.
If $n < d$ , we say that $A$ is wide.

\underbrace{\begin{bmatrix} 5 & 3 \\ 2 & 1 \\ -1 & \frac{1}{3} \\ 3 & 6 \\ 0 & 1 \end{bmatrix}}_{\text{tall}} \qquad \underbrace{\begin{bmatrix} 3 & 0 & 4 \\ 4 & -\pi & 0 \\ \frac{1}{2} & 0 & 1 \end{bmatrix}}_{\text{square}} \qquad \underbrace{\begin{bmatrix} 1 & 0 & 3 & 2 & -1 \\ \frac{1}{9} & 3 & 0 & 0 & 2 \\ 9 & 0 & 0 & 6 & -3 \end{bmatrix}}_{\text{wide}}

As we’ll see in the coming sections, square matrices are the most flexible – there are several properties and operations that are only defined for them. Unfortunately, not every matrix is square. Remember, matrices are used for storing data, and the number of observations, $n$ and number of features, $d$ , don’t need to be the same. (In practice, we’ll often have very tall matrices, i.e. $n \gg d$ , but this is not always the case.)

Addition and Scalar Multiplication¶

Like vectors, matrices support addition and scalar multiplication out-of-the-box, and both behave as you’d expect.

Let’s see an example. Consider the matrices $A$ and $B$ (where $A$ is the same as in the previous example):

A = \begin{bmatrix} 3 & 1 & 4 \\ 2 & 1 & 9 \\ 0 & -1 & 0 \\ 2 & -2 & 0 \end{bmatrix}, \quad B = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{bmatrix}

Then, the operation $3A - B$ is well-defined, and produces the matrix

3A - B = 3 \begin{bmatrix} 3 & 1 & 4 \\ 2 & 1 & 9 \\ 0 & {\color{#3d81f6} \mathbf{-1}} & 0 \\ 2 & -2 & 0 \end{bmatrix} - \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & \color{#3d81f6} \mathbf{8} & 9 \\ 10 & 11 & 12 \end{bmatrix} = \begin{bmatrix} 8 & 1 & 9 \\ 2 & -2 & 21 \\ -7 & \boxed{\color{#3d81f6} \mathbf{-11}} & -9 \\ -4 & -17 & -12 \end{bmatrix}

I’ve colored the entry at position $(3, 2)$ $\color{#3d81f6} \text{blue}$ to help you trace the computation.

3 \cdot (-1) - 8 = -11

Matrix-Vector Multiplication¶

Great – we know how to add two matrices, and how to multiply a matrix by a scalar. The natural next step is to figure out how – and why – to multiply two matrices together.

First, a definition.

Let’s use the Golden Rule. First – as the title of this subsection suggests – we’ll start by computing the product of a matrix and a vector.

Let’s suppose $A$ is the same $4 \times 3$ matrix we’ve become familiar with:

A = \begin{bmatrix} 3 & 1 & 4 \\ 2 & 1 & 9 \\ 0 & -1 & 0 \\ 2 & -2 & 0 \end{bmatrix}

And let’s suppose $\vec x$ is some vector. Note that we can think of an $n$ -dimensional vector as a matrix with $n$ rows and 1 column. In order for the product $A \vec x$ to be valid, $\vec x$ must have 3 elements in it, by the Golden Rule above. To make the example concrete, let’s suppose:

\vec x = \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix}

How do we multiply $A \vec x$ ? The following key definition will help us.

Let me say a little more about the dimensions of the output. Below, I’ve written the dimensions of $A$ ( $4 \times 3$ ) and $\vec x$ ( $3 \times 1$ ) next to each other. By the Golden Rule, the inner dimensions, both of which are bolded, must be equal in order for the multiplication to be valid. The dimensions of the output will be the result of looking at the $\boxed{\text{outer dimensions}}$ , which here are $4 \times 1$ .

\underbrace{A}_{\boxed{4} \times \textbf{3}} \:\:\:\: \underbrace{\vec x}_{\textbf{3} \times \boxed{1}} = \underbrace{\text{output}}_{4 \times 1}

So, the result of multiplying $A \vec x$ will be $4 \times 1$ matrix, or in other words, a vector in $\mathbb{R}^4$ . Indeed, the result of multiply a matrix by a vector always results in another vector, and this act of multiplying a matrix by a vector is often thought of as transforming the vector from $\mathbb{R}^d$ to $\mathbb{R}^n$ .

So, how do we find those 4 components? As mentioned earlier, we compute each component by taking the dot product of a row in $A$ with $\vec x$ .

A = \begin{bmatrix} \color{#3d81f6} \mathbf{3} & \color{#3d81f6} \mathbf{1} & \color{#3d81f6} \mathbf{4} \\ {\color{orange} \mathbf{2}} & {\color{orange} \mathbf{1}} & {\color{orange} \mathbf{9}} \\ {\color{#d81b60}\mathbf{0}} & {\color{#d81b60} \mathbf{-1}} & {\color{#d81b60} \mathbf{0}} \\ {\color{#004d40} \mathbf{2}} & {\color{#004d40} \mathbf{-2}} & {\color{#004d40} \mathbf{0}} \end{bmatrix}, \quad \vec x = \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix}

Let’s start with the top row of $A$ , $\color{#3d81f6}\begin{bmatrix} 3 \\ 1 \\ 4\end{bmatrix}$ . The dot product of two vectors is only defined if they have equal lengths. This is why we’ve instituted the Golden Rule! The Golden Rule tells us we can only multiply $A$ and $\vec x$ if the number of columns in $A$ is the same as the number of components in $\vec x$ , which is true here (both of those numbers are 3).

Then, the dot product of the first row of $A$ with $\vec x$ is:

{\color{#3d81f6}\begin{bmatrix} \mathbf{3} \\ \mathbf{1} \\ \mathbf{4} \end{bmatrix}} \cdot \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix} = {\color{#3d81f6} \mathbf{3}} \cdot 1 + {\color{#3d81f6} \mathbf{1}} \cdot 0 + {\color{#3d81f6} \mathbf{4}} \cdot 3 = 15

Nice! We’re a quarter of the way there. Now, we just need to compute the remaining three dot products:

The dot product of the second row of $A$ with $\vec x$ is ${\color{orange}\begin{bmatrix} \mathbf{2} \\ \mathbf{1} \\ \mathbf{9} \end{bmatrix}} \cdot \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix} = 29$ .
The dot product of the third row of $A$ with $\vec x$ is ${\color{#d81a60}\begin{bmatrix} \mathbf{0} \\ \mathbf{-1} \\ \mathbf{0} \end{bmatrix}} \cdot \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix} = 0$ .
And finally, the dot product of the fourth row of $A$ with $\vec x$ is ${\color{#004d40}\begin{bmatrix} \mathbf{2} \\ \mathbf{-2} \\ \mathbf{0} \end{bmatrix}} \cdot \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix} = 2$ .

The result of our matrix-vector multiplication, then, is the result of stacking all 4 dot products together into the vector $\begin{bmatrix} {\color{#3d81f6} \mathbf{15}} \\ {\color{orange} \mathbf{29}} \\ {\color{#d81b60} \mathbf{0}} \\ {\color{#004d40} \mathbf{2}} \end{bmatrix}$ . To summarize:

\boxed{A \vec x = \begin{bmatrix} {\color{#3d81f6} \mathbf{3}} & {\color{#3d81f6} \mathbf{1}} & {\color{#3d81f6} \mathbf{4}} \\ {\color{orange} \mathbf{2}} & {\color{orange} \mathbf{1}} & {\color{orange} \mathbf{9}} \\ {\color{#d81b60}\mathbf{0}} & {\color{#d81b60} \mathbf{-1}} & {\color{#d81b60} \mathbf{0}} \\ {\color{#004d40} \mathbf{2}} & {\color{#004d40} \mathbf{-2}} & {\color{#004d40} \mathbf{0}} \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix} = \begin{bmatrix} {\color{#3d81f6} \mathbf{15}} \\ {\color{orange} \mathbf{29}} \\ {\color{#d81b60} \mathbf{0}} \\ {\color{#004d40} \mathbf{2}} \end{bmatrix}}

Refer to this example if you’re ever confused on how to multiply a matrix by a vector.

We can’t visualize the output vector as it’s in 4 dimensions, but we can look at the 4 row vectors of $A$ and the vector $\vec x$ in 3D space.

from utils import plot_vectors

plot_vectors([((3, 1, 4), '#3d81f6', 'row 1'), 
              ((2, 1, 9), 'orange', 'row 2'), 
              ((0, -1, 0), '#d81b60', 'row 3'),
              ((2, -2, 0), '#004d40', 'row 4'),
              ((1, 0, 3), 'purple', r'x')],
              vdeltax=0.8, vdeltay=0.8)

Above, you’ll notice that $\color{purple} \vec x$ and the third row vector, $\color{#d81b60} \begin{bmatrix} \mathbf{0} \\ \mathbf{-1} \\ \mathbf{0} \end{bmatrix}$ , are orthogonal (rotate the plot so that you can see this), so the third component in

A \vec x = \begin{bmatrix} {\color{#3d81f6} \mathbf{15}} \\ {\color{orange} \mathbf{29}} \\ {\color{#d81b60} \mathbf{0}} \\ {\color{#004d40} \mathbf{2}} \end{bmatrix}

is ${\color{#d81b60} \mathbf{0}}$ .

Activity 2

We’ll try not to bore you with mundane calculations in the future, but it’s important to perform matrix-vector multiplication by hand a few times to understand how it works.

In each part, perform the matrix-vector multiplication by hand or state that it cannot be done.

$\begin{bmatrix} 7 & 8 & -1 \\ 0 & 1 & 2 \\ 9 & 0 & \frac{1}{2} \end{bmatrix} \begin{bmatrix} 5 \\ 4 \\ 8 \end{bmatrix}$
$\begin{bmatrix} 7 & 8 & -1 \\ 0 & 1 & 2 \\ \end{bmatrix} \begin{bmatrix} 5 \\ 4 \end{bmatrix}$
$\begin{bmatrix} 4 & 2 & 3 \\ 1 & 0 & 1 \\ 5 & 4 & 3 \\ 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 5 \\ 4 \\ 8 \end{bmatrix}$
$\begin{bmatrix} 4 & 2 & 3 \\ 1 & 0 & 1 \\ 5 & 4 & 3 \\ 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 7 & 8 & -1 \\ 0 & 1 & 2 \\ 9 & 0 & \frac{1}{2} \end{bmatrix} \begin{bmatrix} 5 \\ 4 \\ 8 \end{bmatrix}$
(While we haven’t yet looked at how to compute the product of two matrices, you can still answer this just using what you know about matrix-vector multiplication.)

In the cell below, use numpy to verify your answers. You’ll need to define the matrices and vectors as numpy arrays, and use the @ operator to perform the matrix-vector multiplication.

The Linear Combination Interpretation¶

We’ve described matrix-vector multiplication as the result of taking the dot product of each row of $A$ with $\vec x$ , and indeed this is the easiest way to actually compute the output. But, there’s another more important interpretation. In the above dot products, you may have noticed:

Entries in the first column of $A$ (3, 2, 0, and 2) were always multiplied by the first element of $\vec x$ (1).
Entries in the second column of $A$ (1, 1, -1, and -2) were always multiplied by the second element of $\vec x$ (0).
Entries in the third column of $A$ (4, 9, 0, and 0) were always multiplied by the third element of $\vec x$ (3).

In other words:

A \vec x = \begin{bmatrix} 3 & 1 & 4 \\ 2 & 1 & 9 \\ 0 & -1 & 0 \\ 2 & -2 & 0 \end{bmatrix} \begin{bmatrix} \color{orange} \mathbf{1} \\ \color{orange} \mathbf{0} \\ \color{orange} \mathbf{3} \end{bmatrix} = \underbrace{{\color{orange} \mathbf{1}} \begin{bmatrix} 3 \\ 2 \\ 0 \\ 2 \end{bmatrix} + {\color{orange} \mathbf{0}} \begin{bmatrix} 1 \\ 1 \\ -1 \\ -2 \end{bmatrix} + {\color{orange} \mathbf{3}} \begin{bmatrix} 4 \\ 9 \\ 0 \\ 0 \end{bmatrix}}_{\color{orange} \text{linear combination of columns of A}} = \begin{bmatrix} 15 \\ 29 \\ 0 \\ 2 \end{bmatrix}

At the start of this section, we defined $A$ by stacking the vectors $\vec v_1$ , $\vec v_2$ , and $\vec v_3$ side-by-side, and I told you to think of a matrix as a collection of column vectors. The above result is precisely why – it’s because when we multiply $A$ by $\vec x$ , we’re computing a linear combination of the columns of $A$ , where the weights are the components of $\vec x$ !

Since $A \vec x$ produces a linear combination of the columns of $A$ , a natural question to ask at this point is whether the columns of $A$ are all linearly independent. $A$ only has 3 columns, each of which is in $\mathbb{R}^4$ , so while they may or may not be linearly independent (are they?), we know they cannot span all of $\mathbb{R}^4$ , as we’d need at least 4 vectors to reach every element in $\mathbb{R}^4$ .

This is the type of thinking we’ll return to in Chapter 5.3. This will lead us to define the rank of a matrix, perhaps the single most important number associated with a matrix.

The Two Pictures

Any time you see a matrix-vector product, like $A \vec x$ , you should think of it not as a random operation, but as:

(More Important) A linear combination of the columns of $A$ , where the weights are the components of $\vec x$ .
$A \vec x = x_1 \left( \text{column } 1 \text{ of } A \right) + x_2 \left( \text{column } 2 \text{ of } A \right) + \ldots + x_d \left( \text{column } d \text{ of } A \right)$
A dot product of the rows of $A$ with $\vec x$ .
$A \vec x = \begin{bmatrix} (\text{row 1 of } A) \cdot \vec x \\ (\text{row 2 of } A) \cdot \vec x \\ \vdots \\ (\text{row n of } A) \cdot \vec x \end{bmatrix}$

Activity 3

Consider the matrix $M$ defined below.

M = \begin{bmatrix} 2 & -1 & 3 & 0 & 4 \\ 1 & 5 & -2 & 1 & 0 \end{bmatrix}

In each of the following parts, write out $\vec u$ concretely, compute $M \vec u$ , and explain the result in English.

A vector whose second component is 1, and whose other components are 0.
A vector containing all 1s.
A vector containing all $\frac{1}{5}$ s.
A vector whose components sum to 1, whose first component is $\frac{3}{5}$ , and whose other components are all equal to one another.

Matrix Multiplication¶

Matrix-matrix multiplication – or just “matrix multiplication” – is a generalization of matrix-vector multiplication. Let’s present matrix multiplication in its most general terms.

Definition¶

Note that if $p = 1$ , this reduces to the matrix-vector multiplication case from before. In that case, the only possible value of $j$ is 1, since the output only has 1 column, and the element in row $i$ of the output vector is the dot product of row $i$ in $A$ and the vector $B$ (which we earlier referred to as $\vec x$ in the less general case).

For a concrete example, suppose $A$ and $B$ are defined below:

A = \begin{bmatrix} 3 & 1 & 4 \\ 2 & 1 & 9 \\ 0 & -1 & 0 \\ 2 & -2 & 0 \end{bmatrix} \quad B = \begin{bmatrix} 1 & 2\\ 0 & 7\\ 3 & 2 \end{bmatrix}

The number of columns of $A$ must equal the number of rows of $B$ in order for the product $AB$ to be defined, as the Golden Rule tells us. That is fortunately the case here. Since $A$ has shape $\boxed{4} \times 3$ and $B$ has shape $3 \times \boxed{2}$ , the output matrix will have shape $4 \times 2$ . Each of those $4 \cdot 2 = 8$ elements will be the dot product of a row in $A$ with a column in $B$ .

Here is the product of $A$ and $B$ :

AB = \begin{bmatrix} {\color{#3d81f6} \mathbf{3}} & {\color{#3d81f6} \mathbf{1}} & {\color{#3d81f6} \mathbf{4}} \\ {\color{orange} \mathbf{2}} & {\color{orange} \mathbf{1}} & {\color{orange} \mathbf{9}} \\ {\color{#d81b60}\mathbf{0}} & {\color{#d81b60} \mathbf{-1}} & {\color{#d81b60} \mathbf{0}} \\ {\color{#004d40} \mathbf{2}} & {\color{#004d40} \mathbf{-2}} & {\color{#004d40} \mathbf{0}} \end{bmatrix} \begin{bmatrix} 1 & 2\\ 0 & 7\\ 3 & 2 \end{bmatrix} = \begin{bmatrix} {\color{#3d81f6} \mathbf{15}} & \color{#3d81f6} \mathbf{21} \\ \color{orange} \mathbf{29} & \color{orange} \mathbf{29} \\ \color{#d81b60} \mathbf{0} & \color{#d81b60} \mathbf{-7} \\ \color{#004d40} \mathbf{2} & \color{#004d40} \mathbf{-10} \end{bmatrix}

Let’s see if we can audit where these numbers came from. Let’s consider $(AB)_{32}$ , which is the element in row 3 and column 2 of the output. It should have come from the dot product of row 3 of $A$ and column 2 of $B$ .

AB = \begin{bmatrix} {\color{#3d81f6} \mathbf{3}} & {\color{#3d81f6} \mathbf{1}} & {\color{#3d81f6} \mathbf{4}} \\ {\color{orange} \mathbf{2}} & {\color{orange} \mathbf{1}} & {\color{orange} \mathbf{9}} \\ {\color{#d81b60}\boxed{\mathbf{0}}} & {\color{#d81b60} \boxed{\mathbf{-1}}} & {\color{#d81b60} \boxed{\mathbf{0}}} \\ {\color{#004d40} \mathbf{2}} & {\color{#004d40} \mathbf{-2}} & {\color{#004d40} \mathbf{0}} \end{bmatrix} \begin{bmatrix} 1 & \boxed{2}\\ 0 & \boxed{7}\\ 3 & \boxed{2} \end{bmatrix} = \begin{bmatrix} {\color{#3d81f6} \mathbf{15}} & \color{#3d81f6} \mathbf{21} \\ \color{orange} \mathbf{29} & \color{orange} \mathbf{29} \\ \color{#d81b60} \mathbf{0} & \color{#d81b60} \boxed{\mathbf{-7}} \\ \color{#004d40} \mathbf{2} & \color{#004d40} \mathbf{-10} \end{bmatrix}

And indeed, -7 is the dot product of $\color{#d81b60}\begin{bmatrix} \mathbf{0} \\ \mathbf{-1} \\ \mathbf{0} \end{bmatrix}$ and $\begin{bmatrix} 2 \\ 7 \\ 2 \end{bmatrix}$ .

You should notice that many of the numbers in the output $AB$ look familiar. That’s because we used the same $A$ as we did earlier in the section, and the first column of $B$ is just $\vec x$ from the matrix-vector example. So, the first column in $AB$ is the same as the vector $A \vec x = \begin{bmatrix} 15 \\ 29 \\ 0 \\ 2\end{bmatrix}$ as we computed earlier. The difference now is that the output $AB$ isn’t just a single vector, but is a matrix with 2 columns. The second column, $\begin{bmatrix} 21 \\ 29 \\ -7 \\ -10\end{bmatrix}$ , comes from multiplying $A$ by the second column in $B$ , $\begin{bmatrix} 2 \\ 7 \\ 2\end{bmatrix}$ .

Note that as we add columns to $B$ , we’d add columns to the output. If $B$ had 10 columns, then $AB$ would have 10 columns, too, without $A$ needing to change. As long as the Golden Rule – that the number of columns in $A$ equals the number of rows in $B$ – holds, the product $AB$ can be computed, and it has shape $(\text{number of rows in } A) \times (\text{number of columns in } B)$ .

Properties¶

The first two properties – associativity and distributivity – match standard arithmetic properties that we’ve become accustomed to. The associative property allows you to, for example, compute $AB \vec x$ only by using matrix-vector multiplications, since you can first multiply $B \vec x$ , which results in a vector, and then multiply $A$ by that vector. (I had you do this in Activity 2 earlier in this section – I hope you did it! 🧐)

The fact that matrix multiplication is not commutative may come as a surprise, as every other form of multiplication you’ve learned about up until this point has been commutative (including the dot product).

In fact, if $AB$ exists, $BA$ may or may not! If $A$ is $n \times d$ and $B$ is $d \times p$ , then $BA$ only exists if $n = p$ . But even then, $AB \neq BA$ in general.

For example, if $A$ is $2 \times 3$ and $B$ is $3 \times 2$ , then $AB$ is $2 \times 2$ and $BA$ is $3 \times 3$ ; here, both products exist, but they cannot be equal since they have different shapes.

Even if $A$ and $B$ are both square matrices with the same shape, $AB \neq BA$ in general. For illustration, consider:

A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}, \quad B = \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix}

Then,

AB = \begin{bmatrix} 19 & 22 \\ 43 & 50 \end{bmatrix} \neq BA = \begin{bmatrix} 23 & 34 \\ 31 & 46 \end{bmatrix}

Activity 4

Activity 4.1

Let $P = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$ , $S = \begin{bmatrix} 4 & 0 & 0 \\ 0 & \frac{1}{2} & 0 \\ 0 & 0 & 3 \end{bmatrix}$ , and $\vec x = \begin{bmatrix} 4 \\ 6 \\ 12 \end{bmatrix}$ .

Evaluate $P \vec x$ and $S \vec x$ . Then, explain in words what multiplying $P$ and $S$ by $\vec x$ does to $\vec x$ .
Evaluate $PS \vec x$ and $SP \vec x$ . The results should be different, as we’d expect, since matrix multiplication is not commutative in general. Explain the difference intuitively, given the “operations” $P$ and $S$ perform on $\vec x$ .

$P$ is called a permutation matrix, and $S$ is called a diagonal matrix.

Activity 4.2

The famous Fibonacci sequence of integers, $F_0, F_1, F_2, \ldots$ , is defined as follows:

F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \text{ for } n \geq 2

The first few terms in the sequence are $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \ldots$ .

It turns out you can compute the $n$ th term in the sequence using matrix multiplication.

Find a $2 \times 2$ matrix $A$ such that $A \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} = \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix}$ . The answer uses relatively small numbers.
Compute $A \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ , i.e. the product of $A$ and the vector $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$ .
Since $A$ is square, we can multiply it by itself. Compute $A^2 \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ and $A^3 \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ .

If you continue this process, you’ll find that $A^n \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ is a vector containing the $n$ th and $(n-1)$ th terms in the Fibonacci sequence!

Activity 4.3

Using the same matrices $P$ and $S$ from Activity 4.1, compute $(P - S) \vec x$ and $P\vec x - S \vec x$ . Are both the results the same? If so, what property of matrix multiplication guarantees this?

Is the result of $(P - S) \vec x$ interpretable, in the same way that the results of $P \vec x$ and $S \vec x$ were in Activity 4.1?

Computation¶

I’ve shown you the naïve – and by far most common – algorithm for matrix multiplication. If $A$ and $B$ are both square $n \times n$ matrices, then the runtime of the naïve algorithm is $O(n^3)$ .

However, there exist more efficient algorithms for matrix multiplication. Strassen’s algorithm is one such example; it describes how to multiply two square $n \times n$ matrices in $O(n^{2.807})$ time. The study of efficient algorithms for matrix multiplication is an active area of research; if you’re interested in learning more, look here.

Matrix multiplication, I might argue, is one of the reasons NVIDIA is the most valuable company in the world. Modern machine learning is built on matrix multiplication, and GPUs are optimized for it. Why? This comment from Reddit does a good job of explaining:

Imagine you have 1 million math assignments to do, they are very simple assignments, but there are a lot that need to be done, they are not dependent on each other so they can be done on any order.
You have two options, distribute them to 10 thousand people to do it in parallel or give them to 10 math experts. The experts are very fast, but hey, there are only 10 of them, the 10 thousand are more suitable for the task because they have the “brute force” for this.
GPUs have thousands of cores, CPUs have tens.

On that note, the @ operator in numpy is used for matrix multiplication; it is a shorthand for np.matmul. You can also use it to multiply a matrix by a vector.

Next, we look at the transpose and other special matrices that show up throughout linear algebra.