What is LU factorization and why is it useful?

LU factorization decomposes a square matrix A into the product of a lower triangular matrix L and an upper triangular matrix U, so A = LU. It is useful because solving triangular systems is fast (O(n²) per solve). Once you factor A, you can solve Ax = b for many different b vectors efficiently — each solve is two O(n²) substitutions instead of full O(n³) elimination.

What is the difference between Doolittle and Crout methods?

Both produce A = LU, but they differ in where they place the unit diagonal. Doolittle makes L unit lower triangular (all 1s on the diagonal of L), while Crout makes U unit upper triangular (all 1s on the diagonal of U). Both give the same determinant and solve Ax = b identically — the choice is largely a matter of convention.

When should I use PA=LU with partial pivoting?

Use PA=LU when the matrix may have zero or near-zero pivots, which would cause Doolittle or Crout to fail or produce large rounding errors. Partial pivoting swaps rows so the largest element in each column becomes the pivot, improving numerical stability. In practice, production code almost always uses PA=LU.

What is Cholesky decomposition and when can I use it?

Cholesky decomposition factors A = LLᵀ where L is lower triangular. It only works when A is symmetric (A = Aᵀ) and positive definite (all eigenvalues > 0). It is roughly twice as fast as Doolittle because it exploits the symmetry. Common applications include covariance matrices in statistics and stiffness matrices in engineering.

How do I compute the determinant from LU factorization?

For A = LU, det(A) = det(L) × det(U). Since L and U are triangular, their determinants are simply the product of their diagonal entries. For Doolittle, det(L) = 1 (all diagonal entries are 1), so det(A) = product of U's diagonal. For PA=LU, multiply by (−1)^s where s is the number of row swaps performed during pivoting.

How do I solve Ax = b using LU factorization?

First decompose A = LU. Then solve in two steps: (1) Forward substitution — solve Ly = b for y, working top to bottom. (2) Back substitution — solve Ux = y for x, working bottom to top. For PA=LU, apply the permutation first: solve Ly = Pb, then Ux = y. Toggle 'Solve Ax = b' in this calculator to see the solution.

Why does LU factorization fail for some matrices?

Doolittle and Crout fail when they encounter a zero pivot (a zero on the diagonal during elimination). This doesn't necessarily mean the matrix is singular — it may just need row swaps. PA=LU with partial pivoting handles this. If the matrix is truly singular (det = 0), then no method can produce a unique LU factorization.

What is the time complexity of LU factorization?

LU factorization itself is O(n³) for an n×n matrix — the same as Gaussian elimination. The advantage comes when solving multiple systems: each forward/back substitution is O(n²), so solving k systems with the same A costs O(n³ + kn²) instead of O(kn³). For large k this is significantly faster.

Can I use LU factorization for non-square matrices?

Standard LU factorization is defined for square matrices only. For non-square (rectangular) matrices, you would use QR factorization or the singular value decomposition (SVD) instead. This calculator supports square matrices of size 2×2, 3×3, and 4×4.

What are real-world applications of LU factorization?

LU factorization is used extensively in computational science: solving large linear systems in finite element analysis, circuit simulation (SPICE), computational fluid dynamics, econometric models, and machine learning (solving normal equations for linear regression). It is also used to compute matrix inverses and determinants efficiently.

LU Factorization Calculator

Matrix Size

Matrix A

Solve Ax = b

Enter vector b to find x

Doolittle Method

A = L × U

det = 2025

Non-singular

3×3

L (Lower Triangular)

Unit lower triangular — diagonal entries are all 1

0.6

-0.2

0.333333

U (Upper Triangular)

Upper triangular factor with pivot values on diagonal

-5

Step-by-Step Solution

See how the decomposition is computed

1.Initialize L as identity matrix, U as zero matrix

2.U[1][1] = A[1][1] − Σ(L[1][k]·U[k][1]) = 25

3.U[1][2] = A[1][2] − Σ(L[1][k]·U[k][2]) = 15

4.U[1][3] = A[1][3] − Σ(L[1][k]·U[k][3]) = -5

5.L[2][1] = (A[2][1] − Σ(L[2][k]·U[k][1])) / U[1][1] = 0.6

6.L[3][1] = (A[3][1] − Σ(L[3][k]·U[k][1])) / U[1][1] = -0.2

7.U[2][2] = A[2][2] − Σ(L[2][k]·U[k][2]) = 9

8.U[2][3] = A[2][3] − Σ(L[2][k]·U[k][3]) = 3

9.L[3][2] = (A[3][2] − Σ(L[3][k]·U[k][2])) / U[2][2] = 0.3333333333

10.U[3][3] = A[3][3] − Σ(L[3][k]·U[k][3]) = 9

What Is LU Factorization?

Decomposing a matrix into triangular factors

LU factorization (also called LU decomposition) writes a square matrix A as the product of a lower triangular matrix L and an upper triangular matrix U, so that A = LU. It is one of the most fundamental algorithms in numerical linear algebra.

