\documentclass{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{enumerate}

\usepackage{hyperref}

\usepackage{ifthen}
\usepackage{ulem} % for strikethrough \sout{...} command
\usepackage{color}

\usepackage{wasysym}

\usepackage{tikz} % diagram package

\usetikzlibrary{calc}

%\pagestyle{empty}

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.25in}
\setlength{\evensidemargin}{-0.25in}
\setlength{\topmargin}{-0.45in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.6in}
\setlength{\textwidth}{7in}

%\newcommand{\comp}{ \,{\scriptstyle \stackrel{\circ}{}}\, } 
%\newcommand{\nullset}{\mathrm{O}\!\!\!\!\big/\,}

%\def\myfrac#1#2{
%    \hspace{3pt}\!\!\!$^{#1}\!\!\hspace{1pt}/\hspace{2pt}\!\!_{#2}$\!\!\!\hspace{3pt}
%} 

\newcommand{\bdot}{\, {\scriptstyle{\bullet}} \,}
\newcommand{\B}[1]{{\bf {#1}}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}

\newcommand{\myspace}{\parbox[c][0.25in]{0.25in}{\hfill}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}
\newcommand{\force}{{\noindent $\mbox{\;}$}}

\newcommand{\diagquotient}[2]{\displaystyle{{#1 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} \hspace*{0.1in} {\; \atop #2}}}

\newcommand{\F}{\mathbb{F}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}

\newcommand{\LEMMA}{\vspace{0.1in} \noindent \fbox{\large\bf Lemma:}  }
\newcommand{\COR}{\vspace{0.1in} \noindent \fbox{\large\bf Corollary:}  }
\newcommand{\PROP}{\vspace{0.1in} \noindent \fbox{\large\bf Proposition:}  }
\newcommand{\DEF}{\vspace{0.1in} \noindent \fbox{\large\bf Definition:}  }
\newcommand{\THM}{\vspace{0.1in} \noindent \fbox{\large\bf Theorem:}  }
\newcommand{\EX}{\vspace{0.1in} \noindent \fbox{\large\bf Example:}  }
\newcommand{\bproof}{\vspace{0.05in} \noindent {\bf Proof:} }
\newcommand{\eproof}{$\blacksquare$ \vspace{0.05in}}

\newcommand{\vsp}{\vspace{0.05in}}

\newcommand{\HEAD}[1]{\vspace{0.05in} \noindent {\large\bf #1} \vspace{0.05in}}

\definecolor{ignoreGray}{rgb}{0.75,0.75,0.75}
\newcommand{\ig}{\color{ignoreGray}}

\newcommand{\E}[2]{\B e_{#1}\B e_{#2}^T}

\begin{document}

\noindent
{\bf Math 2240}
\hfill {\Large \bf Reduced Row Echelon Form} \hfill 
{\bf Linear Algebra}

\vspace{0.05in}

%\vspace{0.1in}

Techniques for solving systems of linear equations lie at the heart of linear algebra. In high school we learn to solve systems with 2 or 3 variables using ``elimination'' and ``substitution'' of variables. In order to solve systems with a large number of variables we need to be more organized. The process of {\it Gauss-Jordan Elimination} gives us a systematic way of solving linear systems.

\HEAD{From Systems to Matrices:}

To solve a system of equations we should first drop as many unnecessary symbols as possible. This is done by constructing an {\it augmented matrix}. [{\it Note:} The word {\it matrix} comes to us from Latin. In Middle English, {\it matrix} meant {\it womb}. It can be used more generally to mean an enclosure. In mathematics, a matrix is a rectangular array filled numbers, functions, or more general objects.] 

\EX

\vspace{-0.3in}

\begin{equation*}
\begin{array}{rcrcrcr}
2x & - &  y & + & 3z & = & -1 \\
     &   & 5y & -  & 6z & = & 0 \\
-x  &   &      & + & 4z & = & 7 
\end{array} \qquad \Longrightarrow \qquad
\begin{bmatrix} 
 2 & -1 &  3 & : & -1 \\
 0 &  5 & -6 & : &  0 \\
-1 & 0 &  4  & : &  7 
\end{bmatrix}
\end{equation*}

\vspace{-0.05in}

\HEAD{Elementary Operations:}

To solve our system we need to manipulate our equations. We will see that standard manipulations correspond to changing the {\it rows} of our augmented matrix. In the end, it turns out that we need just 3 types of operations to solve any linear system. We call these {\it elementary (row) operations}.

\DEF Elementary Row Operations

\vspace{0.1in}

\noindent
\begin{tabular}{|lclccl|} \hline
                      & &  {\bf Effect on the linear system:} & & & {\bf Effect on the matrix:} $\displaystyle\Large\strut$  \\ \hline \hline
{\bf Type I}   & &  \parbox{2.65in}{Interchange equation $i$ and equation $j$\\ (List the equations in a different order.)} & $\Longleftrightarrow$ & \qquad & \parbox{2.25in}{Swap Row $i$ and Row $j$}  $\displaystyle\Huge\strut$ \\
{\bf Type II}  & & \parbox{2.65in}{Multiply both sides of equation $i$\\ by a non-zero scalar $c$} & $\Longleftrightarrow$ & & \parbox{2.25in}{Multiply Row $i$ by $c$ where $c \not=0$}  $\displaystyle\Huge\strut$ \\
{\bf Type III} & & \parbox{2.65in}{Add $c$ times both sides of equation $i$\\ to equation $j$} & $\Longleftrightarrow$ & & \parbox{2.25in}{Add $c$ times Row $i$ to Row $j$\\ where $c$ is any scalar} \varspace{0.5in}{0.01in} \\
\hline \end{tabular}   

\vspace{0.05in}

\noindent
{\it Note:} A type III operation only changes equation/row $j$. We are not scaling equation/row $i$ by $c$ here.

\vspace{0.05in}

If we can get from matrix $A$ to matrix $B$ by performing a series of elementary row operations, then $A$ and $B$ are called {\bf row equivalent matrices}. 
Of course, there are also corresponding {\it elementary column operations}. If we can get from matrix $A$ to matrix $B$ by performing a series of elementary column operations, we call $A$ and $B$ {\bf column equivalent matrices}. Both of these {\it equivalences} are in fact equivalence relations. [These relations are reflexive: $A \sim A$, symmetric: $A \sim B$ if and only if $B \sim A$, and transitive: $A \sim B$ and $B \sim C$ implies $A \sim C$. Equivalence relations are like a loosened up version of equality.] While both row and column operations are important, we will (for now) focus on row operations since they correspond to steps used when solving linear systems. 

\EX Type I --- swap rows 1 and 3

\vspace{-0.1in}

\begin{equation*}
\begin{array}{rcrcrcr}
2x & - &  y & + & 3z & = & -1 \\
     &   & 5y & -  & 6z & = & 0 \\
-x  &   &      & + & 4z & = & 7 
\end{array} 
\qquad \Longrightarrow \qquad
\begin{array}{rcrcrcr}
-x  &   &      & + & 4z & = & 7 \\
     &   & 5y & -  & 6z & = & 0 \\
2x & - &  y & + & 3z & = & -1 
\end{array} 
\end{equation*}

\begin{equation*}
\begin{bmatrix} 
 2 & -1 &  3 & : & -1 \\
 0 &  5 & -6 & : &  0 \\
-1 & 0 &  4  & : &  7 
\end{bmatrix}
\qquad  \stackrel{R1 \leftrightarrow R3}{\widetilde{\qquad}} \qquad
\begin{bmatrix} 
-1 & 0 &  4  & : &  7 \\
 0 &  5 & -6 & : &  0 \\
 2 & -1 &  3 & : & -1 
\end{bmatrix}
\end{equation*}

\EX Type II --- scale row 3 by -2

\vspace{-0.1in}

\begin{equation*}
\begin{array}{rcrcrcr}
2x & - &  y & + & 3z & = & -1 \\
     &   & 5y & -  & 6z & = & 0 \\
-x  &   &      & + & 4z & = & 7 
\end{array} 
\qquad \Longrightarrow  \qquad
\begin{array}{rcrcrcr}
2x & - &  y & + & 3z & = & -1 \\
     &   & 5y & -  & 6z & = & 0 \\
2x  &   &      & + & -8z & = & -14 
\end{array} 
\end{equation*}

\begin{equation*}
\begin{bmatrix} 
 2 & -1 &  3 & : & -1 \\
 0 &  5 & -6 & : &  0 \\
-1 & 0 &  4  & : &  7 
\end{bmatrix}
\qquad \stackrel{-2 \times R3}{\widetilde{\qquad}} \qquad
\begin{bmatrix} 
 2 & -1 &  3 & : & -1 \\
 0 &  5 & -6 & : &  0 \\
 2 & 0 & -8  & : &  -14 
\end{bmatrix}
\end{equation*}

%\vspace{0.1in}

\EX Type III --- add 3 times row 3 to row 2

\vspace{-0.1in}

\begin{equation*}
\begin{array}{rcrcrcr}
2x & - &  y & + & 3z & = & -1 \\
     &   & 5y & -  & 6z & = & 0 \\
-x  &   &      & + & 4z & = & 7 
\end{array} 
\qquad \Longrightarrow  \qquad
\begin{array}{rcrcrcr}
2x & - &  y & + & 3z & = & -1 \\
-3x &   & 5y & +  & 6z & = & 21 \\
-x  &   &      & + & 4z & = & 7 
\end{array} 
\end{equation*}

\begin{equation*}
\begin{bmatrix} 
 2 & -1 &  3 & : & -1 \\
 0 &  5 & -6 & : &  0 \\
-1 & 0 &  4  & : &  7 
\end{bmatrix}
\qquad \stackrel{3 \times R3 + R2}{\widetilde{\qquad}} \qquad
\begin{bmatrix} 
 2 & -1 &  3 & : & -1 \\
-3 &  5 & 6 & : &  21 \\
-1 & 0 &  4  & : &  7 
\end{bmatrix}
\end{equation*}

\vspace{0.1in}

It is important to notice several things about these operations. First, they are all reversible (that's why we want $c \not= 0$ in type II operations) --- in fact the inverse of a type X operation is another type X operation. Next, these operations don't effect the set of solutions for the system --- that is --- {\bf row equivalent matrices represent systems with the same set of solutions}. Finally, these are {\it row} operations --- columns {\it never} interact with each other. We will discuss this later when we look at the ``Linear Correspondence'' between columns. This last point is quite important as it will allow us to check our work, test spanning and linear independence statements, and allow us to find bases for subspaces associated with matrices.

\vspace{0.05in}

\HEAD{Echelon Form:}

Ultimately we want to solve our linear system. Doing operations blindly probably won't get us anywhere. Instead we will choose our operations carefully so that we head towards some shape of equations which will let us read off the set of solutions. Thus the next few defintions.

\DEF A matrix is in {\bf Row Echelon Form} (or REF) if...  \vspace{-0.05in}
\begin{itemize} \setlength{\itemsep}{0pt}
   \item Each non-zero row is above any rows of zeros -- that is -- zero rows are ``pushed'' to the bottom.
   \item The leading entry of a row is {\it strictly} to the right of the leading entries of the rows above.\\
         (The leftmost non-zero entry of a row is called the ``leading entry''.)  
\end{itemize}
A matrix is in {\bf Reduced Row Echelon Form} (or RREF) if in addition...  \vspace{-0.05in}
\begin{itemize} \setlength{\itemsep}{0pt}
   \item Each leading entry is ``1''. \quad ({\it Note:} Some textbooks say this is a requirement of REF.)
   \item Only zeros appear above (\& below) a leading entry of a row.
\end{itemize}
{\it Note:} Some textbooks require leading entries to be scaled to $1$ to count a matrix as being in row echelon form.

\EX The matrix $A$ (below) is in REF but is not reduced. The matrix $B$ is in RREF.

\[ A = \begin{bmatrix} 0 & 2 & 3 & 4 & 1 & 5 \\ 0 & 0 & 0 & -3 & 3 & 2 \\ 0 & 0 & 0 & 0 & 5 & 6 \\ 0 & 0 & 0 & 0 & 0  & 0 \end{bmatrix} \qquad \qquad
  B = \begin{bmatrix} 0 & 1 & -2 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 5 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} 
 \]

Notice the leading entry in $A$'s first row is not 1 (it is 2). In addition, the leading entries in the next two rows (also not 1) fail to have zeros above them. However, our row of zeros is at the bottom and the leading entries are further and further to the right as we go down. Thus $A$ is in row echelon form -- but not {\it reduced} row echelon form.

\vspace{0.05in}

\HEAD{Gauss-Jordan Elimination:}

Gauss-Jordan Elimination is an algorithm which, given a matrix, returns a row equivalent matrix in reduced row echelon form (RREF). We first perform a {\bf forward pass}:
\begin{enumerate} \setlength{\itemsep}{0pt}
   \item Determine the leftmost non-zero column. This is a {\bf pivot column} and the topmost entry is a {\bf pivot position}.
         If ``0'' is in this pivot position, swap an unignored row with the topmost row (use a Type I operation) so that there 
         is a non-zero entry in the pivot position.
   \item Add appropriate multiples of the topmost (unignored) row to the rows beneath it so that only ``0'' appear below the
         pivot (use several Type III operations).
   \item Ignore the topmost (unignored) row. If any non-zero rows remain, go to step 1.
\end{enumerate}
Once the forward pass is complete, our matrix will be in row echelon form. Sometimes the forward pass alone is referred to as ``Gaussian Elimination''. However, we should be careful since the term ``Gaussian Elimination'' more commonly refers to {\it both} the forward and backward passes. Now we finish Gauss-Jordan Elimination by performing a  {\bf backward pass}:
\begin{enumerate} \setlength{\itemsep}{0pt} \setcounter{enumi}{3}
   \item If necessary, scale the rightmost unfinished pivot to 1 (use a Type II operation).
   \item Add appropriate multiples of the current pivot's row to rows above it so that only 0 appears above the current pivot (using
         several Type III operations).
   \item The current pivot is now ``finished''. If any unfinished pivots remain, go to step 4.
\end{enumerate}
It should be fairly obvious that the entire Gauss-Jordan algorithm will terminate in finitely many steps. The forward pass moves downward and rightward as we iterate and the backward pass moves leftward and upward as we iterate. Only elementary row operations have been used, so our end result is a row equivalent matrix. A tedious, wordy, and unenlightening proof would show us that the resulting matrix is in reduced row echelon form (RREF).

\EX Let's solve the system \qquad $\displaystyle{\begin{array}{rcrcr} 
  x & + & 2y & = &  1 \\
3x & + & 4y & = & -1 \end{array}}$

\vspace{0.05in}

\[ \begin{bmatrix}  
      1 &  2 & : &  1 \\
      3 &  4 & : & -1 \end{bmatrix} \stackrel{-3 \times R1 + R2}{\widetilde{\qquad}}
\begin{bmatrix}  
      1 &  2 & : &  1 \\
      0 & -2 & : & -4 \end{bmatrix} \]

The first non-zero column is just the first column. So the upper left hand corner is a pivot position.
This position already has a non-zero entry so no swap is needed. The type III operation ``$-3$ times row 1 added to row 2'' clears
the only position below the pivot, so after one operation we have finished with this pivot and can ignore row 1.

\vspace{-0.1in}

\[ \begin{bmatrix}  
      \ig 1 &  \ig 2 & \ig : &  \ig 1 \\ 
      0 & -2 & : & -4 \end{bmatrix} \]

Among the (unignored parts of) columns the leftmost non-zero column is the second column. So the ``$-2$'' sits
in a pivot position. Since it's non-zero, no swap is needed. Also, there's nothing below it, so no type III operations
are necessary. Thus we're done with this row and we can ignore it.

\vspace{-0.1in}

\[ \begin{bmatrix}  
      \ig 1 &  \ig 2 & \ig : &  \ig   1 \\ 
      \ig 0 & \ig -2 & \ig : &  \ig -4 \end{bmatrix} \]
 

Nothing is left, so we are done with the forward pass and our matrix is in row echelong form: $\displaystyle{ \begin{bmatrix}  
      1 &  2 & : &  1 \\
      0 & -2 & : & -4 \end{bmatrix} }$

Next, we need to take the rightmost pivot (the ``$-2$'') and scale it to 1 then clear everything
above it.

\vspace{-0.1in}

\[ \begin{bmatrix}  
      1 &  2 & : &  1 \\
      0 & -2 & : & -4 \end{bmatrix} \stackrel{-1/2 \times R2}{\widetilde{\qquad}}
\begin{bmatrix}  
      1 &  2 & : &  1 \\
      0 &  1 & : &  2 \end{bmatrix} \stackrel{-2 \times R2 + R1}{\widetilde{\qquad}}
\begin{bmatrix}  
      1 &  0 & : &  -3 \\
      0 &  1 & : &   2 \end{bmatrix} \]

This ``finishes'' that pivot. The next rightmost pivot is the 1 in the upper left hand corner. But it's
already scaled to 1 and has nothing above it, so it's finished as well. That takes care of all of the 
pivots so the backward pass is complete leaving our matrix in reduced row echelon form.

Finally, we translate the RREF matrix back into a system of equations. The RREF is equivalent to the system:
\qquad $\displaystyle{\begin{array}{rcrcr} 
  x &  &    & = &  -3 \\
     &  & y & = &   2 \end{array}}$
\quad We now merely read off our solution: \fbox{$x=-3$ and $y=2$}.

\vspace{0.05in}

{\it Note:} One can also solve a system quite easily once the forward pass is complete. This is
done using {\bf back substitution}. Notice that the system after the forward pass was
$\displaystyle{\begin{array}{rcrcr} 
  x & + & 2y & = & 1 \\
     &  &  -2y & = &  -4 \end{array}}$. So we have $-2y=-4$ thus $y=2$. Substituting this
back into the first equation we get $x + 2(2) = 1$ so $x=-3$.

\vspace{0.1in}

\EX Let's solve the system \qquad $\displaystyle{\begin{array}{rcrcrcr} 
2x & - &   y & + &   z & = &   0 \\
4x & - & 2y & + & 2z & = &  1 \\
  x &   &      & + &   z & = &  -1 \end{array}}$

\vspace{0.025in}

\[ \begin{bmatrix}  
      2 &  -1 &  1 & : &  0 \\
      4 &  -2 &  2 & : &  1 \\
      1 &   0 &  1 & : & -1 \end{bmatrix} \stackrel{-2 \times R1 + R2}{\widetilde{\qquad}}
   \begin{bmatrix}  
      2 &  -1 &  1 & : &  0 \\
      0 &   0 &  0 & : &  1 \\
      1 &   0 &  1 & : & -1 \end{bmatrix} \stackrel{-1/2 \times R1 + R3}{\widetilde{\qquad}}
   \begin{bmatrix}  
      2 &  -1 &  1 & : &  0 \\
      0 &   0 &  0 & : &  1 \\
      0 &   1/2 & 1/2 & : & -1 \end{bmatrix} \stackrel{\mathrm{Ignore\;}R1}{\widetilde{\qquad}}
\]

\vspace{-0.05in}

\[ \begin{bmatrix}  
     \ig 2 & \ig -1 & \ig 1 & \ig : & \ig 0 \\
      0 &   0 &  0 & : &  1 \\
      0 &   1/2 & 1/2 & : & -1 \end{bmatrix} \stackrel{R2 \leftrightarrow R3}{\widetilde{\qquad}}
   \begin{bmatrix}  
     \ig 2 & \ig -1 & \ig 1 & \ig : & \ig 0 \\
      0 &   1/2 & 1/2 & : & -1 \\
      0 &   0 &  0 & : &  1 \end{bmatrix} \stackrel{\mathrm{Ignore\;}R2}{\widetilde{\qquad}}
   \begin{bmatrix}  
     \ig 2 & \ig -1 & \ig 1 & \ig : & \ig 0 \\
     \ig 0 & \ig  1/2 & \ig 1/2 & \ig : & \ig -1 \\
      0 &   0 &  0 & : &  1 \end{bmatrix} \stackrel{\mathrm{Ignore\;}R3}{\widetilde{\qquad}}
\]

which leaves us with nothing. So the forward pass is complete and
$\displaystyle{   \begin{bmatrix}  
      2 &  -1 &  1 & : &  0 \\
      0 &   1/2 & 1/2 & : & -1 \\
      0 &   0 &  0 & : &  1 \end{bmatrix}}$ is in REF.

\vspace{0.05in}

\[ \begin{bmatrix}  
      2 &  -1 &  1 & : &  0 \\
      0 &   1/2 & 1/2 & : & -1 \\
      0 &   0 &  0 & : &  1 \end{bmatrix} \stackrel{1 \times R3 + R2}{\widetilde{\qquad}}
   \begin{bmatrix}  
      2 &  -1 &  1 & : &  0 \\
      0 &   1/2 & 1/2 & : & 0 \\
      0 &   0 &  0 & : &  1 \end{bmatrix} \stackrel{2 \times R2}{\widetilde{\qquad}}
   \begin{bmatrix}  
      2 &  -1 &  1 & : &  0 \\
      0 &   1 &  1 & : & 0 \\
      0 &   0 &  0 & : &  1 \end{bmatrix} \stackrel{1 \times R2 + R1}{\widetilde{\qquad}}
 \]

%\vspace{-0.05in}

\[  \begin{bmatrix}  
      2 &   0 &  2 & : &  0 \\
      0 &   1 &  1 & : & 0 \\
      0 &   0 &  0 & : &  1 \end{bmatrix} \stackrel{1/2 \times R1}{\widetilde{\qquad}}
    \begin{bmatrix}  
      1 &   0 &  1 & : &  0 \\
      0 &   1 &  1 & : & 0 \\
      0 &   0 &  0 & : &  1 \end{bmatrix} 
\]

\noindent
This finishes the backward pass and our matrix is now in RREF. Our new system of equations is
$\displaystyle{\begin{array}{rcrcrcr} 
  x &  &     & + &   z & = &   0 \\
     &  &  y & + &   z & = &   0 \\
     &  &     &     &   0 & = &  1 \end{array}}$. Of course $0 \not= 1$, so this is an {\bf inconsistent} system --- it has {\bf no solutions}.
{\it Note:} If our only goal was to solve this system, we could have stopped after the very first operation (row number 2 already said ``$0=1$'').
 
\EX Let's solve the system \qquad $\displaystyle{\begin{array}{rcrcrcr} 
  x & + &  2y & + & 3z & = & 3 \\
 4x & + & 5y & + & 6z & = & 9 \\
 7x & + & 8y & + & 9z & = & 15 \end{array}}$

\[ 
   \begin{bmatrix}
   1 & 2 & 3 & : & 3 \\
   4 & 5 & 6 & : & 9 \\
   7 & 8 & 9 & : & 15 
   \end{bmatrix}
   \stackrel{-4 \times R1 + R2}{\widetilde{\qquad}}
   \begin{bmatrix}
   1 &  2 &   3 & : &  3 \\
   0 & -3 & -6 & : & -3 \\
   7 &  8 &   9 & : & 15 
   \end{bmatrix}
   \stackrel{-7 \times R1 + R3}{\widetilde{\qquad}}
   \begin{bmatrix}
   1 &  2 &   3 & : &  3 \\
   0 & -3 & -6 & : & -3 \\
   0 & -6 & -12 & : & -6 
   \end{bmatrix}
   \stackrel{-2 \times R2 + R3}{\widetilde{\qquad}}
\]

\[
   \begin{bmatrix}
   1 &  2 &   3 & : &  3 \\
   0 & -3 & -6 & : & -3 \\
   0 &  0 &   0 & : &  0 
   \end{bmatrix}
   \stackrel{-1/3 \times R2}{\widetilde{\qquad}}
   \begin{bmatrix}
   1 &  2 &   3 & : &  3 \\
   0 &  1 &   2 & : &  1 \\
   0 &  0 &   0 & : &  0 
   \end{bmatrix}
   \stackrel{-2 \times R2 + R1}{\widetilde{\qquad}}
   \begin{bmatrix}
   1 &  0 &  -1 & : &  1 \\
   0 &  1 &   2 & : &  1 \\
   0 &  0 &   0 & : &  0 
   \end{bmatrix}
\]
  
Now our matrix is in RREF. The new system of equations is
$\displaystyle{\begin{array}{rcrcrcr} 
  x &  &     & - &   z   & = &   1 \\
     &  &  y & + &  2z & = &   1 \\
     &  &     &     &   0 & = &  0 \end{array}}$. This is new --- we
don't have an equation of the form ``$z=...$'' This is because $z$ 
does not lie in a pivot column. So we can make $z$ a {\bf free variable}. Let's
relabel it $z=t$. Then we have $x-t=1$, $y+2t=1$, and $z=t$.
So \fbox{$x=1+t$, $y=1-2t$, and $z=t$} is a solution for {\it any} choice of $t$.
For example, $x=y=1$ and $z=0$ is a solution, so is $x=2$, $y=-1$, $z=1$.
In fact, there are infinitely many solutions.

\vspace{0.05in}

\noindent
{\bf Fact:} A system of linear equations will always either have one, infinitely many, or no solutions.

\vspace{0.1in}

\HEAD{Multiple Systems:} 

Gauss-Jordan can handle solving multiple systems at once, if these systems share the same coefficient matrix (the
part of the matrix before the $:$'s). 

Suppose we wanted to solve both $\displaystyle{\begin{array}{rcrcr} 
   x & + &  2y & = & 3 \\
 4x & + & 5y &  = & 6 \\
 7x & + & 8y &  = & 9 \end{array}}$ and also $\displaystyle{\begin{array}{rcrcr}
   x & + &  2y & = & 3 \\
 4x & + & 5y &  = & 9 \\
 7x & + & 8y &  = & 15 \end{array}}$. These lead to the following augmented matrices:
$\displaystyle{ \begin{bmatrix} 1 & 2 & : & 3 \\ 4 & 5 & : & 6 \\ 7 & 8 & : & 9 \end{bmatrix}}$ and
$\displaystyle{ \begin{bmatrix} 1 & 2 & : & 3 \\ 4 & 5 & : & 9 \\ 7 & 8 & : & 15 \end{bmatrix}}$. We can combine them together and get
$\displaystyle{ \begin{bmatrix} 1 & 2 & : & 3 & 3 \\ 4 & 5 & : & 6 & 9 \\ 7 & 8 & : & 9 & 15 \end{bmatrix}}$ which we already know has the RREF
of $\displaystyle{ \begin{bmatrix} 1 &  0 &  : & -1 &  1 \\  0 &  1 &   : & 2 &  1 \\  0 &  0 &  : & 0 &  0 \end{bmatrix}}$ (from the last example --- only the
$:$'s have moved). This corresponds to the augmented matrices $\displaystyle{ \begin{bmatrix} 1 &  0 &  : & -1 \\  0 &  1 &   : & 2 \\  0 &  0 &  : & 0 \end{bmatrix}}$ and $\displaystyle{ \begin{bmatrix} 1 &  0 &  : &  1 \\  0 &  1 &   : &  1 \\  0 &  0 &  : &  0 \end{bmatrix}}$. These in turn tell us that the first system's solution
is \fbox{$x=-1$, $y=2$} and the second system's solution is \fbox{$x=1$ and $y=1$}.

\vspace{0.05in}

This works because row operations never mix columns together. Notice how many ways we could interpret $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 3 \\ 4 & 5 & 6 & 9 \\ 7 & 8 & 9 & 15 \end{bmatrix}}$. Initially it represented a single system in 3 variables and then 2 systems in 2 variables. We could also view it as 3 systems in 1 variable. Or another view point would be to consider this as a single system where the constant terms are all zero (we could neglect to write down this final column of zeros). A system whose constant terms (the right hand side of our equations) are all zero, is called a {\bf homogeneous system}. In our case, this would be the system: 
$\displaystyle{\begin{array}{rcrcrcrcr} 
  x & + & 2y  & + &  3z   & + &  3w & = & 0 \\
  4x & + & 5y & + &  6z & + &  9w & = & 0 \\
  7x & + & 8y & + & 9z & + & 15w  & = & 0 \end{array}}$. Our RREF then reads: $\displaystyle{\begin{array}{rcrcrcrcr} 
  x &  &  & - &  z   & + &  w & = & 0 \\
   & & y & + &  2z & + &  w & = & 0 \\
   & &  & & & & 0 & = & 0 \end{array}}$. So \fbox{$x=s-t$, $y=-2s-t$, $z=s$, and $w=t$} is a solution for any $s$ and $t$.

\vspace{0.1in}

\HEAD{Pivoting:} 

When working with ``real world'' data and using computational devices, we have to deal with rounding error. It turns out that Gaussian elimination is not numerically stable. Small numerical changes in a matrix can yield radically different RREFs. To combat the propagation of errors (like round off error) one can implement partial or full pivoting methods. These are general purpose techniques to tackle solving systems numerically in a stable (or at least more stable) way. 

First, we will mention {\bf partial pivoting}. Solving a system using partial pivoting just modifies step 1 in the forward pass of Gauss-Jordan elimination. Instead of allowing just any element to sit in the pivot position, we swap the element (in an unignored row) of largest magnitude.

This doesn't add much overhead or runtime but greatly improves stability. Why? Well, essentially we get into trouble when doing type III operations to clear out positions below the pivot position. If the pivot is small, we will have to add a {\it large} multiple of our row to wipe out the entry below. This large multiple can greatly magnify any existing error. On the other hand, with partial pivoting since the pivot position contains an element of larger magnitude than the elements below it, we will never add a multiple of our row that is bigger than 1. 

It turns out that partial pivoting is still not stable (in theory). To get a fully stable technique we must use {\bf full pivoting}. Here we consider all elements below and to the right of our pivot position and use both row and column swaps to get the element of largest possible magnitude into the pivot position. This gives us a fully stable method. However, keeping in mind that column swaps are essentially scrambling our list of variables, we incur some overhead keeping track of a relabeling of our variables. In practice partial pivoting is often used but full pivoting not so much. For most systems arising in most applications, partial pivoting is good enough.

\EX Let's rework a previous example using partial pivoting. 

Our goal os to find the RREF of $A = \begin{bmatrix}  
      2 &  -1 &  1 & : &  0 \\
      4 &  -2 &  2 & : &  1 \\
      1 &   0 &  1 & : & -1 \end{bmatrix}$. Now the $(1,1)$-position is clearly our first pivot. However, there is an element of larger magnitude below $2$ so we need to swap rows.

\vspace{-0.1in}

\[ \begin{bmatrix}  
      2 &  -1 &  1 & : &  0 \\
      4 &  -2 &  2 & : &  1 \\
      1 &   0 &  1 & : & -1 \end{bmatrix} \stackrel{R1 \leftrightarrow R2}{\widetilde{\qquad}}
   \begin{bmatrix}  
      4 &  -2 &  2 & : &  1 \\
      2 &  -1 &  1 & : &  0 \\
      1 &   0 &  1 & : & -1 \end{bmatrix} \stackrel{-1/2 \times R1 + R2}{\widetilde{\qquad}}
   \begin{bmatrix}  
      4 &  -2 &  2 & : &  1 \\
      0 &   0 &  0 & : &  -1/2 \\
      1 &   0 &  1 & : & -1 \end{bmatrix} \stackrel{-1/4 \times R1 + R3}{\widetilde{\qquad}} \]
\[  \begin{bmatrix}  
      4 &  -2 &  2 & : &  1 \\
      0 &   0 &  0 & : &  -1/2 \\
      0 &   1/2 & 1/2 & : & -5/4 \end{bmatrix} \stackrel{R2 \leftrightarrow R3}{\widetilde{\qquad}}
   \begin{bmatrix}  
      4 &  -2 &  2 & : &  1 \\
      0 &   1/2 & 1/2 & : & -5/4 \\
      0 &   0 &  0 & : &  -1/2 \end{bmatrix} \]

Notice after swapping $4$ into the first pivot position then clearing entries below, all of our type III operation multiples are of magnitude no greater than 1. This is the whole point of partial pivoting. Next, we found that the $(2,2)$-position was out next pivot position. Now even though $-2$ in column 2 is bigger (in magnitude) than $1/2$, it does not lie below the pivot position so it should be ignored. Thus we choose from $0$ and $1/2$ and so swap $1/2$ into the second pivot position. It is already clear below and so we locate the final pivot position at $(3,4)$. Again, there are larger elements in column 4, but none lying below our pivot position so no swap is needed. This completes the forward pass. The backward pass then proceeds as usual:

\[  \begin{bmatrix}  
      4 &  -2 &  2 & : &  1 \\
      0 &   1/2 & 1/2 & : & -5/4 \\
      0 &   0 &  0 & : &  -1/2 \end{bmatrix} \stackrel{-2 \times R3}{\widetilde{\qquad}}
   \begin{bmatrix}  
      4 &  -2 &  2 & : &  1 \\
      0 &   1/2 & 1/2 & : & -5/4 \\
      0 &   0 &  0 & : &  1 \end{bmatrix} \stackrel{5/4 \times R3 + R2}{\widetilde{\qquad}}
   \begin{bmatrix}  
      4 &  -2 &  2 & : &  1 \\
      0 &   1/2 & 1/2 & : & 0 \\
      0 &   0 &  0 & : &  1 \end{bmatrix} \stackrel{-1 \times R3 + R1}{\widetilde{\qquad}} \]
\[  \begin{bmatrix}  
      4 &  -2 &  2 & : &  0 \\
      0 &   1/2 & 1/2 & : & 0 \\
      0 &   0 &  0 & : &  1 \end{bmatrix} \stackrel{2 \times R2}{\widetilde{\qquad}}
    \begin{bmatrix}  
      4 &  -2 &  2 & : &  0 \\
      0 &   1 & 1 & : & 0 \\
      0 &   0 &  0 & : &  1 \end{bmatrix} \stackrel{2 \times R2 + R1}{\widetilde{\qquad}}
    \begin{bmatrix}  
      4 &   0 &  4 & : &  0 \\
      0 &   1 & 1 & : & 0 \\
      0 &   0 &  0 & : &  1 \end{bmatrix} \stackrel{(1/4) \times R1}{\widetilde{\qquad}}
    \begin{bmatrix}  
      1 &   0 &  1 & : &  0 \\
      0 &   1 & 1 & : & 0 \\
      0 &   0 &  0 & : &  1 \end{bmatrix} \]

\newpage

\HEAD{Practice Problems and Answers:} 

For each of the following matrices perform Gauss-Jordan elimination (carefully following the algorithm defined above). I have given the result of the performing the forward pass to help you verify that you are on the right track. [Note: Each matrix has a unique RREF. However, a REF is {\it not} unique. So if you do not follow my algorithm and use your own random assortment of operations, you will almost certainly get different REFs along the way to the RREF.] Once you have completed row reduction, identify the pivots and pivot columns. Finally, interpret your matrices as a system or collection of systems of equations and note the corresponding solutions.

If you would like, you could try doing these again using partial pivoting. In this case, your RREF after elimination is done should be the same as before, but the REF you get after the forward pass may be quite different.

\noindent
\begin{enumerate}
\item \quad $\displaystyle{ \begin{bmatrix} 1 & 5 \\ 2 & 2 \end{bmatrix} }$ $\Longrightarrow$ forward pass $\Longrightarrow$
         $\displaystyle{ \begin{bmatrix} 1 & 5 \\ 0 & -8 \end{bmatrix} }$ $\Longrightarrow$ backward pass $\Longrightarrow$ $\displaystyle{ \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} }$

\vspace{0.15in}

Interpretations? We could view this as a single system in one variable: $x=5$ and $2x=2$. After elimination, this becomes $x=0$ and $0=1$,  so this system is inconsistent. Alternatively, we could view this as a homogeneous system in two variables: $x+5y=0$ and $2x+2y=0$. From the RREF, this becomes $x=0$ and $y=0$ (we only have the so-called {\it trivial solution}.

\vspace{0.15in}

\item \quad $\displaystyle{ \begin{bmatrix} 2 & -4 & 0 & 4 \\ 1 & -2 & 0 & 2 \\ 0 & 0 & 1 & -2 \\ 4 & -8 & 1 & 6 \end{bmatrix} }$ $\Longrightarrow$ forward pass $\Longrightarrow$
         $\displaystyle{ \begin{bmatrix} 2 & -4 & 0 & 4 \\ 0 & 0 & 1 & -2 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} }$ $\Longrightarrow$ backward pass $\Longrightarrow$ $\displaystyle{ \begin{bmatrix} 1 & -2 & 0 & 2 \\ 0 & 0 & 1 & -2 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} }$

\vspace{0.15in}

Interpretations? We could view this as three systems in a single variable: $2x=-4$, $x=-2$, $0=0$, $4x=-8$ as well as $2x=0$, $x=0$, $0=1$, $4x=1$ and also $2x=4$, $x=2$, $0=-2$, $4x=6$. The latter two systems are inconsistent whereas the first system has solution $x=-2$. We could also view this as two systems in two variables: $2x-4y=0$, $x-2y=0$, $0=1$, $4x-8y=1$ as well as $2x-4y=4$, $x-2y=2$, $0=-2$, $4x-8y=6$. Both of these are inconsistent. Next, we could view this as a single system in three variables: $2x-4y=4$, $x-2y=2$, $z=-2$, $4x-8y+z=6$. From the RREF, the second variable is free. We could write the solution as $x=2t+2$, $y=t$, $z=-2$. Finally, we could interpret this as a homogeneous system in four variables: $2x-4y+4w=0$, $x-2y+2w=0$, $z-2w=0$, $4x-8y+z+6w=0$. From the RREF, the second and last variables are free. We could write the solution as $x=2s-2t$, $y=s$, $z=2t$, $w=t$. 

\vspace{0.15in}

\item \quad $\displaystyle{ \begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{bmatrix} }$ $\Longrightarrow$ forward pass $\Longrightarrow$
         $\displaystyle{ \begin{bmatrix} 2 & 1 & 1 \\ 0 & 3/2 & 1/2 \\ 0 & 0 & 4/3 \end{bmatrix} }$ $\Longrightarrow$ backward pass $\Longrightarrow$ $\displaystyle{ \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} }$

\vspace{0.15in}

Interpretations? We could view this as a pair of systems in a single variable: $2x=1$, $x=2$, $x=1$ as well as $2x=1$, $x=1$, $x=2$. Both of these are inconsistent. We could also view this a single system in two variables: $2x+y=1$, $x+2y=1$, $x+y=2$. The RREF says this is equivalent to $x=0$, $y=0$, $0=1$ so it is inconsistent. Finally, we can view this a homogeneous system $2x+y+z=0$, $x+2y+z=0$, $x+y+2z=0$. The only solution is the trivial one: $x=y=z=0$. 

\vspace{0.15in}

\item  \quad $\displaystyle{ \begin{bmatrix} 1 & -3 & 0 \\ 2 & -6 & -2 \\ 1 & -3 & -2 \end{bmatrix} }$ $\Longrightarrow$ forward pass $\Longrightarrow$
         $\displaystyle{ \begin{bmatrix} 1 & -3 & 0 \\ 0 & 0 & -2 \\ 0 & 0 & 0 \end{bmatrix} }$ $\Longrightarrow$ backward pass $\Longrightarrow$ $\displaystyle{ \begin{bmatrix} 1 & -3 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix} }$

\vspace{0.15in}

Interpretations? We could view this as a pair of systems in a single variable: $x=-3$, $2x=-6$, $x=-3$ as well as $x=0$, $2x=-2$, $x=-2$. The first system has solution $x=-3$ and the second system is inconsistent. We could also view this as a single system in two variables: $x-3y=0$, $2x-6y=-2$, $x-3y=-2$. The RREF reveals this is equivalent to $x-3y=0$, $0=1$, $0=0$ so it is inconsistent. Finally, we could view this as a homogeneous system $x-3y=0$, $2x-6y-2z=0$, $x-3y-2z=0$. The RREF reveals that our second variable is free. We could write our solution as $x=3t$, $y=t$, $z=0$.

\end{enumerate}


\end{document}
