Recipe

Factor a matrix into PA = LU (with pivoting)

Use when: you have a square matrix A and ordinary elimination toward A=LU hits a zero (or, for numerical work, an uncomfortably small) pivot

Goal: a permutation P, unit lower-triangular L, and upper-triangular U with PA=LU

Taught in Permutation matrices, PA = LU, and pivoting · extends Factor a matrix into L and U

1. 1

   Before eliminating a column, check whether the current pivot entry is zero. If it is, look further down that same column for a row with a nonzero entry.

   Example

   A = \begin{pmatrix}0 & 2 & 3\\4 & 1 & -1\\2 & 5 & 6\end{pmatrix} has 0 sitting in the row-1, column-1 pivot spot. Row 2 has a nonzero entry (4) in that column, so row 2 is the swap target.

   Why: the multiplier m=\frac{U_{ik}}{U_{kk}} divides by the pivot, so a zero pivot must be replaced before any division happens, not discovered partway through one.

2. 2

   Start from I, not from A, and perform the exact same row swap on I that column 1 needs.

   Example

   I_3 = \begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix} \xrightarrow{R_1 \leftrightarrow R_2} P = \begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}

   Why: left-multiplying by a permutation matrix reorders rows exactly the way its own rows were reordered from I — building P from I is what makes that guarantee exact, rather than building it by trial and error on A itself.

3. 3

   Multiply P into A; the result is A with its rows reordered to match the swap.

   Example

   PA = \begin{pmatrix}4&1&-1\\0&2&3\\2&5&6\end{pmatrix} — row 1 now holds a nonzero pivot.

   Why: PA now has a usable pivot in every column position elimination will need, so the reordering happens once, up front, instead of interrupting elimination mid-computation.

4. 4

   With PA now pivot-safe, continue with exactly the no-swap elimination procedure from "Factor a matrix into L and U," Steps 2 onward, building L and U from PA.

   Example

   Eliminating PA: pivot 4 in column 1 clears row 3 with multiplier m_{31}=\frac12; pivot 2 in column 2 clears row 3's remainder with m_{32}=\frac94, giving U=\begin{pmatrix}4&1&-1\\0&2&3\\0&0&-\tfrac14\end{pmatrix}, \qquad L=\begin{pmatrix}1&0&0\\0&1&0\\\tfrac12&\tfrac94&1\end{pmatrix}

   • no further zero pivots appear — continue straight through to Step 5.
   • another zero pivot turns up further down — return to Step 1 for that column; a second swap folds into the same P (apply it to P the same way, not to a fresh identity).

   Why: PA satisfies exactly the no-swap assumption the original recipe's steps depend on, so nothing about that procedure needs to change once P is fixed first.

5. 5

   Multiply L and U back out and confirm the product reproduces PA exactly, row by row.

   Example

   Row 3: \tfrac12(4)+\tfrac94(0)+1(0)=2, \tfrac12(1)+\tfrac94(2)+1(0)=5, \tfrac12(-1)+\tfrac94(3)+1(-\tfrac14)=6 — matching PA's row 3 exactly.

   Why: this is the same closing-the-loop check ordinary LU uses — it catches an arithmetic slip in either the swap-detection stage or the elimination that followed, before the factorization is trusted for solving Ax=b.