Solving Ax = b: Gaussian Elimination and LU

Almost every linear-algebra question that starts with a matrix ends up solving $A\mathbf{x} = \mathbf{b}$. The method is Gaussian elimination: use row operations to turn $A$ into an upper-triangular matrix $U$, then read off the unknowns by back-substitution. The multipliers you use along the way are not waste, they assemble into a lower-triangular $L$, so the same work also produces the factorization $A = LU$.

Elimination reduces $A$ to $U$

An elementary row operation adds a multiple of one row to another; it never changes the solution set. Work down the columns. At column $j$ the pivot is the diagonal entry $a_{jj}$, and for each row $i$ below it we subtract the pivot row scaled by the multiplier

That choice of $\ell_{ij}$ is exactly what drives the entry under the pivot to zero. After clearing every entry below every pivot, $A$ has become upper triangular:

Applying the same operations to $\mathbf{b}$ turns the system into $U\mathbf{x} = \mathbf{c}$, which a triangular matrix solves from the bottom up:

A worked $3\times 3$

Take the system with

so the augmented matrix is

Column 1. The pivot is $2$. For row $2$ the multiplier is $\ell_{21} = -3/2$, so $R_2 \leftarrow R_2 - \ell_{21} R_1 = R_2 + \tfrac{3}{2}R_1$. For row $3$, $\ell_{31} = -1$, so $R_3 \leftarrow R_3 + R_1$:

Column 2. The new pivot is $\tfrac{1}{2}$. For row $3$ the multiplier is $\ell_{32} = 2 / \tfrac{1}{2} = 4$, so $R_3 \leftarrow R_3 - 4R_2$, which reaches $U$:

Back-substitution. From the bottom row up,

giving $\mathbf{x} = (2, 3, -1)$. Step through the same numbers below: each Step performs one row operation and shows the resulting matrix, then the Solve steps run back-substitution.

Elimination is $LU$ factorization

Collect the multipliers used above into a unit lower-triangular matrix, placing $\ell_{ij}$ in position $(i,j)$. That matrix is $L$, and together with $U$ it reconstructs $A$:

The reason $L$ works out this way is that each elimination step is left multiplication by a matrix that differs from the identity in a single entry, and the inverse of such a matrix just flips the sign of that entry. Multiplying those inverses back together stacks the multipliers directly into $L$.¹

The factorization is where the payoff sits. Once $A = LU$ is known, solving $A\mathbf{x} = \mathbf{b}$ splits into two triangular solves:

For this system the forward solve gives $\mathbf{y} = (8, 1, 1)$, which is exactly the transformed right-hand side from the elimination above. A second right-hand side then costs only the two triangular solves, not another elimination.

Pivots, exchanges, and cost

The whole scheme rests on nonzero pivots. If a pivot comes out zero, you cannot divide by it, and you swap in a row below that has a nonzero entry in that column: an exchange, recorded by a permutation matrix $P$, so the factorization becomes $PA = LU$.² In floating point the same idea, partial pivoting, chooses the largest available pivot to keep multipliers bounded and the solve stable. If no row supplies a nonzero pivot, that column is dependent and $A$ is singular, so $A\mathbf{x} = \mathbf{b}$ has either no solution or infinitely many.

The cost is dominated by the forward elimination. Clearing column $j$ touches an $(n-j)\times(n-j)$ block, and summing those blocks gives about $\tfrac{2}{3}n^{3}$ floating-point operations.² Each triangular solve is only $O(n^{2})$, which is why factoring once and reusing $L$ and $U$ is the right move when several right-hand sides share the same $A$.