# row reduction

Row reduction, also known as Gaussian elimination, is an algorithm for solving a system of linear equations

 $\begin{array}[]{ccccccccl}a_{11}x_{1}&+&a_{12}x_{2}&+&\ldots&+&a_{1m}x_{m}&=&b% _{1}\\ a_{21}x_{1}&+&a_{22}x_{2}&+&\ldots&+&a_{2m}x_{m}&=&b_{2}\\ \vdots&&\vdots&&\ddots&&\vdots&&\vdots\\ a_{n1}x_{1}&+&a_{n2}x_{2}&+&\ldots&+&a_{nm}x_{m}&=&b_{n}\\ \end{array}$

To describe row reduction, it is convenient to formulate a linear system as a single matrix-vector equation $Ax=b,$ where

 $A=\begin{bmatrix}a_{11}&a_{12}&\cdots&a_{1m}\\ a_{21}&a_{22}&\cdots&a_{2m}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\cdots&a_{nm}\end{bmatrix},\qquad b=\begin{bmatrix}b_{1}\\ b_{2}\\ \vdots\\ b_{n}\end{bmatrix},\qquad x=\begin{bmatrix}x_{1}\\ x_{2}\\ \vdots\\ x_{m}\end{bmatrix}$

are, respectively, the $n\times m$ matrix of coefficients of the linear system, the $n$-place column vector  of the scalars from the right-hand 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

 $\begin{bmatrix}A&b\end{bmatrix}=\begin{bmatrix}a_{11}&a_{12}&\cdots&a_{1m}&b_{% 1}\\ a_{21}&a_{22}&\cdots&a_{2m}&b_{2}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ a_{n1}&a_{n2}&\cdots&a_{nm}&b_{n}\end{bmatrix}=\begin{bmatrix}R_{1}\\ R_{2}\\ \vdots\\ R_{n},\end{bmatrix}$

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 cR_{i},\quad c\neq 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}+cR_{j},\quad c\neq 0,\;i\neq 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 non-singular (), then the algorithm will terminate when the augmented matrix has the following form:

 $\begin{bmatrix}a^{\prime}_{11}&a^{\prime}_{12}&\cdots&a^{\prime}_{1n}&b_{1}\\ 0&a_{22}^{\prime}&\cdots&a_{2n}^{\prime}&b_{2}^{\prime}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&a_{nn}^{\prime}&b_{n}^{\prime}\end{bmatrix}$

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 non-zero entry of some row. We then have

A variant of Gaussian elimination is Gauss-Jordan 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, Gauss-Jordan elimination performs the back substitution; the values of the unknowns can be read off directly from the terminal augmented matrix. Not surprisingly, Gauss-Jordan elimination is slower than Gaussian elimination. It is useful, however, for solving systems on paper.

 Title row reduction Canonical name RowReduction Date of creation 2013-03-22 12:06:48 Last modified on 2013-03-22 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 Gauss-Jordan elimination Related topic RowEchelonForm Related topic ReducedRowEchelonForm Related topic ElementaryMatrix Defines pivot Defines row operation Defines row exchange Defines row replacement Defines row scaling