row reduction
Row reduction, also known as Gaussian elimination, is an algorithm for solving a system of linear equations
$$\begin{array}{ccccccccc}\hfill {a}_{11}{x}_{1}\hfill & \hfill +\hfill & \hfill {a}_{12}{x}_{2}\hfill & \hfill +\hfill & \hfill \mathrm{\dots}\hfill & \hfill +\hfill & \hfill {a}_{1m}{x}_{m}\hfill & \hfill =\hfill & {b}_{1}\hfill \\ \hfill {a}_{21}{x}_{1}\hfill & \hfill +\hfill & \hfill {a}_{22}{x}_{2}\hfill & \hfill +\hfill & \hfill \mathrm{\dots}\hfill & \hfill +\hfill & \hfill {a}_{2m}{x}_{m}\hfill & \hfill =\hfill & {b}_{2}\hfill \\ \hfill \mathrm{\vdots}\hfill & & \hfill \mathrm{\vdots}\hfill & & \hfill \mathrm{\ddots}\hfill & & \hfill \mathrm{\vdots}\hfill & & \mathrm{\vdots}\hfill \\ \hfill {a}_{n1}{x}_{1}\hfill & \hfill +\hfill & \hfill {a}_{n2}{x}_{2}\hfill & \hfill +\hfill & \hfill \mathrm{\dots}\hfill & \hfill +\hfill & \hfill {a}_{nm}{x}_{m}\hfill & \hfill =\hfill & {b}_{n}\hfill \end{array}$$ 
To describe row reduction, it is convenient to formulate a linear system as a single matrixvector equation $Ax=b,$ where
$$A=\left[\begin{array}{cccc}\hfill {a}_{11}\hfill & \hfill {a}_{12}\hfill & \hfill \mathrm{\cdots}\hfill & \hfill {a}_{1m}\hfill \\ \hfill {a}_{21}\hfill & \hfill {a}_{22}\hfill & \hfill \mathrm{\cdots}\hfill & \hfill {a}_{2m}\hfill \\ \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\ddots}\hfill & \hfill \mathrm{\vdots}\hfill \\ \hfill {a}_{n1}\hfill & \hfill {a}_{n2}\hfill & \hfill \mathrm{\cdots}\hfill & \hfill {a}_{nm}\hfill \end{array}\right],b=\left[\begin{array}{c}\hfill {b}_{1}\hfill \\ \hfill {b}_{2}\hfill \\ \hfill \mathrm{\vdots}\hfill \\ \hfill {b}_{n}\hfill \end{array}\right],x=\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \\ \hfill \mathrm{\vdots}\hfill \\ \hfill {x}_{m}\hfill \end{array}\right]$$ 
are, respectively, the $n\times m$ matrix of coefficients of the linear system, the $n$place column vector^{} of the scalars from the righthand of the equations, and the $m$place column vector of unknowns.
The method consists of combining the coefficient matrix $A$ with the right hand vector $b$ to form the “augmented” $n\times (m+1)$ matrix
$$\left[\begin{array}{cc}\hfill A\hfill & \hfill b\hfill \end{array}\right]=\left[\begin{array}{ccccc}\hfill {a}_{11}\hfill & \hfill {a}_{12}\hfill & \hfill \mathrm{\cdots}\hfill & \hfill {a}_{1m}\hfill & \hfill {b}_{1}\hfill \\ \hfill {a}_{21}\hfill & \hfill {a}_{22}\hfill & \hfill \mathrm{\cdots}\hfill & \hfill {a}_{2m}\hfill & \hfill {b}_{2}\hfill \\ \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\ddots}\hfill & \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\vdots}\hfill \\ \hfill {a}_{n1}\hfill & \hfill {a}_{n2}\hfill & \hfill \mathrm{\cdots}\hfill & \hfill {a}_{nm}\hfill & \hfill {b}_{n}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill {R}_{1}\hfill \\ \hfill {R}_{2}\hfill \\ \hfill \mathrm{\vdots}\hfill \\ \hfill {R}_{n},\hfill \end{array}\right]$$ 
where each ${R}_{i}$ is the $m+1$place row vector corresponding to row $i$ of the augmented matrix.
A sequence of elementary row operations is then applied to this matrix so as to transform it to row echelon form^{}. The elementary operations are:

•
row scaling: the multiplication a row by a nonzero scalar;
$${R}_{i}\mapsto c{R}_{i},c\ne 0;$$ 
•
row exchange: the exchanges of two rows;
$${R}_{i}\leftrightarrow {R}_{j};$$ 
•
row replacement: the addition of a multiple of one row to another row;
$${R}_{i}\mapsto {R}_{i}+c{R}_{j},c\ne 0,i\ne j.$$
Note that these operations^{} are “legal” because $x$ is a solution of the transformed system if and only if it is a solution of the initial system.
If the number of equations equals the number of variables ($m=n$), and if the coefficient matrix $A$ is nonsingular (http://planetmath.org/singular^{}), then the algorithm will terminate when the augmented matrix has the following form:
$$\left[\begin{array}{ccccc}\hfill {a}_{11}^{\prime}\hfill & \hfill {a}_{12}^{\prime}\hfill & \hfill \mathrm{\cdots}\hfill & \hfill {a}_{1n}^{\prime}\hfill & \hfill {b}_{1}\hfill \\ \hfill 0\hfill & \hfill {a}_{22}^{\prime}\hfill & \hfill \mathrm{\cdots}\hfill & \hfill {a}_{2n}^{\prime}\hfill & \hfill {b}_{2}^{\prime}\hfill \\ \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\ddots}\hfill & \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\vdots}\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill \mathrm{\cdots}\hfill & \hfill {a}_{nn}^{\prime}\hfill & \hfill {b}_{n}^{\prime}\hfill \end{array}\right]$$ 
With these assumptions^{}, there exists a unique solution, which can be obtained from the above matrix by back substitution.
For the general case, the termination procedure is somewhat more complicated. First recall that a matrix is in echelon form if each row has more leading zeros than the rows above it. A pivot is the leading nonzero entry of some row. We then have

•
If there is a pivot in the last column, the system is inconsistent ; there will be no solutions.

•
If that is not the case, then the general solution will have $d$ degrees of freedom, where $d$ is the number of columns from $1$ to $m$ that have no pivot. To be more precise, the general solution will have the form of one particular solution plus an arbitrary linear combination^{} of $d$ linearly independent^{} $n$vectors.
In even more prosaic language^{}, the variables in the nonpivot columns are to be considered “free variables^{}” and should be “moved” to the righthand side of the equation. The general solution is then obtained by arbitrarily choosing values of the free variables, and then solving for the remaining “nonfree” variables that reside in the pivot columns.
A variant of Gaussian elimination is GaussJordan elimination. In this variation we reduce to echelon form, and then if the system proves to be consistent, continue to apply the elementary row operations until the augmented matrix is in reduced echelon form. This means that not only does each pivot have all zeroes below it, but that each pivot also has all zeroes above it.
In essence, GaussJordan elimination performs the back substitution; the values of the unknowns can be read off directly from the terminal augmented matrix. Not surprisingly, GaussJordan elimination is slower than Gaussian elimination. It is useful, however, for solving systems on paper.
Title  row reduction 
Canonical name  RowReduction 
Date of creation  20130322 12:06:48 
Last modified on  20130322 12:06:48 
Owner  rmilson (146) 
Last modified by  rmilson (146) 
Numerical id  18 
Author  rmilson (146) 
Entry type  Algorithm 
Classification  msc 15A06 
Synonym  Gaussian elimination 
Synonym  GaussJordan elimination 
Related topic  RowEchelonForm 
Related topic  ReducedRowEchelonForm 
Related topic  ElementaryMatrix 
Defines  pivot 
Defines  row operation 
Defines  row exchange 
Defines  row replacement 
Defines  row scaling 