LU Factorization

Introduction

students, when you solve a system of linear equations in Numerical Analysis, one of the biggest goals is to turn a hard problem into a simpler one. LU factorization does exactly that ✨. It rewrites a matrix as the product of two easier matrices, which makes solving many systems faster and more organized.

In this lesson, you will learn how LU factorization works, why it is useful, and how it connects to Gaussian elimination and the bigger picture of Linear Systems I. By the end, you should be able to explain the main idea of LU factorization, carry out the basic steps, and recognize when it helps in real computations.

Learning goals

Understand what LU factorization means and why it is useful.
See how LU factorization is connected to Gaussian elimination.
Learn how to use $L$ and $U$ to solve a system $A\mathbf{x}=\mathbf{b}$.
Recognize when row swaps or pivoting may be needed.
Connect LU factorization to the Midterm 1 material on linear systems.

What LU Factorization Means

LU factorization is a way to write a square matrix $A$ as

$$A=LU,$$

where $L$ is a lower triangular matrix and $U$ is an upper triangular matrix.

A lower triangular matrix has zeros above the main diagonal, and an upper triangular matrix has zeros below the main diagonal. That means $L$ looks “downward,” while $U$ looks “upward.” A simple example is

$$L=\begin{bmatrix}1&0&0\\2&1&0\\-1&3&1\end{bmatrix}, \qquad U=\begin{bmatrix}4&5&6\\0&2&1\\0&0&7\end{bmatrix}.$$

When you multiply these two matrices, you recover $A$.

The most common idea behind LU factorization is this: instead of solving $A\mathbf{x}=\mathbf{b}$ all at once, you first solve

$$L\mathbf{y}=\mathbf{b}$$

and then solve

$$U\mathbf{x}=\mathbf{y}.$$

Because $L$ and $U$ are triangular, each system is much easier to solve than the original one. This is a major advantage in Numerical Analysis, especially when the same matrix $A$ is used with many different right-hand sides $\mathbf{b}$.

Connection to Gaussian Elimination

LU factorization is closely tied to Gaussian elimination. In fact, Gaussian elimination is the process that usually creates the matrices $L$ and $U$.

During elimination, you use row operations to eliminate entries below the pivots. The result is an upper triangular matrix $U$. The numbers used to eliminate entries are stored in $L$.

For example, suppose

$$A=\begin{bmatrix}2&1\\8&7\end{bmatrix}.$$

To eliminate the $8$ below the first pivot $2$, use the multiplier

$$m_{21}=\frac{8}{2}=4.$$

The second row becomes row $2-4\cdot$row $1$, which gives

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

The corresponding lower triangular matrix is

$$L=\begin{bmatrix}1&0\\4&1\end{bmatrix}.$$

Check the product:

$$LU=\begin{bmatrix}1&0\\4&1\end{bmatrix}\begin{bmatrix}2&1\\0&3\end{bmatrix}=\begin{bmatrix}2&1\\8&7\end{bmatrix}=A.$$

This shows the meaning of LU factorization in a very concrete way. The elimination steps are not lost; they are recorded inside $L$.

How to Solve a System Using LU

Suppose you want to solve

$$A\mathbf{x}=\mathbf{b},$$

and you already have $A=LU$. Then the problem becomes two simpler systems.

First solve

$$L\mathbf{y}=\mathbf{b}$$

by forward substitution. Since $L$ is lower triangular, you can solve from top to bottom.

Then solve

$$U\mathbf{x}=\mathbf{y}$$

by back substitution. Since $U$ is upper triangular, you can solve from bottom to top.

Example

Let

$$A=\begin{bmatrix}2&1\\8&7\end{bmatrix}, \qquad \mathbf{b}=\begin{bmatrix}5\\19\end{bmatrix}.$$

Using the factorization from above,

$$L=\begin{bmatrix}1&0\\4&1\end{bmatrix}, \qquad U=\begin{bmatrix}2&1\\0&3\end{bmatrix}.$$

First solve

$$L\mathbf{y}=\mathbf{b}.$$

Write $\mathbf{y}=\begin{bmatrix}y_1\y_2\end{bmatrix}$. Then

$$y_1=5,$$

and

$$4y_1+y_2=19.$$

$$y_2=19-4(5)= -1.$$

Thus

$$\mathbf{y}=\begin{bmatrix}5\\-1\end{bmatrix}.$$

