Computing LU Factors From an Elimination Table

From an Elimination Table to Two Factors

Gaussian elimination changes a matrix one row at a time. An elimination table shows the entries after each change, but it can also preserve information about how those changes were made. The key is to record each multiplier at the moment it is used. The final triangular matrix supplies \(U\), while the multipliers, placed in the correct positions, supply \(L\). This tutorial focuses on carrying out that procedure and checking the result by multiplication.

We work with square matrices over \(\mathbb{R}\). In elimination without row exchanges, the pivot at each step must be nonzero when it is used. At step \(k\), the pivot is the entry in row \(k\), column \(k\), after the earlier steps have been completed. If that pivot is \(u_{kk}\), and the current entry in row \(i\), column \(k\) is \(a_{ik}^{(k)}\), the multiplier for eliminating that entry is \(m_{ik}=a_{ik}^{(k)}/u_{kk}\). The superscript indicates the stage of elimination; it is not a power.

The row operations change the matrix, but the multiplier table records the coefficients needed to reconstruct the original matrix. In particular, do not read the entries below the diagonal of \(\mathbf{L}\) from the final matrix: those entries have been eliminated and are zero in \(\mathbf{U}\). Instead, copy each multiplier into the position corresponding to the entry it eliminated.

Why the Multiplier Is the Right One

Proof. The entry in column \(k\) of row \(i\) after this operation is \(a_{ik}^{(k)}-m_{ik}u_{kk}\). With \(m_{ik}=a_{ik}^{(k)}/u_{kk}\), this becomes \(a_{ik}^{(k)}-(a_{ik}^{(k)}/u_{kk})u_{kk}=0\). Division is valid because \(u_{kk}\ne0\). \(\square\)

This calculation also explains why a table must be read stage by stage. The entry \(a_{ik}^{(k)}\) is the entry after earlier columns have been eliminated, not necessarily the corresponding entry in the original matrix. Each multiplier uses the current pivot and the current entry beneath it.

Worked Elimination Tables

Why Recording the Multipliers Produces \(L\)

Proof. For each step \(k\), let \(\mathbf{M}_k\) be the matrix whose entry in position \((i,k)\) is \(m_{ik}\) for \(i>k\), with all other entries zero. Left multiplication by \(\mathbf{E}_k=\mathbf{I}-\mathbf{M}_k\) replaces row \(i\) by row \(i\) minus \(m_{ik}\) times row \(k\), which is precisely the operation \(R_i\to R_i-m_{ik}R_k\). It leaves row \(k\) unchanged. Also, \(\mathbf{M}_k^2=\mathbf{O}\), since the nonzero entries of \(\mathbf{M}_k\) are in column \(k\) and in rows strictly below \(k\). Consequently, \((\mathbf{I}-\mathbf{M}_k)(\mathbf{I}+\mathbf{M}_k)=\mathbf{I}\), so \(\mathbf{E}_k^{-1}=\mathbf{I}+\mathbf{M}_k\).

After all steps, \(\mathbf{U}=\mathbf{E}_{n-1}\cdots\mathbf{E}_2\mathbf{E}_1\mathbf{A}\). Inverting this sequence gives \(\mathbf{A}=(\mathbf{I}+\mathbf{M}_1)(\mathbf{I}+\mathbf{M}_2)\cdots(\mathbf{I}+\mathbf{M}_{n-1})\mathbf{U}\). For \(i<j\), \(\mathbf{M}_i\mathbf{M}_j=\mathbf{O}\): a nonzero entry of \(\mathbf{M}_i\) can only use column index \(i\) as the intermediate index in a product, while a nonzero row index of \(\mathbf{M}_j\) must be greater than \(j\), and thus greater than \(i\). Expanding the displayed product therefore leaves only \(\mathbf{I}+\mathbf{M}_1+\cdots+\mathbf{M}_{n-1}\). This is exactly the lower-triangular matrix \(\mathbf{L}\) with the recorded multipliers below its diagonal. Hence \(\mathbf{A}=\mathbf{L}\mathbf{U}\). \(\square\)

Common Mistake: Losing an Earlier Multiplier

In the first worked example, the multiplier \(m_{32}=3\) is used after the first two row operations. A tempting but incorrect choice is \(\mathbf{L}_{\mathrm{wrong}}=\begin{bmatrix}1&0&0\\2&1&0\\4&0&1\end{bmatrix}\), which forgets to record that later multiplier. Multiplying this incorrect matrix by the correct \(\mathbf{U}\) gives third row \(4(2,1,1)+(0,0,2)=(8,4,6)\), not the original third row \((8,7,9)\). The correction is to include \(m_{32}=3\) in position \((3,2)\). Then the third product row is \(4(2,1,1)+3(0,1,1)+(0,0,2)=(8,7,9)\), as required.

Another frequent error is to put the negative of each multiplier in \(\mathbf{L}\). The elimination operation subtracts \(m_{ik}\) times the pivot row, but the entry recorded in \(\mathbf{L}\) is \(m_{ik}\), not \(-m_{ik}\). The minus sign belongs to the row operation, while the reconstruction theorem shows why the multiplier itself appears in the lower factor.

A reliable computation can be organized as a short sequence:

The multiplication check is more than a final formality. It catches missing multipliers, misplaced entries, and arithmetic errors in the elimination itself. For a small matrix, computing the rows of \(LU\) explicitly is usually the quickest check. For larger matrices, the same principle applies: each row of \(L\) forms a weighted combination of rows of \(U\), and those combinations must reproduce the corresponding rows of \(A\).