nLab Gaussian elimination



Linear algebra

homotopy theory, (∞,1)-category theory, homotopy type theory

flavors: stable, equivariant, rational, p-adic, proper, geometric, cohesive, directed

models: topological, simplicial, localic, …

see also algebraic topology



Paths and cylinders

Homotopy groups

Basic facts




What is called Gaussian elimination is an algorithm for solving systems of linear equations. It proceeds by encoding the system as a matrix equation

Ax=b A \, x = b

where bb is a column matrix of free coefficients, xx is a column vector of unknowns, and AA is the matrix of coefficients. The entire system is therefore encoded by the matrix of the system which is in block form (A|b)(A | b). The algorithm consists of applying elementary row operations in a systematic way to bring it into upper triangular form.


Over noncommutative rings

Coeffients may be in a noncommutative ring and we may search for a solution in that ring. However, all the coefficients are from the same, say left side of the unknowns. The algorithm is proceeding as in the commutative case, provided certain expressions are invertible along the way. Recursive nature of the algorithm is related to the hereditary property of quasideterminants.

Gauss decomposition

Performing the Gauss elimination procedure when AA is a square matrix to end with upper triangular matrix UU means that AA is written in the form

A=wLU A = w L U

where ww is a permutation matrix, LL a lower triangular matrix with units of diagonal and UU an upper triangular matrix. This is the Gauss decomposition with respect to the lower Borel subgroup of GL(n,k)GL(n,k). A noncommutative Gauss decomposition exists for matrices over noncommutative division rings.


An application of Gauss elimination to a particular system yields the Gram-Schmidt orthogonalization:

Last revised on May 30, 2024 at 13:29:02. See the history of this page for a list of all contributions to it.