Contents

5. RREF

It’s time to get more formal and precise about row elimination. We separate it into downward and upward phases. In what follows we use the term leading nonzero to mean the first (i.e., leftmost) entry of a row that is not zero.

Algorithm 5.1 (Row elimination downward phase)

  1. Set \(i=1\).

  2. Find the leftmost leading nonzero in rows \(i\) and below. The column of this leading nonzero is known as the pivot column. If no such column exists, stop.

  3. As necessary, swap rows and/or multiply a row by a constant to put a 1 in the pivot column of row \(i\).

  4. Add multiples of row \(i\) to the rows below it in order to put zeros into the pivot column.

  5. Increment \(i\) and return to step 2.

At the end of the downward phase, the augmented matrix has a pretty simple form. However, it’s not the cleanest form to work with theoretically, so we continue.

Algorithm 5.2 (Row elimination upward phase)

  1. Set \(i=m\) (the number of equations).

  2. Use multiples of row \(i\) to put zeros above the leading 1 in that row.

  3. Decrement \(i\). If \(i> 1\), return to step 2.

At the end of the upward phase, the matrix is in a form that we define formally here.

Definition 5.3 (RREF)

A matrix is in RREF (reduced row echelon form) if it meets all of these requirements:

  1. Any rows of all zeros appear below all nonzero rows.

  2. The leading nonzero of any row is a one.

  3. Every leading 1 that is lower than another leading 1 is also to the right of it.

  4. Every leading 1 is the only nonzero in its column.

The columns that have leading ones are called pivot columns. The other columns are called free columns.

Here is an example, using MATLAB to do the row operations for us. The linear system is characterized by

\[\begin{split} \bfA = \begin{bmatrix} 2 & 0 & 4 & 3 \\ -2 & 0 & 2 & -13 \\ -4 & 5 & -7 & -10 \\ 1 & 15 & 2 & -4.5 \end{bmatrix}, \qquad \bfb = \begin{bmatrix} 4\\40\\9\\29 \end{bmatrix}. \end{split}\]
A = [
     2    0    4    3 
    -2    0    2  -13
    -4    5   -7  -10 
     1   15    2   -4.5
    ];
b = [ 4; 40; 9; 29 ];

S = [A, b]

ans =

    '9.7.0.1296695 (R2019b) Update 4'

S =

  Columns 1 through 3

   2.000000000000000                   0   4.000000000000000
  -2.000000000000000                   0   2.000000000000000
  -4.000000000000000   5.000000000000000  -7.000000000000000
   1.000000000000000  15.000000000000000   2.000000000000000

  Columns 4 through 5

   3.000000000000000   4.000000000000000
 -13.000000000000000  40.000000000000000
 -10.000000000000000   9.000000000000000
  -4.500000000000000  29.000000000000000

We start at the top, working downward and rightward. In the first row, the leading nonzero occurs in column 1, which is the pivot column for this row. We normalize this row so that the leading nonzero is a 1.

S(1,:) = S(1,:)/S(1,1)

S =

  Columns 1 through 3

   1.000000000000000                   0   2.000000000000000
  -2.000000000000000                   0   2.000000000000000
  -4.000000000000000   5.000000000000000  -7.000000000000000
   1.000000000000000  15.000000000000000   2.000000000000000

  Columns 4 through 5

   1.500000000000000   2.000000000000000
 -13.000000000000000  40.000000000000000
 -10.000000000000000   9.000000000000000
  -4.500000000000000  29.000000000000000

Now multiples of row 1 are added to the rows below it in order to put zeros in the first column.

S(2,:) = S(2,:) - S(2,1)*S(1,:);
S(3,:) = S(3,:) - S(3,1)*S(1,:);
S(4,:) = S(4,:) - S(4,1)*S(1,:)

S =

  Columns 1 through 3

   1.000000000000000                   0   2.000000000000000
                   0                   0   6.000000000000000
                   0   5.000000000000000   1.000000000000000
                   0  15.000000000000000                   0

  Columns 4 through 5

   1.500000000000000   2.000000000000000
 -10.000000000000000  44.000000000000000
  -4.000000000000000  17.000000000000000
  -6.000000000000000  27.000000000000000

Looking at rows 2 to 4, we see that the leftmost nonzero occurs in column 2. Since row 2 has a zero there, we swap rows 2 and 3 to bring a nonzero up.

S(2:3,:) = S([3 2],:)

S =

  Columns 1 through 3

   1.000000000000000                   0   2.000000000000000
                   0   5.000000000000000   1.000000000000000
                   0                   0   6.000000000000000
                   0  15.000000000000000                   0

  Columns 4 through 5

   1.500000000000000   2.000000000000000
  -4.000000000000000  17.000000000000000
 -10.000000000000000  44.000000000000000
  -6.000000000000000  27.000000000000000

Now we normalize row 2 so that the leading nonzero is a 1.

S(2,:) = S(2,:)/S(2,2)

S =

  Columns 1 through 3

   1.000000000000000                   0   2.000000000000000
                   0   1.000000000000000   0.200000000000000
                   0                   0   6.000000000000000
                   0  15.000000000000000                   0

  Columns 4 through 5

   1.500000000000000   2.000000000000000
  -0.800000000000000   3.400000000000000
 -10.000000000000000  44.000000000000000
  -6.000000000000000  27.000000000000000

Multiples of row 2 are now used to put zeros below it in the pivot column.

