Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 62 ยท Linear Systems

LU Decomposition

Factor a matrix as A = PLU, solve Ax = b with two cheap triangular solves, reuse the factors for many right-hand sides, and use scipy.linalg.lu_factor.

Gaussian elimination has a hidden by-product. While it clears the entries below each pivot, it computes numbers (the multipliers) that you normally throw away. Keep them, and you get a factorization: the matrix A becomes the product of a lower triangular matrix L and an upper triangular matrix U. That is the LU decomposition, and it is the engine behind np.linalg.solve, determinants and many other routines.

The payoff is practical. Eliminating is the expensive part of solving a system, and it depends only on A, never on b. With an LU factorization you do that work once and then solve for as many right-hand sides as you like using two very cheap triangular solves. This lesson builds L and U by hand, adds row swaps (the P in A = PLU), and shows how to reuse the factors with SciPy.

The idea: A = LU

Elimination applies row operations that make A upper triangular. Call the result U. Each operation has the form "subtract m times row j from row i", and the multiplier m is exactly the entry you would place in position (i, j) of L. L has ones on its diagonal and the multipliers below it, so

A = L @ U

Because both factors are triangular, equations with them are easy: a lower triangular system is solved from the top by forward substitution, and an upper triangular one from the bottom by back substitution.

Solving Ax = b with LU

Factor Write A = LU once.
Forward Solve Ly = b from the top.
Backward Solve Ux = y from the bottom.

Factoring costs most of the work. Each new b is cheap.

1 / 2

Building L and U by hand

Here is a small matrix where no swaps are needed. The code is plain elimination, storing each multiplier in L as it goes.

Python LU without pivoting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at L: the multipliers 2, 4 and 3 sit exactly where the eliminations happened, and U is the triangular matrix you would have reached by hand. Multiplying them back reproduces A.

Solving with the factors

Given A = LU, the system Ax = b becomes L(Ux) = b. Introduce y = Ux: first solve Ly = b for y (forward substitution), then solve Ux = y (back substitution). Each triangular solve costs only about n^2 operations, against about n^3 for the factorization.

Python Forward and back substitution

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When you need row swaps: A = PLU

Plain LU has a flaw. If a pivot is zero, the algorithm divides by zero. Even if it is merely tiny, dividing by it creates huge multipliers and wrecks accuracy. The cure is the one you already know from elimination: swap rows so that the largest available entry becomes the pivot. We record all swaps in a permutation matrix P (the identity with its rows shuffled), and the factorization becomes A = P L U.

SciPy returns exactly this from scipy.linalg.lu. One detail: its P satisfies A = P @ L @ U, so P.T @ A = L @ U.

Python scipy.linalg.lu on a matrix that needs a swap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because the largest entry in each column is chosen as pivot, every multiplier in L has absolute value at most 1. That is why partial pivoting is so stable in practice.

Different libraries describe the permutation differently: some give A = P L U, some P A = L U, and LAPACK stores a list of row swaps rather than a matrix. When mixing tools, always verify with np.allclose(A, P @ L @ U) before relying on the convention.

Reusing the factorization

Here is the main reason to care. If you must solve Ax = b for many different b (the same machine model under many loads, the same image blur applied to many images, an implicit time-stepping scheme), factor A once with lu_factor and call lu_solve for each right-hand side.

Python Factor once, solve many times

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

lu_factor returns a compact form: one array holding both L (below the diagonal, the unit diagonal is implied) and U (on and above), plus the pivot list. lu_solve accepts that pair and does only the two triangular solves.

The last lines show another benefit: det(A) = ยฑ product of the diagonal of U, with the sign decided by the number of row swaps. This is how np.linalg.det computes determinants, instead of the textbook cofactor expansion, which would take factorial time. (We compare logarithms of the absolute value because a product of 200 numbers easily overflows; see Determinants.)

What LU cannot do

LU needs a square, invertible A. If A is singular, a zero pivot appears with no row below to swap in, and the factorization stops (or yields a U with a zero on its diagonal). For symmetric positive-definite matrices there is a cheaper, more stable cousin, the Cholesky factorization A = L L^T. For rectangular or least-squares problems, use QR or the SVD.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In A = LU, what do the entries below the diagonal of L contain?

    Each row operation 'subtract m times row j from row i' puts the multiplier m into position (i, j) of L. L has ones on its diagonal.
  2. 2. Why is it useful to keep an LU factorization when you have many right-hand sides?

    Factoring costs about n^3 operations, but each forward and back substitution costs about n^2, so repeated solves are cheap.
  3. 3. What does the permutation matrix P in A = PLU record?

    P is the identity with rows rearranged. It captures the swaps made during partial pivoting, which avoid zero or tiny pivots.
  4. 4. How is the determinant obtained from the factors?

    L has a unit diagonal, so det(A) = det(P) det(U), and det(P) is plus or minus one depending on the number of swaps.

Summary

  • Elimination yields A = LU: U is the echelon form, L stores the multipliers with ones on its diagonal.
  • Solve Ax = b with forward substitution on L, then back substitution on U; both are cheap compared with factoring.
  • Row swaps (partial pivoting) give A = PLU and keep multipliers at most 1 in size, which makes the method stable.
  • scipy.linalg.lu returns P, L, U; lu_factor and lu_solve let you factor once and solve many times.
  • det(A) is the product of U's diagonal up to the sign set by the swaps; LU needs a square, invertible matrix.

Next: step into the geometry behind all of this with Linear Combinations and Span.