
\section{Gaussian Elimination}

\subsection{Notation for Linear Systems}

Last time we studied the linear system 

\begin{eqnarray}
	x+y & = & 27\nn \\
	2x-y & = & 0\nn
\end{eqnarray}
and found that
\begin{eqnarray}
	x \phantom{+y}& = & 9\nn \\
	\phantom{x+}y & = & 18\nn
\end{eqnarray}

\noindent
We learned to write the linear system using a matrix and two vectors like so: 

\begin{equation*}
    \begin{pmatrix}
      1             &2  \\
      2             &-1
    \end{pmatrix}
  \colvec{x \\ y}
  =
  \colvec{27 \\ 0}
\end{equation*}

\noindent
Likewise, we can write the solution as:

\begin{equation*}
    \begin{pmatrix}
      1             &0  \\
      0             &1
    \end{pmatrix}
  \colvec{x \\ y}
  =
  \colvec{9 \\ 18}
\end{equation*}
The matrix $I=    \begin{pmatrix}
      1             &0  \\
      0             &1
    \end{pmatrix}$ is called the \emph{Identity Matrix}\index{Identity matrix!$2\times2$}.  You can check that for any vector $v$, then $Iv=v$.

A useful shorthand for a linear system is an \emph{Augmented Matrix}\index{Augmented matrix~$2\times2$}, which looks like this for the linear system we've been dealing with:

\[
\begin{amatrix}{2}
1 &1 &27 \\ 2 &-1 & 0
\end{amatrix}
\]

We don't bother writing the vector $\colvec{x\\y}$, since it will show up in any linear system we deal with.
The solution to the linear system looks like this: 

\[
\begin{amatrix}{2}
1 &0 &9 \\ 0  & 1 & 18
\end{amatrix}
\]

Here's another example of an augmented matrix, for a linear system with three equations and four unknowns:

\[
\begin{amatrix}{4}
1 & 3 & 2 & 0  & 9 \\ 
6 & 2 & 0  & -2& 0  \\
-1& 0  & 1  & 1 & 3
\end{amatrix}
\]

And finally, here's the general case.  The number of equations in the linear system is the number of rows $r$ in the augmented matrix, and the number of columns $k$ in the matrix left of the vertical line is the number of unknowns.

\[
\begin{amatrix}{4}
a^1_1 & a^1_1 & \ldots & a^1_1 & b^1 \\ 
a^2_1 & a^2_2 & \ldots & a^2_k & b^2 \\ 
\vdots & \vdots & & \vdots & \vdots  \\
a^r_1 & a^r_2 & \ldots & a^r_k & b^r \\ 
\end{amatrix}
\]


Here's the idea: Gaussian Elimination is a set of rules for taking a general augmented matrix and turning it into a very simple augmented matrix consisting of the identity matrix on the left and a bunch of numbers (the solution) on the right.

\section*{Equivalence Relations for Linear Systems}

It often happens that two mathematical objects will appear to be different but in fact are exactly the same.  The best-known example of this are fractions.  For example, the fractions $\frac{1}{2}$ and $\frac{6}{12}$ describe the same number.  We could certainly call the two fractions \emph{equivalent}.  

In our running example, we've noticed that the two augmented matrices 

\[
\begin{amatrix}{2}
1 &1 &27 \\ 2 &-1 & 0
\end{amatrix}
,\qquad
\begin{amatrix}{2}
1 &0 &9 \\0   & 1 & 18
\end{amatrix}
\]
both contain the same information: $x=9, y=18$.  

Generally, we say that two augmented matrices are (row) \emph{equivalent}\index{Row equivalence} if they have the same solutions.
To denote this, we write:
\[
\begin{amatrix}{2}
1 &1 &27 \\ 2 &-1 &0
\end{amatrix}
\sim
\begin{amatrix}{2}
1 & 0&9 \\   0& 1 & 18
\end{amatrix}
\]
The symbol $\sim$ is read ``is equivalent to''.

A small excursion into the philosophy of mathematical notation:  Suppose I have a large pile of equivalent fractions, such as $\frac{2}{4}$, $\frac{27}{54}$, $\frac{100}{200}$, and so on.  Most people will agree that their favorite way to write the number represented by all these different factors is $\frac{1}{2}$, in which the numerator and denominator are relatively prime.  We usually call this a \emph{reduced fraction}.  This is an example of a \emph{canonical form}, which is an extremely impressive way of saying ``favorite way of writing it down''.  There's a theorem telling us that every rational number can be specified by a unique fraction whose numerator and denominator are relatively prime.  To say that again, but slower, \emph{every} rational number \emph{has} a reduced fraction, and furthermore, that reduced fraction is \emph{unique}.

\subsection{Reduced Row Echelon Form}

Since there are many different augmented matrices that have the same set of solutions, we should find a canonical form for writing our augmented matrices.  This canonical form is called \emph{Reduced Row Echelon Form}\index{Reduced row echelon form}, or RREF for short.  RREF looks like this in general:

\[
\begin{amatrix}{7}
1 & * & 0 & * & 0 & \ldots & 0 		& b^1 \\ 
0 &   & 1 & * & 0 & \ldots & 0 		& b^2 \\
0 && 0 &   & 1 & \ldots & 0 		& b^3 \\  
  &   &   &   & \vdots & \vdots & 0 	& \vdots \\  

  &   &   &   &   &        & 1 		& b^k \\  
0 &   & 0 &   & 0 &        & 0		& 0 \\ 
  &   &   &   & \vdots & \vdots & 0 	& \vdots \\  
0 &   & 0 &   & 0 &        & 0		& 0 \\ 
\end{amatrix}
\]

The first non-zero entry in each row is called the \emph{pivot}\index{Pivot}.    The asterisks denote arbitrary content which could be several columns long.  The following properties describe the RREF.

\begin{enumerate}
\item  In RREF, the pivot of any row is always $1$.

\item The pivot of any given row is always to the right of the pivot of the row above it.

\item The pivot is the only non-zero entry in its column.
\end{enumerate}

\begin{example}$
\begin{amatrix}{3} 
1 & 0 & 7 & 0 \\ 
0 & 1 & 3 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
\end{amatrix}
$
Here is a NON-Example, which breaks all three of the rules: $
\begin{amatrix}{3} 
1 & 0 & 3 & 0 \\ 
0 & 0 & 2 & 0 \\
0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 \\
\end{amatrix}
$
\end{example}
The RREF is a very useful way to write linear systems: it makes it very easy to write down the solutions to the system.

\begin{example}

$
\begin{amatrix}{4} 
1 & 0 & 7 & 0 & 4 \\ 
0 & 1 & 3 & 0 & 1 \\ 
0 & 0 & 0 & 1 & 2 \\ 
0 & 0 & 0 & 0 & 0 \\ 
\end{amatrix}
$

\noindent
When we write this augmented matrix as a system of linear equations, we get the following:


\begin{eqnarray}
	x \phantom{+y}   + 7z   \phantom{+w} & = & 4\nn \\
         \phantom {x+}         y + 3z   \phantom{+w} & = & 1 \nn\\
	\phantom{x+y+z+}           w & = & 2 \nn\\\nn
\end{eqnarray}
Solving from the bottom variables up, we see that $w=2$ immediately.  $z$ is not a pivot, so it is still undetermined.  Set $z=\lambda$.  Then $y=1-3\lambda$ and $z=4-7\lambda$.  More concisely:

\[
\colvec{x\\y\\z\\w} = \colvec{4\\1\\0\\2} + \lambda\colvec{-7\\-3\\1\\0}
\]
So we can read off the solution set directly from the RREF.
\end{example}

Perhaps unsurprisingly in light of the previous discussion, we have a theorem:

\begin{theorem}
Every augmented matrix is row-equivalent to a \emph{unique} augmented matrix in reduced row echelon form.
\end{theorem}

\noindent
Next time, we'll prove it.

\section*{References}

Hefferon, Chapter One, Section 1

Wikipedia, \href{http://en.wikipedia.org/wiki/Row_echelon_form}{Row Echelon Form}

\section*{Review Problems}

\begin{enumerate}

\item Show that this pair of augmented matrices are row equivalent, assuming $ad-bc \neq 0$.

$
\begin{amatrix}{2} 
a & b & x  \\ 
c & d & y  \\ 
\end{amatrix}\sim
\begin{amatrix}{2} 
1 & 0 & \frac{dx-by}{ad-bc}  \\ 
0 & 1 & \frac{ay-cx}{ad-bc}  \\ 
\end{amatrix}
$

\item Consider the augmented matrix: $ \begin{amatrix}{2} 
2 & -1 & 3  \\ 
-6 & 3 & 1  \\ 
\end{amatrix} $

Give a \emph{geometric} reason that the associated system of equations has no solution.  Given a general augmented matrix $
\begin{amatrix}{2} 
a & b & x  \\ 
c & d & y  \\ 
\end{amatrix}$, can you find a condition on the numbers $a,b,c$ and $d$ that create the geometric condition you found?


\item List as many operations on augmented matrices that \emph{preserve} row equivalence as you can.  Explain your answers.  Give examples of operations that break row equivalence.

\item Row equivalence of matrices is an example of an \emph{equivalence relation}.  A relation $\sim$ on a set of objects $U$ is an equivalence relation if the following three properties are satisfied:
\begin{itemize}
\item Reflexive:  For any $x\in U$, we have $x\sim x$.
\item Symmetric:  For any $x,y \in U$, if $x\sim y$ then $y\sim x$.
\item Transitive: For any $x,y$ and $z \in U$, if $x\sim y$ and $y\sim z$ then $x\sim z$.
\end{itemize}

\begin{enumerate}
\item Consider the real numbers with the relation $\geq$.  Is this an equivalence relation?  Why or why not?
\item Consider the set of Euclidean triangles with the relation of similarity.  (Recall that two triangles are similar if all of their angles are equal.)  Is this an equivalence relation?  Why or why not?
\item Show that row equivalence of augmented matrices is an equivalence relation.
\end{enumerate}

\end{enumerate}

\newpage

