# Row echelon form

(Redirected from Reduced row echelon form)

In linear algebra, a matrix is in echelon form if it has the shape resulting from a Gaussian elimination.

A matrix being in row echelon form means that Gaussian elimination has operated on the rows, and column echelon form means that Gaussian elimination has operated on the columns. In other words, a matrix is in column echelon form if its transpose is in row echelon form. Therefore, only row echelon forms are considered in the remainder of this article. The similar properties of column echelon form are easily deduced by transposing all the matrices. Specifically, a matrix is in row echelon form if

• All rows consisting of only zeroes are at the bottom.[1]
• The leading entry (that is the left-most nonzero entry) of every nonzero row is to the right of the leading entry of every row above.[2]

Some texts add the condition that the leading coefficient must be 1[3] while others regard this as reduced row echelon form.

These two conditions imply that all entries in a column below a leading coefficient are zeros.[4]

The following is an example of a 4x5 matrix in row echelon form, which is not in reduced row echelon form (see below):

${\displaystyle \left[{\begin{array}{ccccc}1&a_{0}&a_{1}&a_{2}&a_{3}\\0&0&2&a_{4}&a_{5}\\0&0&0&1&a_{6}\\0&0&0&0&0\end{array}}\right]}$

Many properties of matrices may be easily deduced from their row echelon form, such as the rank and the kernel.

## Reduced row echelon form

A matrix is in reduced row echelon form (also called row canonical form) if it satisfies the following conditions:[5]

• It is in row echelon form.
• The leading entry in each nonzero row is a 1 (called a leading 1).
• Each column containing a leading 1 has zeros in all its other entries.

The reduced row echelon form of a matrix may be computed by Gauss–Jordan elimination. Unlike the row echelon form, the reduced row echelon form of a matrix is unique and does not depend on the algorithm used to compute it.[6] For a given matrix, despite the row echelon form not being unique, all row echelon forms and the reduced row echelon form have the same number of zero rows and the pivots are located in the same indices.[6]

This is an example of a matrix in reduced row echelon form, which shows that the left part of the matrix is not always an identity matrix:

${\displaystyle \left[{\begin{array}{ccccc}1&0&a_{1}&0&b_{1}\\0&1&a_{2}&0&b_{2}\\0&0&0&1&b_{3}\end{array}}\right]}$

For matrices with integer coefficients, the Hermite normal form is a row echelon form that may be calculated using Euclidean division and without introducing any rational number or denominator. On the other hand, the reduced echelon form of a matrix with integer coefficients generally contains non-integer coefficients.

## Transformation to row echelon form

By means of a finite sequence of elementary row operations, called Gaussian elimination, any matrix can be transformed to row echelon form. Since elementary row operations preserve the row space of the matrix, the row space of the row echelon form is the same as that of the original matrix.

The resulting echelon form is not unique; any matrix that is in echelon form can be put in an (equivalent) echelon form by adding a scalar multiple of a row to one of the above rows, for example:

${\displaystyle {\begin{bmatrix}1&3&-1\\0&1&7\\\end{bmatrix}}{\xrightarrow {\text{add row 2 to row 1}}}{\begin{bmatrix}1&4&6\\0&1&7\\\end{bmatrix}}.}$

However, every matrix has a unique reduced row echelon form. In the above example, the reduced row echelon form can be found as

${\displaystyle {\begin{bmatrix}1&3&-1\\0&1&7\\\end{bmatrix}}\xrightarrow {{\text{subtract 3}}\times {\text{(row 2) from row 1}}} {\begin{bmatrix}1&0&-22\\0&1&7\\\end{bmatrix}}.}$

This means that the nonzero rows of the reduced row echelon form are the unique reduced row echelon generating set for the row space of the original matrix.

## Systems of linear equations

A system of linear equations is said to be in row echelon form if its augmented matrix is in row echelon form. Similarly, a system of linear equations is said to be in reduced row echelon form or in canonical form if its augmented matrix is in reduced row echelon form.

