Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Reduced row echelon form

Is there a function in R that produces the reduced row echelon form of a matrix?. This reference says there isn't. Do you agree?

like image 668
George Dontas Avatar asked Jun 27 '10 08:06

George Dontas


People also ask

What is the reduced row echelon form?

Definition of reduced row echelon form Definition We say that a matrix is in reduced row echelon form if and only if it is in row echelon form, all its pivots are equal to 1 and the pivots are the only non-zero entries of the basic columns.

What is the difference between row echelon form and reduced row echelon form?

Essentially the difference between the two forms is that the reduced echelon form has 1 as a leading entry, and the column of the leading entry has 0's below and above. The pivot position is just the leading entries of the echelon form matrix. The pivot column is the column of the pivot position.

What is reduced column echelon form?

A matrix is in a reduced column echelon form (RCEF) if it is in CEF and, additionally, any row containing the leading one of a column consists of all zeros except this leading one. In examples of matrices in CEF above, first and third matrices are in RCEF, and the second is not.

Why do we need reduced row echelon form?

The row echelon or the column echelon form of a matrix is important because it lets you easily determine if the system of linear equations corresponding to the augmented matrix is solvable.


1 Answers

I don't have enough rep to comment, but the function given above by soldier.moth in the accepted answer [edit 2018: no longer the accepted answer] is buggy - it doesn't handle matrices where the RREF solution has zeroes on its main diagonal. Try e.g.

m<-matrix(c(1,0,1,0,0,2),byrow=TRUE,nrow=2) rref(m)

and note that the output is not in RREF.

I think I have it working, but you may want to check outputs for yourself:

rref <- function(A, tol=sqrt(.Machine$double.eps),verbose=FALSE,
                 fractions=FALSE){
  ## A: coefficient matrix
  ## tol: tolerance for checking for 0 pivot
  ## verbose: if TRUE, print intermediate steps
  ## fractions: try to express nonintegers as rational numbers
  ## Written by John Fox
  # Modified by Geoffrey Brent 2014-12-17 to fix a bug
  if (fractions) {
    mass <- require(MASS)
    if (!mass) stop("fractions=TRUE needs MASS package")
  }
  if ((!is.matrix(A)) || (!is.numeric(A)))
    stop("argument must be a numeric matrix")
  n <- nrow(A)
  m <- ncol(A)
  x.position<-1
  y.position<-1
  # change loop:
  while((x.position<=m) & (y.position<=n)){
    col <- A[,x.position]
    col[1:n < y.position] <- 0
    # find maximum pivot in current column at or below current row
    which <- which.max(abs(col))
    pivot <- col[which]
    if (abs(pivot) <= tol) x.position<-x.position+1     # check for 0 pivot
    else{
      if (which > y.position) { A[c(y.position,which),]<-A[c(which,y.position),] } # exchange rows
      A[y.position,]<-A[y.position,]/pivot # pivot
      row <-A[y.position,]
      A <- A - outer(A[,x.position],row) # sweep
      A[y.position,]<-row # restore current row
      if (verbose)
        if (fractions) print(fractions(A))
        else print(round(A,round(abs(log(tol,10)))))
      x.position<-x.position+1
      y.position<-y.position+1
    }
  }
  for (i in 1:n)
    if (max(abs(A[i,1:m])) <= tol)
      A[c(i,n),] <- A[c(n,i),] # 0 rows to bottom
  if (fractions) fractions (A)
  else round(A, round(abs(log(tol,10))))
}
like image 93
Geoffrey Brent Avatar answered Nov 09 '22 01:11

Geoffrey Brent