Partial Pivoting and Permutation Matrices

Why Partial Pivoting Changes the Elimination Steps

In Gaussian elimination, a pivot is the entry used to eliminate the entries beneath it in its column. If that entry is zero, the step cannot be carried out as written; a row exchange may put a nonzero entry in the pivot position. Partial pivoting makes a more specific choice: among the available entries in the current pivot column, choose one with the largest absolute value. This ensures that the pivot is nonzero whenever any available entry in that column is nonzero, and it bounds the elimination multipliers in that step.

The row exchanges must be tracked as part of the calculation. A permutation matrix records the order change, while the updated matrix records the elimination. These are related but distinct tasks: choosing a pivot tells us which rows to exchange, and multiplying on the left by the corresponding permutation matrix applies that exchange to the rows.

If several entries tie for the largest absolute value, any of their row indices is a valid choice. A practical implementation needs a tie-breaking rule, but the mathematics of partial pivoting does not prescribe one. The pivot choice is made in the current matrix, after any earlier row exchanges and elimination updates; it is not necessarily made from the original column.

Row Exchanges as Permutation Matrices

A permutation matrix is obtained by rearranging the rows of the identity matrix. For example, exchanging rows 1 and 2 of \(\mathbf{I}_3\) gives \(\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}\). Multiplication by this matrix on the left exchanges rows 1 and 2 of any matrix with three rows. A sequence of row exchanges is recorded by multiplying the corresponding permutation matrices in the same order in which they act: if the first exchange uses \(\mathbf{P}_1\) and the second uses \(\mathbf{P}_2\), the combined action is \(\mathbf{P}_2\mathbf{P}_1\).

Proof. Left multiplication forms each row of \(\mathbf{P}\mathbf{A}\) as a linear combination of the rows of \(\mathbf{A}\), with coefficients from the corresponding row of \(\mathbf{P}\). The rows of \(\mathbf{P}\) are the rows of \(\mathbf{I}_n\), except that the two rows at the exchanged indices have been interchanged. Thus every row of \(\mathbf{P}\mathbf{A}\) equals the corresponding row of \(\mathbf{A}\), except that the selected pair is interchanged. Performing the same exchange a second time restores the original order, so the exchange matrix satisfies \(\mathbf{P}^2=\mathbf{I}_n\). \(\square\)

For multiple exchanges, it is important to preserve the order of multiplication. A later exchange acts on the result of the earlier one, so it appears on the left. The product is itself a permutation matrix, since its action simply rearranges the rows.

Why the Pivot Choice Bounds the Multipliers

Partial pivoting has a useful property that follows directly from its selection rule. It does not say that every part of the elimination is numerically harmless; it gives a bound on the multipliers for the current column.

Proof. Let \(q\) be any row index below the pivot position after the exchange. Before the exchange, the magnitude of the entry in row \(q\), column \(k\) was no larger than \(\lvert a_{pk}\rvert\), because the chosen entry had largest absolute value among all active entries. The exchange moves \(a_{pk}\) to position \((k,k)\) and does not change the other active entries. The multiplier for row \(q\) is its column-\(k\) entry divided by the pivot. Therefore its magnitude is at most \(\lvert a_{pk}\rvert/\lvert a_{pk}\rvert=1\). The denominator is nonzero by the hypothesis that at least one active entry is nonzero and the selection rule chooses a largest one. \(\square\)

The condition matters. If every available entry is zero, the largest magnitude is zero, so there is no nonzero pivot and no multiplier can be computed. Partial pivoting chooses among entries in the current column only; it does not move a nonzero entry from another column into the pivot position.

Tracing Several Exchanges and Updates

When elimination multipliers are stored for later use, a row exchange at a later stage also changes which row owns each earlier multiplier. In the example, the first-stage multipliers \(1/4\) and \(1/2\) belong to the two rows below the first pivot. When those active rows are exchanged for the second pivot, the earlier multipliers must be exchanged with them. Otherwise, the recorded values no longer describe the row updates that were actually performed. This is a bookkeeping rule for an elimination calculation; it does not change how the current pivot is selected.

Ties, Checks, and a Common Mistake

Common mistake: swapping the entries but forgetting the permutation. In the first worked example, the exchanged matrix is \(\begin{bmatrix}2&3\\\tfrac14&1\end{bmatrix}\). It would be incorrect to claim that this is \(\mathbf{I}_2\mathbf{A}\), because \(\mathbf{I}_2\mathbf{A}=\mathbf{A}\) leaves the rows in their original order. The correct record is \(\mathbf{P}\mathbf{A}\), with \(\mathbf{P}=\begin{bmatrix}0&1\\1&0\end{bmatrix}\). Multiplying back checks both the chosen row order and the entries.

A second error is to choose the first nonzero entry without checking whether a larger one is available. In the first worked example, choosing \(1/4\) as the pivot would give multiplier \(2/(1/4)=8\). Partial pivoting instead selects \(2\), giving multiplier \(1/8\). The rule is about the largest magnitude among the active entries in that column, not merely finding a nonzero entry.

A Reliable Calculation Checklist

At each stage, keep the pivot choice, the row order, and the arithmetic distinct. A careful calculation can be organized as follows:

These steps make the calculation auditable: the permutation records where the rows went, and each elimination update records what was subtracted. Partial pivoting also guarantees that each multiplier in a successfully processed column has magnitude at most \(1\). The question of how this choice affects broader numerical behavior requires additional analysis; the immediate task here is to apply and record the row exchanges correctly.