Now solve

$$U\mathbf{x}=\mathbf{y}.$$

Write $\mathbf{x}=\begin{bmatrix}x_1\x_2\end{bmatrix}$. Then

$$3x_2=-1,$$

$$x_2=-\frac{1}{3}.$$

Next,

$$2x_1+x_2=5,$$

$$2x_1=5+\frac{1}{3}=\frac{16}{3}.$$

Therefore,

$$x_1=\frac{8}{3}.$$

The solution is

$$\mathbf{x}=\begin{bmatrix}\frac{8}{3}\\-\frac{1}{3}\end{bmatrix}.$$

This method is efficient because the expensive elimination is done once, and then each new right-hand side can be handled quickly.

When Pivoting Is Needed

Not every matrix can be factored neatly as $A=LU$ without changing row order. Sometimes a pivot on the diagonal is $0$, or a pivot is so small that numerical errors could become large.

In those cases, row exchanges are used. This leads to a factorization of the form

$$PA=LU,$$

where $P$ is a permutation matrix that represents row swaps.

A permutation matrix is a matrix formed by swapping rows of the identity matrix. Its job is to reorder the equations so elimination can proceed safely.

For example, if the first entry in the first column is $0$, you cannot divide by it to form a multiplier. Swapping with a lower row that has a better pivot fixes the problem.

This idea is important in Numerical Analysis because computers must control rounding error carefully. Pivoting improves stability and reduces the chance that small computational errors will grow too much 📉.

Why LU Factorization Matters in Practice

LU factorization is useful whenever the same matrix $A$ appears with several different vectors $\mathbf{b}$. This happens in science, engineering, economics, and data analysis.

For instance, imagine a model where the structure of the system stays the same, but the input data changes many times. Instead of repeating full Gaussian elimination every time, you compute $L$ and $U$ once and reuse them.

This is especially important for large systems. If $A$ is $n\times n$, solving one system directly by elimination takes about the same basic work as building the factorization. But after that, solving for another right-hand side is much faster because forward and back substitution are simpler than elimination.

LU factorization also helps explain how algorithms are built. Numerical Analysis does not only ask for the answer; it asks how to compute the answer efficiently, accurately, and reliably. LU factorization is a perfect example of this idea.

Common Terms to Know

Here are the key words students should know:

$A$: the original matrix in the system.
$L$: lower triangular matrix.
$U$: upper triangular matrix.
Pivot: the entry used to eliminate numbers below it.
Multiplier: the number used to eliminate a lower entry, such as $m_{21}=\frac{a_{21}}{a_{11}}$.
Forward substitution: solving $L\mathbf{y}=\mathbf{b}$ from top to bottom.
Back substitution: solving $U\mathbf{x}=\mathbf{y}$ from bottom to top.
Permutation matrix $P$: a matrix that records row swaps.

These terms often appear together because they describe one connected process.

Conclusion

LU factorization is one of the central tools in linear systems. It turns a matrix problem into two triangular systems, which are much easier to solve. It is built from the same elimination ideas as Gaussian elimination, but it stores the work in a reusable form.

For Midterm 1 and Linear Systems I, LU factorization matters because it connects theory, computation, and efficiency. It helps explain how linear systems are solved by hand and by computer, and it prepares you for more advanced topics in Numerical Analysis.

If you remember one idea, let it be this: factorization changes a difficult system $A\mathbf{x}=\mathbf{b}$ into simpler steps using $A=LU$ or, when row swaps are needed, $PA=LU$.

Study Notes

LU factorization writes a matrix as $A=LU$.
$L$ is lower triangular and $U$ is upper triangular.
LU comes from Gaussian elimination; the elimination multipliers are stored in $L$.
To solve $A\mathbf{x}=\mathbf{b}$, first solve $L\mathbf{y}=\mathbf{b}$, then solve $U\mathbf{x}=\mathbf{y}$.
Use forward substitution for $L\mathbf{y}=\mathbf{b}$.
Use back substitution for $U\mathbf{x}=\mathbf{y}$.
If row swaps are needed, the factorization becomes $PA=LU$.
Pivoting helps avoid division by $0$ and improves numerical stability.
LU factorization is efficient when solving many systems with the same matrix $A$ but different vectors $\mathbf{b}$.
It is a key topic in Midterm 1 and Linear Systems I because it links matrix theory, elimination, and computation.