reduced row echelon form

In mathematics, a matrix is in reduced row echelon form (also known as row canonical form - the resulting matrix is sometimes called a Hermite matrix) if it satisfies the following requirements:

• All nonzero rows are above any rows of all zeroes.
• The leading coefficient of a row is always to the right of the leading coefficient of the row above it.
• All leading coefficients are 1.
• All entries above a leading coefficient in the same column are zero.

It is readily seen that these conditions are stronger than those for row echelon form. Therefore, every matrix in reduced row echelon form is in row echelon form.

Unlike row echelon form, every matrix reduces to a unique matrix in reduced row echelon form by elementary row operations (see Elementary matrix transformations). The reduced row echelon form of a matrix completely and uniquely determines its row space.

Examples

The following matrix is in reduced row echelon form:

However, the following matrix is not in reduced row echelon form, as the leading 1 in the third row is not the only nonzero entry in its column:

Pseudocode

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

ToReducedRowEchelonForm(Matrix M)
{
  int lead = 0;
  for(int row = 0; row < M.rowCount; row++) {
    int i = row;
    while(ABS(M[i, lead]) < 1e-12) {
      if(++i >= M.rowCount) {
        i = row;
        if(++lead >= M.columnCount)
          return;
        }
    }
    M.SwapRows(i, row);
    M.row(row) *= 1.0 / M[row, lead];
    for(i = 0; i < M.rowCount; i++)
      if(i != row)
        M.row(i) += ((-M[i, lead]) * M.row(row));
    lead++;
  }
}

See also

• Gaussian elimination
• Gauss–Jordan elimination
• Row echelon form

External links

• MIT Linear Algebra Lecture on Row Reduced Form at Google Video, from MIT OpenCourseWare
• Calculate the reduced row echelon form online
• Module for Row Reduce Echelon Form

Donate to Wikimedia