LU Decomposition: A = LU

What is LU decomposition?

An $n \times n$ matrix $A$ is LU decomposed if it can be written as $A = L U$

where $L$ is lower triangular with ones on the diagonal and $U$ is upper triangular. The decomposition encodes the Gaussian elimination steps: $U$ is the reduced (upper triangular) matrix, and $L$ records the multipliers used to create zeros.

Step-by-step

$A = \begin{pmatrix} 2 & 1 \\ 6 & 4 \end{pmatrix}$

Step 1 — Identify the first pivot. $u_{11} = 2$, so $U$'s first row is simply $A$'s first row: $(2, 1)$.

Step 2 — Compute the multiplier to zero out $a_{21}$. $\ell_{21} = \dfrac{a_{21}}{u_{11}} = \dfrac{6}{2} = 3$

So row operation: $R_2 \to R_2 - 3 R_1$ gives $(6, 4) - 3(2, 1) = (0, 1)$. Therefore the second row of $U$ is $(0, 1)$.

Step 3 — Assemble $L$ and $U$. $L = \begin{pmatrix} 1 & 0 \\ 3 & 1 \end{pmatrix}, \quad U = \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}$

$L$ stores multipliers below the diagonal (in this $2 \times 2$ case, just $\ell_{21} = 3$); $U$ is the row-reduced form.

Verification: $LU = A$?

$LU = \begin{pmatrix} 1 & 0 \\ 3 & 1 \end{pmatrix} \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}$

• Entry (1,1): $1 \cdot 2 + 0 \cdot 0 = 2$ ✓
• Entry (1,2): $1 \cdot 1 + 0 \cdot 1 = 1$ ✓
• Entry (2,1): $3 \cdot 2 + 1 \cdot 0 = 6$ ✓
• Entry (2,2): $3 \cdot 1 + 1 \cdot 1 = 4$ ✓

$LU = A$ ✓

Why LU is useful

Once you have $A = LU$:

• Solving $A \mathbf{x} = \mathbf{b}$ becomes two triangular systems:
  1. Solve $L \mathbf{y} = \mathbf{b}$ by forward substitution.
  2. Solve $U \mathbf{x} = \mathbf{y}$ by back substitution. Each is $O(n^2)$ once you have $LU$.
• Reusable: for many different right-hand sides $\mathbf{b}_1, \mathbf{b}_2, \ldots$, you factor $A$ once ($O(n^3)$) and solve each system in $O(n^2)$.
• Determinant: $\det A = \det L \cdot \det U = \prod u_{ii}$ — just multiply diagonal entries of $U$.

When LU doesn't exist

If a pivot turns out to be zero mid-elimination, pure LU breaks down. The fix: PA = LU — pivoted LU, where $P$ is a permutation matrix that reorders rows to avoid zero pivots. Most software uses this form (e.g. NumPy's scipy.linalg.lu).

Common mistakes

• Forgetting the 1s on $L$'s diagonal. They're part of the definition; they make $L$ unit lower triangular.
• Signs on multipliers. $\ell_{21}$ is positive if the row operation subtracts $\ell_{21} R_1$; many texts use the opposite sign convention.
• Skipping pivoting when needed. If a zero pivot appears, plain LU fails — use partial pivoting.

Try it in the visualization

The elimination animates: the first row stays fixed, the second row is updated, and the multiplier $\ell_{21}$ is pulled out into $L$'s (2,1) position. At the end, $L$ and $U$ are multiplied back together to confirm $LU = A$.