2.4 Partitioned matrices

Big idea

Draw horizontal and vertical lines through a matrix and the pieces become matrices in their own right. A partitioned matrix is the same array of numbers with that grid drawn on it, and the striking fact is that the arithmetic survives the cut. Add blockwise, scale blockwise, and multiply blockwise by the same row-times-column rule you use on entries, with block products replacing number products.

This is not a labour-saving trick for hand computation. It is how large matrices are handled in practice. A matrix too big for memory gets processed block by block, and a matrix with obvious structure, such as a big corner of zeros, gets an algorithm that skips the zero blocks entirely. The same partitioning explains why a system built from loosely coupled subsystems can be solved in pieces.

You have already used a partition without naming it. Writing $A$ as a list of columns and reading $A\mathbf{x}$ as a combination of those columns is partitioning $A$ into $n$ one-column blocks. This section names the idea and lets you cut the other way as well.

Decoder

A partition is only legal for multiplication when the cuts line up. For $AB$, the vertical cuts in $A$ must sit at the same positions as the horizontal cuts in $B$. Nothing else is required: the outer cuts, across the rows of $A$ and the columns of $B$, are free.

The reason is the one that always governs matrix products. Block $(i,j)$ of the answer is a sum of products $A_{ik}B_{kj}$, and each of those has to be a legal product of matrices, so the width of $A_{ik}$ and the height of $B_{kj}$ have to agree. “Conformable for block multiplication” is the phrase, and that is all it means.

A notational warning: $A_{12}$ in this section is a block, not the entry in row $1$ column $2$. Which one is meant comes from context, and a partitioned matrix is usually announced before its blocks are used.

Definitions and results

Partition. Cutting a matrix with horizontal and vertical lines produces a partitioned, or block, matrix. The blocks are submatrices, and the partitioned matrix is written as an array whose entries are those submatrices.

Sum and scalar multiple. Two matrices partitioned the same way add blockwise, and a scalar multiplies every block. Both follow from the entrywise definitions, since a block only ever meets the block in its own position.

Block multiplication. If the cuts are conformable, then the block in position $(i,j)$ of $AB$ is

$$ A_{i1}B_{1j} + A_{i2}B_{2j} + \cdots + A_{ik}B_{kj} $$

the same row-times-column pattern as for entries. Keep each product in the written order: $A_{i1}B_{1j}$ is not $B_{1j}A_{i1}$.

Column-row expansion. Cut $A$ into its $n$ columns and $B$ into its $n$ rows. Block multiplication then says that $AB$ is the sum of the products of matching column and row:

$$ AB = \mathbf{a}_1\text{row}_1(B) + \mathbf{a}_2\text{row}_2(B) + \cdots + \mathbf{a}_n\text{row}_n(B) $$

Each term is a column times a row, so each term is a full-size matrix built from a single column and a single row. This view returns when factorizations are discussed.

Block diagonal and block triangular. A block diagonal matrix has zero blocks everywhere off the diagonal of blocks. A block upper triangular matrix has zero blocks below it. Both invert in pieces. A block diagonal matrix with square diagonal blocks is invertible exactly when every diagonal block is, and then you invert each block separately. For a block upper triangular matrix with invertible square diagonal blocks $A$ and $D$,

$$ \begin{bmatrix} A & B \\ 0 & D \end{bmatrix}^{-1} = \begin{bmatrix} A^{-1} & -A^{-1}BD^{-1} \\ 0 & D^{-1} \end{bmatrix} $$

You do not memorise that formula. You derive it by writing the unknown inverse as a block matrix, multiplying, and forcing the four block equations to give the identity blocks.

Transpose of a partitioned matrix. Transpose the array of blocks, then transpose each block. The block in position $(i,j)$ of $A^T$ is the transpose of the block in position $(j,i)$ of $A$. It is the same order-reversal you saw for products, one level up.

Worked examples

The same product, cut into blocks

Let

$$ A = \begin{bmatrix} 1 & 2 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 2 & 0 & 1 & 3 \\ 1 & 1 & 0 & 2 \end{bmatrix}, \qquad B = \begin{bmatrix} 1 & 0 & 2 & 1 \\ 0 & 1 & 0 & 1 \\ 3 & 1 & 1 & 0 \\ 1 & 0 & 0 & 2 \end{bmatrix} $$

Cut both down the middle and across the middle, so every block is $2 \times 2$. The vertical cut in $A$ sits after column $2$ and the horizontal cut in $B$ sits after row $2$, so the partitions are conformable.

