Pivoted factors and repeated solves

Try

Solve a system whose coefficient rows are (0,2,1), (1,1,0), (2,0,1). The first displayed diagonal entry is zero, but the matrix is not singular. We can exchange equations. For this lesson arithmetic is exact over the rationals; a zero means exactly zero, not a value below a numerical tolerance.

Partial pivoting chooses the active entry with largest absolute value in the current column. The first choice is 2 in original row 3. Exchange rows 1 and 3. The working rows become (2,0,1), (1,1,0), (0,2,1). Subtract half the first row from the second; the third needs multiplier zero. The active lower-right rows are now (0,1,−1/2) and (0,2,1).

Predict the next exchange. The second-column maximum is 2, so rows 2 and 3 exchange. The previously stored multipliers 1/2 and 0 must move with them. Then eliminate the remaining second-column entry using multiplier 1/2. The final row is (0,0,−1).

Multiply the second and third rows of L by U. They reconstruct original rows 1 and 2 respectively. Thus PA=LU, where P reorders rows into (3,1,2). Two exchanges make det P=1. The upper-triangular determinant is 2·2·(−1)=−4, so det A=−4.

Predict

Why not leave the first-column multipliers where they were? The incorrect L would have rows (1,0,0), (1/2,1,0), (0,1/2,1). Its second row times U is (1,2,3/2), whereas the second row of PA should be (0,2,1). The failure can be detected before solving any particular right-hand side. A factor record is a claim about the entire matrix, not just one successful output.

Now let b=(7,3,5). Predict which right-hand side belongs beside LU. Because the original equation is Ax=b, multiplying both sides by P gives LUx=Pb=(5,7,3). Forgetting the permutation would solve a different equation.

First solve Ly=Pb from top to bottom. The values are y₁=5, y₂=7, y₃=3−5/2−7/2=−3. Then solve Ux=y from bottom to top: x₃=3, x₂=(7−3)/2=2, x₁=(5−3)/2=1. Substitution into the original matrix gives (7,3,5), as required.

Experiment

Use the explorer to inspect the row exchanges, multipliers and the identity PA=LU. Before checking the displayed solve, write the permuted right-hand side and predict the order of the two triangular substitutions. Use the Factorization step selector to inspect the record; the solve below it always uses the completed factors. Toggle Apply P to b before the triangular solves to test the deliberate omission, then restore it. The following fixed worked calculations use the matrix above; changing a playground setting is a separate calculation, not a change to this written example.

Keep the factors; change the right-hand side

The fixed matrix A has rows (0, 2, 1), (1, 1, 0), (2, 0, 1). Predict which earlier multiplier moves when the second row exchange occurs. Then inspect each exact step.

Factorization step1. Start with P = I, L = I and U = A.2. Swap current rows 1 and 3; no earlier L columns exist.3. Row 2 ← row 2 − (1/2) row 1; store the multiplier in L.4. Swap current rows 2 and 3; also swap their entries in the first 1 column of L.5. Row 3 ← row 3 − (1/2) row 2; store the multiplier in L. Right-hand side b(7, 3, 5)(2, 0, -2)(0, 1, 2) Reset explorer

Start with P = I, L = I and U = A.

P currently puts original rows in order 1, 2, 3. Each tuple below is one matrix row.

L

(1, 0, 0)

(0, 1, 0)

(0, 0, 1)

U

(0, 2, 1)

(1, 1, 0)

(2, 0, 1)

PA

(0, 2, 1)

(1, 1, 0)

(2, 0, 1)

LU

(0, 2, 1)

(1, 1, 0)

(2, 0, 1)

Compare PA with LU at every step. The second exchange moves the stored 1/2 from row 2 to row 3 of L; it does not exchange L's diagonal ones.

Use the completed factors

This solve always uses the final factors, even while the step selector displays an earlier stage. The final row order is 3, 1, 2. Changing b leaves those factors unchanged.

Apply P to b before the triangular solves

Predict the residual if you omit P. Uncheck the box to test that deliberate mistake.

Original b

(7, 3, 5)

Correct Pb

(5, 7, 3)

Right-hand side actually used for Ly

(5, 7, 3)

Forward solve y

(5, 7, -3)

Backward solve x

(1, 2, 3)

Original-equation residual Ax − b

(0, 0, 0)

Verified: Ax = b exactly. Verification uses the original A and b, not the rearranged system.

Explain why factor reuse works for each new b and why changing A would need a new factorization. These temporary controls do not record completion.

