Skip to content
Linear Algebra, Optimisation and Numerical Methods / Solving Linear Systems and Matrix Algebra

Derivation — LU Factorisation with Partial Pivoting

This sub-note carries the algebra behind the claim, made informally in Fact 1 of the elimination note, that forward elimination is a matrix factorisation. It shows precisely how the multipliers recorded during elimination assemble into a lower-triangular matrix LL, states the factorisation A=LUA=LU (and its pivoted form PA=LUPA=LU), and works the operation-count argument for why this factorisation, not an explicitly computed A−1A^{-1}, is the production route to solving Ax=bA\mathbf{x}=\mathbf{b} repeatedly.
Learning objectives. By the end of this note you should be able to:
  • assemble the multipliers from forward elimination directly into the matrix LL;
  • state and verify the factorisation A=LUA=LU for a small matrix;
  • explain the role of the permutation matrix PP when row exchanges are needed;
  • compare the operation counts of solving via LULU versus via an explicit A−1A^{-1}.

In this lesson

  1. From elimination matrices to LL
  2. Row exchanges: PA=LUPA = LU
  3. Why LULU beats computing A−1A^{-1}

Before you start

The full lesson, with worked examples and exercise solutions, is for members.

Read the full lesson

New to SelfMadeQuant.com? See membership options or browse the Linear Algebra, Optimisation and Numerical Methods syllabus.