M3-T3 — LU Decomposition

Learning objectives

After this lesson, you should be able to:

• Factor a square matrix as A = LU by recording the elimination multipliers.
• Solve A x = b by forward substitution on L followed by back substitution on U.
• Explain why LU pays off for many right-hand sides, and what changes with pivoting (PA = LU).
• Use LU for the determinant and recognise when a symmetric positive definite matrix should use Cholesky instead.

Introduction and motivation

Elimination costs about n³/3 operations, but applying its result to a new right-hand side costs only about n². For a 1,000-unknown system that is a factor of several hundred. Robots exploit this everywhere: a Kalman filter reuses the same gain computation structure, a controller with a fixed model solves repeatedly with changing measurements, and an optimiser reuses a factorisation across several right-hand sides.

The intuition

Think of elimination as two products of work. First, a record of what you did: the multipliers. Second, what is left: the upper triangular matrix. If you save both, you never have to eliminate again. The multipliers form a lower triangular matrix L (with ones on the diagonal), the result of elimination is the upper triangular matrix U, and together they reproduce the original: A = LU.

Solving then splits into two easy triangular problems. L y = b is solved from the top (forward substitution), and U x = y from the bottom (back substitution). Neither needs any elimination.

Geometric and physical interpretation

Geometric view. The factorisation says the transformation A can be carried out as U followed by L: first a transformation that keeps one coordinate direction in each step (U, upper triangular), then a lower-triangular shearing (L) that mixes earlier coordinates into later ones. Both are cheap to undo because triangular systems are solved one coordinate at a time. Physical view. L records how much of each earlier constraint was subtracted from each later one, the bookkeeping of “which requirement was folded into which”. U records what is left to solve.

The mathematics

L

a lower triangular matrix with ones on the diagonal; below the diagonal it holds the multipliers ℓ_ij.

U

an upper triangular matrix: the result of forward elimination.

P

a permutation matrix recording the row swaps of partial pivoting.

y

the intermediate vector in Ly = b.

The factorisation

A = L U           with pivoting:   P A = L U

What it means. A square matrix (when elimination does not meet a zero pivot) equals a lower triangular times an upper triangular matrix. With row swaps for pivoting, the permuted matrix PA has this form.

Solving with the factors

A x = b   ⇒   L (U x) = b   ⇒   solve  L y = b  (forward),  then  U x = y  (backward)

What it means. Introducing y = Ux splits one hard problem into two triangular ones, each solved one unknown at a time without further elimination.

cost of factoring ≈ n³/3          cost of each additional solve ≈ n²          det A = ± Π uii

What it means. Factoring is the expensive step and is done once. The determinant is the product of the diagonal of U, with a sign for each row swap.

Factor once (A = LU), then solve many right-hand sides cheaply with forward and back substitution.

Step-by-step derivation: why the multipliers drop straight into L

Each elimination step is multiplication by an elementary matrix. For a 3 × 3 matrix with multipliers ℓ₂₁, ℓ₃₁, ℓ₃₂:

1. Step 1 subtracts ℓ₂₁ R1 from row 2 and ℓ₃₁ R1 from row 3: E₁ = [[1, 0, 0], [−ℓ₂₁, 1, 0], [−ℓ₃₁, 0, 1]].
2. Step 2 subtracts ℓ₃₂ R2 from row 3: E₂ = [[1, 0, 0], [0, 1, 0], [0, −ℓ₃₂, 1]].
3. After both steps, E₂E₁A = U. Multiply on the left by the inverses: A = E₁⁻¹E₂⁻¹ U.
4. Each inverse just adds back what was subtracted: E₁⁻¹ = [[1, 0, 0], [ℓ₂₁, 1, 0], [ℓ₃₁, 0, 1]] and E₂⁻¹ = [[1, 0, 0], [0, 1, 0], [0, ℓ₃₂, 1]].
5. Multiply them: L = E₁⁻¹E₂⁻¹ = [[1, 0, 0], [ℓ₂₁, 1, 0], [ℓ₃₁, ℓ₃₂, 1]]. The multipliers appear in L unchanged, with no interaction terms, because of the order in which the matrices are multiplied (this is the lucky fact that makes LU practical).

So A = LU with L collecting the multipliers. For the matrix of the figure the multipliers were ℓ₂₁ = 0, ℓ₃₁ = 2, ℓ₃₂ = 1.5.

Operation counts. Eliminating column k touches about (n − k)² entries; summing over k gives about n³/3. A triangular solve touches each entry of the triangle once, about n²/2 operations, so two of them cost about n².

