Block Matrices and the LU Factorization

Treating a matrix as a list of columns already proved useful in defining the matrix product. Partitioning generalizes that view: split a matrix with horizontal and vertical rules into a grid of smaller matrices, or blocks, and the algebra of sums, products, and inverses carries through block by block. Partitioning makes sparse structure visible and speeds computation, and it produces the LU factorization used by most linear-system solvers.

Partitioned matrices

A matrix may be divided by horizontal and vertical lines into submatrices. For example,

A = 3 - 5 - 8 02 - 6 - 1 43 501 9 - 3 7 = [A_{11} A_{21} A_{12} A_{22} A_{13} A_{23}],

where each $A_{ij}$ is a block, for instance $A_{11} = [3 - 5 02 - 1 4]$ and $A_{23} = [7]$ . When a matrix models a physical system — a circuit board of interconnected chips, a sparse aerodynamic grid — a natural partition groups related variables, and the off-diagonal blocks record the couplings between groups.

Addition and scaling. If $A$ and $B$ have the same size and the same partition, then $A + B$ is formed block by block, each block being the sum of the corresponding blocks, and $r A$ scales every block by $r$ . Both reduce to the entrywise operations already defined.

Block multiplication

The row-column rule works on blocks, provided the partitions line up.

Given conformable partitions, $A B$ is computed as though the blocks were scalar entries, each product written with the block from $A$ on the left, since matrix multiplication does not commute.

Block multiplication: each block of AB is a row-of-blocks of A times a column-of-blocks of B, exactly the row-column rule one level up.

Block multiplication is the most general way to view a product: the column form of $A x$ , the column definition of $A B$ , the row-column rule, and the rows-of- $A B$ identity are all special partitions. One more partition gives a form used repeatedly later.

Column-row expansion

Partition $A$ into its columns and $B$ into its rows. The blocks are conformable (one column times one row), and the product becomes a sum of outer products.¹

Each term $col_{k} (A) row_{k} (B)$ is an $m \times p$ rank-one matrix, and their sum reconstructs $A B$ . The $(i, j)$ -entry of the $k$ th term is $a_{ik} b_{k j}$ ; summing over $k$ recovers the row-column rule. This decomposition reappears when a large data matrix is stored as two thin factors, and in the rank-one layers of the SVD.

Inverses of block matrices

Block structure often makes an inverse easy to write down.

Block upper triangular. Suppose $A = [A_{11} 0 A_{12} A_{22}]$ is invertible, with $A_{11}$ of size $p \times p$ and $A_{22}$ of size $q \times q$ . Writing $A^{- 1} = B$ in the same partition and setting $A B = I$ gives four block equations whose solution is

A^{- 1} = [A_{11}^{- 1} 0 - A_{11}^{- 1} A_{12} A_{22}^{- 1} A_{22}^{- 1}] .

The derivation also shows $A_{11}$ and $A_{22}$ must themselves be invertible.

Block diagonal. A block diagonal matrix — zero blocks off the diagonal of blocks — is invertible if and only if each diagonal block is invertible, and its inverse is block diagonal with each block inverted:

[B 0 0 C]^{- 1} = [B^{- 1} 0 0 C^{- 1}] .

These identities let a large problem decouple into independent smaller ones — the computational reason partitioning appears in high-performance libraries and in algorithms that estimate eigenvalues.

The LU factorization

The LU factorization splits a matrix into a lower and an upper triangular factor.

A = LU: a unit lower triangular L (1s on the diagonal) times an upper triangular echelon form U.

Two triangular solves

With $A = LU$ , the equation $A x = b$ becomes $L (U x) = b$ . Setting $y = U x$ splits the solve into two triangular systems:

L y = b (forward substitution), U x = y (back substitution) .

Each is cheap because a triangular system is solved by sweeping through the unknowns in order. The value of the factorization shows when many systems $A x = b_{1}, \dots, A x = b_{p}$ share the coefficient matrix $A$ : factor once, then each right-hand side costs only two triangular solves. The inverse power method and repeated design iterations both fit this pattern.

Solving Ax = b in two stages once A = LU is known: forward-solve Ly = b for y, then back-solve Ux = y for x.

The two solves sweep opposite ways: forward substitution runs down the lower-triangular L, back substitution runs up the upper-triangular U.

