Block Matrix Multiplication
Consider two matrices \(\displaystyle A\) and \(\displaystyle B\) compatible for multiplication. Let their shapes be \(\displaystyle m\times n\) and \(\displaystyle n\times p\) respectively. Now, we consider the following partition of the matrices into sub-matrices or blocks:
\[ \begin{equation*} A=\left[\begin{array}{ c|c } A_{11} & A_{12}\\ \hline A_{21} & A_{22} \end{array}\right] ,\ B=\left[\begin{array}{ c|c } B_{11} & B_{12}\\ \hline B_{21} & B_{22} \end{array}\right] \end{equation*} \]
Here, each \(\displaystyle A_{ij}\) and \(\displaystyle B_{ij}\) are themselves matrices with the following shapes:
\[ \begin{equation*} A=\left[\begin{array}{ c|c } m_{1} \times n_{1} & m_{1} \times n_{2}\\ \hline m_{2} \times n_{1} & m_{2} \times n_{2} \end{array}\right] ,\ B=\left[\begin{array}{ c|c } n_{1} \times p_{1} & n_{1} \times p_{2}\\ \hline n_{2} \times p_{1} & n_{2} \times p_{2} \end{array}\right] \end{equation*} \]
With this partition, we can compute \(\displaystyle AB\) as:
\[ \begin{equation*} AB=\left[\begin{array}{ c|c } A_{11} B_{11} +A_{12} B_{21} & A_{11} B_{12} +A_{12} B_{22}\\ \hline A_{21} B_{11} +A_{22} B_{21} & A_{21} B_{12} +A_{22} B_{22} \end{array}\right] \end{equation*} \]
We can compute \(\displaystyle AB\) as though the \(\displaystyle A_{ij}\) and \(\displaystyle B_{ij}\) are scalars and \(\displaystyle A,B\) are just \(\displaystyle 2\times 2\) matrices. The partitions must be chosen in such a way that the individual blocks are compatible. Visually:
To see why this works, consider the following decomposition:
\[ \begin{equation*} \begin{array}{ l l } A & =\left[\begin{array}{ c|c } A_{11} & 0\\ \hline 0 & 0 \end{array}\right] +\left[\begin{array}{ c|c } 0 & A_{12}\\ \hline 0 & 0 \end{array}\right] +\left[\begin{array}{ c|c } 0 & 0\\ \hline A_{21} & 0 \end{array}\right] +\left[\begin{array}{ c|c } 0 & 0\\ \hline 0 & A_{22} \end{array}\right]\\ & \\ B & =\left[\begin{array}{ c|c } B_{11} & 0\\ \hline 0 & 0 \end{array}\right] +\left[\begin{array}{ c|c } 0 & B_{12}\\ \hline 0 & 0 \end{array}\right] +\left[\begin{array}{ c|c } 0 & 0\\ \hline B_{21} & 0 \end{array}\right] +\left[\begin{array}{ c|c } 0 & 0\\ \hline 0 & B_{22} \end{array}\right] \end{array} \end{equation*} \]
We will get eight pairs of products. It is easier to work with these matrices thanks to all those zeros. One of these products is:
\[ \begin{equation*} \left[\begin{array}{ c|c } A_{11} & 0\\ \hline 0 & 0 \end{array}\right]\left[\begin{array}{ c|c } 0 & B_{12}\\ \hline 0 & 0 \end{array}\right] =\left[\begin{array}{ c|c } 0 & A_{11} B_{12}\\ \hline 0 & 0 \end{array}\right] \end{equation*} \]
If it is not immediately obvious consider a concrete example and convince yourself:
\[ \begin{equation*} \left[\begin{array}{ c c|c c } 1 & 2 & 0 & 0\\ 3 & 4 & 0 & 0\\ \hline 0 & 0 & 0 & 0 \end{array}\right]\left[\begin{array}{ c|c c } 0 & 5 & 6\\ 0 & 7 & 8\\ \hline 0 & 0 & 0\\ 0 & 0 & 0 \end{array}\right] =\left[\begin{array}{ c|c c } 0 & 19 & 22\\ 0 & 43 & 50\\ \hline 0 & 0 & 0 \end{array}\right] \end{equation*} \]