LibreNotebook

0.1 Matrix Multiplication

Before we get into formulas and computations, let’s build our intuition on what a matrix and its multiplication is supposed to represent. We will discuss linear transformation in depth in latter notes, but we can think of it as a function that transforms the vector space. Matrix instructs the function how to transform the space. Let’s take a look at a quick example.

Let \(A\) be a matrix that has order \(2 \times 2\). The first column tells how to map the \(\hat {i}\) and the second column represents where our \(\hat {j}\) is mapped. \[ \begin {bmatrix} 2 & 1 \\ 1 & 3 \end {bmatrix} \] Matrix \(A\) is telling us to map the standard basis \(\hat {i} = \langle 1, 0 \rangle \) to \(\hat {i}'= \langle 2, 1 \rangle \) and from \(\hat {j} = \langle 0, 1 \rangle \) to \(\hat {j}' = \langle 1, 3 \rangle \). Consider the diagram below.

After the transformation, you can imagine mapping everything in the standard vector space with respect to the new colored space. That, is what matrix multiplication does. See how a vector \(\vec {v} = \langle 1, 2 \rangle \) is now on \(\langle 4, 7 \rangle \). Using matrix multiplication, we can represent the mapping as the following. \[ \begin {bmatrix} 2 & 1 \\ 1 & 3 \end {bmatrix} \begin {bmatrix} 1 \\ 2 \end {bmatrix} = \begin {bmatrix} 4 \\ 7 \end {bmatrix} \] Because we cannot draw such planes every time, let’s take a look at how the vector \(\vec {v} = \langle 1, 2 \rangle \) is mapped to \(\langle 4, 7 \rangle \). First, from the previous note, we have seen that the first row represents the \(x\) coordinate and the second row represents the \(y\) coordinate. Now, to find where the point \((1, 2)\) is located in the “scaled” version, we could simply look at the basis vectors in the “scaled” plane. Because the vector that we are looking for is the sum of the two “scaled” basis vector, we can represent our multiplication as the following. \[ \begin {bmatrix} 2 & 1 \\ 1 & 3 \end {bmatrix} \begin {bmatrix} 1 \\ 2 \end {bmatrix} = 1 \begin {bmatrix} 2 \\ 1 \end {bmatrix} + 2 \begin {bmatrix} 1 \\ 3 \end {bmatrix} = \begin {bmatrix} 2 \\ 1 \end {bmatrix} + \begin {bmatrix} 2 \\ 6 \end {bmatrix} = \begin {bmatrix} 4 \\ 7 \end {bmatrix} \] Nice! We get the same result. Now that we have intuitions on what a matrix and its multiplication represents, let’s take a look at algebraic properties and resulting formulas from the intuition.

0.1.1 The Method and Properties

As you can see above, matrix multiplication is not defined elementwise unlike addition and scalar multiplication. First, take a look at the following formula for individual elements.

Theorem 0.1.1

For matrices \([a_{ij}]_{m \times n}\) and \([b_{ij}]_{n \times p}\), the elements \(c_{ij}\) of the product matrix \([c_{ij}]_{m \times p}\) are defined as the following expression. \[ c_{ij} = \sum _{k=1}^{n} a_{ik} b_{kj} \]

Let’s take a look at an example to see how this works.

Exercise 0.1.2

Compute the following matrix multiplication. \[ \begin {bmatrix} 2 & 3 & 4 \\ 1 & 5 & -1 \end {bmatrix} \begin {bmatrix} 1 & 2 \\ 2 & 3 \\ 4 & 0 \end {bmatrix} \]

Solution.

