Row echelon form

From Wikipedia, the free encyclopedia

In linear algebra a matrix is in row echelon form if

  • All nonzero rows are above any rows of all zeroes, and
  • The leading coefficient of a row is always strictly to the right of the leading coefficient of the row above it.

This is the definition used in this article, but some texts add a third condition:

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

A matrix is in reduced row echelon form (also called row canonical form) if it satisfies the above three conditions, and if, in addition

  • Every leading coefficient is the only nonzero entry in its column.

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

Contents

[edit] Examples

This matrix is in reduced row echelon form:

\begin{bmatrix} 0 & 1 & 4 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix}

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

\begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 9 & 0 & 2 \\ 0 & 0 & 0 & 3 \\ \end{bmatrix}

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.

\begin{bmatrix} 1 & 2 & 3 & 4 \\ 0 & 3 & 7 & 2 \\ 0 & 2 & 0 & 0 \\ \end{bmatrix}

[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 echelon form if its augmented matrix is in row echelon form. Similarly, a system of equations is said to be in reduced 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:

ToReducedRowEchelonForm(Matrix M)
  Let lead = 0
  Let rowCount be the number of rows in M
  Let columnCount be the number of columns in M
  FOR r = 0 to rowCount - 1
    IF columnCount <= lead
      STOP
    END IF
    Let i = r
    WHILE M[i, lead] = 0
      Increment i
      IF rowCount = i
        Let i = r
        Increment lead
        IF columnCount = lead
          STOP
        END IF
      END IF
    END WHILE
    Swap rows i and r
    Divide row r by M[r, lead]
    FOR all rows i, from 0 to number of rows, every row except r
      Subtract M[i, lead] multiplied by row r from row i
    END FOR
    Increment lead
  END FOR
END ToReducedRowEchelonForm

[edit] See also

[edit] Notes

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