Table of Contents

Solving a system in REF or RREF

Given an augmented matrix in REF (or RREF), each column except the last column corresponds to a variable. These come in two types:

Example

For the augmented matrix $$ \begin{bmatrix} 1&2&3&0&0&8\\0&0&1&1&1&5\\0&0&0&1&3&4\end{bmatrix}$$ which is in REF, if we use the variables $x_1,x_2,x_3,x_4,x_5$ then

To solve such a linear system, we use the following procedure:

  1. assign a free parameter (a letter like $r,s,t,\dots$ representing some arbitrary real number) to each free variable
  2. starting at the bottom of the matrix, write out each row and rearrange it to give an equation for its leading variable, substituting the other variables as needed.

In the example above, this gives:

  1. $x_2$ and $x_5$ are free, so set $x_2=s$ where $s\in \mathbb{R}$ and $x_5=t$ where $t\in \mathbb{R}$
  2. Working from the bottom: $$ x_4+3x_5=4\implies x_4=4-3x_5=4-3t$$ $$ x_3+x_4+x_5=5\implies x_3=5-x_4-x_5=5-(4-3t)-t=1+2t$$ $$ x_1+2x_2+3x_3=8\implies x_1=8-2x_2-3x_3=8-2s-3(1+2t)=5-2s-6t.$$

So \begin{align*} x_1&=5-2s-6t\\x_2&=s\\x_3&=1+2t\\x_4&=4-3t\\x_5&=t\end{align*} where $s$ and $t$ are free parameters, i.e. $s,t\in \mathbb{R}$.

Writing this solution in vector form gives: $$ \begin{bmatrix} x_1\\x_2\\x_3\\x_4\\x_5\end{bmatrix} = \begin{bmatrix} 5\\0\\1\\4\\0\end{bmatrix}+s\begin{bmatrix} -2\\1\\0\\0\\0\end{bmatrix} +t\begin{bmatrix} -6\\0\\2\\-3\\1\end{bmatrix},\quad s,t\in \mathbb{R}.$$

Note that the solution set is a subset of $\mathbb{R}^5$, which is $5$-dimensional space; and the solution set is $2$-dimensional, because there are $2$ free parameters.

Gaussian elimination

We've seen that putting a matrix into REF (or even better, in RREF) makes it easier to solve equations.

Aim: put any matrix into REF using EROs.

Algorithm

  1. Re-order the rows so that the leftmost leading entry in the matrix is in the top row.
  2. Divide all of the top row by its leading entry, so that this entry becomes a $1$.
  3. “Pivot about the leading 1”: subtract multiples of the top row from each row below so that all entries below the leading $1$ in the top row become $0$.
  4. Go back to the start, ignoring the top row (until no rows remain, except possibly zero rows).

If we want, we can go further and put the matrix into RREF. First put it into REF as above, and then:

  1. Look at the non-zero row nearest the bottom of the matrix
  2. Pivot about the leading $1$ in that row and use it to make zeros above: subtract multiples of that row from each row above
  3. Move to the next row up, and go to step 2 (until no rows remain).

Example

Use Gaussian elimination to solve the linear system \begin{align*} 2x+y+3z+4w&=27\\ x+2y+3z+2w&=30\\x+y+3z+w&=25\end{align*}

Solution 1

We put the augmented matrix into REF: \begin{align*} \def\go#1#2#3{\begin{bmatrix}#1\\#2\\#3\end{bmatrix}} \def\ar#1{\\[6pt]\xrightarrow{#1}&} &\go{2&1&3&4&27}{1&2&3&2&30}{1&1&3&1&25} \ar{\text{reorder rows (to avoid division)}} \go{1&1&3&1&25}{1&2&3&2&30}{2&1&3&4&27} \ar{R2\to R2-R1\text{ and }R3\to R3-2R2} \go{1&1&3&1&25}{0&1&0&1&5}{0&-1&-3&2&-23} \ar{R3\to R3+R2} \go{1&1&3&1&25}{0&1&0&1&5}{0&0&-3&3&-18} \ar{R3\to-\tfrac13R3} \go{1&1&3&1&25}{0&1&0&1&5}{0&0&1&-1&6} \end{align*} This is in REF. There are leading entries in the columns for $x,y,z$ but not for $w$, so $w=t$ is a free variable (where $t\in\mathbb{R}$). Now $$ z-w=6\implies z=6+w=6+t$$ $$ y+w=5\implies y=5-w=5-t$$ $$ x+y+3z+w=25\implies x=25-y-3z-w=25-(5-t)-3(6+t)-t=2-3t.$$ So $$ \begin{bmatrix}x\\y\\z\\w\end{bmatrix}=\begin{bmatrix} 2\\5\\6\\0\end{bmatrix}+t\begin{bmatrix}-3\\-1\\1\\1\end{bmatrix},\quad t\in\mathbb{R}.$$

Solution 2

We put the augmented matrix into RREF. \begin{align*} \def\go#1#2#3{\begin{bmatrix}#1\\#2\\#3\end{bmatrix}} \def\ar#1{\\[6pt]\xrightarrow{#1}&} &\go{2&1&3&4&27}{1&2&3&2&30}{1&1&3&1&25} \ar{\text{do everything as above}} \go{1&1&3&1&25}{0&1&0&1&5}{0&0&1&-1&6} \ar{R1\to R1-3R3} \go{1&1&0&4&7}{0&1&0&1&5}{0&0&1&-1&6} \ar{R1\to R1-R2} \go{1&0&0&3&2}{0&1&0&1&5}{0&0&1&-1&6} \end{align*} This is in RREF. There are leading entries in the columns for $x,y,z$ but not for $w$, so $w=t$ is a free variable (where $t\in\mathbb{R}$). Now $$ z-w=6\implies z=6+w=6+t$$ $$ y+w=5\implies y=5-w=5-t$$ $$ x+3w=2\implies x=2-3w=2-3t$$ So $$ \begin{bmatrix}x\\y\\z\\w\end{bmatrix}=\begin{bmatrix} 2\\5\\6\\0\end{bmatrix}+t\begin{bmatrix}-3\\-1\\1\\1\end{bmatrix},\quad t\in\mathbb{R}.$$