Consider the following computation. \begin{align*} \begin {bmatrix} \tikzmarknode {a11}{2} & \tikzmarknode {a12}{3} & \tikzmarknode {a13}{4} \\ \tikzmarknode {a21}{1} & \tikzmarknode {a22}{5} & \tikzmarknode {a23}{-1} \end {bmatrix} \begin {bmatrix} \tikzmarknode {b11}{1} & \tikzmarknode {b12}{2} \\ \tikzmarknode {b21}{2} & \tikzmarknode {b22}{3} \\ \tikzmarknode {b31}{4} & \tikzmarknode {b32}{0} \end {bmatrix} \begin {tikzpicture}[ overlay, remember picture, arrow/.style = {->, very thick, opacity=0.7} ] \draw [arrow, Red] (a11.west) -- (a13.east); \draw [arrow, Blue] (a21.west) -- (a23.east); \draw [arrow, Red] (b11.north west) -- (b31.south west); \draw [arrow, Blue] (b11.north east) -- (b31.south east); \draw [arrow, Red] (b12.north west) -- (b32.south west); \draw [arrow, Blue] (b12.north east) -- (b32.south east); \end {tikzpicture} &= \begin {bmatrix} \textcolor {Red}{2} \cdot 1 + \textcolor {Red}{3} \cdot 2 + \textcolor {Red}{4} \cdot 4 & \textcolor {Red}{2} \cdot 2 + \textcolor {Red}{3} \cdot 3 + \textcolor {Red}{4} \cdot 0 \\ \textcolor {Blue}{1} \cdot 1 + \textcolor {Blue}{5} \cdot 2 - \textcolor {Blue}{1} \cdot 4 & \textcolor {Blue}{1} \cdot 2 + \textcolor {Blue}{5} \cdot 3 - \textcolor {Blue}{1} \cdot 0 \end {bmatrix} \\ &= \begin {bmatrix} 2 + 6 + 16 & 4 + 9 + 0 \\ 1 + 10 - 4 & 2 + 15 \end {bmatrix} = \begin {bmatrix} 24 & 13 \\ 7 & 17 \end {bmatrix} \end{align*}

It is important to note that matrix multiplication applies under a specific condition.

Theorem 0.1.3

For matrices \(A_{m \times n}\) and \(B_{p \times q}\), the matrices can be multiplied if and only if \(n = p\). The resulting matrix will have order \(m \times q\).

I believe the condition above is somewhat self-evident. When the condition above is not met, we say the product is undefined. Continuing from this condition, we could get an interesting property.

Theorem 0.1.4

Matrix multiplication is not commutative, i.e. for matrices \(A\) and \(B\), it is not necessarily true that \(AB = BA\).

Proof.

I will leave a more formal proof for the readers. However, I believe this is self-evident as for matrices \(A_{m \times n}\) and \(B_{n \times p}\) where \(m \neq p\), \(AB\) is defined while \(BA\) is not.

A fun way of understanding commutativity is to think about transformation questions that we see in elementary or middle school competition math. You might be familiar with questions asking orders of transformation of an object. For instance, let \(A\) be defined as the \(90^\circ \) rotation counterclockwise and let transformation \(B\) be reflection across the \(y\) axis. Is performing \(AB\) equal to \(BA\)? Obviously, the answer is false when you visually think about it. What if we apply the same idea here with matrices?

Notice the matrices \(A\) and \(B\) can be represented as following using matrices. \[ A = \begin {bmatrix} 0 & -1 \\ 1 & 0 \end {bmatrix}, \quad B = \begin {bmatrix} -1 & 0 \\ 0 & 1 \end {bmatrix} \] Taking a look at the visualization, the left diagram represents \(AB\) and the right diagram visualizes \(BA\) with \(\vec {v} = \langle 1, 1 \rangle \) as the reference.

Let’s take a look at what’s happening here. \(\vec {v}''\) in our left diagram can be represented as the following. \[ \vec {v}'' = \begin {bmatrix} -1 & 0 \\ 0 & 1 \end {bmatrix} \left ( \begin {bmatrix} 0 & -1 \\ 1 & 0 \end {bmatrix} \begin {bmatrix} 1 \\ 1 \end {bmatrix} \right ) \] Notice that we have to write it in the order \(B(A\vec {v})\) as we would be performing \(A\) first. We can think of it as reading it from left to right just as we would read from left to right when computing composite functions. \[ \vec {v}'' = \begin {bmatrix} -1 & 0 \\ 0 & 1 \end {bmatrix} \left ( \begin {bmatrix} 0 & -1 \\ 1 & 0 \end {bmatrix} \begin {bmatrix} 1 \\ 1 \end {bmatrix} \right ) = \begin {bmatrix} -1 & 0 \\ 0 & 1 \end {bmatrix} \left ( \begin {bmatrix} -1 \\ 1 \end {bmatrix} \right ) = \begin {bmatrix} 1 \\ 1 \end {bmatrix} \] This is exactly what we have for the left diagram. We could do the same for the right side. \[ \vec {v}'' = \begin {bmatrix} 0 & -1 \\ 1 & 0 \end {bmatrix} \left ( \begin {bmatrix} -1 & 0 \\ 0 & 1 \end {bmatrix} \begin {bmatrix} 1 \\ 1 \end {bmatrix} \right ) = \begin {bmatrix} 0 & -1 \\ 1 & 0 \end {bmatrix} \left ( \begin {bmatrix} -1 \\ 1 \end {bmatrix} \right ) = \begin {bmatrix} -1 \\ -1 \end {bmatrix} \] This is also supported! Alternatively, we could just compute \(AB\) and \(BA\) to see what our “final transformation is”. \begin{align*} BA &= \begin {bmatrix} -1 & 0 \\ 0 & 1 \end {bmatrix} \begin {bmatrix} 0 & -1 \\ 1 & 0 \end {bmatrix} = \begin {bmatrix} 0 & 1 \\ 1 & 0 \end {bmatrix} \\ AB &= \begin {bmatrix} 0 & -1 \\ 1 & 0 \end {bmatrix} \begin {bmatrix} -1 & 0 \\ 0 & 1 \end {bmatrix} = \begin {bmatrix} 0 & -1 \\ -1 & 0 \end {bmatrix} \end{align*}

