Reduced Row Echelon Form and Applications to Matrix Arithmetic

Recall the following procedure for converting a matrix to reduced row echelon form (RREF):


row_index = 0

for each column:
    if a pivot row exists for the column:

        if the pivot row does not match the current row_index:
            swap the current row with the pivot row so that it now matches

        divide the pivot row so that the first nonzero entry is 1
        
        clear all entries below and above the pivot entry by subtracting appropriate multiples of the pivot row

        row_index += 1


This algorithm is a bit tricky, so before you attempt to implement anything, be sure to work out the above algorithm by hand on several concrete examples until you feel comfortable with it.

Once you’re comfortable working out the algorithm by hand, write some helper functions.

  • For example, the first helper method you'll need to write will check whether a pivot row exists for a particular column in a matrix. If it does exist, then return the index of the row. Otherwise, return nothing.
  • There are at least $3$ other helper methods that you'll need to write. But don't stop thinking once you come up with $3$ helper methods. Keep going until you think you've really narrowed down the problem to its atomic sub-procedures.

It’s a often good idea to write tests for your helper functions and get them passing before you start trying to use them together, especially when you’re fairly new to coding. In your tests, be sure to consider a variety of matrices that are substantially different from each other. When writing tests, your goal is to try to break the function that you wrote.

Once you’ve written a working RREF algorithm, you can use it to implement a method that computes the inverse of a matrix. Remember that to compute the inverse of a square matrix $A,$ you can just

  1. augment the matrix as $[A | I]$ where $I$ is the identity matrix,
  2. run RREF on the augmented matrix to convert it to $[I | A^{-1}],$ and then
  3. read $A^{-1}$ on the right-hand side.

You can also use the RREF algorithm to compute determinants much faster than with the recursive cofactor expansion method.

  • Whenever you divide a row by some amount during the RREF algorithm, the determinant gets divided by that same amount.
  • Whenever you swap two rows during the RREF algorithm, the determinant switches sign (from positive to negative or vice versa).
  • At the end of the RREF algorithm, the final matrix has a determinant of $1.$
  • So, you can "build up" the determinant during the execution of the RREF algorithm by keeping track of the product of the numbers you divide by and switching the sign every time you swap two rows.

To avoid cluttering up your RREF algorithm, it is advisable to just copy-paste it into a new determinant method and then make whatever adjustments you need to in order to “build up” the determinant along the way.

Leave a Comment