Triangular systems are cheap to solve — forward substitution for L and back substitution for U each take O(n²) operations. By paying an O(n³) cost once to factor A, you can solve Ax = b for many different right-hand sides b in O(n²) time each.

Core Identity

A = L × U

L = lower triangular

U = upper triangular

Lower Triangular (L)

Non-zero on and below diagonal

Upper Triangular (U)

Non-zero on and above diagonal

Why LU over Gaussian Elimination? Once A is factored, solving for a new b costs O(n²) instead of O(n³). For k right-hand sides: O(n³ + kn²) vs O(kn³).

Decomposition Methods

Doolittle, Crout, Cholesky, and PA=LU compared

Doolittle

A = LU where L has 1s on diagonal

Produces a unit lower triangular L and upper triangular U. The most commonly taught method.

Crout

A = LU where U has 1s on diagonal

Produces a lower triangular L and unit upper triangular U. Reverses the Doolittle convention.

Cholesky

A = LLᵀ (symmetric positive definite)

Decomposes A into L × Lᵀ. ~2× faster than Doolittle but requires symmetric positive definite input.

PA = LU

PA = LU with row permutation P

Uses partial pivoting for numerical stability. The default in production numerical libraries.

Property	Doolittle	Crout	Cholesky	PA=LU
L diagonal	1s	Computed	Computed	Multipliers
U diagonal	Computed	1s	Lᵀ diagonal	Pivots
Requires	Non-zero pivots	Non-zero pivots	SPD matrix	Nothing
Stability	Fragile	Fragile	Guaranteed	Robust
Cost	⅔n³	⅔n³	⅓n³	⅔n³ + swaps

Worked Examples

Step-by-step calculations with color-coded values

Example 1 — 3×3 Doolittle Decomposition

3×3

matrix

L[2][1]

−2

multiplier

U[2][2]

pivot

det(A)

determinant

A = [[2, −1, −2], [−4, 6, 3], [−4, −2, 8]]

L[2][1] = −4/2 = −2, L[3][1] = −4/2 = −2

U[2][2] = 6 − (−2)(−1) = 4

det = 2 × 4 × 3 = 24

Example 2 — 2×2 with Ax = b

[[4,3],[6,3]]

input

[10, 12]

RHS

det(A)

−6

non-singular

[1, 2]

solution

Formulas & Algorithms

How each element of L and U is computed

Doolittle Method

U[i][j] = A[i][j] − Σ(k=1 to i−1) L[i][k] × U[k][j]

L[i][j] = (A[i][j] − Σ(k=1 to j−1) L[i][k] × U[k][j]) / U[j][j]

L diagonal = always 1

U[j][j] = pivot element

First compute row i of U, then column i of L.

Cholesky Method

L[j][j] = √(A[j][j] − Σ(k=1 to j−1) L[j][k]²)

L[i][j] = (A[i][j] − Σ(k=1 to j−1) L[i][k] × L[j][k]) / L[j][j]

A = symmetric positive definite

L[j][j] = diagonal pivot

Only valid for symmetric positive definite matrices. About half the computation of Doolittle.

Tips & Best Practices

When to use each method and how to avoid pitfalls

Which method should I use?

Doolittle is the standard choice for most matrices. Use PA=LU when the matrix may have zero or near-zero pivots. Use Cholesky only for symmetric positive definite matrices — it's faster but restrictive.

Solving linear systems with LU

Once you have A = LU, solve Ax = b in two steps: (1) Forward substitution to solve Ly = b, then (2) Back substitution to solve Ux = y. This is faster than Gaussian elimination when solving multiple systems with the same A.

Computing the determinant

det(A) = det(L) × det(U). Since L and U are triangular, their determinants are just the product of their diagonal entries. For PA=LU, multiply by (−1)^s where s is the number of row swaps.

When LU factorization fails

Doolittle and Crout fail when a zero pivot is encountered. Switch to PA=LU with partial pivoting to handle this. If the matrix is truly singular (det = 0), no method can produce a unique factorization.

Common Mistakes

Pitfalls to avoid when computing LU factorizations

Using Cholesky on non-symmetric matrices

Cholesky requires A = Aᵀ and all positive eigenvalues. Applying it to a general matrix silently gives wrong results. Use Doolittle or PA=LU instead.

Ignoring zero pivots

Proceeding with Doolittle or Crout when U[i][i] = 0 causes division by zero. Switch to PA=LU with partial pivoting to handle this automatically.

Confusing L and U conventions

Doolittle puts 1s on L's diagonal; Crout puts 1s on U's diagonal. Mixing conventions when comparing results leads to apparent mismatches.

Forgetting the permutation matrix

When PA=LU is used, you must apply P to b first: solve Ly = Pb, then Ux = y. Ignoring P gives the wrong solution.

Frequently Asked Questions

Common questions and detailed answers

Embed LU Factorization Calculator

Add this calculator to your website or blog for free.

Related calculators from other categories

Last updated Apr 26, 2026