Determinant. det A = det L · det U = 1 · Π uᵢᵢ, since the determinant of a triangular matrix is the product of its diagonal. With row swaps, each swap multiplies the determinant by −1.

A worked example: factor, solve and re-solve

Use the matrix of the elimination lesson, A = [[1, 1, 1], [0, 2, 5], [2, 5, −1]].

1. Factor. The multipliers were 0, 2 and 1.5, so L = [[1, 0, 0], [0, 1, 0], [2, 1.5, 1]] and U = [[1, 1, 1], [0, 2, 5], [0, 0, −10.5]]. Check the entry (3, 3): 2·1 + 1.5·5 + 1·(−10.5) = −1. ✓ (and so on for the other entries.)
2. First right-hand side b = (6, −4, 27). Forward: y₁ = 6, y₂ = −4, y₃ = 27 − 2·6 − 1.5·(−4) = 21. Backward: z = 21/(−10.5) = −2, y = (−4 − 5(−2))/2 = 3, x = 6 − 3 − (−2) = 5. So (5, 3, −2).
3. Second right-hand side b = (1, 0, 0), with no new elimination. Forward: y = (1, 0, −2). Backward: z = −2/(−10.5) = 0.1905, y = (0 − 5·0.1905)/2 = −0.4762, x = 1 + 0.4762 − 0.1905 = 1.2857.
4. Determinant. det A = 1 · 2 · (−10.5) = −21.
5. Pivoting. For [[10⁻²⁰, 1], [1, 1]] the solver swaps the two rows first (so P is the swap matrix) and then factors, keeping every multiplier at most 1.

Robotics application

Repeated solves. In a real-time controller with a fixed linearised model, the matrix is factored once at start-up and each control cycle only needs the two triangular solves.

Filters and estimators. A Kalman filter update solves a system with the innovation covariance matrix; for a fixed sensor set the structure is reused, and the covariance matrices are symmetric positive definite, for which the Cholesky factorisation A = L Lᵀ (about half the cost and always stable without pivoting) is the right tool. The UAV error-state Kalman filter lesson contains such a solve.

Large sparse systems. SLAM back ends such as pose-graph optimisation factor a huge, very sparse matrix with a sparse LU or Cholesky factorisation, choosing the elimination order to keep L and U sparse. Understanding L and U makes the “fill-in” discussion in the pose graph lesson readable.

Determinants from factors. A log-determinant (the sum of logs of the diagonal of U or of a Cholesky factor) is how Gaussian likelihoods are evaluated without overflow.

Engineering implications and limitations

Practical rules

• Never invert to solve. Factor the matrix and solve with the factors. It is cheaper and more accurate than computing A⁻¹.
• Always use pivoting. Library routines return the permutation along with L and U (PA = LU); store all three. A factorisation without pivoting can fail on a perfectly good matrix.
• Match the factorisation to the structure. Symmetric positive definite: Cholesky. Banded or sparse: sparse LU. Rectangular: QR (Module 5).
• Factor once, solve many. Cache the factors for as long as the matrix is unchanged, and refactor only when it changes.
• Check the pivots. A tiny diagonal entry in U (relative to the matrix scale) means a nearly singular matrix; do not trust the solution without checking conditioning.

Limits

LU applies to square systems. If elimination hits a column with no usable pivot, the matrix is singular and the factorisation (or the solve) must report it. For singular or rectangular problems use QR or the SVD.

Common misconceptions

Engineering takeaways

1. Elimination written down is A = LU: L stores the multipliers, U is the eliminated matrix.
2. Solve A x = b by L y = b (forward substitution), then U x = y (back substitution).
3. Factoring costs about n³/3, each extra solve about n²: factor once and reuse.
4. With pivoting the factorisation is PA = LU; the determinant is ± the product of the diagonal of U.
5. For symmetric positive definite matrices (covariances) use Cholesky A = LLᵀ.

References and further reading

Primary papers and authoritative documentation.

• MIT 18.06SC Linear Algebra (OCW): lecture on factorisation A = LU
• Michigan ROB 101: Computational Linear Algebra: LU factorisation in a computational setting
• Boyd and Vandenberghe, Introduction to Applied Linear Algebra (VMLS): the chapter on matrix inverses and solving with factorisations; the site did not load when we last checked
• Mathematics for Machine Learning: the chapter on matrix decompositions (Cholesky, LU)

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Elimination also reveals how many of the equations are genuinely independent. That count, the rank, is the single most useful number describing a linear system, and the subject of the next lesson.

Related content

Nothing below is required to finish this lesson.

• Before
  M3-T2: Gaussian Elimination and Row Reduction

  Solve a system by elimination with pivoting and read the outcome from the reduced form.