Block Matrix Multiplication

It is often useful to partition a matrix into smaller matrices, called blocks. A matrix viewed in this way is said to be partitioned into blocks. For example, each column of a matrix can be considered to be a block. Writing a matrix \(B\) in the form

\begin{equation*} B = \begin{bmatrix} \vec {b}_{1} & \vec {b}_{2} & \ldots & \vec {b}_{k} \end{bmatrix} \mbox { where the } \vec {b}_{j} \mbox { are the columns of } B \end{equation*}

is a block partition of \(B\).

Here is another example. Consider matrix \(A\).

\begin{equation*} A = \left [ \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 2 & -1 & 4 & 2 & 1 \\ 3 & 1 & -1 & 7 & 5 \end{array} \right ] \end{equation*}

There is a natural way to partition \(A\). Observe the \(2\times 2\) identity matrix, \(I_2\), in the upper left corner. There is also a \(2\times 3\) zero matrix, \(O_{23}\), in the upper right corner. We will take advantage of these features to partition \(A\) as follows.

\begin{equation*} A = \left [ \begin{array}{rr|rrr} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ \hline 2 & -1 & 4 & 2 & 1 \\ 3 & 1 & -1 & 7 & 5 \end{array} \right ] = \left [ \begin{array}{cc} I_{2} & O_{23} \\ P & Q \end{array} \right ] \end{equation*}

This notation is particularly useful when we are multiplying two matrices because the product can be computed in block form.

Consider matrix \(B\).

\begin{equation*} B = \left [ \begin{array}{rr} 4 & -2 \\ 5 & 6 \\ 7 & 3 \\ -1 & 0 \\ 1 & 6 \end{array} \right ] \end{equation*}

We will compute the product \(AB\) by ordinary matrix multiplication, using blocks as entries. The only requirement is that the blocks be compatible. That is, the sizes of the blocks must be such that all matrix products of blocks that occur make sense. This means that the number of columns in each block of \(A\) must equal the number of rows in the corresponding block of \(B\).

To find the product \(AB\), we need to partition \(B\) so that block \(I_2\) corresponds to a \(2\times 2\) block of \(B\), and block \(O_{23}\) of \(A\) corresponds to a \(3\times 2\) block of \(B\). We partition \(B\) as follows.

\begin{equation*} B = \left [ \begin{array}{rr} 4 & -2 \\ 5 & 6 \\ \hline 7 & 3 \\ -1 & 0 \\ 1 & 6 \end{array} \right ] = \left [ \begin{array}{c} X \\ Y \end{array} \right ] \end{equation*}

Then,

\begin{equation*} AB = \left [ \begin{array}{cc} I & O \\ P & Q \end{array} \right ] \left [ \begin{array}{c} X \\ Y \end{array} \right ] = \left [ \begin{array}{c} IX + OY \\ PX + QY \end{array} \right ] = \left [ \begin{array}{c} X \\ PX + QY \end{array} \right ] = \left [ \begin{array}{rr} 4 & -2 \\ 5 & 6 \\ \hline 30 & 8 \\ 8 & 27 \end{array} \right ] \end{equation*}

This is easily checked to be the product \(AB\), computed in the conventional manner.

We omit the proof.

Block multiplication has theoretical uses, as we shall see later. It is also useful in computing products of matrices when using a computer with limited memory capacity. The matrices are partitioned into blocks in such a way that each product of blocks can be handled. Then the blocks are stored in auxiliary memory and their products are computed one by one.

Practice Problems

Compute \(AB\), using the indicated block partitioning.
\begin{equation*} A = \left [ \begin{array}{rr|rr} 2 & -1 & 3 & 1 \\ 1 & 0 & 1 & 2 \\ \hline 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right ] \quad B = \left [ \begin{array}{rr|r} 1 & 2 & 0 \\ -1 & 0 & 0 \\ \hline 0 & 5 & 1 \\ 1 & -1 & 0 \end{array} \right ] \end{equation*}

Answer:

\begin{equation*} AB = \left [ \begin{array}{rr|r} \answer {4} & \answer {18} & \answer {3} \\ \answer {3} & \answer {5} & \answer {1} \\ \hline \answer {0} & \answer {5} & \answer {1} \\ \answer {1} & \answer {-1} & \answer {0} \end{array} \right ] \end{equation*}
In each case give formulas for all powers \(A, A^{2}, A^{3}, \dots \) of \(A\) using the block decomposition indicated.
1.
\(A = \left [ \begin{array}{r|rr} 1 & 0 & 0 \\ \hline 1 & 1 & -1\\ 1 & -1 & 1 \end{array} \right ] \)
2.
\(A = \left [ \begin{array}{rr|rr} 1 & -1 & 2 & -1 \\ 0 & 1 & 0 & 0 \\ \hline 0 & 0 & -1 & 1 \\ 0 & 0 & 0 & 1 \end{array} \right ] \)

Click the arrow to see the answer.

\( A^{2k} = \left [ \begin{array}{rc|rr} 1 & -2k & 0 & 0 \\ 0 & 1 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right ]\) for \(k = 0, 1, 2, \dots \)

\(A^{2k + 1} = A^{2k}A = \left [ \begin{array}{rc|rr} 1 & -(2k + 1) & 2 & -1 \\ 0 & 1 & 0 & 0 \\ \hline 0 & 0 & -1 & 1 \\ 0 & 0 & 0 & 1 \end{array} \right ]\) for \(k = 0, 1, 2, \dots \)

Compute the following using block multiplication (all blocks are \(k \times k\)).
1.
\(\left [ \begin{array}{rr} I & X \\ -Y & I \end{array} \right ] \left [ \begin{array}{rr} I & 0 \\ Y & I \end{array} \right ] \)
2.
\(\left [ \begin{array}{cc} I & X \\ 0 & -I \end{array} \right ]^{n} \) any \(n \geq 1\)
3.
\(\left [ \begin{array}{cc} 0 & X \\ I & 0 \end{array} \right ]^{n} \) any \(n \geq 1\)

Click the arrow to see the answer.

\(\left [ \begin{array}{cc} X^{m} & 0 \\ 0 & X^{m} \end{array} \right ]\) if \(n = 2m\); \(\left [ \begin{array}{cc} 0 & X^{m + 1} \\ X^{m} & 0 \end{array} \right ]\) if \(n = 2m + 1\)

Text Source

The text in this section is an adaptation of Section 2.3 of Keith Nicholson’s Linear Algebra with Applications. (CC-BY-NC-SA)

W. Keith Nicholson, Linear Algebra with Applications, Lyryx 2018, Open Edition, p 73-74.