Row echelon form

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (July 2010)

In linear algebra a matrix is in row echelon form if

• All nonzero rows (rows with at least one nonzero element) are above any rows of all zeroes [All zero rows, if any, belong at the bottom of the matrix]
• The leading coefficient (the first nonzero number from the left, also called the pivot) of a nonzero row is always strictly to the right of the leading coefficient of the row above it.
• All entries in a column below a leading entry are zeroes (implied by the first two criteria).^[1]

This is an example of 3×4 matrix in row echelon form:

A matrix is in reduced row echelon form (also called row canonical form) if it satisfies the additional condition:

• Every leading coefficient is 1 and is the only nonzero entry in its column,^[2] like in this example:

Note that this does not always mean that the left of the matrix will be an identity matrix. For example, the following matrix is also in reduced row-echelon form:

Transformation to row echelon form

By means of a finite sequence of elementary row operations, 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; for example, any multiple of a matrix in echelon form is also in echelon form. However, it is the case that every matrix has a unique reduced row echelon form. 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 equations is said to be in reduced row echelon form or canonical form if its augmented matrix is in reduced row echelon form.

Pseudocode

This section may contain original research. Please improve it by verifying the claims made and adding references. Statements consisting only of original research may be removed. More details may be available on the talk page. (September 2011)

The following pseudocode converts a matrix to (non-reduced) row-echelon form^{[citation needed]}:

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 - 1
            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) <-- bug. nr < p+r at this point
                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

See also

• Gaussian elimination
• Gauss–Jordan elimination

Notes

References

• Meyer, Carl D. (2000), Matrix Analysis and Applied Linear Algebra, SIAM, ISBN 978-0-89871-454-8, http://www.matrixanalysis.com/ .

External links

• Interactive Row Echelon Form with rational output

The Wikibook Linear Algebra has a page on the topic of Row Reduction and Echelon Forms