Matrix LU Decomposition Calculator

What is LU Decomposition?

LU decomposition (also called LU factorization) is a method that factors a square matrix $A$ into the product of a lower triangular matrix $L$ and an upper triangular matrix $U$, such that $A = LU$. When partial pivoting is used to improve numerical stability, the factorization becomes $PA = LU$, where $P$ is a permutation matrix that records the row swaps performed during Gaussian elimination.

The lower triangular matrix $L$ has ones on its diagonal and stores the multipliers used during elimination, while the upper triangular matrix $U$ is the row echelon form of the original matrix. This factorization is one of the most fundamental and widely used techniques in numerical linear algebra.

How LU Decomposition Works

The algorithm proceeds through each column $k$ of the matrix:

1. Partial pivoting: Find the row with the largest absolute value in column $k$ and swap it into the pivot position. This prevents division by zero and improves numerical stability.
2. Elimination: For each row below the pivot, compute the multiplier $L_{ik} = U_{ik} / U_{kk}$ and subtract the scaled pivot row to eliminate the column entry.
3. The multiplier values form the subdiagonal entries of $L$, while the eliminated matrix becomes $U$.

The result is stored compactly: the elimination multipliers fill $L$ (with ones on the diagonal), and the row echelon form fills $U$. The permutation matrix $P$ records all row swaps.

Solving Linear Systems with LU

Once $PA = LU$ is computed, solving $Ax = b$ becomes a two-step process. First, solve $Ly = Pb$ using forward substitution (straightforward since $L$ is lower triangular). Then solve $Ux = y$ using back substitution (straightforward since $U$ is upper triangular). This two-step approach is much more efficient than performing Gaussian elimination from scratch for each new right-hand side $b$, making LU decomposition ideal for problems with multiple right-hand sides.

Applications

LU decomposition is widely used in:

• Engineering — solving large systems from finite element analysis, circuit simulation, and structural mechanics
• Scientific computing — numerical solution of differential equations, matrix inversion, and condition number estimation
• Statistics — regression analysis, covariance matrix factorization, and maximum likelihood estimation
• Computer graphics — transformation pipelines and physics simulations
• Machine learning — training linear models and Gaussian processes

For related linear algebra tools, try the Matrix Exponential Calculator, Linear Equation Solver, or Derivative Calculator.