S(3,:) = S(3,:) - S(3,2)*S(2,:);
S(4,:) = S(4,:) - S(4,2)*S(2,:)

S =

  Columns 1 through 3

   1.000000000000000                   0   2.000000000000000
                   0   1.000000000000000   0.200000000000000
                   0                   0   6.000000000000000
                   0                   0  -3.000000000000000

  Columns 4 through 5

   1.500000000000000   2.000000000000000
  -0.800000000000000   3.400000000000000
 -10.000000000000000  44.000000000000000
   6.000000000000000 -24.000000000000000

Rows 3 and 4 have a pivot in column 3, and we only need to normalize row 3 to make it 1. Then we subtract a multiple of row 3 from row 4 to put a zero beneath it.

S(3,:) = S(3,:)/S(3,3);
S(4,:) = S(4,:) - S(4,3)*S(3,:)

S =

  Columns 1 through 3

   1.000000000000000                   0   2.000000000000000
                   0   1.000000000000000   0.200000000000000
                   0                   0   1.000000000000000
                   0                   0                   0

  Columns 4 through 5

   1.500000000000000   2.000000000000000
  -0.800000000000000   3.400000000000000
  -1.666666666666667   7.333333333333333
   1.000000000000000  -2.000000000000000

We complete the downward phase by normalizing row 4 to get a leading 1.

S(4,:) = S(4,:)/S(4,4)

S =

  Columns 1 through 3

   1.000000000000000                   0   2.000000000000000
                   0   1.000000000000000   0.200000000000000
                   0                   0   1.000000000000000
                   0                   0                   0

  Columns 4 through 5

   1.500000000000000   2.000000000000000
  -0.800000000000000   3.400000000000000
  -1.666666666666667   7.333333333333333
   1.000000000000000  -2.000000000000000

Now we turn around for the upward phase. The leading 1 in row 4 needs to have zeros above it. We accomplish that by subtracting multiples of row 4 from the others.

S(3,:) = S(3,:) - S(3,4)*S(4,:);
S(2,:) = S(2,:) - S(2,4)*S(4,:);
S(1,:) = S(1,:) - S(1,4)*S(4,:)

S =

  Columns 1 through 3

   1.000000000000000                   0   2.000000000000000
                   0   1.000000000000000   0.200000000000000
                   0                   0   1.000000000000000
                   0                   0                   0

  Columns 4 through 5

                   0   5.000000000000000
                   0   1.800000000000000
                   0   4.000000000000000
   1.000000000000000  -2.000000000000000

We move up to row 3 and use multiples of it to put zeros above its leading 1.

S(2,:) = S(2,:) - S(2,3)*S(3,:);
S(1,:) = S(1,:) - S(1,3)*S(3,:)

S =

  Columns 1 through 3

   1.000000000000000                   0                   0
                   0   1.000000000000000                   0
                   0                   0   1.000000000000000
                   0                   0                   0

  Columns 4 through 5

                   0  -2.999999999999999
                   0   1.000000000000000
                   0   4.000000000000000
   1.000000000000000  -2.000000000000000

The last move is to use a multiple of row 2 to put a zero above its leading 1. As it has played out in this example, this line of code changes nothing because the position was already zero.

S(1,:) = S(1,:) - S(1,2)*S(2,:);

This matrix is in RREF. We interpret it as the trivial linear system

\[\begin{align*} x_1 &= -3,\\ x_2 &= 1,\\ x_3 &= 4, \\ x_4 &= -2. \end{align*}\]

Warning

MATLAB has a command rref to put a matrix in RREF. However, it’s not ideal, because MATLAB uses floating point and cannot always produce exact zeros. You can instead try Wolfram Alpha for finding the exact RREF.

5.1. Solution from the RREF

The RREF of an augmented matrix represents a linear system that we can solve by inspection:

  1. Ignore all zero rows.

  2. If a leading one occurs in the last column, the system is inconsistent.

  3. Otherwise, each variable associated with a free column is assigned to a free parameter (e.g., \(s\), \(t\), etc.).

  4. Use the pivot columns to solve for their corresponding variables in terms of the free parameters.

Example

A linear system has an augmented matrix equivalent to the RREF

\[\begin{split} \begin{bmatrix} 0 & 1 & -3 & 0 & 2 \\ 0 & 0 & 0 & 1 & -4 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}. \end{split}\]

Find all solutions to the linear system.

Solution

The last two rows have no information and can be ignored. Columns 2 and 4 are pivot columns. We give variables from the other columns arbitrary values, \(x_1=s\) and \(x_3=t\). The pivot variables are solved in terms of these to get \(x_2=2+3t\) and \(x_4=-4\). All solutions are expressed as the vector

\[\begin{split} \bfx = \begin{bmatrix} s \\ 2+3t \\ t \\ -4 \end{bmatrix}, \qquad s,t\in \real. \end{split}\]

Example

A linear system has an augmented matrix equivalent to the RREF

\[\begin{split} \begin{bmatrix} 1 & 0 & -4 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}. \end{split}\]

Find all solutions to the linear system.

Solution

Look at the last row of the system. It expresses the equation \(0=1\), which is impossible to satisfy. Thus the system is inconsistent.

There are only three possible outcomes for a linear system, all deducible from the RREF of the augmented matrix:

  1. There is a leading 1 in the last column, in which case there are no solutions.

  2. There are fewer pivot columns than variables, in which case there are infinitely many solutions.

  3. There is a unique solution.

4. Row elimination 6. Vector algebra