View source for Gauss method

A method of successive elimination of unknowns in solving a set of linear equations, first introduced by C.F. Gauss [[#References|[1]]]. Let there be given a system

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g0434801.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g0434802.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g0434803.png" /> are elements of an arbitrary field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g0434804.png" />. Without loss of generality one may assume that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g0434805.png" />. The Gauss method operates as follows. One subtracts the first equation of the set, multiplied by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g0434806.png" /> term by term, from the second equation; then one subtracts the first equation multiplied by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g0434807.png" /> from the third equation; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g0434808.png" /> then one subtracts the first equation multiplied by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g0434809.png" /> from the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348010.png" />-th equation. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348011.png" /> be the system of subtracted equations thus obtained. If a coefficient in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348012.png" /> is non-zero (possibly after changing the sequence of equations and unknowns), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348013.png" /> is treated as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348014.png" />, etc. If the rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348015.png" /> of the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348016.png" /> (i.e. the rank of the matrix of its coefficients) is smaller than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348017.png" />, then the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348018.png" />-th step will yield a system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348019.png" /> in which all coefficients at the unknowns are zero; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348020.png" />, the system is said to be empty. The system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348021.png" /> is compatible if and only if the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348022.png" /> is either compatible (i.e. has no non-zero free terms) or is empty.

The process of obtaining one solution of a (compatible) system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348023.png" /> may be described as follows. One takes some solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348024.png" /> of the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348025.png" />. By assigning the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348026.png" /> to the unknowns <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348027.png" /> in some equations of the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348028.png" /> with a non-zero coefficient at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348029.png" /> (e.g. to its first equation), one finds <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348030.png" /> and obtains a solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348031.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348032.png" />. In other words, the value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348033.png" /> is obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348034.png" /> by replacing the unknowns <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348035.png" /> by the values taken for them. The values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348036.png" /> are then substituted in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348037.png" />, the value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348038.png" /> is found, and hence the solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348039.png" />, etc. The values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348040.png" /> thus found, together with the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348041.png" /> taken, constitute a solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348042.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348043.png" /> [[#References|[2]]].

This method may be generalized as follows [[#References|[4]]]. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348044.png" /> be some subspace of the vector space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348045.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348046.png" /> be the set of all solutions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348047.png" /> of the equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348048.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348049.png" /> runs through <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348050.png" />. For an arbitrary finite system

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348051.png" /></td> </tr></table>

of non-zero generating elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348052.png" /> it is possible to construct a system

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348053.png" /></td> </tr></table>

(where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348054.png" /> is the unknown), known as the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348056.png" />-convolution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348057.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348058.png" /> contains no non-zero elements, one says that the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348059.png" /> has an empty <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348061.png" />-convolution. If the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348062.png" /> is compatible, then the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348063.png" />-convolution of any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348064.png" /> is compatible or is empty. It was found that, for the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348065.png" /> to be compatible, it is sufficient that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348066.png" />-convolution is empty or compatible for only one <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348067.png" />. Again, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348068.png" /> be subspaces generated in the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348069.png" /> by the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348070.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348071.png" /> equation (*) is reduced to the equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348072.png" /></td> </tr></table>

Let, for example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348073.png" />. If also <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348074.png" />, then the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348075.png" /> may be taken as the non-zero generating elements of the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348076.png" />, and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348077.png" />-convolution of the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348078.png" /> will coincide with the procedure of elimination of the unknown <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348079.png" /> in Gauss' method.

The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348080.png" />-convolution of the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348081.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348082.png" /> is a procedure for the simultaneous elimination of two unknowns <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348083.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348084.png" />. For example, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348085.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348086.png" />. If also

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348087.png" /></td> </tr></table>

then the rows of the matrix

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348088.png" /></td> </tr></table>

where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348089.png" /></td> </tr></table>

may be used to obtain the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348090.png" />-convolution of the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348091.png" />. By a suitable elimination of individual unknowns with eliminations of certain pairs (or, generally, samples) of unknowns, the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348092.png" /> may be solved by using algorithms which are generalizations of the Gauss method.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  C.F. Gauss,   "Beiträge zur Theorie der algebraischen Gleichungen" , ''Werke'' , '''3''' , K. Gesellschaft Wissenschaft. Göttingen  (1876)  pp. 71–102</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.G. Kurosh,   "Higher algebra" , MIR  (1972)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  D.K. Faddeev,   V.N. Faddeeva,   "Computational methods of linear algebra" , Freeman  (1963)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  S.N. Chernikov,   "Lineare Ungleichungen" , Deutsch. Verlag Wissenschaft.  (1971)  (Translated from Russian)</TD></TR></table>



====Comments====
There are a number of variants of this method, mostly based on practical implementation considerations (like the methods of Crout and Doolittle) or efficiency (like the method of Choleski for symmetric systems).

In the Western literature, the notions of LU-decomposition, forward elimination and back substitution are often associated with Gauss' method (which is also called the Gaussian elimination method). Consider the particular case where the matrix of coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348094.png" /> in the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348095.png" /> is a square matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348096.png" />. Then LU-decomposition refers to the decomposition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348097.png" /> into a lower- and upper-triangular matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348098.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g04348099.png" />, i.e., <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g043480100.png" />. Forward elimination and back substitution are understood to be the solution of the triangular systems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g043480101.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g043480102.png" />, respectively. By using the concept of a flop (as introduced by C.B. Moler), that is, the amount of work involved in performing a floating point addition, a floating point multiplication and a little subscripting, it can be shown that LU-decomposition, forward elimination and back substitution require <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g043480103.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g043480104.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g043480105.png" /> flops, respectively.

For numerical purposes it is not sufficient to ensure that the coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g043480106.png" />, etc., the pivots, are just non-zero, but they are the best possible; if the absolutely largest <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g043480107.png" /> is used as a pivot, then this is called partial pivoting. If the absolutely largest element in the entire matrix (or submatrix at later stages) is used as a pivot, this is being called complete pivoting. Partial pivoting to make LU-decomposition possible in case the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g043480108.png" /> has singular leading principal submatrices amounts to interchanging rows. It requires <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043480/g043480109.png" /> comparisons. With such a strategy the method can be shown to be numerically stable (see [[Stability of a computational algorithm|Stability of a computational algorithm]]; [[Stability of a computational process|Stability of a computational process]]).

An excellent book on numerical linear algebra is [[#References|[a1]]]. The problem of numerical stability in Gaussian elimination is discussed in [[#References|[a6]]].

Fortan routines can be found in [[#References|[a4]]]; for an older Algol version see [[#References|[a5]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G.H. Golub,   C.F. van Loan,   "Matrix computations" , North Oxford Acad.  (1983)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J.H. Wilkinson,   "The algebraic eigenvalue problem" , Clarendon Press  (1965)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G. Strang,   "Linear algebra and its application" , Acad. Press  (1976)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  H. Dongarra,   J.R. Bunch,   C.B. Moler,   G.W. Stewart,   "LINPACK users guide" , SIAM  (1978)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  J.H. Wilkinson,   C. Reinsch,   "Handbook for automatic computation" , '''2. Linear algebra''' , Springer  (1971)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  P.A. Bussinger,   "Monotoring the numerical stability of Gaussian elimination"  ''Numer. Math.'' , '''16'''  (1971)  pp. 360–361</TD></TR></table>