Why an LU Factorization Makes Solving Easier
Suppose a square matrix \(\mathbf{A}\) has already been factored as \(\mathbf{A}=\mathbf{L}\mathbf{U}\), where \(\mathbf{L}\) is lower triangular and \(\mathbf{U}\) is upper triangular. Instead of solving \(\mathbf{A}\mathbf{x}=\mathbf{b}\) directly, introduce an intermediate vector \(\mathbf{y}\). First solve \(\mathbf{L}\mathbf{y}=\mathbf{b}\), then solve \(\mathbf{U}\mathbf{x}=\mathbf{y}\). The first system can be solved from top to bottom; the second can be solved from bottom to top. These procedures are called forward substitution and back substitution.
Throughout, take \(\mathbf{A},\mathbf{L},\mathbf{U}\in\mathbb{R}^{n\times n}\), and let vectors be columns. A matrix is lower triangular if its entries above the main diagonal are zero; it is upper triangular if its entries below the main diagonal are zero. In the usual LU convention, \(\mathbf{L}\) has ones on its diagonal. For a unique solution by substitution, the diagonal entries of both factors must be nonzero. The unit diagonal of \(\mathbf{L}\) automatically satisfies this condition.
The Substitution Formulas
Let \(\mathbf{T}\) be lower triangular with nonzero diagonal entries, and suppose \(\mathbf{T}\mathbf{y}=\mathbf{b}\). Row \(i\) of this equation contains only \(y_1,\dots,y_i\). Once \(y_1,\dots,y_{i-1}\) are known, the equation determines \(y_i\):
For \(i=1\), the sum has no terms and is taken to be zero, so \(y_1=b_1/t_{11}\). If \(\mathbf{T}\) is unit lower triangular, then \(t_{ii}=1\), and no division is needed.
For an upper triangular system \(\mathbf{U}\mathbf{x}=\mathbf{y}\) with nonzero diagonal entries, row \(i\) contains only \(x_i,\dots,x_n\). Starting from row \(n\), the variables \(x_{i+1},\dots,x_n\) are already known when row \(i\) is reached:
These formulas specify both the order and the arithmetic of the two solves. They require nonzero diagonal entries: if a diagonal entry is zero, the corresponding equation cannot be solved for its diagonal variable by division. A zero diagonal does not by itself tell us whether a system has no solutions or many solutions; that depends on the other equations and the right-hand side.
Proof. First let \(\mathbf{T}\) be lower triangular and solve \(\mathbf{T}\mathbf{y}=\mathbf{b}\). In row 1, \(t_{11}y_1=b_1\), so the nonzero value \(t_{11}\) determines exactly one \(y_1\). Suppose rows \(1,\dots,i-1\) have determined exactly one choice of \(y_1,\dots,y_{i-1}\). Row \(i\) is \(t_{i1}y_1+\cdots+t_{ii}y_i=b_i\), since all entries in columns greater than \(i\) are zero. The earlier variables are fixed, and \(t_{ii}\ne0\), so this equation determines exactly one \(y_i\) by the forward formula. Continuing through row \(n\) produces a solution satisfying every row, and the same argument shows that every solution must have these values. For an upper triangular matrix, begin with row \(n\): it determines exactly one \(x_n\) because \(u_{nn}\ne0\). If rows \(n,n-1,\dots,i+1\) have determined exactly one choice of \(x_{i+1},\dots,x_n\), row \(i\) contains \(u_{ii}x_i\) and terms involving only those already determined variables. Since \(u_{ii}\ne0\), it determines exactly one \(x_i\). Continuing upward gives a solution to every row and forces every solution to have the same values. \(\square\)
Solving a System from Its LU Factors
Proof. By the triangular-system result, the first system has a unique solution \(\mathbf{y}\), and the second system has a unique solution \(\mathbf{x}\). Since \(\mathbf{U}\mathbf{x}=\mathbf{y}\) and \(\mathbf{L}\mathbf{y}=\mathbf{b}\), associativity of matrix multiplication gives \(\mathbf{A}\mathbf{x}=(\mathbf{L}\mathbf{U})\mathbf{x}=\mathbf{L}(\mathbf{U}\mathbf{x})=\mathbf{L}\mathbf{y}=\mathbf{b}\). Thus the result of the two solves is a solution of the original system. If \(\mathbf{x}'\) is any other solution of \(\mathbf{A}\mathbf{x}'=\mathbf{b}\), then \(\mathbf{L}(\mathbf{U}\mathbf{x}')=\mathbf{b}=\mathbf{L}\mathbf{y}\). Because the lower triangular system with matrix \(\mathbf{L}\) has a unique solution, \(\mathbf{U}\mathbf{x}'=\mathbf{y}\). Because the upper triangular system with matrix \(\mathbf{U}\) also has a unique solution, \(\mathbf{x}'=\mathbf{x}\). Therefore the original solution is unique. \(\square\)
Worked Example: Forward Then Back Substitution
Use the given factors to solve \(\mathbf{A}\mathbf{x}=\mathbf{b}\), where \(\mathbf{A}=\mathbf{L}\mathbf{U}\) and \(\mathbf{b}=\begin{bmatrix}1\\7\\5\end{bmatrix}\):
First solve \(\mathbf{L}\mathbf{y}=\mathbf{b}\) from top to bottom. Row 1 gives \(y_1=1\). Row 2 gives \(2y_1+y_2=7\), hence \(2(1)+y_2=7\) and \(y_2=5\). Row 3 gives \(-y_1+3y_2+y_3=5\), hence \(-1+3(5)+y_3=5\) and \(y_3=-9\). Thus \(\mathbf{y}=\begin{bmatrix}1\\5\\-9\end{bmatrix}\).
Now solve \(\mathbf{U}\mathbf{x}=\mathbf{y}\) from bottom to top. Row 3 gives \(x_3=-9\). Row 2 gives \(3x_2+2x_3=5\), so \(3x_2-18=5\), \(3x_2=23\), and \(x_2=\tfrac{23}{3}\). Row 1 gives \(2x_1+x_2-x_3=1\), so \(2x_1+\tfrac{23}{3}+9=1\). Therefore \(2x_1+\tfrac{50}{3}=1\), \(2x_1=-\tfrac{47}{3}\), and \(x_1=-\tfrac{47}{6}\).
Check the factorization and the answer. Multiplying the factors gives \(\mathbf{A}=\begin{bmatrix}2&1&-1\\4&5&0\\-2&8&8\end{bmatrix}\). Then
The substitution steps solve the two triangular systems, and the final multiplication confirms the solution of the original system.
Several Right-Hand Sides
The same factors can be used when the right-hand side is a matrix \(\mathbf{B}\in\mathbb{R}^{n\times q}\). The goal is then to solve \(\mathbf{A}\mathbf{X}=\mathbf{B}\), where each column of \(\mathbf{X}\) is the solution for the corresponding column of \(\mathbf{B}\). Set \(\mathbf{Y}\) to solve \(\mathbf{L}\mathbf{Y}=\mathbf{B}\), then solve \(\mathbf{U}\mathbf{X}=\mathbf{Y}\). Each column can be treated as a separate vector solve; the matrix equations express all \(q\) solves together.
Proof. Write \(\mathbf{B}=\begin{bmatrix}\mathbf{b}_1&\cdots&\mathbf{b}_q\end{bmatrix}\). The equation \(\mathbf{L}\mathbf{Y}=\mathbf{B}\) consists of the \(q\) systems \(\mathbf{L}\mathbf{y}_k=\mathbf{b}_k\), one for each column \(k\). Each has exactly one solution by the triangular-system result. The equation \(\mathbf{U}\mathbf{X}=\mathbf{Y}\) likewise consists of \(q\) upper triangular systems, each with exactly one solution. Consequently \(\mathbf{X}\) is uniquely determined. Finally, \(\mathbf{A}\mathbf{X}=(\mathbf{L}\mathbf{U})\mathbf{X}=\mathbf{L}(\mathbf{U}\mathbf{X})=\mathbf{L}\mathbf{Y}=\mathbf{B}\), as required. \(\square\)
Worked Example: Two Right-Hand Sides at Once
Use the factors below to solve \(\mathbf{A}\mathbf{X}=\mathbf{B}\):
First compute \(\mathbf{Y}\) from \(\mathbf{L}\mathbf{Y}=\mathbf{B}\). Row 1 gives \(\mathbf{Y}_{1,:}=\begin{bmatrix}4&1\end{bmatrix}\), where \(\mathbf{Y}_{i,:}\) denotes row \(i\) of \(\mathbf{Y}\). Row 2 gives \(2\mathbf{Y}_{1,:}+\mathbf{Y}_{2,:}=\begin{bmatrix}10&2\end{bmatrix}\), so \(\mathbf{Y}_{2,:}=\begin{bmatrix}10&2\end{bmatrix}-2\begin{bmatrix}4&1\end{bmatrix}=\begin{bmatrix}2&0\end{bmatrix}\). Hence \(\mathbf{Y}=\begin{bmatrix}4&1\\2&0\end{bmatrix}\).
Next solve \(\mathbf{U}\mathbf{X}=\mathbf{Y}\). Row 2 gives \(2\mathbf{X}_{2,:}=\begin{bmatrix}2&0\end{bmatrix}\), so \(\mathbf{X}_{2,:}=\begin{bmatrix}1&0\end{bmatrix}\). Row 1 gives \(3\mathbf{X}_{1,:}+\mathbf{X}_{2,:}=\begin{bmatrix}4&1\end{bmatrix}\), so \(3\mathbf{X}_{1,:}=\begin{bmatrix}3&1\end{bmatrix}\) and \(\mathbf{X}_{1,:}=\begin{bmatrix}1&\tfrac13\end{bmatrix}\). Thus \(\mathbf{X}=\begin{bmatrix}1&\tfrac13\\1&0\end{bmatrix}\).
Check. The factor product is \(\mathbf{A}=\begin{bmatrix}3&1\\6&4\end{bmatrix}\), and multiplication gives
Each column checks separately: the first is mapped to \(\begin{bmatrix}4\\10\end{bmatrix}\), and the second to \(\begin{bmatrix}1\\2\end{bmatrix}\).
When a Diagonal Entry Is Zero
The nonzero-diagonal condition is essential to the unique-solution statement. Consider \(\mathbf{L}=\mathbf{I}_2\), \(\mathbf{U}=\begin{bmatrix}1&2\\0&0\end{bmatrix}\), and \(\mathbf{b}=\begin{bmatrix}3\\0\end{bmatrix}\). Here \(\mathbf{A}=\mathbf{L}\mathbf{U}=\mathbf{U}\), so the system is \(x_1+2x_2=3\) and \(0=0\). It has infinitely many solutions: taking \(x_2=t\) gives \(x_1=3-2t\). For instance, \(\begin{bmatrix}3\\0\end{bmatrix}\) and \(\begin{bmatrix}1\\1\end{bmatrix}\) both solve it. Indeed, multiplication by \(\mathbf{A}\) gives \(\begin{bmatrix}3\\0\end{bmatrix}\) for each. If instead the right-hand side is \(\begin{bmatrix}3\\1\end{bmatrix}\), the second equation is \(0=1\), so no solution exists.
Common Mistake: Skipping the Forward Solve
A frequent error is to treat \(\mathbf{U}\mathbf{x}=\mathbf{b}\) as the system to solve after receiving \(\mathbf{A}=\mathbf{L}\mathbf{U}\). This is wrong unless \(\mathbf{L}\mathbf{y}=\mathbf{b}\) happens to give \(\mathbf{y}=\mathbf{b}\). In the first worked example, incorrectly solving \(\mathbf{U}\mathbf{x}=\mathbf{b}\) gives \(x_3=5\), then \(3x_2+10=7\), so \(x_2=-1\), and then \(2x_1-1-5=1\), so \(x_1=\tfrac72\). But the second row of the actual matrix equation gives \(4(\tfrac72)+5(-1)=14-5=9\ne7\). The correction is to first solve \(\mathbf{L}\mathbf{y}=\mathbf{b}\), obtaining \(\mathbf{y}=\begin{bmatrix}1\\5\\-9\end{bmatrix}\), and only then solve \(\mathbf{U}\mathbf{x}=\mathbf{y}\).
For several right-hand sides, the same order applies: solve \(\mathbf{L}\mathbf{Y}=\mathbf{B}\) before solving \(\mathbf{U}\mathbf{X}=\mathbf{Y}\). Keeping the intermediate right-hand side explicit prevents confusing the original data \(\mathbf{B}\) with the result \(\mathbf{Y}\) of the forward solve.
Check Your Understanding
For each question, use the stated factorization and verify any computed solution by substitution.
- For \(\mathbf{L}=\begin{bmatrix}1&0\\3&1\end{bmatrix}\), solve \(\mathbf{L}\mathbf{y}=\begin{bmatrix}2\\11\end{bmatrix}\).
- For \(\mathbf{U}=\begin{bmatrix}2&-1\\0&4\end{bmatrix}\), solve \(\mathbf{U}\mathbf{x}=\begin{bmatrix}5\\8\end{bmatrix}\).
- Suppose \(\mathbf{A}=\mathbf{L}\mathbf{U}\) with both factors having nonzero diagonal entries. Explain why solving the two triangular systems gives a solution of \(\mathbf{A}\mathbf{x}=\mathbf{b}\).
- For \(\mathbf{L}=\begin{bmatrix}1&0\\1&1\end{bmatrix}\), \(\mathbf{U}=\begin{bmatrix}2&1\\0&3\end{bmatrix}\), and \(\mathbf{B}=\begin{bmatrix}1&0\\4&6\end{bmatrix}\), find \(\mathbf{Y}\) and then \(\mathbf{X}\) satisfying \(\mathbf{L}\mathbf{Y}=\mathbf{B}\) and \(\mathbf{U}\mathbf{X}=\mathbf{Y}\).
- Give a reason that a zero diagonal entry in an upper triangular matrix prevents the general nonzero-diagonal uniqueness result from applying.
