3.4LU decomposition
The idea
LU decomposition records elimination as a product A = LU, so a system can be solved by two easy triangular solves.
Think of it like this: A recipe split in two: first prepare the ingredients (L), then cook (U).
Why it exists
GATE asks for the entries of L and U, and for true/false statements about invertibility and symmetry.
How it works
- Eliminate to get U (upper triangular).
- Store each multiplier you used in L (below the diagonal, with 1s on the diagonal).
- Solve Ly = b by forward substitution, then Ux = y by back substitution.
- det A = product of the diagonal of U; A is singular exactly when some diagonal entry of U is 0.
Worked example: GATE 2022
For x₁ + x₂ − 2x₃ = 4, x₁ + 3x₂ − x₃ = 7, 2x₁ + x₂ − 5x₃ = 7 the multipliers are 1, 2 and −1/2, and U₃₃ = −1/2. Then y = (4, 3, 1/2) and x = (0, 2, −1).
Now play with it
- →Step through the first example and read L and U growing.
- →Load the row-swap example and see why plain LU stops.
| 1 | 1 | -2 |
| 1 | 3 | -1 |
| 2 | 1 | -5 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
- l21 = 1; R2 ← R2 − (1)·R1
- l31 = 2; R3 ← R3 − (2)·R1
- l32 = -1/2; R3 ← R3 − (-1/2)·R2
| 4 |
| 3 |
| 1/2 |
| 0 |
| 2 |
| -1 |
Check yourself
If A = LU with L having 1s on the diagonal, det A equals
Exam notes (the dense version)
If no row swaps are needed, A = LU with L lower triangular (1s on the diagonal, holding the elimination multipliers) and U upper triangular (the echelon form). To solve Ax = b: solve Ly = b by forward substitution, then Ux = y by back substitution. det A = product of the diagonal of U. A is singular exactly when some diagonal entry of U is 0. If a zero pivot appears, swap rows: PA = LU.
Previous year questions: Rank, Elimination & LU (4)
PYQs are grouped by topic, so this is the full set for Rank, Elimination & LU; try the ones that match this subtopic. Open all 4 on the topic page.