Constructing $L$ and $U$

Suppose $A$ reduces to an echelon form $U$ using only row replacements that add a multiple of one row to a row below it. Those operations are left-multiplications by unit lower triangular elementary matrices $E_{p} \dots E_{1} A = U$ , so $A = (E_{p} \dots E_{1})^{- 1} U = LU$ with $L = (E_{p} \dots E_{1})^{- 1}$ , itself unit lower triangular. In practice $L$ is built without forming any $E_{k}$ : it records the multipliers used during the reduction.

Algorithm:LU factorization by recording row-replacement multipliers

1
reduce $A$ to an echelon form $U$ using only row replacements
2
that add a multiple of one row to a lower row
3
set every diagonal entry of $L$ to $1$
4
for each pivot column $j$ , from left to right do
5
for each row $i$ below the pivot do
6
place in $L_{ij}$ the multiple of the pivot row subtracted from row $i$
7
(the entry that was cleared, divided by the pivot)

Worked example. Factor $A = 2 - 4 2 - 6 4 - 5 - 5 0 - 1 3 - 4 7 5 - 8 1 - 3 - 2 181$ using row replacements only. Clear column $1$ below the pivot $2$ with multipliers $- 2, 1, - 3$ (recorded as $L_{21}, L_{31}, L_{41}$ ):

A \sim 2000 43 - 9 12 - 1 1 - 3 4 52 - 4 12 - 2 - 3 10 - 5 .

Clear column $2$ below the pivot $3$ with multipliers $- 3, 4$ ( $L_{32}, L_{42}$ ), then clear column $4$ below the pivot $2$ with multiplier $2$ ( $L_{43}$ ):

\sim 20004300 - 1 100 5224 - 2 - 3 17 \sim 20004300 - 1 100 5220 - 2 - 3 15 = U .

The recorded multipliers fill the lower triangle of $L$ :

L = 1 - 2 1 - 3 01 - 3 4 00120001, U = 20004300 - 1 100 5220 - 2 - 3 15 .

Clearing the $- 4$ below the first pivot used the multiplier $- 4/2 = - 2 = L_{21}$ ; the others are recorded the same way. A direct multiplication confirms $LU = A$ .

Row interchanges

When a needed pivot is zero — or, in floating point, when partial pivoting selects the largest available pivot for accuracy — row interchanges enter. The factorization then takes the permuted form $P A = LU$ , where $P$ is a permutation matrix recording the swaps, and $L$ is permuted lower triangular. The two-stage solve is unchanged apart from applying $P$ to $b$ first. Most references to an LU factorization allow this permuted case.

Operation counts

Flop counts explain why LU is preferred to computing $A^{- 1}$ . For a dense $n \times n$ matrix with $n$ moderately large:²

Task	Flops	Notes
LU factorization of $A$	$\approx \frac{2}{3} n^{3}$	same cost as reducing $[A ∣ b]$
Solve $L y = b$ then $U x = y$	$\approx 2 n^{2}$	each triangular solve is $\approx n^{2}$
Compute $A^{- 1}$	$\approx 2 n^{3}$	three times the LU cost
Multiply $A^{- 1} b$	$\approx 2 n^{2}$	but often less accurate than the LU solve

Once $A = LU$ is available, each additional right-hand side costs only $2 n^{2}$ flops, against the $2 n^{3}$ needed to build $A^{- 1}$ in the first place. When $A$ is sparse, $L$ and $U$ often stay sparse while $A^{- 1}$ fills in, widening the gap further. The numerical module develops pivoting, stability, and the symmetric Cholesky variant $A = R^{⊤} R$ .

Lay, Linear Algebra and Its Applications, §2.4 — Theorem 10, the column-row expansion $A B = \sum_{k} col_{k} (A) row_{k} (B)$ , together with block multiplication of conformable partitions and the inverse formulas for block triangular and block diagonal matrices. ↩
Lay, §2.5 — the LU factorization, its two-stage triangular solve, the row-replacement construction of $L$ , and the numerical note giving $\frac{2}{3} n^{3}$ flops for the factorization against $2 n^{3}$ for the inverse; partial pivoting yields the permuted factorization $P A = LU$ . ↩