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 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 .

Here is another example. Consider matrix . \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 . Observe the identity matrix, , in the upper left corner. There is also a zero matrix, , in the upper right corner. We will take advantage of these features to partition 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 . \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 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 must equal the number of rows in the corresponding block of .

To find the product , we need to partition so that block corresponds to a block of , and block of corresponds to a block of . We partition 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 , 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 , 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 of using the block decomposition indicated.
(a)
(b)

Click the arrow to see the answer.

for

for

Compute the following using block multiplication (all blocks are ).
(a)
(b)
any
(c)
any

Click the arrow to see the answer.

if ; if

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.

2024-09-06 01:54:58