For a second paper solve, keep A fixed and set b=(2,0,−2). Reuse exactly the same P,L,U. Obtain Pb=(−2,2,0), then y=(−2,2,0). Back substitution gives x=(−1,1,0). Verify all three original equations. The expensive matrix work has been reused, but neither the new permuted right-hand side nor the new substitution arithmetic may be skipped.

Understand

Here is the invariant behind the record. After k completed columns, write PA=LₖUₖ in block form. The leading k×k block of Lₖ is unit lower triangular, its upper-right block is zero, its lower-left block M stores completed multipliers, and its lower-right block is the identity. The leading block of Uₖ is upper triangular, its lower-left block is zero, and its active lower-right block S is still being eliminated.

Exchange two active rows with Q=diag(I,Q₂). Update P to QP and Uₖ to QUₖ. To preserve the product, update Lₖ to QLₖQᵀ, because

(QLₖQᵀ)(QUₖ)=Q Lₖ Uₖ=QPA.

The new lower-left block is Q₂M, while the lower-right block remains the identity. Therefore exchange only the two active rows’ first k stored columns of L. Exchanging complete rows without the matching column action would scramble its identity block; ignoring M would lose the already accumulated elimination history. This proves the late-swap rule for arbitrary dimensions.

For the next elimination, let E subtract the appropriate multiples of the pivot row from the rows below it. Replace U by EU and L by LE⁻¹. The product is unchanged. At this stage the active lower-right block of L is the identity and its upper-right block is zero. For the multiplier vector m supported strictly below the pivot, this gives Lm=m. Since E⁻¹=I+m eₖᵀ, the update LE⁻¹=L+m eₖᵀ inserts precisely the new multipliers in column k below the diagonal and leaves the completed columns intact. Starting from P=L=I and U=A, induction proves PA=LU after every exchange and elimination. For a nonsingular square matrix the active pivot column cannot be entirely zero: with the completed upper block that would force rank below n. A nonzero active pivot exists, and elimination continues. Singular systems require separate consistency and free-variable analysis; this lesson’s unique-solve claims assume nonsingularity.

Once U has a nonzero diagonal, forward substitution in unit L uniquely determines y. Back substitution in U uniquely determines x because every needed division is by a nonzero diagonal entry. The product identity gives Ax=b, and another solution would have to follow the same uniquely determined substitution steps. This proves both existence and uniqueness for every right-hand side. Forming A⁻¹ is unnecessary.

For dense n×n arithmetic, pivot k leaves n−k multipliers and (n−k)² trailing entries to update. Summing gives n(n−1)/2 multiplier divisions and (n−1)n(2n−1)/6 trailing updates. Each ordinary update uses one multiplication and one subtraction. Forward substitution uses n(n−1)/2 such product/subtraction pairs, and backward substitution uses another n(n−1)/2 plus n divisions. Thus factoring once and solving r right-hand sides has arithmetic work of order n³+rn², rather than repeatedly paying the cubic term. Pivot searches, swaps, storage and data movement are additional costs. Exact rational numerators and denominators can also grow; these counts are not bit-complexity bounds, timing benchmarks or rounding-stability guarantees.

Apply

Repair this statement: “The right-hand side is unchanged, so yesterday’s factors are still valid.” The matrix must be unchanged too. If A changes to A+uvᵀ and the old solve gives Ax=b, then its residual for the new matrix is u(vᵀx). That can vanish in a special case, but it need not. With A=I₂, u=(1,0), v=(0,1), the old solution for b=(1,0) still works; for b=(0,1) it fails, and the new solution is (−1,1). Even the successful special case does not turn the old factors into a factorization of the new matrix.

For a changed late-swap challenge, use rows (0,1,2),(2,1,0),(4,0,2). After selecting 4 first, the two active second-column entries tie at 1. Choose original row 1 next and move the stored multipliers accordingly. You should obtain P row order (3,1,2), L rows (1,0,0),(0,1,0),(1/2,1,1), and U rows (4,0,2),(0,1,2),(0,0,−3). Verify the product. A different tie rule may produce different valid factors; correctness rests on the product and triangular conditions, not on matching a single expected permutation.

Continue

A reusable factorization records the original matrix, arithmetic domain, permutation and triangular factors. Check PA=LU independently, apply P to every new right-hand side, and verify a solve against the original equations. Partial pivoting supplies a practical row-selection rule, but the exact proof here is not a numerical error analysis. The written tasks distinguish correct algebra, changed matrices, operation estimates and rounding questions rather than treating one computed residual as evidence for every future solve.

For rounding, residuals and pivot-growth limitations, return to numerical elimination and pivoting. That numerical analysis addresses questions not settled by an exact rational identity.