Clearly, we could see that the mapping is different.

Another interesting property for matrices \(A\), \(B\), and \(C\) is that even if \(AC = BC\), it does not necessarily mean that \(A = B\). Think about the case when \(C\) is a zero matrix. Although matrix multiplication is not commutative, the associative and distributive property still applies.

Theorem 0.1.5

For matrices \(A\), \(B\), and \(C\), the following equations are true given that the conditions for the addition and multiplication are met.

1.: \(A(BC) = (AB)C\)
2.: \(A(B + C) = AB + AC\)
3.: \((B + C)A = BA + CA\)
4.: \(\lambda (AB) = A(\lambda B)\)

Let’s start by proving the associative property.

Proof.

Let \(A = [a_{ij}]_{m \times n}\), \(B = [b_{ij}]_{n \times q}\), and \(C = [c_{ij}]_{q \times r}\). First, notice that the elements of the product \(BC\), or \(D = [d_{ij}]_{n \times r}\) can be represented as \(d_{ij} = \sum _{k=1}^{q} b_{ik} c_{kj}\). Multiplying it again with \([a_{ij}]\), the elements of the product \(E = [e_{ij}]_{m \times r}\) can be represented as the following. \[ e_{ij} = \sum _{s=1}^{n} a_{is} d_{sj} = \sum _{s=1}^{n} \left ( a_{is} \sum _{k=1}^{q} b_{sk} c_{kj} \right ) = \sum _{s=1}^{n} \sum _{k=1}^{q} a_{is} b_{sk} c_{kj} \] Similarly, we could do the same for the right-hand side of the equation. Note that the elements of the product \(AB\), or \(D' = [d'_{ij}]_{m \times q}\) can be represented as \(d'_{ij} = \sum _{k=1}^{n} a_{ik} b_{kj}\). Continuing, the elements in the final product \(E' = [e'_{ij}]_{m \times r}\) can be written as the following. \begin{align*} e'_{ij} &= \sum _{s=1}^{q} d'_{is} c_{sj} = \sum _{s=1}^{q} \left ( \left (\sum _{k=1}^{n} a_{ik} b_{ks} \right ) c_{sj} \right ) = \sum _{s=1}^{q} \sum _{k=1}^{n} a_{ik} b_{ks} c_{sj} \\ &= \sum _{k=1}^{q} \sum _{s=1}^{n} a_{is} b_{sk} c_{kj} = \sum _{s=1}^{n} \sum _{k=1}^{q} a_{is} b_{sk} c_{kj} = e_{ij} \end{align*}

Because \(e_{ij} = e'_{ij}\) for all possible combinations, \(A(BC) = (AB)C\).

In my head...

You might wonder if we are allowed to say that the following equation is true. \[ \sum _{k=1}^{q} \sum _{s=1}^{n} a_{is} b_{sk} c_{kj} = \sum _{s=1}^{n} \sum _{k=1}^{q} a_{is} b_{sk} c_{kj} \] When proving this property, I initially thought that my proof contained an error and spent my time reading the proof over and over again. This actually applies and visualizing it helped me. This part is not rigorous, so I didn’t include it in the proof above, but you can think of rotating the entire summation by \(90^\circ \). \[ \sum _{k=1}^{q} \sum _{s=1}^{n} a_{is} b_{sk} c_{kj} = \begin {array}{ccc} a_{i1}b_{11}c_{1j} & & a_{i1}b_{1q}c_{qj} \\ \vdots & + \cdots + & \vdots \\ a_{in}b_{n1}c_{1j} & & a_{in}b_{nq}c_{qj} \end {array} \] Similarly, the second sum can be represented as the following. \[ \sum _{s=1}^{n} \sum _{k=1}^{q} a_{is} b_{sk} c_{kj} = \begin {array}{ccc} a_{i1}b_{11}c_{1j} & & a_{in}b_{n1}c_{1j} \\ \vdots & + \cdots + & \vdots \\ a_{i1}b_{1q}c_{qj} & & a_{in}b_{nq}c_{qj} \end {array} \] Now imagine you write the entire terms out, and rotate it \(90^\circ \). They are identical!

Next, let’s prove the first distributive law.

Proof.

Let \(A = [a_{ij}]_{m \times n}\), \(B = [b_{ij}]_{n \times q}\), and \(C = [c_{ij}]_{n \times q}\). Consider the following equation. \begin{align*} [a_{ij}] \left ( [b_{ij}] + [c_{ij}] \right ) &= [a_{ij}] [b_{ij} + c_{ij}] = \left [ \sum _{k=1}^{n} a_{ik} (b_{kj} + c_{kj}) \right ] \\ &= \left [ \sum _{k=1}^{n} a_{ik} b_{kj} + \sum _{k=1}^{n} a_{ik} c_{kj} \right ] \\ &= \left [ \sum _{k=1}^{n} a_{ik} b_{kj} \right ] + \left [ \sum _{k=1}^{n} a_{ik} c_{kj} \right ] \\ &= [a_{ij}] [b_{ij}] + [a_{ij}] [c_{ij}] \end{align*}

Therefore, the distributive property \(A(B + C) = AB + AC\) applies.

We could prove the right distributive law in similar fashion.

Proof.

Let \(A = [a_{ij}]_{n \times q}\), \(B = [b_{ij}]_{m \times n}\), and \(C = [c_{ij}]_{m \times n}\). Consider the following equation. \begin{align*} \left ( [b_{ij}] + [c_{ij}] \right ) [a_{ij}] &= [b_{ij} + c_{ij}] [a_{ij}] = \left [ \sum _{k=1}^{n} (b_{ik} + c_{ik}) a_{kj} \right ] \\ &= \left [ \sum _{k=1}^{n} b_{ik} a_{kj} + \sum _{k=1}^{n} c_{ik} a_{kj} \right ] \\ &= \left [ \sum _{k=1}^{n} b_{ik} a_{kj} \right ] + \left [ \sum _{k=1}^{n} c_{ik} a_{kj} \right ] \\ &= [b_{ij}] [a_{ij}] + [c_{ij}] [a_{ij}] \end{align*}

Thus, the right distributive property \((B + C)A = BA + CA\) holds.

Finally, let’s prove the fourth property.

Proof.

Let \(A = [a_{ij}]_{m \times n}\) and \(B = [b_{ij}]_{n \times p}\). Consider the following equation. \[ \lambda (AB) = \lambda \left [ \sum _{k = 1}^{n} a_{ik} b_{kj} \right ] = \left [ \sum _{k = 1}^{n} \lambda a_{ik} b_{kj} \right ] = \left [ \sum _{k = 1}^{n} a_{ik} (\lambda b_{kj}) \right ] = A(\lambda B) \] Thus, the fourth property holds.

In addition to the visual implications of a matrix and its multiplication above, matrix multiplication can be extended to systems of equations. For instance, consider the following system of equations. \begin{align*} 2x + 3y &= 5 \\ -x + 7y &= 3 \end{align*}

Using coefficient matrix, we could represent the system above as the following matrix multiplication. \[ \begin {bmatrix} 2 & 3 \\ -1 & 7 \end {bmatrix} \begin {bmatrix} x \\ y \end {bmatrix} = \begin {bmatrix} 5 \\ 3 \end {bmatrix} \] Let’s take a look at more interesting facts on matrix multiplication.

Definition 0.1.6

A square matrix with \(1\) in all entries of its main diagonal and \(0\) in the other entries is an identity matrix, denoted as \(I_n\) for an identity matrix with order \(n \times n\). Moreover, all identity matrices satisfy the following equation for square matrix \(A\) that can be multiplied. \[ AI = IA = A \]

In other word, identity matrices have the following form. \[ \begin {bmatrix} 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \\ 0 & 0 & \cdots & 0 & 1 \end {bmatrix} \] This is called an identity matrix because when you multiply any square matrix by the identity matrix with the corresponding order, you get the square matrix itself. Consider the following example. \[ \begin {bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end {bmatrix} \begin {bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end {bmatrix} = \begin {bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end {bmatrix} \] From this, we can obtain an important fact about the uniqueness of the identity matrix.

Theorem 0.1.7

The identity matrix \(I\) for square matrices \(A\) is unique.

Proof.

For the sake of contradiction, let matrix \(A_{m \times m}\) have two unique identity matrices \(I_{m \times m}\) and \(J_{m \times m}\). By definition, \(AI = IA = A\) and \(AJ = JA = A\). Therefore, \(AI = IA = AJ = JA\) and \(AI = AJ\). Because \(A\) is any square matrix with order \(m \times m\), let \(A = I\). Substituting, \(II = IJ\), and \(I = J\) is obtained by definition. By contradiction from the assumption that \(I \neq J\), the identity matrix for a square matrix \(A\) is unique.

Another interesting insight on matrix multiplication is dissecting the matrices being multiplied. Let’s take a look at a simple example. \begin{align*} \begin {bmatrix} \scriptstyle a_{11} & \scriptstyle a_{12} & \scriptstyle a_{13} \\ \scriptstyle a_{21} & \scriptstyle a_{22} & \scriptstyle a_{23} \end {bmatrix} &\begin {bmatrix} \scriptstyle b_{11} & \scriptstyle b_{12} \\ \scriptstyle b_{21} & \scriptstyle b_{22} \\ \scriptstyle b_{31} & \scriptstyle b_{32} \end {bmatrix} = \begin {bmatrix} \scriptstyle a_{11} b_{11} + a_{12} b_{21} + a_{13} b_{31} & \scriptstyle a_{11} b_{12} + a_{12} b_{22} + a_{13} b_{32} \\ \scriptstyle a_{21} b_{11} + a_{22} b_{21} + a_{23} b_{31} & \scriptstyle a_{21} b_{12} + a_{22} b_{22} + a_{23} b_{32} \end {bmatrix} \\ &= \begin {bmatrix} \scriptstyle a_{11} & \scriptstyle a_{12} & \scriptstyle a_{13} \\ \scriptstyle 0 & \scriptstyle 0 & \scriptstyle 0 \end {bmatrix} \begin {bmatrix} \scriptstyle b_{11} & \scriptstyle b_{12} \\ \scriptstyle b_{21} & \scriptstyle b_{22} \\ \scriptstyle b_{31} & \scriptstyle b_{32} \end {bmatrix} + \begin {bmatrix} \scriptstyle 0 & \scriptstyle 0 & \scriptstyle 0 \\ \scriptstyle a_{21} & \scriptstyle a_{22} & \scriptstyle a_{23} \end {bmatrix} \begin {bmatrix} \scriptstyle b_{11} & \scriptstyle b_{12} \\ \scriptstyle b_{21} & \scriptstyle b_{22} \\ \scriptstyle b_{31} & \scriptstyle b_{32} \end {bmatrix} \\ &= \begin {bmatrix} \scriptstyle a_{11} & \scriptstyle a_{12} & \scriptstyle a_{13} \\ \scriptstyle a_{21} & \scriptstyle a_{22} & \scriptstyle a_{23} \end {bmatrix} \begin {bmatrix} \scriptstyle b_{11} & \scriptstyle 0 \\ \scriptstyle b_{21} & \scriptstyle 0 \\ \scriptstyle b_{31} & \scriptstyle 0 \end {bmatrix} + \begin {bmatrix} \scriptstyle a_{11} & \scriptstyle a_{12} & \scriptstyle a_{13} \\ \scriptstyle a_{21} & \scriptstyle a_{22} & \scriptstyle a_{23} \end {bmatrix} \begin {bmatrix} \scriptstyle 0 & \scriptstyle b_{12} \\ \scriptstyle 0 & \scriptstyle b_{22} \\ \scriptstyle 0 & \scriptstyle b_{32} \end {bmatrix} \end{align*}

In the matrix multiplication above, we could see that to find the element in the entry \((i, j)\), it is sufficient for us to see row \(i\) from the left matrix and column \(j\) from the right. In the next section of the note, we will discuss different topics about matrix.