Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 62 ยท Linear Systems

Reduced Row Echelon Form

Learn reduced row echelon form: pivots, free variables, parametric solutions and a short RREF function in NumPy that you can reuse on any system.

Gaussian elimination turns a system into a staircase, and then you walk back up the stairs with back substitution. Reduced row echelon form (RREF) goes two steps further: it scales every pivot to 1 and clears the entries above each pivot as well. When the elimination is finished, the answer can simply be read off the matrix. There is nothing left to substitute.

RREF is also the cleanest way to understand systems with infinitely many solutions. The pivots tell you which unknowns are determined, the other unknowns are free, and the free ones become the parameters of the solution. In this lesson you will learn the rules, read solutions off RREF matrices by hand, and write a small rref function that you will reuse in later lessons on rank and the null space.

The four rules of RREF

A matrix is in reduced row echelon form when all of these hold:

  1. Every row of zeros is at the bottom.
  2. The first nonzero entry of each nonzero row (its leading entry or pivot) is 1.
  3. Each pivot lies strictly to the right of the pivot in the row above it.
  4. Each pivot is the only nonzero entry in its column.

Rules 1 and 3 give the staircase of plain echelon form. Rules 2 and 4 are the "reduced" part. A key fact: every matrix can be turned into RREF by row operations, and the RREF is unique. Two different people eliminating the same matrix in different orders still end up with the same final matrix. That uniqueness is what makes RREF a reliable fingerprint of a system.

Row operations never change the solutions

Swap Exchange two rows.
Scale Multiply a row by a nonzero number.
Add Add a multiple of one row to another.

Any sequence of these keeps the solution set exactly the same.

1 / 3

Reducing a matrix by hand

Take the augmented matrix of a small system. Its three equations are x + 2y + z = 3, 2x + 5y + 4z = 9 and x + 3y + 5z = 8.

Python Step by step to RREF

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first stage is ordinary Gaussian elimination. The second stage (the last four lines of code) is what makes the result reduced: starting from the bottom pivot, clear the entries above it, then move left. The left block ends up as the identity matrix, and the last column holds the solution x = 0, y = 1, z = 1. Plug the values back into all three equations to confirm. Reading a solution straight from the final column is the whole point of RREF.

Writing a reusable rref function

Doing this by hand gets old quickly. Here is a compact implementation that works on any matrix, square or not. It uses partial pivoting (it picks the largest entry in the column as the pivot, which keeps rounding errors small) and a tolerance, because after floating-point arithmetic a value that should be zero may be 1e-17.

Python A general rref function

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the second matrix the third row vanishes completely, and column 2 never receives a pivot. That is the signature of a matrix that does not have full rank.

Free variables and parametric solutions

Now the interesting case. Suppose the system has more unknowns than independent equations. The augmented matrix below stands for x1 + 2x2 + x3 + 3x4 = 5, 2x1 + 4x2 + 3x3 + 7x4 = 12 and x1 + 2x2 + 2x3 + 4x4 = 7. Look at the coefficients: the second equation minus twice the first equals the third minus the first, so one equation is redundant.

Python Pivots and free variables

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Columns 1 and 3 hold pivots, so x1 and x3 are determined. Columns 2 and 4 have none, so x2 and x4 are free: choose them as you like, and the pivot variables follow. Each nonzero row of the RREF is an equation with one pivot variable on the left. You solve that row for the pivot variable.

To build the full solution, set each free variable to a parameter (call them s and t), then write every pivot variable in terms of them. The result is a particular solution (all parameters 0) plus a combination of direction vectors, one per free variable. The directions are exactly the solutions of the homogeneous system Ax = 0, which is the null space you will study later.

Python From RREF to a parametric solution

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The test n in pivots deserves attention. If the augmented column receives a pivot, some row reads 0 = 1, and the system has no solution at all. This gives you the whole classification in one place:

  • a pivot in the b column: no solution;
  • a pivot in every unknown's column and none in b: exactly one solution;
  • at least one free column and none in b: infinitely many solutions.

RREF works with exact arithmetic on paper. In floating point, the line if abs(A[best, col]) < tol is a judgment call. If your data are noisy, a tolerance that is too small leaves phantom pivots and too large erases real ones. For serious numerical rank work, use the SVD-based tools from Rank rather than RREF.

Why RREF is worth knowing

Many questions reduce to "compute the RREF and look at it":

  • Rank: the number of pivots.
  • Is a vector in the span of others? Put the vectors in columns, append the target, and look for a pivot in the last column.
  • Are columns independent? They are when every column has a pivot.
  • Which columns form a basis of the column space? The pivot columns of the original matrix.
  • Inverse: row-reduce [A | I] and read A^-1 from the right half (see Inverse Matrices).

The last trick is short enough to try right now.

Python Inverse from RREF of [A | I]

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which extra condition separates reduced row echelon form from ordinary echelon form?

    Echelon form only needs the staircase shape. RREF additionally scales pivots to 1 and clears the entries above them.
  2. 2. An augmented matrix has pivots in columns 1 and 3 only, and the system has four unknowns. How many free variables are there?

    Columns 2 and 4 contain no pivot, so x2 and x4 are free. With no pivot in the b column, the system has infinitely many solutions.
  3. 3. After row reduction a row reads [0 0 0 | 5]. What does that mean?

    That row says 0 = 5, which is impossible, so the system is inconsistent.
  4. 4. Is the RREF of a matrix unique?

    Different elimination orders reach the same final matrix. That uniqueness is why pivot positions and rank are well defined.

Summary

  • RREF has pivots equal to 1, a staircase shape, zero rows at the bottom, and zeros above and below each pivot.
  • Row swaps, scaling and adding multiples of rows never change the solution set, and the RREF of a matrix is unique.
  • Pivot columns give determined unknowns; columns without pivots are free and become parameters.
  • A pivot in the augmented column means no solution; free columns without that mean infinitely many.
  • A short rref function with partial pivoting and a tolerance handles any matrix, and [A | I] reduces to [I | A^-1].

Next: let NumPy do the work in Solving Systems with NumPy.