Game Math: Block Matrices

This post is part of my Game Math Series.

Splitting Matrices into Blocks

When performing matrix multiplication, we can split matrices into “blocks”. The matrix multiplication can then be performed as if each block is a single matrix element, given that we split the matrices in a way that the multiplication of block matrices are of legal dimensions.

For instance, a product of two 4-by-4 matrices can be viewed as a product of 2-by-2 matrices, where each matrix element is a 2-by-2 block matrix. Since a 2-by-2 matrix can be legally multiplied by another 2-by-2 matrix, such splitting scheme is valid.

Let’s look at an example with numbers:

    \[ A =  {\left[ {\begin{array}{cccc}    1 & 1 & 0 & 0 \\    1 & 1 & 0 & 0 \\    0 & 0 & 1 & 1 \\    0 & 0 & 1 & 1 \\   \end{array} } \right]} , B =  {\left[ {\begin{array}{cccc}    2 & 1 & 0 & 0 \\    1 & -1 & 0 & 0 \\    0 & 0 & 2 & 1 \\    0 & 0 & 1 & -1 \\   \end{array} } \right]} \]

We can split each of these matrices into four 2-by-2 block matrices:

    \[ A =  {\left[ {\begin{array}{cc}    C & O \\    O & C \\   \end{array} } \right]} ,  B =  {\left[ {\begin{array}{cc}    D & O \\    O & D \\   \end{array} } \right]} \]

where C = {\left[ {\begin{array}{cc} 1 & 1 \\ 1 & 1 \end{array} } \right]}, D = {\left[ {\begin{array}{cc} 2 & 1 \\ 1 & -1 \end{array} } \right]}, and O = {\left[ {\begin{array}{cc} 0 & 0 \\ 0 & 0 \end{array} } \right]}.

If we perform the matrix multiplication AB as if the block matrices are single matrix elements, we get:

    \[ AB =  {\left[ {\begin{array}{cc}    CD + OO & OC + DO \\    DO + OC & OO + CD \\   \end{array} } \right]},   =  {\left[ {\begin{array}{cc}   CD & O \\   O & CD \\   \end{array} } \right]} \]

We can find out that CD = {\left[ {\begin{array}{cc} 3 & 0 \\ 3 & 0 \end{array} } \right]}. If we substitute out CD in AB, we get:

    \[ AB =  {\left[ {\begin{array}{cc}   CD & O \\   O & CD \\   \end{array} } \right]}  =  {\left[ {\begin{array}{cccc}   3 & 0 & 0 & 0 \\   3 & 0 & 0 & 0 \\   0 & 0 & 3 & 0 \\   0 & 0 & 3 & 0 \\   \end{array} } \right]} \]

We can easily verify that this is the same matrix we will get if we multiply out the matrix product AB normally.

Transformation Matrices

In computer graphics, we represent points and vectors as 4D vectors with the w component equal to 1 and 0, respectively. We can represent a series of scaling, rotation, and translation as a 4-by-4 matrix in the form:

    \[ M =  {\left[ {\begin{array}{cccc}   R_{00} & R_{01} & R_{02} & T_0 \\   R_{10} & R_{11} & R_{12} & T_1 \\   R_{20} & R_{21} & R_{22} & T_2 \\   0 & 0 & 0 & 1   \end{array} } \right]} \]

We can split a 4-by-4 transformation matrix into a 2-by-2 matrix, with the top-left element a 3-by-3 matrix, the top-right element a 3-by-1 matrix, the bottom-left element a 1-by-3 zero matrix, and the bottom-right element the 1-by-1 identity matrix:

    \[ M =  {\left[ {\begin{array}{cc}   R & T \\   O & I \\   \end{array} } \right]},  \]

where R = {\left[ {\begin{array}{ccc} R_{00} & R_{01} & R_{02} \\ R_{10} & R_{11} & R_{12} \\ R_{20} & R_{21} & R_{22} \end{array} } \right]}, T = {\left[ {\begin{array}{c} T_0 \\ T_1 \\ T_2 \end{array} } \right]}, O = {\left[ {\begin{array}{ccc} 0 & 0 & 0 \end{array} } \right]}, and I = {\left[ {\begin{array}{c} 1 \end{array} } \right]}.

Now if we were to concatenate two transformation matrices:

    \[ M_1 =  {\left[ {\begin{array}{cc}   R_1 & T_1 \\   O & I \\   \end{array} } \right]},  M_2 =  {\left[ {\begin{array}{cc}   R_2 & T_2 \\   O & I \\   \end{array} } \right]},  \]

we can simply perform a 2-by-2 matrix multiplication and get:

    \[ M_2 M_1 =  {\left[ {\begin{array}{cc}   R_2 R_1 + T_2 O & R_2 T_1 + T_2 I \\   O R_1 + I O & O T_1 + I I \\   \end{array} } \right]}  =  {\left[ {\begin{array}{cc}   R_2 R_1 & R_2 T_1 + T_2 \\   O & I \\   \end{array} } \right]} \]

You might have seen the formula above before in a book or class on computer graphics. This is one way we can derive this formula, using block matrices.

Using this formula, we can save a lot of computation time if we know beforehand that the two 4-by-4 matrices we are multiplying together are of the form M = {\left[ {\begin{array}{cc} R & T \\ O & I \\ \end{array} } \right]}.

Inverting Transformation Matrices

Splitting matrices into blocks can also help us finding the inverses of matrices. Let’s use the 4-by-4 transformation matrix as an example again:

    \[ M =  {\left[ {\begin{array}{cc}   R & T \\   O & I \\   \end{array} } \right]},  \]

With careful inspection, we can find that:

    \[ M^{-1} =  {\left[ {\begin{array}{cc}   R^{-1} & -R^{-1}T \\   O & I \\   \end{array} } \right]} \]

We can verify that M^{-1} is correct by performing a block matrix multiplication with M:

    \[ M M^{-1} =  {\left[ {\begin{array}{cc}   R R^{-1} + T O & -R R^{-1} T + T I \\   O R + I O & O T + I I \\   \end{array} } \right]}  =  {\left[ {\begin{array}{cc}   I_{3 \times 3} & O^T \\   O & I \\   \end{array} } \right]}  =  I_{4 \times 4} \]

where I_{3 \times 3} is the 3-by-3 identity matrix and I_{4 \times 4} is the 4-by-4 identity matrix.

End of Block Matrices

As you have seen, if we can split matrices in a matrix product into simple block matrices (like identity matrices and zero matrices), we can save a lot of computation time, because many block matrices can possibly be simplified or even zeroed out when multiplied with simple block matrices. The block matrix technique can also help us simplify matrix inversion with matrices in certain forms.

About Allen Chou

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

Leave a Reply