L and U as Records of Elimination

Two Matrices, Two Records

Gaussian elimination changes a matrix one stage at a time. At each stage, entries below a pivot are eliminated by subtracting multiples of the pivot row. The final upper-triangular matrix records the result of all those operations, but it does not by itself record which multiples were used. In an LU factorization, the two factors preserve both kinds of information: \(U\) is the final matrix, and \(L\) stores the multipliers from the elimination stages.

Throughout, matrices and scalars are over \(\mathbb{R}\). We consider square matrices and elimination without row exchanges. At each stage, the pivot must be nonzero so that the required multipliers are defined. The row operation that eliminates the entry in row \(i\), column \(k\) is \(R_i\to R_i-l_{ik}R_k\); the multiplier is calculated using the matrix as it stands at stage \(k\), after the earlier stages have been completed.

For a \(3\times3\) matrix, the factors have the form

The position of each multiplier tells you its stage. The entries \(l_{21}\) and \(l_{31}\) describe the eliminations below the first pivot; \(l_{32}\) describes the elimination below the second pivot. The diagonal entries of \(\mathbf{L}\) are \(1\), not additional multipliers. By contrast, the entries of \(\mathbf{U}\), conventionally denoted \(u_{ij}\), are entries of the final upper-triangular matrix.

Recovering the Steps from the Factors

This example illustrates how to use both factors as records. To replay the elimination, read the multipliers in \(\mathbf{L}\) by columns, starting with column 1 and then moving right. To recover the matrix before elimination, multiply \(\mathbf{L}\mathbf{U}\). These are related tasks, but they are not the same: \(\mathbf{U}\) gives the endpoint, while the off-diagonal entries of \(\mathbf{L}\) give the elimination history.

Why the Factorization Stores the Multipliers

Proof. For each stage \(k\), let \(\mathbf{N}_k\) be the matrix with entries \(l_{ik}\) in positions \((i,k)\) for \(i>k\), and zeros elsewhere. The elimination at stage \(k\) is left multiplication by \(\mathbf{E}_k=\mathbf{I}_n-\mathbf{N}_k\): this subtracts \(l_{ik}\) times row \(k\) from row \(i\) for every \(i>k\). Since the only potentially nonzero entries of \(\mathbf{N}_k\) are in column \(k\), and its row \(k\) is zero, \(\mathbf{N}_k^2=\mathbf{O}\). Consequently, \((\mathbf{I}_n-\mathbf{N}_k)(\mathbf{I}_n+\mathbf{N}_k)=\mathbf{I}_n\), so \(\mathbf{E}_k^{-1}=\mathbf{I}_n+\mathbf{N}_k\). After all stages, \(\mathbf{U}=\mathbf{E}_{n-1}\cdots\mathbf{E}_1\mathbf{A}\), hence \(\mathbf{A}=(\mathbf{I}_n+\mathbf{N}_1)\cdots(\mathbf{I}_n+\mathbf{N}_{n-1})\mathbf{U}\). If \(i<j\), then \(\mathbf{N}_i\mathbf{N}_j=\mathbf{O}\): a nonzero product would require a row index greater than \(j\) to equal the column index \(i\), which is impossible when \(i<j\). Thus the product of the factors \(\mathbf{I}_n+\mathbf{N}_k\), in the displayed order, is \(\mathbf{I}_n+\mathbf{N}_1+\cdots+\mathbf{N}_{n-1}\). This is precisely the unit lower-triangular matrix with entry \(l_{ik}\) in position \((i,k)\). Calling it \(\mathbf{L}\) gives \(\mathbf{A}=\mathbf{L}\mathbf{U}\), as required. \(\square\)

The proof explains why the entries below \(\mathbf{L}\)'s diagonal are the actual stage multipliers, rather than a new set of coefficients obtained by multiplying arbitrary elimination matrices. The order of the elimination stages matters, and the zero products in the proof ensure that each multiplier remains in its own position in \(\mathbf{L}\).

Computing the Record from an Original Matrix

The stage number is essential when recording a multiplier. At stage 2, row 3 has already been changed by the first elimination. Its entry in column 2 is \(4\), and the current pivot is \(1\), so \(l_{32}=4\). The original entries \(a_{32}=5\) and \(a_{22}=3\) do not determine this multiplier.

A Small Factorization and Uniqueness

Proof. A triangular matrix with nonzero diagonal has an inverse of the same triangular type: solving a triangular system by substitution determines each variable uniquely in order, and applying this to each coordinate vector gives the columns of the inverse. Thus \(\mathbf{L}_2^{-1}\) is unit lower-triangular and \(\mathbf{U}_1^{-1}\) is upper-triangular. From \(\mathbf{L}_1\mathbf{U}_1=\mathbf{L}_2\mathbf{U}_2\), multiply on the left by \(\mathbf{L}_2^{-1}\) and on the right by \(\mathbf{U}_1^{-1}\) to obtain \(\mathbf{L}_2^{-1}\mathbf{L}_1=\mathbf{U}_2\mathbf{U}_1^{-1}\). The left side is unit lower-triangular and the right side is upper-triangular. A matrix that is both lower- and upper-triangular is diagonal; because the left side has diagonal entries \(1\), both sides must equal \(\mathbf{I}_n\). Therefore \(\mathbf{L}_2^{-1}\mathbf{L}_1=\mathbf{I}_n\) and \(\mathbf{U}_2\mathbf{U}_1^{-1}=\mathbf{I}_n\), which give \(\mathbf{L}_1=\mathbf{L}_2\) and \(\mathbf{U}_1=\mathbf{U}_2\). \(\square\)

This uniqueness statement concerns factorizations with the stated triangular forms and nonzero diagonal in \(\mathbf{U}\). In the no-row-exchange setting, it means the multiplier record and the final upper-triangular matrix are fixed once the factorization exists.

Common Mistake: Using Original Entries for Later Multipliers

In the second worked example, a tempting but incorrect calculation is \(l_{32}=a_{32}/a_{22}=5/3\). That ratio uses entries from the original matrix, even though the second pivot step occurs after the first elimination. Using \(5/3\) would produce the incorrect candidate

With the correct final matrix \(\mathbf{U}\), its product has third row \((2,1,0)+\frac53(0,1,1)+(0,0,2)=(2,\frac83,\frac{11}{3})\), which is not the original third row \((2,5,6)\). The correction is to use the current matrix after stage 1: the relevant entry is \(4\), and the current pivot is \(1\), so \(l_{32}=4/1=4\). This gives the correct product and the correct elimination step.

Another sign error is to read a negative multiplier as the number added to the row. The prescribed operation is \(R_i\to R_i-l_{ik}R_k\). Thus \(l_{21}=-2\) means add \(2R_1\), while \(l_{21}=2\) means subtract \(2R_1\). Keeping the multiplier and the row-operation sign distinct prevents confusion when reconstructing the steps.

Why the Records Are Useful

The factorization separates the elimination outcome from the operations that produced it. The upper-triangular matrix \(\mathbf{U}\) is useful because it shows the system after elimination. The lower-triangular matrix \(\mathbf{L}\) preserves the multipliers, so the original matrix can be recovered as \(\mathbf{L}\mathbf{U}\), and the elimination can be replayed stage by stage. This record is also useful when checking a computed factorization: multiply the factors to recover \(\mathbf{A}\), then compare the entries of \(\mathbf{L}\) with the ratios used at the corresponding stages.

The factorization described here assumes no row exchanges and nonzero pivots at every stage. If a pivot is zero, the multiplier ratio at that stage is undefined, so this procedure cannot continue as stated. The treatment of row exchanges and pivot choices requires a different factorization form.