Row echelon form

From Wikipedia, the free encyclopedia

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, and
• The leading coefficient (the first non-zero 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.

Some texts add a third condition:

• The leading coefficient of each nonzero row is 1.^[1]

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.

The first non-zero entry in each row is called a pivot.

Contents 1 Examples 2 Non-uniqueness 3 Systems of linear equations 4 Pseudocode 5 See also 6 Notes

[edit] Examples

This matrix is in reduced row echelon form:

The following matrix is also in row echelon form, but not in reduced row form:

However, this matrix is not in row echelon form, as the leading coefficient of row 3 is not strictly to the right of the leading coefficient of row 2, and the main diagonal is not made up of only ones.

[edit] Non-uniqueness

Every non-zero matrix can be reduced to an infinite number of echelon forms (they can all be multiples of each other, for example) via elementary matrix transformations. However, all matrices and their row echelon forms correspond to exactly one matrix in reduced row echelon form.

[edit] 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.

[edit] Pseudocode

The following pseudocode converts a matrix to reduced row-echelon form:

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

[edit] See also

• Gaussian elimination
• Gauss–Jordan elimination

[edit] Notes

1. ^ See, for instance, Larson and Hostetler, Precalculus, 7th edition.