Gausselimination

Gaussian elimination, or Gauss elimination, is a method for solving systems of linear equations. It operates on the augmented matrix [A|b] and uses elementary row operations to transform the coefficient matrix A into an upper triangular form, after which the solution is obtained by back-substitution.

The process consists of forward elimination to create zeros below the main diagonal. Pivoting strategies improve stability: partial pivoting selects the row with the largest absolute value in the current column as the pivot; complete pivoting also permutes columns. If a zero pivot is encountered and no suitable row can be swapped, the system may be singular.

The method reveals whether the system has a unique solution, no solution, or infinitely many solutions, depending on the rank of the coefficient matrix and the augmented matrix. Inconsistent systems occur when a row in the augmented matrix reduces to [0 ... 0 | c] with c ≠ 0. Dependent systems have free variables.

Variants and related methods include LU decomposition, where A = LU and forward/back substitution solves the system without repeated elimination, and Gauss-Jordan elimination, which transforms A to reduced row-echelon form. Gaussian elimination is typically O(n^3) time for an n×n system and uses O(n^2) memory; for large or sparse systems, specialized algorithms or iterative methods are often preferred.

Applications span engineering, physics, computer graphics, and economics, where linear systems model equilibrium states, circuit analysis, or least squares problems (via normal equations or QR factorization). The technique is named after Carl Friedrich Gauss, who contributed to the development of elimination methods in the 19th century.