Elimination is a sequence of reversible changes to equations. LU packages those changes into factors that can be reused when the right-hand side changes. Pivoting adds a complication: the order of the equations may change halfway through the calculation. The permutation must remember the complete order, while the multipliers already recorded must move with the rows they describe. We will prove existence for nonsingular square matrices in exact arithmetic, explain the bookkeeping, and establish when the factors are unique.
The factorization we want
Theorem 4.2.1
(Pivoted LU factorization)
Let be nonsingular over a field , with . Then there is a permutation matrix , a unit lower triangular matrix and an upper triangular matrix such that
Definition 4.2.2
(Unit lower triangular and permutation conventions)
“Unit” means every diagonal entry of is 1. The diagonal entries of are nonzero for a nonsingular . A permutation matrix rearranges rows when multiplied on the left. If successive row swaps are in chronological order, then : the latest operation is on the left. We use this convention consistently. Some books write with a differently defined permutation; one must check its convention rather than transpose a permutation by guesswork.
Counterexample mode
An invertible matrix without an LU factorization
Claim: every nonsingular matrix factors as with unit lower triangular and upper triangular. This is false. Nonsingularity matters to the nonzero-pivot conclusion and to the triangular solve. Singular matrices can admit factorizations of this form, but zero pivots and nonuniqueness need separate treatment. Even nonsingularity does not guarantee unpivoted elimination: is invertible but its first pivot is zero. No unit-lower and upper can multiply to this matrix without a row exchange, since the first entry of would be zero and the lower-left entry of would then be zero as well.
Why a nonzero pivot is available
Proof
(A nonzero pivot at every step)
At the beginning of step , suppose columns have been cleared below their diagonal entries and those earlier pivots are nonzero. The current matrix has block form
where is an invertible upper triangular matrix. All operations so far are invertible, so the current matrix is nonsingular. Its determinant is ; hence the trailing block is nonsingular. Its first column cannot be zero. Consequently some entry in column at or below row is nonzero, and a swap among those rows can bring it into the pivot position.
For real matrices, partial pivoting chooses an entry of largest absolute value in that column among the available rows. It is nonzero by the argument above, and the resulting multipliers have absolute value at most 1. The existence proof needs only a nonzero choice; it does not say partial pivoting eliminates every numerical difficulty. Once a pivot is chosen, subtract suitable multiples of its row from the rows below. Those operations preserve zeros in earlier columns because the pivot row has zeros there. After stages the result is upper triangular, and all pivots are nonzero. The last step is included: its trailing block is a nonzero scalar.
The invariant behind the bookkeeping
Proof
(Maintaining through swaps and eliminations)
At the start of step , maintain with already cleared below the first pivots and
The trailing identity represents rows whose current pivot-column multipliers have not yet been stored. Initially and . Suppose a permutation swaps two rows at or below . It has block form relative to the processed rows. Then
The new factor has the same unit lower-triangular form: its already stored lower-left block becomes , and its trailing identity remains an identity. Thus the rows of the previously computed columns of must be swapped, while its unprocessed diagonal ones stay in place. Merely swapping the current rows of and leaving the old multipliers untouched breaks the invariant.
Now let , where the vector is zero in positions and contains the new multipliers below them. The eliminated matrix is . Because , . Thus
The product is again unit lower triangular and stores the new multipliers in column . This proves the invariant step by step. It also explains why previous multipliers move: they belong to equations that have changed places, not to fixed row labels on the original matrix.
Proof X-ray
Why the old multipliers must move
The invariant is the whole proof: every step must leave true. The key move is writing a swap as . Conjugating by swaps the stored multipliers of the processed columns together with the rows they describe, while the trailing identity block stays an identity; updating only would break the equation. The nonzero pivot comes from nonsingularity of the trailing block , which is where the hypothesis on is used. The elimination factor is harmless because , so multiplying by it just writes the new multipliers into column . The process closes after steps because the last trailing block is a nonzero scalar.
What uniqueness actually says
Theorem 4.2.3
(Uniqueness for a fixed permutation)
For a fixed permutation matrix , if with nonsingular, unit lower triangular and upper triangular, then and .
Proof
(A unit lower triangular matrix that is also upper triangular)
For a fixed permutation , suppose , where both are unit lower triangular and both are upper triangular. Since and the are invertible, the are invertible too. Rearranging gives
The left side is unit lower triangular; the right side is upper triangular. A matrix with both shapes is diagonal, and its diagonal must be all ones. Hence it is , so and . This does not say the permutation is unique. Different valid pivot choices may lead to different , and thus to different factors. If the normalization on is removed, even a fixed allows diagonal rescaling of the factors.
The argument also explains the role of nonzero pivots. In a nonsingular factorization , so every diagonal entry of is nonzero. If is singular, the inverses in the uniqueness proof may not exist; the conclusion cannot be imported without new hypotheses.
Reading the factorization as a sequence
The equation can be read in two directions. Starting with , first reorder its rows to obtain ; then elimination turns that reordered matrix into . In the opposite direction, reconstructs the eliminated combinations, so reproduces the reordered rows. Neither nor by itself is generally a row permutation of . Their positions in the product matter.
The determinant provides a compact additional check. Since , we have , and is the product of its diagonal entries. Each swap changes the sign of , but it does not change whether is singular. This check cannot replace the matrix product: two incorrect factors can accidentally have the correct determinant. Likewise, a particular numerical pivot choice does not determine a universal permutation for every input matrix; the permutation records the operations that were actually performed.
Concept lensAlgorithmic
The factorization as a recursion on Schur complements
Write for after a swap that makes the pivot , and split . Then
Since , the Schur complement is nonsingular and the same step applies to it. The multipliers form the first column of , and is the first row of . A later swap inside permutes those stored multipliers, as the invariant requires.
Solving after a row exchange
From , the system is equivalent to . First solve by forward substitution, then solve by back substitution. The same that reorders must reorder . Since is unit lower triangular and has nonzero diagonal, both triangular solves have unique answers. If many right-hand sides are supplied, the factorization is done once and each new right-hand side is permuted and solved separately.
A check should use the original problem: verify and then compute . Checking only is helpful, but it can conceal a consistently misrecorded permutation if itself was not checked against the actual swaps. In exact arithmetic a zero residual verifies the numerical solution; in floating point the interpretation of a small residual requires further analysis.
Worked examples
Worked example 4.2.4
(A swap after multipliers have been stored)
Over , factor and solve for
Solution. Use the first entry 2 as pivot. The multipliers for rows 2 and 3 are 2 and 3. Subtracting gives rows and . The second pivot is zero, so exchange rows 2 and 3. Their stored first-column multipliers must also exchange, becoming 3 and 2. The new entry below the second pivot is zero, so the final multiplier is zero. We obtain
Indeed has rows , and , exactly . Also . Forward substitution gives . Back substitution yields , , . Finally . If the old multipliers 2 and 3 were left in their original positions, the second and third rows of would not equal those of .
The explorer below replays the elimination step by step, recomputing P, L, U and PA − LU after every operation, so you can see the invariant survive each swap only when the stored multipliers move with their rows.
Worked example 4.2.5
(A first pivot that must be exchanged)
Over , let and . Find a pivoted factorization and solve the system.
Solution. The first pivot is zero even though . Swap rows 1 and 2:
Here . The permuted right-hand side is . Since , ; back substitution gives and , so . Direct multiplication returns . A different nonsingular matrix may permit several pivot choices, but for this fixed and unit diagonal the factors are uniquely determined by the argument above.
Worked example 4.2.6
(Partial pivoting chooses the largest entry)
Let and . In the first column the entry of largest absolute value is , so swap the rows: and . The multiplier is , which has absolute value at most one, and the second row becomes . Hence , , and has rows and , so . With , forward substitution gives , and back substitution gives , then , so . Check: .
Common mistakes and subtle points
Common mistake
(Swapping rows of but not the stored multipliers)
In the first worked example, leaving the multipliers and in their original positions gives , and has rows , and . Neither of the last two rows equals the corresponding row or of .
Common mistake
(Forgetting to permute the right-hand side)
In the second worked example, solving with the unpermuted gives , then . But , not : the solver has answered the system with the equations in the wrong order.
Exercises
Quick check
(Use the factorization in the first worked example to find .)
Recall and that is a single row swap.
Solution · Answer
, and for one swap, so . Direct cofactor expansion along the first row gives .
Quick check
(For and , find , , and solve .)
The first pivot is zero, so swap the two rows.
Solution · Answer
, and . Then , so and gives . Check: .
Quick check
(Why can no unit lower triangular and upper triangular satisfy ?)
Compare the top-left entries first.
Solution · Answer
The entry of is , so . The entry is , but it must equal . This contradiction is why a row exchange is needed.