Game Math: Alternate Views on Matrix Multiplication

This post is part of my Game Math Series.

Definition of Matrix Multiplication

Let A_{l \times m} and B_{m \times n} be a l-by-m matrix and an m-by-n matrix, respectively. Let A_{ij} denote the element in the matrix A on row i and column j (zero-based indexing), “element (i, j)” for short.

From the definition of matrix multiplication, we know that:

    \[ (AB)_{ij} = \sum\limits_{k = 0}^{m - 1} {A_{ik} B_{kj}} \]

Essentially, element (i, j) of the matrix product AB is the dot product of i-th row from A and j-th column from B.

We can compute matrix multiplication by performing one dot product per element in the resulting matrix product AB. However, there are two alternative ways to look at the matrix multiplication operation that can sometimes make your life easier. I learned these neat tips from the “Linear Algebra and Its Applications” course when I was studying at National Taiwan University back in Taiwan.

Linear Combination of Columns

The i-th column of the matrix product AB is a linear combination of columns from the left matrix A, where the coefficients of linear combination are from the i-th column of the right matrix B.

Let’s look at a product of two 3-by-3 matrices as an example:

    \[ A =  {\left[ {\begin{array}{ccc}    A_{00} & A_{01} & A_{02} \\    A_{10} & A_{11} & A_{12} \\    A_{20} & A_{21} & A_{22} \\   \end{array} } \right]}  =  {\left[ {\begin{array}{ccc}    C_{A_0} & C_{A_1} & C_{A_2} \\   \end{array} } \right]} , \]

    \[ B =  {\left[ {\begin{array}{ccc}    B_{00} & B_{01} & B_{02} \\    B_{10} & B_{11} & B_{12} \\    B_{20} & B_{21} & B_{22} \\   \end{array} } \right]},  \]

where C_A^i denotes the i-th column of matrix A.

Then the i-th column of the matrix product AB is:

    \[ C_{AB}^i =    B_{0i} C_A^0}    + B_{1i} C_A^1    + B_{2i} C_A^2  \]

Now let’s look at an example with real numbers:

    \[ A =  {\left[ {\begin{array}{ccc}    1 & 2 & 3 \\    4 & 5 & 6 \\    7 & 8 & 9 \\   \end{array} } \right]} ,  B =  {\left[ {\begin{array}{ccc}    1 & -1 & 0 \\    2 & 1 & -2 \\    0 & 2 & 3 \\   \end{array} } \right]} \]

The columns of A are {\left[ {\begin{array}{c} 1 \\ 4 \\ 7 \end{array} } \right]}, {\left[ {\begin{array}{c} 2 \\ 5 \\ 8 \end{array} } \right]}, and {\left[ {\begin{array}{c} 3 \\ 6 \\ 9 \end{array} } \right]}. The first column of B is {\left[ {\begin{array}{c} 1 \\ 2 \\ 0 \end{array} } \right]}, so the first column of the matrix product AB is:

    \[ C_{AB}^0 =    1 {\left[ {\begin{array}{c} 1 \\ 4 \\ 7 \end{array} } \right]}   + 2 {\left[ {\begin{array}{c} 2 \\ 5 \\ 8 \end{array} } \right]}   + 0 {\left[ {\begin{array}{c} 3 \\ 6 \\ 9 \end{array} } \right]}  =   {\left[ {\begin{array}{c} 5 \\ 14 \\ 23 \end{array} } \right]} \]

Similarly, the second and third columns of the matrix product AB are:

    \[ C_{AB}^1 =    -1 {\left[ {\begin{array}{c} 1 \\ 4 \\ 7 \end{array} } \right]}   + 1 {\left[ {\begin{array}{c} 2 \\ 5 \\ 8 \end{array} } \right]}   + 2 {\left[ {\begin{array}{c} 3 \\ 6 \\ 9 \end{array} } \right]}  =   {\left[ {\begin{array}{c} 7 \\ 13 \\ 19 \end{array} } \right]} \]

    \[ C_{AB}^2 =    0 {\left[ {\begin{array}{c} 1 \\ 4 \\ 7 \end{array} } \right]}   - 2 {\left[ {\begin{array}{c} 2 \\ 5 \\ 8 \end{array} } \right]}   + 3 {\left[ {\begin{array}{c} 3 \\ 6 \\ 9 \end{array} } \right]}  =   {\left[ {\begin{array}{c} 5 \\ 8 \\ 11 \end{array} } \right]} \]

