Linear Algebra › Section B · Matrix algebra › Topic B.4

Partitioned (block) matrices

A big matrix often has natural pieces: one block for each part of a system, or tiles small enough for a computer to handle quickly. Partitioning lets you do matrix algebra with those pieces as if they were single numbers, as long as you respect their sizes and their order.

Seeing a matrix in pieces

Engineering models often join several subsystems with only a few links between them, so their matrices contain large blocks of zeros and smaller dense blocks. Writing the matrix as a grid of blocks makes that structure visible and lets us reason about each part separately. The same idea drives modern computing: libraries multiply huge matrices tile by tile. This topic shows how to add, multiply and invert matrices block by block, and introduces a second way to read every product.

Partitioning a matrix

To partition a matrix, draw horizontal lines between some rows and vertical lines between some columns. Each rectangle that results is a block, or submatrix. A \(3 \times 5\) matrix split after row 2 and after column 3 becomes

A = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix}

where \(A_{11}\) is \(2 \times 3\), \(A_{12}\) is \(2 \times 2\), \(A_{21}\) is \(1 \times 3\) and \(A_{22}\) is \(1 \times 2\). The blocks in one block row share a number of rows, and the blocks in one block column share a number of columns. Writing a matrix by its columns, \([\mathbf{a}_1 \ \cdots \ \mathbf{a}_n]\), is itself a partition.

Sums and scalar multiples

If \(A\) and \(B\) are the same size and partitioned in exactly the same way, then \(A + B\) is found block by block: each block of the sum is the sum of the matching blocks. Likewise \(rA\) multiplies every block by \(r\). Nothing new happens here, because adding or scaling blocks just adds or scales the entries inside them. The same-partition condition matters: if the lines are drawn in different places, the matching blocks need not even be the same size.

Multiplying block matrices

Block matrices multiply with the row-column rule, treating each block like an entry:

\begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix}\begin{bmatrix} B_1 \\ B_2 \end{bmatrix} = \begin{bmatrix} A_{11}B_1 + A_{12}B_2 \\ A_{21}B_1 + A_{22}B_2 \end{bmatrix}

This works when the partitions are conformable: the column split of \(A\) must match the row split of \(B\), so that every small product such as \(A_{12}B_2\) is defined. Because blocks are matrices, the order inside each product must be kept: \(A_{11}B_1\), never \(B_1A_{11}\).

Worked example: a product in blocks

Let \(A\) have rows (1, 2, 0), (3, −1, 2), (0, 4, 1), split after row 2 and after column 2. Let \(B\) have rows (2, 1), (0, 3), (1, −2), split after row 2, which matches the column split of \(A\). 1. \(A_{11}B_1\): rows (1, 2), (3, −1) times rows (2, 1), (0, 3) gives rows (2, 7) and (6, 0). 2. \(A_{12}B_2\): the column (0, 2) times the row (1, −2) gives rows (0, 0) and (2, −4). 3. Top block: rows (2, 7) and (8, −4). 4. Bottom block:

A_{21}B_1 + A_{22}B_2 = (0, 12) + (1, -2) = (1, 10)

5. Check one entry directly: row 2 of \(A\) with column 2 of \(B\) is \(3 - 3 - 4 = -4\), as found.

Columns times rows

Partition \(A\) into its columns and \(B\) into its rows. Block multiplication then gives the column-row expansion:

AB = \mathbf{a}_1\mathbf{r}_1 + \mathbf{a}_2\mathbf{r}_2 + \cdots + \mathbf{a}_n\mathbf{r}_n

where \(\mathbf{a}_k\) is column \(k\) of \(A\) and \(\mathbf{r}_k\) is row \(k\) of \(B\). Each term, a column times a row, is called an outer product. Every column of an outer product is a multiple of the same vector, so when neither vector is zero it is a rank-one matrix, a term made precise in "Dimension and rank". Writing a matrix as a short sum of outer products is the basis of data compression and recommendation systems.

Worked example: a column-row expansion

