Reduced Row Echelon Form and Applications to Matrix Arithmetic

by Justin Skycak (x.com/justinskycak) on March 02, 2021

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

This post is part of the book Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. Suggested citation: Skycak, J. (2021). Reduced Row Echelon Form and Applications to Matrix Arithmetic. In Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. https://justinmath.com/reduced-row-echelon-form-and-applications-to-matrix-arithmetic/

Want to get notified about new posts? Join the mailing list.

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


row_index = 0

for each column:
  if pivot row exists for column:

    if pivot row does not match current row_index:
      swap current row with pivot row
      (so that it matches)

    divide pivot row (so that first nonzero entry is 1)
        
    clear entries below and above pivot entry
    (by subtracting multiples of 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.

Again, we will jump straight to exercises – it is assumed that you are already familiar with matrix arithmetic and reduced row echelon form.

Exercise: RREF with Helper Functions

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 often a 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 (and fail) to break the function that you wrote.

Once you’ve written the helper functions, you can stitch them together into the full RREF algorithm.

Exercise: Inverse via RREF

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

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

Exercise: Determinant via RREF

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 “build up” the determinant along the way.

Want to get notified about new posts? Join the mailing list.