Why Group Rows and Columns into Blocks?
Gaussian elimination can be viewed at two levels. At the scalar level, each pivot eliminates entries below it. At the block level, a group of variables is eliminated at once, and the resulting formulas look like the scalar ones with matrices in place of numbers. This viewpoint is useful when a matrix has natural groups of variables, and it also makes explicit why a computed factorization can serve many right-hand sides.
Throughout, matrices and vectors have real entries. Partition a matrix into four blocks, with the block sizes compatible as follows:
The block partition groups the first \(p\) variables and equations together, and the remaining \(q\) variables and equations together. Assume \(\mathbf{A}_{11}\) is invertible. Eliminating the first group of variables from the second group produces the matrix \(\mathbf{A}_{22}-\mathbf{A}_{21}\mathbf{A}_{11}^{-1}\mathbf{A}_{12}\).
The dimensions in this expression matter: \(\mathbf{A}_{21}\mathbf{A}_{11}^{-1}\) is \(q\times p\), and multiplying it by \(\mathbf{A}_{12}\), which is \(p\times q\), gives a \(q\times q\) matrix. Thus it can be subtracted from \(\mathbf{A}_{22}\).
The Block LU Formula
Proof. The block sizes in the first factor are \(p\times p,p\times q,q\times p,q\times q\), respectively, and those in the second factor are the same. Multiplying the block matrices gives $$ \begin{bmatrix} \mathbf{A}_{11}&\mathbf{A}_{12}\\ \mathbf{A}_{21}\mathbf{A}_{11}^{-1}\mathbf{A}_{11}& \mathbf{A}_{21}\mathbf{A}_{11}^{-1}\mathbf{A}_{12}+\mathbf{S} \end{bmatrix}. $$ Since \(\mathbf{A}_{11}^{-1}\mathbf{A}_{11}=\mathbf{I}_p\), the lower-left block is \(\mathbf{A}_{21}\). By the definition of \(\mathbf{S}\), the lower-right block is \(\mathbf{A}_{21}\mathbf{A}_{11}^{-1}\mathbf{A}_{12}+\mathbf{A}_{22}-\mathbf{A}_{21}\mathbf{A}_{11}^{-1}\mathbf{A}_{12}=\mathbf{A}_{22}\). The product is \(\mathbf{A}\), as required. \(\square\)
This factorization records one elimination stage: the block below \(\mathbf{A}_{11}\) is removed, and the remaining lower-right block becomes \(\mathbf{S}\). The theorem does not require \(\mathbf{S}\) to be invertible. If \(\mathbf{S}\) is singular, the displayed factorization still holds, but it cannot be used to obtain a unique solution for every right-hand side by solving with the second factor.
Worked Example: Forming and Verifying a Block LU Factorization
Partition the matrix after its first two rows and columns, and find its block LU factorization:
where \(\mathbf{A}_{11}=\begin{bmatrix}2&1\\4&5\end{bmatrix}\), \(\mathbf{A}_{12}=\begin{bmatrix}1\\0\end{bmatrix}\), \(\mathbf{A}_{21}=\begin{bmatrix}2&1\end{bmatrix}\), and \(\mathbf{A}_{22}=\begin{bmatrix}5\end{bmatrix}\). The determinant of \(\mathbf{A}_{11}\) is \(2(5)-1(4)=6\), so this \(2\times2\) block is invertible. Its inverse is
Now multiply the \(1\times2\) block \(\mathbf{A}_{21}\) by the full \(2\times2\) inverse:
Then \(\mathbf{A}_{21}\mathbf{A}_{11}^{-1}\mathbf{A}_{12}=\begin{bmatrix}1&0\end{bmatrix}\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}1\end{bmatrix}\). Hence \(\mathbf{S}=\begin{bmatrix}5\end{bmatrix}-\begin{bmatrix}1\end{bmatrix}=\begin{bmatrix}4\end{bmatrix}\). Substituting into the block formula gives
To obtain ordinary scalar triangular factors, factor the leading block as \(\mathbf{A}_{11}=\mathbf{L}_{11}\mathbf{U}_{11}\), where \(\mathbf{L}_{11}=\begin{bmatrix}1&0\\2&1\end{bmatrix}\) and \(\mathbf{U}_{11}=\begin{bmatrix}2&1\\0&3\end{bmatrix}\). Their product is \(\begin{bmatrix}2&1\\4&5\end{bmatrix}\). In this example \(\mathbf{A}_{21}\mathbf{U}_{11}^{-1}=\begin{bmatrix}1&0\end{bmatrix}\) and \(\mathbf{L}_{11}^{-1}\mathbf{A}_{12}=\begin{bmatrix}1\\-2\end{bmatrix}\). Thus the scalar factors are
Check: The first row of \(\mathbf{L}\mathbf{U}\) is \((2,1,1)\). Its second row is twice the first row of \(\mathbf{U}\) plus the second row of \(\mathbf{U}\), giving \((4,5,0)\). Its third row is the first row of \(\mathbf{U}\) plus the third row of \(\mathbf{U}\), giving \((2,1,5)\). Therefore \(\mathbf{L}\mathbf{U}=\mathbf{A}\).
Solving by Eliminating a Block
Write the unknown vector and right-hand side in matching blocks, \(\mathbf{x}=\begin{bmatrix}\mathbf{x}_1\\\mathbf{x}_2\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}\mathbf{b}_1\\\mathbf{b}_2\end{bmatrix}\). The system \(\mathbf{A}\mathbf{x}=\mathbf{b}\) is equivalent to the two equations $$ \mathbf{A}_{11}\mathbf{x}_1+\mathbf{A}_{12}\mathbf{x}_2=\mathbf{b}_1, \qquad \mathbf{A}_{21}\mathbf{x}_1+\mathbf{A}_{22}\mathbf{x}_2=\mathbf{b}_2. $$
If \(\mathbf{A}_{11}\) is invertible, the first equation gives \(\mathbf{x}_1=\mathbf{A}_{11}^{-1}(\mathbf{b}_1-\mathbf{A}_{12}\mathbf{x}_2)\). Substituting this into the second equation yields $$ \left(\mathbf{A}_{22}-\mathbf{A}_{21}\mathbf{A}_{11}^{-1}\mathbf{A}_{12}\right)\mathbf{x}_2 = \mathbf{b}_2-\mathbf{A}_{21}\mathbf{A}_{11}^{-1}\mathbf{b}_1. $$
Consequently, if both \(\mathbf{A}_{11}\) and its Schur complement \(\mathbf{S}\) are invertible, first solve this equation for \(\mathbf{x}_2\), then use the first block equation to recover \(\mathbf{x}_1\). The invertibility condition on \(\mathbf{S}\) is needed for this procedure to produce a unique \(\mathbf{x}_2\).
Worked Example: Solving with a Scalar Schur Complement
Solve \(\begin{bmatrix}3&1\\2&2\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix}=\begin{bmatrix}7\\8\end{bmatrix}\) by taking the top-left entry as \(\mathbf{A}_{11}\). Here \(\mathbf{A}_{11}=3\), \(\mathbf{A}_{12}=1\), \(\mathbf{A}_{21}=2\), and \(\mathbf{A}_{22}=2\). The Schur complement is \(S=2-2(1/3)(1)=4/3\).
The reduced equation for \(x_2\) is $$ \frac{4}{3}x_2=8-2\left(\frac{1}{3}\right)7 =8-\frac{14}{3} =\frac{10}{3}, \qquad x_2=\frac{10}{3}\frac{3}{4}=\frac{5}{2}. $$ Then \(3x_1+1\cdot\frac52=7\), so \(3x_1=\frac92\) and \(x_1=\frac32\).
Check: \(3(\frac32)+\frac52=\frac92+\frac52=7\), and \(2(\frac32)+2(\frac52)=3+5=8\). Both original equations hold.
One Factorization, Many Right-Hand Sides
Suppose the coefficient matrix has already been factored as \(\mathbf{A}=\mathbf{L}\mathbf{U}\), where \(\mathbf{L}\) and \(\mathbf{U}\) are invertible triangular matrices. For a right-hand-side matrix \(\mathbf{B}\), whose columns are several vectors to be used as right-hand sides, solve \(\mathbf{L}\mathbf{Y}=\mathbf{B}\) by forward substitution and then solve \(\mathbf{U}\mathbf{X}=\mathbf{Y}\) by back substitution. The same factors are used for every column.
Proof. From \(\mathbf{U}\mathbf{X}=\mathbf{Y}\) and \(\mathbf{L}\mathbf{Y}=\mathbf{B}\), multiplication of the first equation on the left by \(\mathbf{L}\) gives \(\mathbf{L}\mathbf{U}\mathbf{X}=\mathbf{L}\mathbf{Y}=\mathbf{B}\). Since \(\mathbf{A}=\mathbf{L}\mathbf{U}\), this is \(\mathbf{A}\mathbf{X}=\mathbf{B}\). For uniqueness, if \(\mathbf{A}\widetilde{\mathbf{X}}=\mathbf{B}\), then \(\mathbf{L}\mathbf{U}\widetilde{\mathbf{X}}=\mathbf{L}\mathbf{U}\mathbf{X}\). Multiplying on the left by \(\mathbf{L}^{-1}\), then by \(\mathbf{U}^{-1}\), gives \(\widetilde{\mathbf{X}}=\mathbf{X}\). \(\square\)
This is the practical advantage of factoring once. When new right-hand sides arrive, the elimination that produced the factors need not be repeated; only the two triangular solves are needed for each new column. This is the same principle as solving repeated right-hand sides one at a time, expressed in a way that allows all columns to be handled together.
Worked Example: Reusing the Factors for Two Right-Hand Sides
Use the factors from the first example to solve \(\mathbf{A}\mathbf{X}=\mathbf{B}\), where \(\mathbf{B}=\begin{bmatrix}3&0\\4&5\\7&-4\end{bmatrix}\). First solve \(\mathbf{L}\mathbf{Y}=\mathbf{B}\). From the first row, \(y_{11}=3\) and \(y_{12}=0\). From the second row, \(2y_{11}+y_{21}=4\) and \(2y_{12}+y_{22}=5\), so \(y_{21}=-2\) and \(y_{22}=5\). From the third row, \(y_{11}+y_{31}=7\) and \(y_{12}+y_{32}=-4\), so \(y_{31}=4\) and \(y_{32}=-4\). Therefore
Now solve \(\mathbf{U}\mathbf{X}=\mathbf{Y}\). The last row gives \(4x_{31}=4\) and \(4x_{32}=-4\), so \(x_{31}=1\) and \(x_{32}=-1\). The second row gives \(3x_{21}-2x_{31}=-2\), hence \(3x_{21}-2=-2\) and \(x_{21}=0\); also \(3x_{22}-2x_{32}=5\), hence \(3x_{22}+2=5\) and \(x_{22}=1\). The first row gives \(2x_{11}+x_{21}+x_{31}=3\), so \(2x_{11}+1=3\) and \(x_{11}=1\); and \(2x_{12}+x_{22}+x_{32}=0\), so \(2x_{12}+1-1=0\) and \(x_{12}=0\). Thus
Check: Multiplication gives \(\mathbf{A}\mathbf{X}= \begin{bmatrix}2+0+1&0+1-1\\4+0+0&0+5+0\\2+0+5&0+1-5\end{bmatrix} =\begin{bmatrix}3&0\\4&5\\7&-4\end{bmatrix}=\mathbf{B}\). Both right-hand sides are solved using the same \(\mathbf{L}\) and \(\mathbf{U}\).
Common Pitfall: Multiplying the Wrong Block
Block products must respect dimensions. A tempting but incorrect calculation is \(\begin{bmatrix}2&1\end{bmatrix}\begin{bmatrix}1/2\\0\end{bmatrix}=\begin{bmatrix}1&0\end{bmatrix}\). The left side is a \(1\times2\) matrix multiplied by a \(2\times1\) matrix, so the result is the scalar \(1\), not a row vector. In the first worked example, the vector \(\begin{bmatrix}1/2\\0\end{bmatrix}\) is not \(\mathbf{A}_{11}^{-1}\); it is only a possible vector-sized factor in a different product. The correct multiplier is the full inverse matrix: $$ \begin{bmatrix}2&1\end{bmatrix} \frac{1}{6}\begin{bmatrix}5&-1\\-4&2\end{bmatrix} = \begin{bmatrix}1&0\end{bmatrix}. $$
Another condition to keep visible is that the leading block \(\mathbf{A}_{11}\) must be invertible for this particular formula. A different block partition may have a different leading block, and pivoting may be needed if the chosen block cannot be inverted. The algebraic factorization explains a valid elimination step; it does not remove the need to check that its required inverse exists.
Check Your Understanding
Use the block sizes and invertibility hypotheses explicitly in your reasoning.
- For \(\mathbf{A}=\begin{bmatrix}4&2\\3&5\end{bmatrix}\), partition into scalar blocks and compute the Schur complement of the top-left entry.
- State the dimensions of \(\mathbf{A}_{21}\mathbf{A}_{11}^{-1}\) and \(\mathbf{A}_{21}\mathbf{A}_{11}^{-1}\mathbf{A}_{12}\) for the general block partition in this tutorial.
- For \(\mathbf{A}=\begin{bmatrix}2&1\\1&3\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}5\\7\end{bmatrix}\), use the top-left scalar block and the Schur complement to solve \(\mathbf{A}\mathbf{x}=\mathbf{b}\).
- Explain why the block LU factorization formula can still be valid when \(\mathbf{S}\) is singular, even though the solve procedure may fail to give a unique solution.
- If \(\mathbf{A}=\mathbf{L}\mathbf{U}\) is already known, describe the two triangular systems to solve for a matrix of right-hand sides \(\mathbf{B}\), and explain why the factorization is not recomputed for each column.
