Expert: Scott A Wilson - 11/1/2009

Question
Hi Scott,

Could you help me create a MATLAB program that reduces ANY 5x5 matrix to its reduced row echelon form without using rref? Below is the pseudocode... this is all I have and not sure how accurate.
%This function uses Gauss' Elimination to reduce any 5x % matrix to its
%reduced row echelon form
function ReducedREF(myMatrix)
lead := 0
rowCount := the number of rows in myMatrix
columnCount := the number of columns in myMatrix
for r < 0 < rowCount
   if columnCount < lead
       stop;
   end if
       i = r;
       while myMatrix;
           [i, lead] = 0;
           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 myMatrix[r, lead]
                   for 0 <= i < rowCount do
                       if i ~= r do
                           Subtract myMatrix[i, lead] multiplied by row r from row i
                       end if
                       end for
                           lead = lead + 1
                       end for
                       end function

Thanks so much for all of your help.

Evelyn


Answer
I've never programmed in MATLAB, but after a few questions, I should learn.
I like to space two spaces in for each operation we're doing.
The 'end' should go in just one space farther than what it is ending.
I aslo like to put comments about the program in.
In C++, // signifies that the rest of the line is a comment.
Using MatLab, it looks like comments are started with %

As far as that, here is how I read the program:

function ReducedREF(myMatrix)
 rowCount := the number of rows in myMatrix
 columnCount := the number of columns in myMatrix
 for r = 0 to rowCount-1
   if columnCount < lead   % stops the program at the end
     stop;
    end if

   i = r;
   while myMatrix;
     [i, lead] = 0;            % checks for a 0 at the start
     i = i + 1
     if rowCount = i then
       i = r
       lead = lead + 1
       if columnCount = lead then   // if on last row of matrix, end
         stop
        end if
      end if
    end while

   Swap rows i and r
   Divide row r by myMatrix[r, lead]

   for 0 <= i < rowCount do
     if i ~= r do
       Subtract myMatrix[i, lead] multiplied by row r from row i
      end if
     end for
   lead = lead + 1
  end for
end function

Problems:
 When a 0 is checked for at the start, it needs to increment i until a row with a 0 is found.
 Once this has been found, swap the two rows.

Improvements
 I would use a for r=1 to rowCount.
 Where a zero was found at the critical element, swap the two rows.
 After this was done, proceed to zero the rest of the rows in that element out.
 I would also have a 5x10 matrix.  That would be a 5x5 added on at the end that started as a
 5x5 identity matrix.  This would give the inverse of the matrix as well.


Here is my version of pseudocode, almost in C++:
// m = matrix passed
// rc = row count
// cc = column count
constant
 rowCount
 colCount

void reduce_matrix (rc, cc)
 r=1;
 c=1;
 i=r;   // which row is being worked on

 for (r=1 to rowCount) do
   % finds which element in that column to work on
   while (m[i,c]=0)
     r++; // add one to r
     if r>rowCount
       c++; r=i;    // try the next column over
       if c>colCount
         exit with error "Not Invertible"
        end if
      end if
    end while

   if r<rowCount and c<colCount
     % this is done if the row being worked on has a zero at the key spot
     if r<>i SwapRows (row(i),row(r))   % swaps row i and row r

     for (j=r+1 to rowCount)
       Make_A_Zero (row(j), row(i))   % makes zeros below the nonzero element in proper column
      end for
    end if

Again, like any program, it has errors that would need to be taken out.
Also, I believe that it is like your code and only puts the matrix in row echelon form
since it does not worry about what's over the element.