So the matrix product is:

    \[ AB =  {\left[ {\begin{array}{ccc}    5 & 7 & 5 \\    14 & 13 & 8 \\    23 & 19 & 11 \\   \end{array} } \right]} \]

Linear Combination of Rows

Alternatively, we can view matrix multiplication from a row perspective.

The i-th row of the matrix product AB is a linear combination of rows from the right matrix B, where the coefficients of linear combination are from the i-th row of the left matrix A.

Let R_A^i denote the i-th row of matrix A.

I will skip the symbolic notations and jump right back into the previous example we used:

    \[ A =  {\left[ {\begin{array}{ccc}    1 & 2 & 3 \\    4 & 5 & 6 \\    7 & 8 & 9 \\   \end{array} } \right]} ,  B =  {\left[ {\begin{array}{ccc}    1 & -1 & 0 \\    2 & 1 & -2 \\    0 & 2 & 3 \\   \end{array} } \right]} \]

The rows of B are {\left[ {\begin{array}{ccc} 1 & -1 & 0 \end{array} } \right]}, {\left[ {\begin{array}{ccc} 2 & 1 & -2 \end{array} } \right]}, and {\left[ {\begin{array}{ccc} 0 & 2 & 3 \end{array} } \right]}. The first rowof A is {\left[ {\begin{array}{ccc} 1 & 2 & 3 \end{array} } \right]}, so the first column of the matrix product AB is:

    \[ R_{AB}^0 =    1 {\left[ {\begin{array}{ccc} 1 & -1 & 0 \end{array} } \right]}   + 2 {\left[ {\begin{array}{ccc} 2 & 1 & -2 \end{array} } \right]}   + 3 {\left[ {\begin{array}{ccc} 0 & 2 & 3 \end{array} } \right]}  =    {\left[ {\begin{array}{ccc} 5 & 7 & 5 \end{array} } \right]} \]

Similarly, the second and third rows of the matrix product AB are:

    \[ R_{AB}^1 =    4 {\left[ {\begin{array}{ccc} 1 & -1 & 0 \end{array} } \right]}   + 5 {\left[ {\begin{array}{ccc} 2 & 1 & -2 \end{array} } \right]}   + 6 {\left[ {\begin{array}{ccc} 0 & 2 & 3 \end{array} } \right]}  =    {\left[ {\begin{array}{ccc} 14 & 13 & 8 \end{array} } \right]} \]

    \[ R_{AB}^2 =    7 {\left[ {\begin{array}{ccc} 1 & -1 & 0 \end{array} } \right]}   + 8 {\left[ {\begin{array}{ccc} 2 & 1 & -2 \end{array} } \right]}   + 9 {\left[ {\begin{array}{ccc} 0 & 2 & 3 \end{array} } \right]}  =    {\left[ {\begin{array}{ccc} 23 & 19 & 11 \end{array} } \right]} \]

So the matrix product is:

    \[ AB =  {\left[ {\begin{array}{ccc}    5 & 7 & 5 \\    14 & 13 & 8 \\    23 & 19 & 11 \\   \end{array} } \right]} ,  \]

same as what we got before.

End of Alternate Views on Matrix Multiplication

Now that you understand the two alternative views of matrix multiplication, you are well equipped to make your life easier when dealing with various matrix operations. For instance, I will show how to quickly eyeball the inverse of small matrices using this technique in another post.

About Allen Chou

Physics / Graphics / Procedural Animation / Visuals
This entry was posted in Gamedev, Math. Bookmark the permalink.

Leave a Reply