Perspectives on matrix multiplication¶

Lots of you seem to have learned how to multiply matrices (matrix multiplication) in high school.
We compute the product $C=AB$ of an $m \times n$ matrix $A$ with an $n \times p$ matrix $B$ to produce an $m \times p$ matrix $C$.

Did you ever wonder why "matmul" has such a fancy definition?

When we add matrices we add elements. Why coudn't matmul be just as easy?

Compare Elementwise Multiply¶

Of course the elementwise multiply is doable but never seems to be quite as important:

(I'll bet your high school teacher never mentioned elementwise multiply!)

For square n x n matrices, elementwise multiply requires $n^2$ operations, while matmul requires about $2n^3$. (Think $n^2$ dot products, each requiring $n$ mults and almost $n$ adds.)

Raising the Abstraction¶

Why is matmul defined this way? We will find out later in the course when we begin to understand that a matrix represents a linear transformation, and matmul is the natural representation of the composition of transformations. It is only then you can understand the true nature of matrix multiplication. (Bet your high school teacher never told you that!)

One of our goals in 18.06 is to sometimes stop thinking of matrices as arrays of numbers, and more as holistic objects.

Abstractly, the rules for matrix multiplication are determined once you define how to multiply matrices by vectors $Ax$, the central linear operation of 18.06, by requiring that multiplication be associative. That is, we require: $$ A(Bx)=(AB)x $$ for all matrices $A$ and $B$ and all vectors $x$. The expression $A(Bx)$ involves only matrix × vector (computing $y=Bx$ then $Ay$), and requiring this to equal $(AB)x$ actually uniquely defines the matrix–matrix product $AB$.

Perspective 1 (high school!): rows × columns¶

The most familar definition is that you take dot products of rows of A with columns of B to get the product $C$. For example: $$ \begin{pmatrix} -14 & 5 & 10 \\ \color{red}{-5} & -20 & 10 \\ -6 & 10 & 6 \end{pmatrix} = \begin{pmatrix} 2 & -1 & 5 \\ \color{red}{3} & \color{red}{4} & \color{red}{4} \\ -4 & -2 & 0 \end{pmatrix} \begin{pmatrix} \color{red}{1} & 0 & -2 \\ \color{red}{1} & -5 & 1 \\ \color{red}{-3} & 0 & 3 \end{pmatrix} $$ where we have highlighted the entry $\color{red}{-5 = 3 \times 1 + 4 \times 1 + 4 \times -3}$ (second row of $A$ ⋅ first column of $B$).

This can be written out as the formula $$ c_{ij} = \sum_{k=1}^n a_{ik} b_{kj} $$ in terms of the entries of the matrices, e.g. $c_{ij}$ is the entry in row $i$, column $j$ of $C$, assuming $A$ has $n$ columns and $B$ has $n$ rows.

Essentially all matrix multiplications in practice are done with a version of this formula — at least, with the same operations, but often the order in which you multiply/add individual numbers is re-arranged.

In this notebook, we will explore several ways to think about these operations by re-arranging their order.

Because matrix multiplication is generally not commutative, $AB$ and $BA$ give different matrices:

Though sometimes it can happen to be commutative.

If we want, we can compute the individual dot products in Julia too. For example, let's compute $c_{2,1} = -5$ (the 2nd row and first column of $C$, or C[2,1] in Julia) by taking the dot product of the second row of $A$ with the first column of $B$.

To extract rows and columns of a matrix, Julia supports a syntax for "array slicing" pioneered by APL. The second row of $A$ is A[2,:], and the first column of B is B[:,1]:

Now we can compute $c_{2,1}$ by their dot product via the dot function:

We can also write the dot product with the $x \dot y$ notation:

This matches $c_{2,1}$ from above, or C[2,1] in Julia:

The summation $$c_{ij} = \sum_{k=1}^n a_{ik} b_{kj}$$ directly in a triple loop code¶

Perspective 2: matrix × columns¶

$AB$ can be viewed as multiplying $A$ on the left by each column of $B$.

For example, let's multiply $A$ by the first column of $B$:

This is the first column of $C$! If we do this to all the columns of $B$, we get $C$:

Equivalently, each column of $B$ specifies a linear combination of columns of $A$ to produce the columns of $C$. So, if you want to rearrange the columns of a matrix, multiply it by another matrix on the *right*.

For example, let's do the transformation that flips the sign of the first column of $A$ and swaps the second and third columns.

As another example, let's swap the first two columns:

A lot of students are perplexed. They wonder how it could be legal to reorder in this way. It might take working through a few examples by hand to realize that from the perspective of C[i,j], the same sum is accumulated in the same order, but the order in which the different elements of C finish may vary. This little Julia demo may help with this understanding.

Perspective 3: rows × matrix¶

$AB$ can be viewed as multiplying each row of $A$ by the matrix $B$ on the right. Multiplying a row vector by a matrix on the right produces another row vector.

For example, here is the first row of $A$:

Whoops, slicing a matrix in Julia produces a 1d array, which is interpreted as a column vector, no matter how you slice it. We can't multiply a column vector by a matrix $B$ on the right — that operation is not defined in linear algebra (the dimensions don't match up). Julia will give an error if we try it:

To get a row vector we must transpose the slice A[1,:]. In linear algebra, the transpose of a vector $x$ is usually denoted $x^T$. In Julia, the transpose is x.'.

If we omit the . and just write x' it is the complex-conjugate of the transpose, sometimes called the adjoint, often denoted $x^H$ (in matrix textbooks), $x^*$ (in pure math), or $x^\dagger$ (in physics). For real-valued vectors (no complex numbers), the conjugate transpose is the same as the transpose, and correspondingly we usually just do x' for real vectors.

Now, let's multiply this by $B$, which should give the first row of $C$:

Yup!

Note that if we multiply a row vector by a matrix on the left, it doesn't really make sense. Julia will give an error:

If we multiply $B$ on the right by all the rows of $A$, we get $C$ again:

Equivalently, each row of $A$ specifies a linear combination of rows of $B$ to produce the rows of $C$. So, if you want to rearrange the rows of a matrix, multiply it by another matrix on the *left*.

For example, let's do the transformation that adds two times the first row of $B$ to the third row, and leaves the other rows untouched. This is resembles one of the steps of Gaussian elimination!

In fact, we can write exactly one of the steps for Gaussian elimination on $B$ in this form:

Let's do the transformation that adds three times the first row of $B$ to the third row, subtracts the first row from the second, and leaves the first row untouched.

As desired, this "eliminates" the sub-diagonal entries of the first column of B. The nice thing about writing elimination algebraically in this way, instead of in words, is that it will allow us to think about the elimination process algebraically.

Perspective 4: columns × rows¶

The key to this perspective is to observe:

• elements in column $i$ of $A$ only multiply elements in row $j$ of $B$
• a column times a row vector, sometimes denoted $xy^T$, is an outer product and produces a "rank-1" matrix

(See this excellent paper by Gil Strang for more on this perspective applied to linear algebra. You will be in a better position to understand this at the end of 18.06, however.)

For example, here is column 1 of $A$ times row 1 of $B$:

If we do this for all three rows and columns and add them up, we get $C$:

So, from this perspective, we could write:

$$ AB = \sum_{k=1}^3 (\mbox{column } k \mbox{ of } A) (\mbox{row } k \mbox{ of } B) = \sum_{k=1}^3 A[:,k] \, B[k,:]^T $$

where in the last expression we have used Julia notation for slices.

Perspective 5: submatrix blocks × blocks¶

It turns out that all of the above are special cases of a more general rule, by which we can break up a matrix in to "submatrix" blocks and multiply the blocks. Rows, columns, etc. are just blocks of different shapes. We will do more of this later in the course.