LU Decomposition Calculator
Enter a 2x2 or 3x3 matrix and this calculator finds its LU decomposition using the Doolittle algorithm with partial pivoting. It returns the lower triangular matrix L, the upper triangular matrix U, and the permutation matrix P so that PA = LU. You also get the matrix determinant, a singularity check, and a step-by-step walkthrough of every row-elimination operation.
What is LU decomposition?
LU decomposition (also called LU factorisation) rewrites any invertible square matrix A as the product of two triangular matrices: A = LU. The lower triangular matrix L has non-zero entries on and below its main diagonal; the upper triangular matrix U has non-zero entries on and above its. The name comes from the notation: L for lower and U for upper. When row swaps are needed for numerical stability, a third permutation matrix P is introduced, giving PA = LU. Introduced in a practical form by Alan Turing in 1948, LU decomposition is the workhorse of computational linear algebra and is used internally by virtually every numerical solver and programming language.
How the Doolittle algorithm works
This calculator uses the Doolittle algorithm with partial pivoting. In the Doolittle convention, L has 1s on its diagonal (it is unit lower triangular) and U carries the pivots. The algorithm works in n - 1 stages for an n x n matrix. At stage k, the pivot is the entry in position (k, k) after any necessary row swaps. Each entry below the pivot is divided by it to form the multiplier stored in L. That multiplier is then used to zero out all entries below the pivot in column k, producing the next column of U. Partial pivoting means the algorithm first scans column k for the entry with the largest absolute value and swaps that row to the pivot position; this is the single most important step for avoiding catastrophic cancellation in floating-point arithmetic.
Solving Ax = b with LU decomposition
The main practical use of LU decomposition is solving linear systems Ax = b. Once you have PA = LU you break the problem into two easy triangular systems. First, permute the right-hand side to get Pb, then forward-substitute into Ly = Pb: because L is lower triangular, y₁ = b₁ immediately and each subsequent yᵢ is found by subtracting the known terms. Second, back-substitute into Ux = y: because U is upper triangular, xₙ = yₙ / uₙₙ and you work upward through xₙ₋₁, ..., x₁. Each triangular solve costs O(n²) operations, a huge saving over recomputing a fresh inverse or running Gaussian elimination from scratch for each new right-hand side. If you need to solve the same A with many different b vectors, factorise once and reuse L and U.
Determinant and invertibility from LU
The determinant of A equals the product of all diagonal entries of U, multiplied by -1 for each row swap performed by partial pivoting. Concretely, det(A) = (-1)^s * u₁₁ * u₂₂ * ... * uₙₙ, where s is the number of swaps. This is dramatically cheaper than expanding along a row with cofactors, which costs O(n!) multiplications. If any uᵢᵢ is zero the matrix is singular: det(A) = 0 and Ax = b either has no solution or infinitely many, depending on b. The calculator flags this as a singularity warning.
LU decomposition: key properties at a glance
| Property | What it means | Where to look |
|---|---|---|
| L matrix | Unit lower triangular - 1s on diagonal, zeros above | Forward substitution: Ly = Pb |
| U matrix | Upper triangular - pivots on diagonal | Back substitution: Ux = y |
| P matrix | Permutation - records which rows were swapped | Rearrange b before substitution: Pb |
| det(A) | Product of U diagonal * sign of swaps | Non-zero means A is invertible |
| Singular | At least one pivot is zero or near-zero | Ax = b has no unique solution |
| Partial pivoting | Row swap to maximise pivot magnitude | Reduces floating-point rounding error |
| Doolittle form | L has 1s on diagonal; U carries pivots | Used by this calculator |
| Crout form | U has 1s on diagonal; L carries pivots | Alternative convention |
Quick reference for interpreting LU decomposition results.
Frequently asked questions
What is the difference between LU decomposition with and without partial pivoting?
Without pivoting, the algorithm uses whatever entry sits in the pivot position. If that entry is zero the algorithm breaks down, and if it is very small division amplifies rounding errors. Partial pivoting finds the row with the largest absolute value in the current column and swaps it into the pivot position before continuing. This bounds the growth of rounding errors and is the standard approach in practice. This calculator always uses partial pivoting, so P may be the identity (no swaps needed) or a non-trivial permutation matrix.
What is the difference between Doolittle and Crout LU decompositions?
Both decompose A into the same pair of triangular matrices but place the 1s differently. Doolittle puts 1s on the diagonal of L and lets U carry the pivots. Crout does the opposite: 1s on the diagonal of U and pivots in L. Numerically the results are equivalent; the choice is a convention. This calculator uses the Doolittle form.
When does LU decomposition fail?
LU decomposition fails when the matrix is singular - that is, when at least one pivot is zero even after partial pivoting. Practically this means the matrix rows are linearly dependent: one row is a scalar multiple of another, or one row is a linear combination of the others. A matrix whose columns are linearly dependent is also singular. The calculator detects this and displays a singularity warning along with a determinant of zero.
Why is LU decomposition more useful than finding the inverse?
Computing the full inverse of an n x n matrix costs roughly 2n³ multiplications and then each solve Ax = b still costs another n². LU decomposition costs roughly (2/3)n³ once and then each forward-back substitution costs only 2n². If you need to solve Ax = b for many different b vectors, factorising once and substituting repeatedly is far cheaper. The inverse also accumulates more rounding error because every entry in A⁻¹ mixes contributions from all of A, whereas LU substitution keeps errors local.
Can LU decomposition be used for non-square matrices?
Not in the standard form. LU decomposition is defined for square matrices. For rectangular matrices (m x n with m not equal to n) you need the related LU decomposition with a rectangular U, or more commonly QR decomposition (which works for any m x n matrix and is the standard tool for solving least-squares problems). This calculator handles square 2x2 and 3x3 matrices.
How do I read the matrices shown in the results?
Each matrix is displayed as a semicolon-separated list of rows, where each row is a comma-separated list inside square brackets. For example, "[1, 0, 0]; [0.5, 1, 0]; [0.25, 0.667, 1]" is a 3x3 lower triangular matrix with 1s on the diagonal. The step-by-step panel below the results explains how each entry was computed.