==== Solving a system in REF or RREF ====

{{page>leading variable}}

== 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

  * $x_1$, $x_3$ and $x_4$ are leading variables, since the corresponding columns have a leading entry
  * $x_2$ and $x_5$ are free variables, since the corresponding columns do not have a leading entry

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

  - assign a free parameter (a letter like $r,s,t,\dots$ representing some arbitrary real number) to each free variable
  - 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:

  - $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}$
  - 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.

{{page>gaussian elimination algorithm}}

=== 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}.$$