The canonical form may be viewed as an explicit solution of the linear system. In fact, the system is inconsistent if and only if one of the equations of the canonical form is reduced to 0 = 1.[7] Otherwise, regrouping in the right hand side all the terms of the equations but the leading ones, expresses the variables corresponding to the pivots as constants or linear functions of the other variables, if any.

## Pseudocode for reduced row echelon form

The following pseudocode converts a matrix into a reduced row echelon form:

function ToReducedRowEchelonForm(Matrix M) is
rowCount := the number of rows in M
columnCount := the number of columns in M
for 0 ≤ r < rowCount do
if columnCount ≤ lead then
stop function
end if
i = r
while M[i, lead] = 0 do
i = i + 1
if rowCount = i then
i = r
if columnCount = lead then
stop function
end if
end if
end while
if i ≠ r then Swap rows i and r
Divide row r by M[r, lead]
for 0 ≤ j < rowCount do
if j ≠ r do
Subtract M[j, lead] multiplied by row r from row j
end if
end for
end for
end function


The following pseudocode converts the matrix to a row echelon form (not reduced):

function ToRowEchelonForm(Matrix M) is
nr := number of rows in M
nc := number of columns in M

for 0 ≤ r < nr do
allZeros := true
for 0 ≤ c < nc do
if M[r, c] != 0 then
allZeros := false
exit for
end if
end for
if allZeros = true then
In M, swap row r with row nr
nr := nr - 1
end if
end for

p := 0
while p < nr and p < nc do
label nextPivot:
r := 1
while M[p, p] = 0 do
if (p + r) <= nr then
p := p + 1
goto nextPivot
end if
In M, swap row p with row (p + r)
r := r + 1
end while
for 1 ≤ r < (nr - p) do
if M[p + r, p] != 0 then
x := -M[p + r, p] / M[p, p]
for p ≤ c < nc do
M[p + r, c] := M[p , c] * x + M[p + r, c]
end for
end if
end for
p := p + 1
end while
end function


## Notes

1. ^ Phrased in terms of each individual zero row in Leon (2010, p. 13):"A matrix is said to be in row echelon form ... (iii) If there are rows whose entries are all zero, they are below the rows having nonzero entries."
2. ^ Leon (2010, p. 13):"A matrix is said to be in row echelon form ... (ii) If row k does not consist entirely of zeros, the number of leading zero entries in row ${\displaystyle k+1}$  is greater than the number of leading zero entries in row k."
3. ^ See, for instance, the first clause of the definition of row echelon form in Leon (2010, p. 13): "A matrix is said to be in row echelon form (i) If the first nonzero entry in each nonzero row is 1."
4. ^ Meyer 2000, p. 44
5. ^ Meyer 2000, p. 48
6. ^ a b Anton, Howard; Rorres, Chris (2013-10-23). Elementary Linear Algebra: Applications Version, 11th Edition. Wiley Global Education. p. 21. ISBN 9781118879160.
7. ^ Cheney, Ward; Kincaid, David R. (2010-12-29). Linear Algebra: Theory and Applications. Jones & Bartlett Publishers. pp. 47–50. ISBN 9781449613525.

## References

• Leon, Steven J. (2010), Lynch, Deirdre; Hoffman, William; Celano, Caroline (eds.), Linear Algebra with Applications (8th ed.), Pearson, ISBN 978-0-13-600929-0, A matrix is said to be in row echelon form (i) If the first nonzero entry in each nonzero row is 1. (ii) If row k does not consist entirely of zeros, the number of leading zero entries in row ${\displaystyle k+1}$  is greater than the number of leading zero entries in row k. (iii) If there are rows whose entries are all zero, they are below the rows having nonzero entries..
• Meyer, Carl D. (2000), Matrix Analysis and Applied Linear Algebra, SIAM, ISBN 978-0-89871-454-8.