LU Decomposition

LU decomposition factors a matrix into a lower triangular matrix $L$ and an upper triangular matrix $U$:

$$A = LU$$

The Matrices

• $L$ — lower triangular (1’s on diagonal, multipliers below)
• $U$ — upper triangular (the result of elimination)

Why It’s Useful

Instead of solving $Ax = b$ once, we solve:

1. $Lc = b$ (forward substitution)
2. $Ux = c$ (back substitution)

This is fast! And if you have many right-hand sides $b_1, b_2, \ldots$, you only factor $A$ once.

With Row Exchanges

If row exchanges are needed, we get:

$$PA = LU$$

Where $P$ is a permutation matrix that records the row swaps.

Cost

• Factorization: $O(\frac{1}{3}n^3)$
• Each solve: $O(n^2)$

Much cheaper than inverting the matrix!