The top-left block of $AB$ is $A_{11}B_{11} + A_{12}B_{21}$:

$$ \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} + \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} 3 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 2 \\ 3 & 2 \end{bmatrix} $$

The bottom-right block is $A_{21}B_{12} + A_{22}B_{22}$:

$$ \begin{bmatrix} 2 & 0 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} 2 & 1 \\ 0 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 3 \\ 0 & 2 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ 0 & 2 \end{bmatrix} = \begin{bmatrix} 4 & 2 \\ 2 & 2 \end{bmatrix} + \begin{bmatrix} 1 & 6 \\ 0 & 4 \end{bmatrix} = \begin{bmatrix} 5 & 8 \\ 2 & 6 \end{bmatrix} $$

Check against the ordinary product, which is

$$ AB = \begin{bmatrix} 2 & 2 & 2 & 5 \\ 3 & 2 & 1 & 1 \\ 8 & 1 & 5 & 8 \\ 3 & 1 & 2 & 6 \end{bmatrix} $$

The top-left corner is $\begin{bmatrix} 2 & 2 \\ 3 & 2 \end{bmatrix}$ and the bottom-right corner is $\begin{bmatrix} 5 & 8 \\ 2 & 6 \end{bmatrix}$. Both blocks agree.

A product as a sum of column-times-row terms

Let

$$ A = \begin{bmatrix} 1 & 2 \\ 3 & -1 \\ 0 & 4 \end{bmatrix}, \qquad B = \begin{bmatrix} 2 & 1 & 0 \\ 1 & -1 & 3 \end{bmatrix} $$

The first column of $A$ times the first row of $B$ gives a $3 \times 3$ matrix, and so does the second column times the second row:

$$ \begin{bmatrix} 1 \\ 3 \\ 0 \end{bmatrix}\begin{bmatrix} 2 & 1 & 0 \end{bmatrix} = \begin{bmatrix} 2 & 1 & 0 \\ 6 & 3 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \qquad \begin{bmatrix} 2 \\ -1 \\ 4 \end{bmatrix}\begin{bmatrix} 1 & -1 & 3 \end{bmatrix} = \begin{bmatrix} 2 & -2 & 6 \\ -1 & 1 & -3 \\ 4 & -4 & 12 \end{bmatrix} $$

Add them:

$$ AB = \begin{bmatrix} 4 & -1 & 6 \\ 5 & 4 & -3 \\ 4 & -4 & 12 \end{bmatrix} $$

Check one entry the usual way. The entry in row $2$, column $3$ of $AB$ is row $2$ of $A$ against column $3$ of $B$: $3(0) + (-1)(3) = -3$. It matches.

Inverting a block triangular matrix

Let

$$ M = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 2 & 1 \end{bmatrix} $$

Cut it into $2 \times 2$ blocks. The bottom-left block is zero, so this is block upper triangular with $A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$, $B = I_2$, and $D = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}$. Both diagonal blocks are triangular with $1$s on the diagonal, so both invert easily: $A^{-1} = \begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix}$ and $D^{-1} = \begin{bmatrix} 1 & 0 \\ -2 & 1 \end{bmatrix}$.

The corner block of the inverse is $-A^{-1}BD^{-1}$. Since $B = I$, that is $-A^{-1}D^{-1} = -\begin{bmatrix} 3 & -1 \\ -2 & 1 \end{bmatrix} = \begin{bmatrix} -3 & 1 \\ 2 & -1 \end{bmatrix}$. Assembling:

$$ M^{-1} = \begin{bmatrix} 1 & -1 & -3 & 1 \\ 0 & 1 & 2 & -1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & -2 & 1 \end{bmatrix} $$

Check the top-left block of $MM^{-1}$ by blocks: $AA^{-1} + B \cdot 0 = I_2$. Check the top-right block: $A(-A^{-1}BD^{-1}) + BD^{-1} = -BD^{-1} + BD^{-1}$, the zero block. Verify one entry by hand as well. Row $1$ of $M$ against column $3$ of $M^{-1}$ is $1(-3) + 1(2) + 1(1) + 0(-2) = 0$, which is what the identity needs there.

Practice

Multiply matrices, including the products that appear inside a block computation.

Transpose matrices, and remember that a partitioned transpose flips the block array and each block.

Videos

The composition picture is what makes block multiplication believable: a block product is still a composition, just organised by groups of coordinates instead of one at a time. Watch the section on why the order of the factors survives every rearrangement of the computation.

Quiz

Five items on block products, column-row expansions, and transposes.