Deriving PA = LU With Row Exchanges

Why Row Exchanges Change the LU Record

In elimination without row exchanges, each step subtracts a multiple of a pivot row from rows below it. The multipliers used in these operations are stored below the diagonal of a lower triangular matrix \(\mathbf{L}\); the resulting upper triangular matrix is \(\mathbf{U}\). When a pivot is zero or is not the pivot chosen by partial pivoting, rows of the active part of \(\mathbf{U}\) are exchanged. Those exchanges also change the order of the original equations, recorded by a permutation matrix \(\mathbf{P}\).

There is an additional bookkeeping requirement. If a row is exchanged after earlier elimination steps, its previously stored multipliers belong with that row and must be exchanged too. The factorization is therefore not generally \(\mathbf{A}=\mathbf{L}\mathbf{U}\), but \(\mathbf{P}\mathbf{A}=\mathbf{L}\mathbf{U}\). We derive the update rule and then check it by multiplication.

For partial pivoting at column \(k\), the pivot row is chosen among rows \(k,\dots,n\), usually as a row whose entry in column \(k\) has largest absolute value. The derivation below requires only that the selected pivot be nonzero. If every candidate in that active column is zero, this elimination step cannot proceed. The algorithm describes a factorization when it completes all the required steps.

The Elimination and Bookkeeping Rule

Start with \(\mathbf{U}=\mathbf{A}\), \(\mathbf{P}=\mathbf{I}_n\), and \(\mathbf{L}=\mathbf{I}_n\). At step \(k\), exchange the selected pivot row \(r\) with row \(k\) in \(\mathbf{U}\) and \(\mathbf{P}\). In \(\mathbf{L}\), exchange rows \(k\) and \(r\) only in columns \(1,\dots,k-1\). These columns contain the multipliers from completed steps; the remaining part of \(\mathbf{L}\) is still being constructed. Next, for each \(i>k\), set \(l_{ik}=u_{ik}/u_{kk}\), perform \(R_i\to R_i-l_{ik}R_k\) on \(\mathbf{U}\), and store \(l_{ik}\) in \(\mathbf{L}\).

Proof. We track the relation between the permuted original matrix and the current elimination data. Before step \(k\), let \(\mathbf{B}=\mathbf{P}\mathbf{A}\), so the current record satisfies \(\mathbf{B}=\mathbf{L}\mathbf{U}\). At this stage, rows \(1,\dots,k-1\) of \(\mathbf{U}\) have been completed, and in columns \(1,\dots,k-1\) the entries below the diagonal are zero. The active rows of \(\mathbf{L}\), in columns \(k,\dots,n\), still form an identity block.

Suppose rows \(k\) and \(r\) are exchanged. Apply the same exchange to \(\mathbf{B}\), which is achieved by updating \(\mathbf{P}\), and to \(\mathbf{U}\). In the product relation, each active row of \(\mathbf{B}\) is a combination of the already completed rows of \(\mathbf{U}\), with coefficients given by the stored entries in columns \(1,\dots,k-1\) of \(\mathbf{L}\), plus that active row of \(\mathbf{U}\) itself. Swapping the active rows therefore requires swapping their stored coefficients in those earlier columns of \(\mathbf{L}\). The rows of \(\mathbf{U}\) above \(k\) are unchanged, and their rows in \(\mathbf{L}\) have zero entries in columns \(k,\dots,n\), so their product equations are unchanged. Thus the relation is preserved by the pivot exchange when the earlier multipliers are exchanged as stated.

Now eliminate below the pivot. For each \(i>k\), the row operation replaces row \(i\) of \(\mathbf{U}\) by row \(i\) minus \(l_{ik}\) times row \(k\). The corresponding row equation for \(\mathbf{B}\) remains valid if its coefficient on row \(k\) of \(\mathbf{U}\) is increased by \(l_{ik}\). That is exactly the update that stores \(l_{ik}\) in position \((i,k)\) of \(\mathbf{L}\). Hence the relation \(\mathbf{B}=\mathbf{L}\mathbf{U}\) is preserved through the elimination step as well. Initially \(\mathbf{P}=\mathbf{L}=\mathbf{I}_n\) and \(\mathbf{U}=\mathbf{A}\), so the relation holds before the first step. By applying the two updates at every step, it holds at completion. The elimination has made \(\mathbf{U}\) upper triangular, and the stored multipliers make \(\mathbf{L}\) unit lower triangular. Therefore \(\mathbf{P}\mathbf{A}=\mathbf{L}\mathbf{U}\). \(\square\)

A Factorization With Two Exchanges

Examples With an Initial Exchange

Common Pitfall: Leaving the Multipliers in Place

In the first example, after the second pivot exchange the multiplier in column 1 of row 2 must be \(1/4\), and the multiplier in row 3 must be \(1/2\). If those stored values are not exchanged, one might incorrectly use \(\widetilde{\mathbf{L}}=\begin{bmatrix}1&0&0\\1/2&1&0\\1/4&2/11&1\end{bmatrix}\) with the same \(\mathbf{U}\). Its second product row is \(\tfrac12(4,1,0)+(0,\tfrac{11}{4},2)=(2,\tfrac{13}{4},2)\), but row 2 of \(\mathbf{P}\mathbf{A}\) is \((1,3,2)\). So \(\widetilde{\mathbf{L}}\mathbf{U}\ne\mathbf{P}\mathbf{A}\). The correction is to swap the previously stored entries whenever active rows of \(\mathbf{U}\) are exchanged. The current pivot exchange changes which original row occupies each active position; the multipliers in earlier columns must follow that same row.

The order of the updates is therefore meaningful: exchange the active rows, move the earlier stored multipliers with them, and then compute and store the new multipliers. Once elimination is complete, \(\mathbf{P}\) records the row order, \(\mathbf{L}\) records the elimination multipliers in that order, and \(\mathbf{U}\) is the final upper triangular matrix. Multiplying the factors is the direct check that all three records agree.