Let \(A\) have rows (2, 1), (0, 3) and \(B\) have rows (1, 4), (2, −1). 1. Column 1 of \(A\) is (2, 0) and row 1 of \(B\) is (1, 4); their outer product has rows (2, 8) and (0, 0). 2. Column 2 of \(A\) is (1, 3) and row 2 of \(B\) is (2, −1); their outer product has rows (2, −1) and (6, −3). 3. Add:

AB = \begin{bmatrix} 2 & 8 \\ 0 & 0 \end{bmatrix} + \begin{bmatrix} 2 & -1 \\ 6 & -3 \end{bmatrix} = \begin{bmatrix} 4 & 7 \\ 6 & -3 \end{bmatrix}

4. Check with the row-column rule: entry (1, 2) is \(2(4) + 1(-1) = 7\), and entry (2, 1) is \(0 + 3(2) = 6\).

Inverting block triangular matrices

Suppose \(A_{11}\) is \(p \times p\), \(A_{22}\) is \(q \times q\), and both are invertible. Then

\begin{bmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{bmatrix}^{-1} = \begin{bmatrix} A_{11}^{-1} & -A_{11}^{-1}A_{12}A_{22}^{-1} \\ 0 & A_{22}^{-1} \end{bmatrix}

You can confirm it by multiplying the two block matrices and getting \(I\). A block diagonal matrix, with zero blocks off the diagonal, is inverted simply by inverting each diagonal block. For example, with \(A_{11}\) having rows (2, 1), (1, 1), \(A_{12} = (3, 1)\) as a column and \(A_{22} = [2]\), the top-right block of the inverse is \((-1, 0.5)\).

Why computers like blocks

Multiplying two \(n \times n\) matrices straight from the definition takes \(n^3\) multiplications. Fast libraries still do that work, but in blocks sized to fit the processor's fast cache memory, which avoids slow trips to main memory and lets blocks be handled in parallel. Block thinking also led Volker Strassen, in 1969, to multiply \(2 \times 2\) block matrices with 7 block products instead of 8, giving about \(n^{2.81}\) operations. Theoretical methods now go below \(n^{2.38}\), but practical software mostly uses carefully tuned blocked versions of the standard method.

Common mistakes to avoid

First, multiplying blocks whose partitions do not match: the column split of the left matrix must equal the row split of the right one. Second, reversing the order inside a block product, as if blocks commuted. Third, inverting a full block matrix by inverting each block separately; that works only when the off-diagonal blocks are zero. Fourth, mixing up an outer product \(\mathbf{u}\mathbf{v}^T\), which is a matrix, with \(\mathbf{u}^T\mathbf{v}\), which is a single number.

Key takeaways

Partitioning splits a matrix into blocks by lines between rows and columns. Same-size matrices partitioned the same way add and scale block by block. Block matrices multiply by the row-column rule when the column split of the left factor matches the row split of the right, with the order kept in every block product. Partitioning A by columns and B by rows gives AB as a sum of outer products, each of rank one. A block upper triangular matrix with invertible diagonal blocks has a block upper triangular inverse, and a block diagonal matrix inverts block by block. Blocking speeds up real computation.

Flashcards

Flashcard

Partitioned matrix

A matrix divided into blocks by lines between rows and columns

Also called a block matrix.

Test your understanding

Question 1 of 5

A is 5 × 6, partitioned with its columns split 2 | 4. B is 6 × 3. How must the rows of B be split for the block product AB to work?

Question 2 of 5

Writing a semicolon between block rows, A = [A₁₁ A₁₂; A₂₁ A₂₂] and B = [B₁; B₂] are conformably partitioned. What is the bottom block of AB?

Question 3 of 5

A has columns (1, 2) and (0, 1). B has rows (3, 1) and (4, 2). Which pair of outer products adds up to AB?

Question 4 of 5

With semicolons between block rows, M = [A 0; 0 D] is block diagonal, with A and D square and invertible. What is M⁻¹?

Question 5 of 5

u and v are vectors in R⁴. Which statement about uvᵀ and uᵀv is correct?

← Previous topicNext topic →