Gaussian Elimination as Matrix Factorization

From Row Operations to Two Factors

Gaussian elimination transforms a matrix into a simpler one by subtracting multiples of pivot rows from rows below them. Those multiples are not temporary bookkeeping: they record how the original rows are reconstructed from the eliminated rows. Collecting that information gives a lower triangular matrix, while the result of elimination is upper triangular. Together these matrices express the original matrix as a product.

We work over \(\mathbb{R}\). A square matrix is lower triangular if every entry above its main diagonal is zero, and upper triangular if every entry below its main diagonal is zero. In the factorization considered here, the diagonal entries of the lower triangular factor are all \(1\). The tutorial focuses on elimination without row exchanges; the pivots used in the examples are nonzero.

There is a sign distinction to keep straight. The row operation subtracts the multiplier times the pivot row. The corresponding entry in \(\mathbf{L}\) is the multiplier itself, not its negative. One way to explain this is through an elimination matrix. For example, the matrix that performs \(R_2\to R_2-mR_1\) when multiplied on the left is \(\begin{bmatrix}1&0\\-m&1\end{bmatrix}\). Its inverse is \(\begin{bmatrix}1&0\\m&1\end{bmatrix}\), which restores the eliminated row and records \(m\) in the lower triangular factor.

How the Multipliers Build the Lower Factor

For a three-by-three matrix, suppose the first pivot is \(a\ne0\), and after eliminating the first column the second pivot is \(p\ne0\). Write the original matrix as \(\begin{bmatrix}a&b&c\\d&e&f\\g&h&i\end{bmatrix}\). The first two multipliers are \(m_{21}=d/a\) and \(m_{31}=g/a\). After the first-column eliminations, the second entry in row 2 is \(p=e-m_{21}b\), and the second entry in row 3 is \(h-m_{31}b\). Hence the next multiplier is \(m_{32}=(h-m_{31}b)/p\).

Proof. The condition \(a\ne0\) allows the first-column row operations \(R_2\to R_2-m_{21}R_1\) and \(R_3\to R_3-m_{31}R_1\). They give rows \((0,p,f-m_{21}c)\) and \((0,h-m_{31}b,i-m_{31}c)\), respectively. Since \(p\ne0\), the next operation subtracts \(m_{32}\) times the new second row from the new third row. It produces a zero in position \((3,2)\), so the resulting matrix \(\mathbf{U}\) is upper triangular. Write its rows as \(\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3\). Reversing the operations expresses the original rows as \(\mathbf{u}_1\), \(m_{21}\mathbf{u}_1+\mathbf{u}_2\), and \(m_{31}\mathbf{u}_1+m_{32}\mathbf{u}_2+\mathbf{u}_3\). Those are exactly the rows of \(\mathbf{L}\mathbf{U}\) for the displayed \(\mathbf{L}\). Therefore \(\mathbf{A}=\mathbf{L}\mathbf{U}\). \(\square\)

The proposition makes the order of the multipliers explicit. The multiplier \(m_{32}\) is calculated after the first elimination has changed row 3, but it is recorded in position \((3,2)\) of \(\mathbf{L}\); \(m_{31}\), recorded in position \((3,1)\), is not replaced by a later value. The product \(\mathbf{L}\mathbf{U}\) checks that the entire sequence has been recorded consistently.

A Three-by-Three Factorization and a System

Elimination Matrices Explain the Sign

The same reasoning can be stated using matrices for row operations. Left multiplication by a matrix performs the corresponding row operation. For example, in the first step of the preceding example, the matrix for \(R_2\to R_2-2R_1\) is \(\begin{bmatrix}1&0&0\\-2&1&0\\0&0&1\end{bmatrix}\). Its inverse has \(+2\) in position \((2,1)\), because adding \(2R_1\) reverses the subtraction. Thus, if an elimination step is represented by \(\mathbf{E}\), the original matrix is recovered by multiplying by \(\mathbf{E}^{-1}\) on the left.

Proof. The matrix \(\mathbf{e}_i\mathbf{e}_j^{\top}\) has a \(1\) in position \((i,j)\) and zeros elsewhere, so \(\mathbf{E}\) changes row \(i\) by subtracting \(m\) times row \(j\) and leaves the other rows unchanged. Let \(\mathbf{N}=\mathbf{e}_i\mathbf{e}_j^{\top}\). Since \(i\ne j\), \(\mathbf{N}^2=\mathbf{e}_i(\mathbf{e}_j^{\top}\mathbf{e}_i)\mathbf{e}_j^{\top}=\mathbf{O}\), because \(\mathbf{e}_j^{\top}\mathbf{e}_i=0\). Consequently, \((\mathbf{I}-m\mathbf{N})(\mathbf{I}+m\mathbf{N})=\mathbf{I}-m^2\mathbf{N}^2=\mathbf{I}\), and reversing the factors gives the same identity. Therefore \(\mathbf{E}^{-1}=\mathbf{I}+m\mathbf{N}\). \(\square\)

With multiple elimination steps, the row-operation matrices act in sequence on the left, so their order matters. Reversing those operations recovers the original matrix. The three-by-three proposition gives a direct way to carry out that recovery: retain each multiplier in its corresponding position in \(\mathbf{L}\), then verify the result by multiplication.

Common Pitfall: Recording the Wrong Sign

A frequent error is to copy the coefficient as it appears in the row operation, including its subtraction sign. In the two-by-two example, the operation was \(R_2\to R_2-2R_1\). Putting \(-2\) in \(\mathbf{L}\) would give the incorrect product \(\begin{bmatrix}1&0\\-2&1\end{bmatrix}\begin{bmatrix}3&2\\0&1\end{bmatrix}=\begin{bmatrix}3&2\\-6&-3\end{bmatrix}\), which is not \(\mathbf{A}\). The correction is to record the multiplier \(2\), so the lower row of \(\mathbf{L}\mathbf{U}\) is \(2(3,2)+(0,1)=(6,5)\). The subtraction sign belongs to the row operation; reversing the operation to recover the original matrix puts the positive multiplier into \(\mathbf{L}\).

Always check \(\mathbf{L}\mathbf{U}=\mathbf{A}\) by multiplication, rather than relying only on the appearance of the factors. The check detects sign errors and misplaced multipliers. It also reinforces the meaning of the factorization: each row of \(\mathbf{A}\) is assembled from rows of \(\mathbf{U}\) using the coefficients in the corresponding row of \(\mathbf{L}\).