~~REVEAL~~

===== The story so far... =====

  * Systems of linear equations
  * The augmented matrix
  * Elementary Row Operations (EROs)
  * Row Echelon Form (REF)
  * Reduced Row Echelon Form (RREF)

===== Today =====

  - How to solve a system in REF or RREF
  - How to find REF or RREF for a system

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

  * **leading variables** are variables whose column contains the leading entry of some row;
  * **free variables** are all the other variables.

==== ====

To solve the corresponding linear system:

  - assign a free parameter ($r,s,t,\dots$) to each free variable
  - starting at the bottom, write out each equation and rearrange for its leading variable


==== Example ====


Solve the linear system for $\newcommand{\sm}{\left[\begin{smallmatrix}}\newcommand{\esm}{\end{smallmatrix}\right]} \sm 1&2&3&0&0&8\\0&0&1&1&1&5\\0&0&0&1&3&4\esm$.

  * Observe: it's in REF
  * Free variables: $x_2$, $x_5$. Set $x_2=s$, $x_5=t$.
    * $ x_4+3x_5=4\implies x_4=4-3x_5=4-3t$ 
    * $ x_3+x_4+x_5=5\implies x_3=1+2t$ 
    * $ x_1+2x_2+3x_3=8\implies x_1=5-2s-6t.$
  * $ \left[\begin{smallmatrix} x_1\\x_2\\x_3\\x_4 \\x_5\end{smallmatrix}\right]= \left[\begin{smallmatrix} 5\\0\\1\\4\\0\end{smallmatrix}\right] +s\left[\begin{smallmatrix} -2\\1\\0\\0\\0\end{smallmatrix}\right] +t\left[\begin{smallmatrix} -6\\0\\2\\-3\\1\end{smallmatrix}\right],\quad s,t\in \mathbb{R}.$
  * (A $2$-dimensional set in $5$-dimensional space $\mathbb{R}^5$).

====== Gaussian elimination ======
A systematic way to put an augmented matrix into REF or RREF using EROs
  * REF=row echelon form
  * RREF=reduced row echelon form
  * ERO=elementary row operation
    - reordering rows
    - scaling a row
    - combining two different rows


===== Gaussian elimination 1 =====

To put a matrix in REF using EROs:

  - Re-order rows so that the leftmost [[leading entry]] is in the top row. 
  - Divide top row by its leading entry, making this a $1$.
  - "Pivot about the leading 1": subtract multiples of the top row from rows below to make entries below leading $1$ zero.
  - Go back to the start, ignoring the top row (until no rows remain, except possibly zero rows).

===== Gaussian elimination 2 =====

To put a matrix into RREF using EROs: first put it into REF as above. Then:

  - Look at the non-zero row nearest the bottom of the matrix
  - Pivot about the [[leading entry|leading]] $1$ in that row and use it to make zeros above
  - 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*}

==== ====

We put the augmented matrix into REF:
\begin{align*} 
\def\go#1#2#3{\left[\begin{smallmatrix}#1\\#2\\#3\end{smallmatrix}\right]}
\def\ar#1{\\\xrightarrow{#1}&}
\go{2&1&3&4&27}{1&2&3&2&30}{1&1&3&1&25}
\xrightarrow{\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*}

==== ====
$\go{1&1&3&1&25}{0&1&0&1&5}{0&0&1&-1&6}$

  * $w=t$ is a free variable (where $t\in\mathbb{R}$).
  * $ z-w=6\implies z=6+w=6+t$
  * $ y+w=5\implies y=5-w=5-t$
  * $ x+y+3z+w=25$ so $x=25-y-3z-w=2-3t.$
  * $ \left[\begin{smallmatrix}x\\y\\z\\w\end{smallmatrix}\right]=\left[\begin{smallmatrix} 2\\5\\6\\0\end{smallmatrix}\right]+t\left[\begin{smallmatrix}-3\\-1\\1\\1\end{smallmatrix}\right],\quad t\in\mathbb{R}.$

==== ====
Solution using RREF instead:
\begin{align*} 
\def\go#1#2#3{\left[\begin{smallmatrix}#1\\#2\\#3\end{smallmatrix}\right]}
\def\ar#1{\\\xrightarrow{#1}&}
\go{2&1&3&4&27}{1&2&3&2&30}{1&1&3&1&25}
\xrightarrow{\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*}

==== ====
$\go{1&0&0&3&2}{0&1&0&1&5}{0&0&1&-1&6}$ is in RREF.

  * $w=t$ is a free variable
  * $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$
  * $\left[\begin{smallmatrix}x\\y\\z\\w\end{smallmatrix}\right]=\left[\begin{smallmatrix}2\\5\\6\\0\end{smallmatrix}\right]+t\left[\begin{smallmatrix}-3\\-1\\1\\1\end{smallmatrix}\right],\quad t\in\mathbb{R}.$

==== Example ====
If $ f(x)=ax^2+bx+c$ and $f(1)=3$, $f(2)=2$ and $f(3)=4$, find $f(x)$.

  * $f(1)=3\implies a+b+c=3$
  * $f(2)=2\implies 4a+2b+c=2$
  * $f(3)=4\implies 9a+3b+c=4$
  * $\begin{gather*}  a+b+c=3\\4a+2b+c=2\\9a+3b+c=4\end{gather*}$ 
  * Solve using RREF.
==== ====
\begin{align*} 
\go{1&1&1&3}{4&2&1&2}{9&3&1&4}
\xrightarrow{R2\to R2-4R1\text{ and }R3\to R3-9R1}&
\go{1&1&1&3}{0&-2&-3&-10}{0&-6&-8&-23}
\ar{R2\to -\tfrac12 R2}
\go{1&1&1&3}{0&1&\tfrac32&5}{0&-6&-8&-23}
\ar{R3\to R3+6R2}
\go{1&1&1&3}{0&1&\tfrac32&5}{0&0&1&7}
\end{align*}
  * So far: in REF!

==== ====
\begin{align*}
\go{1&1&1&3}{0&1&\tfrac32&5}{0&0&1&7}
\xrightarrow{R1\to R1-R3\text{ and }R2\to R2-\tfrac32R3}&
\go{1&1&0&-4}{0&1&0&-5.5}{0&0&1&7}
\ar{R1\to R1-R2}
\go{1&0&0&1.5}{0&1&0&-5.5}{0&0&1&7}
\end{align*}
  * So $a=1.5$, $b=-5.5$ and $c=7$
  * So $f(x)=1.5x^2-5.5x+7$.