Gaussian Elimination · aiwiki.page

Gaussian elimination is an algorithm for solving a system of linear equations by systematically eliminating unknowns. It transforms the system’s matrix representation into a simpler form using reversible row operations, preserving its solutions. A central technique of linear algebra, it also provides methods for determining rank and describing solution sets. In numerical computation, elimination is commonly organized as a triangular factorization followed by substitution. (textbooks.math.gatech.edu)

Mathematical basis

A system with $m$ equations and $n$ unknowns is written

Ax=b,

where $A$ is the coefficient matrix, $x$ contains the unknowns, and $b$ contains the right-hand sides. Computation proceeds on the augmented matrix $[A\mid b]$ , so that each operation changes the coefficients and corresponding right-hand side together. Three elementary row operations are permitted:

Interchanging two rows.
Multiplying a row by a nonzero scalar.
Adding a scalar multiple of one row to another.

Each operation is invertible, so the transformed system has exactly the original solution set. (math.mit.edu)

The forward phase produces row echelon form: zero rows occur below nonzero rows, each successive leading nonzero entry lies farther right, and entries below each leading entry are zero. These leading entries are called pivots. Further elimination above pivots, together with normalization of pivots to one, produces reduced row echelon form. This extended procedure is commonly called Gauss–Jordan elimination. Reduced row echelon form is unique, although intermediate echelon forms need not be. (textbooks.math.gatech.edu)

Elimination and back substitution

At each stage, a nonzero pivot is selected in the remaining coefficient columns. Rows may be exchanged to place it in the active row. Multiples of that row are then subtracted from lower rows to eliminate entries in the pivot column. If a column has no eligible nonzero entry, it is skipped and the search continues to the right. (textbooks.math.gatech.edu)

For a nonsingular square system, this yields an upper triangular system $Ux=c$ . At step $k$ , the elimination multiplier and row update are

\ell_{ik}=\frac{u_{ik}}{u_{kk}},\qquad R_i\leftarrow R_i-\ell_{ik}R_k \quad(i>k).

Back substitution then determines the unknowns from last to first:

x_i=\frac{c_i-\sum_{j=i+1}^{n}u_{ij}x_j}{u_{ii}}.

Unlike Gauss–Jordan elimination, this approach does not require eliminating entries above the pivots. (math.mit.edu)

For example, consider

\begin{aligned} x+y+z&=6,\\ 2x+3y+z&=11,\\ x+2y+3z&=14. \end{aligned}

Applying $R_2\leftarrow R_2-2R_1$ and $R_3\leftarrow R_3-R_1$ , followed by $R_3\leftarrow R_3-R_2$ , gives

\left[\begin{array}{ccc|c} 1&1&1&6\\ 0&1&-1&-1\\ 0&0&3&9 \end{array}\right].

Thus $z=3$ , $y=2$ , and $x=1$ .

Rank and solution structure

Elimination also handles rectangular and singular systems. The number of coefficient pivots equals the rank of $A$ . A transformed row

[\,0\ \cdots\ 0\mid d\,],\qquad d\ne0,

represents a contradiction and establishes that the system is inconsistent. Otherwise, variables in columns without coefficient pivots are free variables, and pivot variables are expressed in terms of them. Over the real or complex numbers, a consistent system has a unique solution when every variable column contains a pivot, and infinitely many solutions otherwise. (textbooks.math.gatech.edu)

For a consistent system, all solutions can be written $x=x_p+z$ , where $x_p$ is one particular solution and $z$ belongs to the null space of $A$ . This solution set is an affine space with dimension $n-\operatorname{rank}(A)$ . Elimination can also identify linearly independent columns: the pivot columns of the original matrix form a basis for its column space. Using the original columns matters because row operations generally change the column space itself. (textbooks.math.gatech.edu)

Pivoting and numerical accuracy

In numerical linear algebra, floating-point arithmetic introduces rounding errors. A very small pivot can create large elimination multipliers and substantial growth in intermediate entries. Partial pivoting selects an entry of greatest absolute value in the active column and exchanges rows to place it at the pivot position. Complete pivoting searches the entire remaining coefficient submatrix and may interchange both rows and columns; column interchanges require tracking the unknowns’ reordered positions. (netlib.org)

Partial pivoting is generally effective in practice, but it does not guarantee small errors for every matrix: exceptional examples exhibit exponential element growth. Algorithmic stability must also be distinguished from problem conditioning. The condition number measures sensitivity to input perturbations; an ill-conditioned system can have substantial solution error even when the computed answer has a small backward error. (epubs.siam.org)

Factorization and computational cost

Recording elimination multipliers gives an LU decomposition. With row pivoting, it is conventionally written

PA=LU,

where $P$ represents row permutations, $L$ is unit lower triangular, and $U$ is upper triangular. Solving $Ly=Pb$ and then $Ux=y$ separates factorization from solution. The same factors can therefore serve multiple right-hand sides without repeating elimination. (math.mit.edu)

For a dense $n\times n$ matrix, conventional factorization requires approximately $2n^3/3$ floating-point operations to leading order. Each subsequent triangular solve requires $O(n^2)$ operations, using big-O notation, and the factors can occupy $O(n^2)$ storage by sharing an array. For a sparse matrix, elimination may create new nonzero entries, called fill-in, making ordering and pivot selection important to storage and computation. (math.mit.edu)

Historical development

The name commemorates Carl Friedrich Gauss, but elimination procedures substantially predate him. Related methods occur in the Chinese mathematical work The Nine Chapters on the Mathematical Art. The modern method developed through a longer history of equation solving, Gauss’s computational work, and later adaptations for electronic computers; its name should not be understood as identifying a single invention by Gauss. (doi.org)