LU Decomposition

Gaussian elimination is an algorithm. LU decomposition records that algorithm as a matrix factorization — so you can reuse the work.

The idea

Every invertible matrix A can be written as:

where L is lower triangular with 1s on the diagonal, and U is upper triangular. These are exactly the two triangles produced by Gaussian elimination.

Where L and U come from

When you do Gaussian elimination on a 2×2 matrix:

The multiplier $m = c/a$ is the number you used to eliminate c. It becomes the off-diagonal entry of L:

Why it matters

To solve $A\mathbf{x} = \mathbf{b}$, substitute A = LU:

Each sub-problem (forward substitution for Ly = b, back substitution for Ux = y) is trivial because the matrices are triangular. And if you need to solve with multiple right-hand sides b₁, b₂, …, you only factorize A once.

Pivoting

If the top-left entry is zero (or near-zero), the multiplier blows up. The fix is partial pivoting: swap rows to put the largest entry in the pivot position first. In practice, A = PLU where P is a permutation matrix recording the swaps.

Try it

Edit the matrix or pick a preset. The L and U factors update live. Notice that L always has 1s on the diagonal and zeros above, while U has zeros below. Their product reconstructs A exactly.

from scipy.linalg import lu
import numpy as np

A = np.array([[2., 1.], [4., 3.]])
P, L, U = lu(A)

print(L)  # lower triangular
print(U)  # upper triangular
print(np.allclose(P @ L @ U, A))  # True

# Efficient: solve multiple systems with same A
import scipy.linalg
lu_factor = scipy.linalg.lu_factor(A)
x1 = scipy.linalg.lu_solve(lu_factor, [1, 2])
x2 = scipy.linalg.lu_solve(lu_factor, [3, 4])