LU decomposition calculator

This page is an LU decomposition calculator with steps, the factorization also called an LU factorization. It writes a square matrix as A = L U, or as P A = L U when a row exchange is required. L is lower triangular with ones on the diagonal. U is upper triangular. Each entry below the diagonal of L is a multiplier from elimination, and U is the matrix those steps leave behind. Entries can be integers, decimals, or fractions such as 3/4. The arithmetic stays exact.

Reduced row echelon form keeps going: it clears above the pivots and scales each pivot to 1. LU factorization stops at U and saves the multipliers. That is why the factors solve A x = b without an inverse. Forward substitution solves L y = b, or L y = P b if rows moved, and back substitution solves U x = y. Building the inverse repeats elimination several times and throws the factors away. The reduced row echelon form calculator is the tool when you want the cleared matrix and the free variables. The 3 by 3 matrix calculator is the tool when you want the determinant and the inverse.

The box opens on a 3 by 3 matrix whose factors need no row exchange. The right hand side (4, −2, 7) has solution (1, 1, 1). Mark "Solve A x = b" to see the substitution. The same writeup is printed below. A zero on the diagonal that a lower entry could replace is the "Needs a row exchange" button. A repeated row is the singular example, and the page refuses it.

Where L and U come from

Elimination subtracts a multiple of the pivot row from a lower row so that the entry under the pivot becomes zero. The multiplier is that entry divided by the pivot. U keeps the rows after every subtraction, including the pivots and the entries above them, and it puts explicit zeros under the pivots. L stores each multiplier in the position that was cleared, and it puts ones on the diagonal. Multiply L by U and the multipliers put the cleared entries back. That product is A when no rows were swapped.

The pattern with ones on the diagonal of L is the Doolittle factorization. Some books put the ones on the diagonal of U instead and call the result Crout. The two splittings are not the same matrices, and their product is still A. This page does Doolittle only, because that is the splitting elimination writes if you leave the pivots in U and the multipliers in L.

Partial pivoting is the version that looks down the column first. The remaining entry of largest absolute value becomes the pivot, and that row exchange is recorded in P. The check is then P A = L U. A homework key that never swapped rows will not match this mode. Use "No row exchanges" when the textbook problem does not mention pivoting. If that mode hits a zero pivot with a nonzero entry below it, the page stops and names the column. It does not silently swap.

A fully worked example

Let A have rows (2, 1, 1), (4, −6, 0), and (−2, 7, 2), and let b = (4, −2, 7). The first pivot is 2. The multiplier for row 2 is 2, and row 2 becomes (0, −8, −2). The multiplier for row 3 is −1, so row 3 gains a copy of row 1 and becomes (0, 8, 3). The next pivot is −8. The multiplier is −1, so row 3 gains a copy of the new row 2 and becomes (0, 0, 1). Then

L has rows (1, 0, 0), (2, 1, 0), and (−1, −1, 1). U has rows (2, 1, 1), (0, −8, −2), and (0, 0, 1). Their product is A. Forward substitution on L y = b gives y = (4, −10, 1). Back substitution on U x = y gives x = (1, 1, 1). The lines below are the same steps the calculator prints when you load the worked system.

No row exchanges. This is the Doolittle pattern: ones on the diagonal of L, multipliers below that diagonal, and U the upper triangular matrix left by elimination.
A
Row 1: 2, 1, 1
Row 2: 4, −6, 0
Row 3: −2, 7, 2
Column 1 pivot is 2.
Multiplier for row 2 is 4 / 2 = 2.
Row 2 becomes row 2 minus 2 times row 1.
Row 2 is now 0, −8, −2.
Multiplier for row 3 is −2 / 2 = −1.
Row 3 becomes row 3 plus 1 times row 1.
Row 3 is now 0, 8, 3.
Column 2 pivot is −8.
Multiplier for row 3 is 8 / −8 = −1.
Row 3 becomes row 3 plus 1 times row 2.
Row 3 is now 0, 0, 1.
Column 3 pivot is 1. No rows remain below it.
L
Row 1: 1, 0, 0
Row 2: 2, 1, 0
Row 3: −1, −1, 1
U
Row 1: 2, 1, 1
Row 2: 0, −8, −2
Row 3: 0, 0, 1
No rows were exchanged, so P is the identity and A = L times U.
L times U
Row 1: 2, 1, 1
Row 2: 4, −6, 0
Row 3: −2, 7, 2
Check passed. L times U matches A.
Solve A x = b by solving L y = b, then U x = y.
Right hand side in elimination order: 4, −2, 7.
Forward substitution, y₁ = 4 = 4.
Forward substitution, y₂ = −2 − (2)(4) = −10.
Forward substitution, y₃ = 7 − (−1)(4) − (−1)(−10) = 1.
Back substitution, x₃ = (1) / 1 = 1.
Back substitution, x₂ = (−10 − (−2)(1)) / −8 = 1.
Back substitution, x₁ = (4 − (1)(1) − (1)(1)) / 2 = 1.
Solution: x₁ = 1, x₂ = 1, x₃ = 1.
Check passed. A times x equals b.

Common mistakes

The first mistake is multiplying U L and expecting A. The product that rebuilds A is L U. Matrix multiplication is not commutative, which you can see on a 2 by 2 pair with the 2 by 2 matrix calculator.

The second mistake is dropping the sign of a multiplier. The multiplier is (the entry being cleared) divided by the pivot. It is negative when those two numbers have opposite signs. Subtracting a negative multiplier is the same as adding the absolute value. The steps say "plus" in that case so the arithmetic on the row is the arithmetic you would write by hand.

The third mistake is solving with the original b after a row exchange. If P moved row 1 and row 2, the right hand side has to move the same way before forward substitution. The page does that when partial pivoting is on and the solve box is checked.

The fourth mistake is forcing a factorization of a singular matrix. Rows (1, 2) and (2, 4) are dependent. After the first elimination the second pivot is zero and nothing below it can replace it. There is no inverse, and the determinant calculator would report zero for a 3 by 3 matrix in the same situation. This page reports the column and stops.

Related reading

Elimination is the engine of the linear algebra pillar. The linear algebra first course puts matrices before eigenvalues. Glossary lines for matrix, linear map, and determinant name what a zero pivot means: the linear map is not invertible, so the determinant is zero.

If the assignment is the cleared matrix rather than the factors, stay on the RREF calculator. If the assignment is an inverse of a 3 by 3 matrix by cofactors, use the 3 by 3 matrix calculator. The two answers are related, because the inverse can be built from elimination, but the pages show different steps on purpose.