Every time you row reduce a matrix, you do the same arithmetic on its left side, whatever the right side happens to be. A computer solving a thousand systems with the same coefficients would be foolish to redo that work a thousand times. This page shows how to save it: elimination writes $A$ as a product $LU$ of two triangular matrices, and once you have them, each new right-hand side costs two quick passes instead of a whole reduction. It's how almost every numerical library actually solves $Ax = b$.
Row reducing a matrix means doing a string of moves to it, one row operation at a time. This page keeps the receipt. The moves that clear the bottom-left corner fit into one lower triangular matrix $L$, and what's left over is an upper triangular matrix $U$, so $A = LU$. In pictures: $U$ is a box that only leans back, and $L$ slides it into the shape of $A$. Once you have the two pieces, solving $Ax = b$ for any $b$ is two easy passes, each one adding a single new unknown at a time.
The practice is mixed into the lesson: each question sits right after the idea it needs, and the Mixed Practice at the bottom takes that hint away.
Doing a row operation to $A$ is the same as multiplying $A$ on the left by its elementary matrix, the operation done to $I$. So a whole row reduction is a product: $E_k \cdots E_2E_1A$.
Look at what the forward phase of Gaussian elimination usually needs: no swaps, no scaling, only "subtract a multiple of a higher row from a lower row". Each of those elementary matrices has $1$s on the diagonal and one number below it, so each one is lower triangular. Here's a forward phase from start to finish.
Run the forward phase on $A = \begin{pmatrix} 2 & -1 & -1 \\ 2 & 1 & 0 \\ 6 & 1 & 1 \end{pmatrix}$, and keep track of every multiplier.
Clear column 1 with $R_2 \to R_2 - R_1$ and $R_3 \to R_3 - 3R_1$, then column 2 with $R_3 \to R_3 - 2R_2$: $$\begin{pmatrix} 2 & -1 & -1 \\ 2 & 1 & 0 \\ 6 & 1 & 1 \end{pmatrix} \to \begin{pmatrix} 2 & -1 & -1 \\ 0 & 2 & 1 \\ 0 & 4 & 4 \end{pmatrix} \to \begin{pmatrix} 2 & -1 & -1 \\ 0 & 2 & 1 \\ 0 & 0 & 2 \end{pmatrix} = U.$$ The multipliers were $1$ (row 2, column 1), $3$ (row 3, column 1), and $2$ (row 3, column 2). Put each one in its spot below the diagonal of an identity matrix: $$L = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 3 & 2 & 1 \end{pmatrix}.$$ Multiply it out: $LU = A$. Row 3 of $LU$, for instance, is $3(2, -1, -1) + 2(0, 2, 1) + (0, 0, 2) = (6, 1, 1)$.
In space: $U$'s columns make a box that only leans back (each column has nothing below its diagonal entry), and $L$ slides that box into $A$'s box:
Two definitions name what just happened.
A square matrix is unit lower triangular if it is lower triangular and every entry on its diagonal is $1$.
Every $L$ elimination builds is one of those, and the factorization gets the name.
An LU factorization of a square matrix $A$ is a way of writing $A = LU$, where $L$ is unit lower triangular and $U$ is upper triangular.
Here's the bookkeeping from the first example in motion: each entry below a pivot gets cleared, and its multiplier drops into the same spot of $L$.
The example's $L$ and $U$ weren't lucky guesses. Whenever elimination runs without swaps, it hands you both.
Suppose the forward phase of Gaussian elimination takes a square matrix $A$ to an echelon form $U$, working column by column and using only operations $R_i \to R_i - \ell_{ij}R_j$ with $j < i$ (no swaps, no scaling). Let $L$ be the unit lower triangular matrix with $\ell_{ij}$ in spot $(i, j)$ (and $0$ wherever no operation was needed). Then $A = LU$.
Write $e_i$ for column $i$ of $I$. The operation $R_i \to R_i - \ell_{ij}R_j$ has elementary matrix $E = I - \ell_{ij}e_ie_j^t$, and its inverse is $I + \ell_{ij}e_ie_j^t$ (add the multiple back). If the operations are $E_1, \ldots, E_k$ in order, then $E_k \cdots E_1A = U$, so $A = E_1^{-1} \cdots E_k^{-1}U$.
Multiply out $E_1^{-1}E_2^{-1} \cdots E_k^{-1}$. Each factor is $I$ plus one term $\ell e_ie_j^t$, so the product is $I$, plus every single term, plus products of two or more terms. A product of two terms, taken left to right as $\ell e_ie_j^t$ then $\ell' e_pe_q^t$, is $\ell\ell' e_i(e_j^t e_p)e_q^t$, and $e_j^te_p$ is $0$ unless $j = p$. But the operations go column by column, so the later factor has column $q \ge j$, and its row is $p > q \ge j$. So $p \ne j$, every cross term vanishes, and the product is exactly $I + \sum \ell_{ij}e_ie_j^t$, which is $L$. $\blacksquare$
This is a visual argument, not a formal proof. Watch each row of $A$ as it's eliminated. Row $i$ only ever gets multiples of finished rows subtracted from it: by the time row 2 is used to clear row 3, row 2 is already its final $U$ row. So undo it: add those multiples back, and row $i$ of $A$ is row $i$ of $U$ plus $\ell_{i1}$ times row 1 of $U$, plus $\ell_{i2}$ times row 2 of $U$, and so on. Those weights are exactly row $i$ of $L$, and that's what $LU$ computes, one row at a time. Here's the example:
The column-by-column order is what makes every row it borrows from already finished. The full proof is in the n version.
In practice that means no extra work at all.
You get $L$ for free: write each multiplier down the moment you use it. The step is $R_i \to R_i - \ell R_j$, and $\ell$ goes into $L$ with exactly that sign, because $L$ undoes the step by adding $\ell$ of row $j$ back. Storing $-\ell$ is the classic slip. And $L$'s diagonal is all $1$s; the pivots live on $U$'s diagonal.
A matrix doesn't have to be invertible to have an LU factorization. Elimination can end with a row of zeros, and that's fine.
Factor $A = \begin{pmatrix} 1 & 0 & 1 \\ 2 & 1 & 3 \\ 1 & -1 & 0 \end{pmatrix}$, the rank-2 matrix from Rank & Inverses.
$R_2 \to R_2 - 2R_1$ and $R_3 \to R_3 - R_1$ give rows $(0, 1, 1)$ and $(0, -1, -1)$. Then $R_3 \to R_3 - (-1)R_2$, that is, $R_3 \to R_3 + R_2$, clears row 3 completely. So the multipliers are $2$, $1$, and $-1$: $$A = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & -1 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{pmatrix}.$$ The zero row of $U$ is the rank showing up: two pivots, rank 2.
$U$'s box is squashed flat (its columns lie in the floor), and $L$ slides that flat sheet into the tilted sheet $A$'s columns fill. A flat box stays flat:
Now find the multipliers yourself. Pick each one, and watch it clear its entry and drop into $L$.
Your turn: a factorization, start to finish.
Loading practice engine...
Here's the payoff. A system whose matrix is triangular is easy: one equation has a single unknown, the next adds one more, and so on, so you solve them in a row without any elimination. $A = LU$ splits one hard system into two easy ones.
Suppose $A = LU$. Then $x$ solves $Ax = b$ exactly when $y = Ux$ solves $Ly = b$. So to solve $Ax = b$, solve $Ly = b$ from the top down (forward substitution), then $Ux = y$ from the bottom up (back substitution).
$Ax = (LU)x = L(Ux)$, so $Ax = b$ says exactly that $y = Ux$ satisfies $Ly = b$. Since $L$ is unit lower triangular, $Ly = b$ has exactly one solution, found row by row: $y_i = b_i - \sum_{j < i} \ell_{ij}y_j$. The solutions of $Ax = b$ are then exactly the solutions of $Ux = y$ for that one $y$. $\blacksquare$
This is a visual argument, not a formal proof. $LU$ means "move with $U$, then with $L$". Solving runs the moves backward, so the last move comes off first: undo $L$ to get from $b$ back to $y$, then undo $U$ to get from $y$ back to $x$. Here it is in the plane with $A = \begin{pmatrix} 2 & 1 \\ 6 & 4 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 3 & 1 \end{pmatrix}\begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}$:
Each undo is one triangular system, which you solve one unknown at a time. The full proof is in the n version.
Here are the two passes on the first example.
With $A = LU$ from the first example, solve $Ax = b$ for $b = (1, 1, 7)$.
Forward pass, $Ly = b$, top down: $$\begin{aligned} y_1 &= 1, \\ y_1 + y_2 &= 1 \implies y_2 = 0, \\ 3y_1 + 2y_2 + y_3 &= 7 \implies y_3 = 7 - 3 - 0 = 4. \end{aligned}$$ Back pass, $Ux = y$, bottom up: $$\begin{aligned} 2x_3 &= 4 \implies x_3 = 2, \\ 2x_2 + x_3 &= 0 \implies x_2 = -1, \\ 2x_1 - x_2 - x_3 &= 1 \implies x_1 = 1. \end{aligned}$$ So $x = (1, -1, 2)$. Check one row of $A$: $6 - 1 + 2 = 7$.
Each equation is a plane, and a triangular system adds one new unknown at a time. In the forward pass the first equation is a wall that pins $y_1$, the second plane cuts the wall in a line, and the third cuts that line in a point. The back pass does the same from the bottom up:
Two passes, and no elimination anywhere. The only way to go wrong is the order.
Order matters: $L$ first, then $U$, because $Ax = L(Ux)$ and the outside matrix comes off first. Solving $Ux = b$ first, or stopping at $y$ and calling it the answer, are the two ways to get a confident wrong vector.
Your turn: two passes.
Loading practice engine...
Elimination without swaps breaks down the moment a $0$ lands in a pivot spot with something nonzero below it. The fix is to swap rows, and the clean way to record swaps is one more matrix.
A permutation matrix is the identity matrix with its rows put in some new order. If $P$ is $I$ with its rows reordered, then $PA$ is $A$ with its rows reordered the same way.
Here is one in action, on a system whose first pivot spot is empty.
Solve $3z = 9$, $x + 5y - 2z = 2$, $x + 6y = 9$ with a factorization.
The coefficient matrix $A = \begin{pmatrix} 0 & 0 & 3 \\ 1 & 5 & -2 \\ 1 & 6 & 0 \end{pmatrix}$ has a $0$ in its first pivot spot, so there is no $A = LU$. Swap rows 1 and 3 first, with $P = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}$: $$PA = \begin{pmatrix} 1 & 6 & 0 \\ 1 & 5 & -2 \\ 0 & 0 & 3 \end{pmatrix}.$$ Now one operation, $R_2 \to R_2 - R_1$, finishes the forward phase: $$PA = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 6 & 0 \\ 0 & -1 & -2 \\ 0 & 0 & 3 \end{pmatrix} = LU.$$ The system $Ax = b$ is the same as $PAx = Pb$, with $Pb = (9, 2, 9)$. Forward pass: $y = (9, -7, 9)$. Back pass: $3z = 9$ gives $z = 3$, $-y - 6 = -7$ gives $y = 1$, and $x + 6 = 9$ gives $x = 3$. So $(x, y, z) = (3, 1, 3)$.
A swap only reorders the equations, so the three planes never move; they just trade labels. Then the one row operation swings one plane around the line it shares with another, and the meeting point $(3, 1, 3)$ stays put:
One permutation, chosen up front, is always enough.
For every square matrix $A$ there is a permutation matrix $P$ such that $PA = LU$, with $L$ unit lower triangular and $U$ upper triangular.
Induction on the size $n$. For $n = 1$, take $P = L = (1)$ and $U = A$. For $n > 1$, if column 1 of $A$ has a nonzero entry, let $P_1$ swap a row with one into the top; otherwise let $P_1 = I$. Then clearing column 1 gives, in block form, $$P_1A = \begin{pmatrix} 1 & 0 \\ m & I \end{pmatrix}\begin{pmatrix} a & r \\ 0 & A' \end{pmatrix},$$ where $a$ is the top-left entry, $r$ the rest of the top row, $m$ the column of multipliers ($m = 0$ when column 1 was all zeros), and $A'$ is $(n - 1) \times (n - 1)$. By induction, $P'A' = L'U'$. Let $P = \begin{pmatrix} 1 & 0 \\ 0 & P' \end{pmatrix}P_1$. Then $$PA = \begin{pmatrix} 1 & 0 \\ P'm & P' \end{pmatrix}\begin{pmatrix} a & r \\ 0 & A' \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ P'm & I \end{pmatrix}\begin{pmatrix} a & r \\ 0 & P'A' \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ P'm & L' \end{pmatrix}\begin{pmatrix} a & r \\ 0 & U' \end{pmatrix},$$ which is unit lower triangular times upper triangular. (The multipliers in $m$ get reordered by $P'$: they travel with their rows.) $\blacksquare$
This is a visual argument, not a formal proof. Think of each row as a card that carries its multiplier with it. Elimination might discover halfway through that it needs a swap. But a swap only reorders cards, so you could have made the same swap at the very start, and every card would get the same multiplier in the end. Here are both routes on $\begin{pmatrix} 1 & 1 & 1 \\ 2 & 2 & 3 \\ 3 & 4 & 5 \end{pmatrix}$, which hits a $0$ in the second pivot spot:
Both routes end at the same $L$ and $U$. Doing every swap first is the $P$ in $PA = LU$. The full proof is in the n version.
Two small facts make permutation matrices easy to live with.
Undoing a permutation is easy: $P^{-1} = P^t$, since the rows of $P$ are the rows of $I$ in a new order. For a single swap that's $P$ itself, but not for a reorder of three rows. And when $A$ is invertible, its $L$ and $U$ (with $1$s on $L$'s diagonal) are the only ones, so it doesn't matter how you find them.
Your turn: find the row order that lets elimination run clean.
Loading practice engine...
There's a test for whether $A = LU$ works with no swaps at all: every top-left corner of $A$ (the $1 \times 1$, the $2 \times 2$, and so on) has to be invertible. "Invertible" for each corner is a single number, its determinant.
Why do computers bother with $L$ and $U$ instead of computing $A^{-1}$? Count the arithmetic. For an $n \times n$ matrix:
| $n$ | factor once ($\approx n^3/3$) | each $b$ ($\approx n^2$) | invert ($\approx n^3$) |
|---|---|---|---|
| $10$ | $333$ | $100$ | $1{,}000$ |
| $1{,}000$ | $333$ million | $1$ million | $1$ billion |
The factoring is a pyramid of work, and each solve is a single flat triangle on top of it:
The stools-and-benches workshop on Rank & Inverses solved the same $A$ every week with a new $b$. An inverse did the job there, but $LU$ does it with a third of the work, and in floating-point arithmetic it's also more accurate.
Here's "factor once, solve many times" with the first example's $L$ and $U$.
With $A = LU$ from the first example, solve $Ax = b$ for $b = (0, 3, 8)$ and for $b = (0, 1, 0)$.
For $b = (0, 3, 8)$: forward, $y = (0, 3 - 0, 8 - 0 - 6) = (0, 3, 2)$; back, $x_3 = 1$, $x_2 = \frac{3 - 1}{2} = 1$, $x_1 = \frac{0 + 1 + 1}{2} = 1$. So $x = (1, 1, 1)$.
For $b = (0, 1, 0)$: forward, $y = (0, 1, 0 - 0 - 2) = (0, 1, -2)$; back, $x_3 = -1$, $x_2 = \frac{1 + 1}{2} = 1$, $x_1 = \frac{0 + 1 - 1}{2} = 0$. So $x = (0, 1, -1)$.
No elimination either time: just two triangles of arithmetic.
Swaps come back later for a different reason. Even when a pivot isn't $0$, a tiny pivot multiplies rounding errors, so real software swaps the biggest available entry into each pivot spot ("partial pivoting"). That's on Conditioning & Accuracy, coming up in Applications & Computation.
The toolkit for this page: elimination without swaps writes $A = LU$, with the multipliers in $L$ and the echelon form in $U$. Solve $Ax = b$ in two passes, $Ly = b$ then $Ux = y$. When a zero pivot forces a swap, do the swaps first: $PA = LU$.
Every question so far came right after its idea, which is a hint a quiz never gives you. Down here the hint is gone. First, true or false: a claim from anywhere on this page, and you decide whether it holds.
Loading practice engine...
Next, a mixed set: every question type on this page, shuffled. Type a matrix row by row, with commas between entries and a semicolon between rows, like 1, 0, 0; 1, 1, 0; 3, 2, 1, and a vector on one line, like 1, -1, 2.
Loading practice engine...
Made it this far? Time for something with a little heat. Column $j$ of $A^{-1}$ is the vector $x$ with $Ax = e_j$, since $A$ times it has to be column $j$ of $I$. So with $L$ and $U$ in hand, a column of the inverse is just two passes, and you never have to build $A$ at all.
Loading practice engine...