--- title: "LU Factorisation, Pivoting and the Cost of a Solve" description: "Record Gaussian elimination as a product of two triangular matrices, add pivoting for stability, and count the operations each stage costs." canonical: https://lightmysky.com/learn/mathematics/lu-factorisation-pivoting-and-the-cost-of-a-solve-mt_5Gg2v3Oxrr source: https://lightmysky.com/learn/mathematics/lu-factorisation-pivoting-and-the-cost-of-a-solve-mt_5Gg2v3Oxrr.md retrieved: 2026-09-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # LU Factorisation, Pivoting and the Cost of a Solve Record Gaussian elimination as a product of two triangular matrices, add pivoting for stability, and count the operations each stage costs. Subject: Mathematics · Area: Linear Algebra · Ages 20 to 21 Page: https://lightmysky.com/learn/mathematics/lu-factorisation-pivoting-and-the-cost-of-a-solve-mt_5Gg2v3Oxrr ## Ready when they can - Factor a matrix into lower and upper triangular factors and solve by two substitutions - Explain why partial pivoting is needed even when no pivot is exactly zero - Count the operations for a factorisation and for each extra right-hand side, and say why the split matters ## Lesson: Factor once, solve many times LU factorisation records elimination as you go. Each multiplier drops into a lower triangular L and each surviving row into an upper triangular U. The product LU reproduces the original matrix. Solving then runs in two easy triangular stages. Forward substitution cracks Ly equals b, then back substitution cracks Ux equals y. Triangular systems need plain substitution only, no elimination. Zero pivots stop naive elimination cold. Tiny pivots are nearly as bad: huge multipliers amplify rounding error until the result is noise. Partial pivoting swaps in the largest available pivot at each step, which keeps multipliers small. The swaps are tracked by a permutation, giving PA equals LU. The swaps cost almost nothing beside the factorisation. **Example.** Take A with rows [2, 1] and [4, 3]. The multiplier is 4 over 2, which is 2. Subtract twice row one from row two to get [0, 1]. So L has rows [1, 0] and [2, 1], while U has rows [2, 1] and [0, 1]. Contrast A with rows [0, 1] and [1, 0]: the leading pivot is zero, so elimination breaks at step one without a swap. **Tip.** Factorisation costs about n cubed over 3 operations, paid once. Each new right hand side then needs only two triangular solves at about n squared each. With many right hand sides the factorisation pays for itself fast. So never re-eliminate from scratch for each new b. **Recap.** You store elimination as L times U, pivot to keep multipliers small, and reuse the factors so every extra solve costs only about n squared. ## Practice 17 questions on this page, each with its working shown. ## Needs first - [The Inverse of a Matrix and When It Exists](https://lightmysky.com/learn/mathematics/the-inverse-of-a-matrix-and-when-it-exists-mt_1K6lcfMQ_b) - [Gaussian Elimination and Row Echelon Form](https://lightmysky.com/learn/mathematics/gaussian-elimination-and-row-echelon-form-mt_PZBce3UvRm) ## Opens up - [Iterative Methods for Large Linear Systems](https://lightmysky.com/learn/mathematics/iterative-methods-for-large-linear-systems-mt_FKkxKYVGYJ)