
\section{Elementary Row Operations}

Our goal is to begin with an arbitrary matrix and apply operations that respect row equivalence until we have a matrix in Reduced Row Echelon Form (RREF).  The three elementary row operations\index{Elementary row operations} are:

\begin{itemize}
\item (Row Swap) Exchange any two rows.
\item (Scalar Multiplication) Multiply any row by a constant.
\item (Row Sum) Add a multiple of one row to another row.
\end{itemize}

Why do these preserve the linear system in question?  Swapping rows is just changing the order of the equations begin considered, which certainly should not alter the solutions.  Scalar multiplication is just multiplying the equation by the same number on both sides, which does not change the solution(s) of the equation.  Likewise, if two equations share a common solution, adding one to the other preserves the solution.  

There is a very simple process for row reducing a matrix, working column by column.  This process is called \emph{Gauss--Jordan elimination}\index{Gauss--Jordan elimination} or simply Gaussian elimination\index{Gaussian elimination}.

\begin{enumerate}
\item If all entries in a given column are zero, then the associated variable is undetermined; make a note of the undetermined variable(s) and then ignore all such columns.

\item Swap rows so that the first entry in the first column is non-zero.  

\item Multiply the first row by $\lambda$ so that the pivot is $1$.

\item Add multiples of the first row to each other row so that the first entry of every other row is zero.

\item Now ignore the first row and first column and repeat steps 1-5 until the matrix is in RREF.
\end{enumerate}

\begin{example}
    \begin{equation*}
      \begin{linsys}{2}
                &   &  3x_3  &=  &9  \\[1mm]
            x_1  &+ 5x_2 & - 2x_3   &=  &2 \\[1mm]
            \frac{1}{3}x_1  &+ 2x_2 &    &=  &3  
      \end{linsys}
    \end{equation*}
First we write the system as an augmented matrix:


\begin{eqnarray*}
\begin{amatrix}{3} 
0 & 0 & 3 & 9 \\ 
1 & 5 & -2& 2 \\
\frac{1}{3} & 2 & 0 & 3 \\
\end{amatrix} & \stackrel{R_1\leftrightarrow R_2}{\sim} & \begin{amatrix}{3} 
\frac{1}{3} & 2 & 0 & 3 \\
1 & 5 & -2& 2 \\
0 & 0 & 3 & 9 \\ 
\end{amatrix}\\
 & \stackrel{3R_1}{\sim} & \begin{amatrix}{3} 
1 & 6 & 0 & 9 \\
1 & 5 & -2& 2 \\
0 & 0 & 3 & 9 \\ 
\end{amatrix}\\
 & \stackrel{R_2=R_2-R_1}{\sim} & \begin{amatrix}{3} 
1 & 6 & 0 & 9 \\
0 & -1 & -2 & -7 \\
0 & 0 & 3 & 9 \\ 
\end{amatrix}\\
 & \stackrel{-R_2}{\sim} & \begin{amatrix}{3} 
1 & 6 & 0 & 9 \\
0 & 1 & 2 & 7 \\
0 & 0 & 3 & 9 \\
\end{amatrix}\\
 & \stackrel{R_1=R_1-6R_2}{\sim} & \begin{amatrix}{3} 
1 & 0 & -12 & -33 \\
0 & 1 & 2 & 7 \\
0 & 0 & 3 & 9 \\ 
\end{amatrix}\\
 & \stackrel{\frac{1}{3}R_3}{\sim} & \begin{amatrix}{3} 
1 & 0 & -12 & -33 \\
0 & 1 & 2 & 7 \\
0 & 0 & 1 & 3 \\ 
\end{amatrix}\\
 & \stackrel{R_1=R_1+12R_3}{\sim} & \begin{amatrix}{3} 
1 & 0 & 0 & 3 \\
0 & 1 & 2 & 7 \\
0 & 0 & 1 & 3 \\ 
\end{amatrix}\\
 & \stackrel{R_2=R_2-2R_3}{\sim} & \begin{amatrix}{3} 
1 & 0 & 0 & 3 \\
0 & 1 & 0 & 1 \\
0 & 0 & 1 & 3 \\ 
\end{amatrix}\\
\end{eqnarray*}
Now we're in RREF and can see that the solution to the system is given by $x_1=1$, $x_2=3$, and $x_3=1$; it happens to be a unique solution.  Notice that we kept track of the steps we were taking; this is important for checking your work!
\end{example}

\begin{example}
\begin{eqnarray*}
 &  & \begin{amatrix}{4} 
1 & 0 & -1& 2 & -1 \\
1 & 1 & 1 & -1& 2  \\
0 & -1& -2& 3 & -3 \\
5 & 2 & -1& 4 &  1 \\
\end{amatrix}\\
 & \stackrel{R_2-R_1; R_4-5R_2}{\sim} & \begin{amatrix}{4} 
1 & 0 & -1& 2 & -1 \\
0 & 1 & 2 & -3& 3  \\
0 & -1& -2& 3 & -3 \\
0 & 2 & 4 & -6 & 6 \\
\end{amatrix}\\
 & \stackrel{R_3+R_2; R_4-2R_3}{\sim} & \begin{amatrix}{4} 
1 & 0 & -1& 2 & -1 \\
0 & 1 & 2 & -3& 3  \\
0 & 0 & 0 & 0 & 0  \\
0 & 0 & 0 & 0 & 0  \\
\end{amatrix}\\
\end{eqnarray*}
Here the variables $x_3$ and $x_4$ are undetermined; the solution is not unique.  Set $x_3=\lambda$ and $x_4=\mu$ where $\lambda$ and $\mu$ are {\it arbitrary} real numbers.  Then we can write $x_1$ and $x_2$ in terms of $\lambda$ and $\mu$ as follows:

\begin{eqnarray*}
x_1 & = &  \phantom{-2}\lambda -2\mu -1 \\
x_2 & = & -2 \lambda +3\mu +3
\end{eqnarray*}
We can write the solution set with vectors like so:

\[
\colvec{x_1\\x_2\\x_3\\x_4} = 
\colvec{-1\\3\\0\\0} 
+ \lambda \colvec{1\\-2\\1\\0} 
+ \mu \colvec{-2\\3\\0\\1} 
\]
This is our preferred form for writing the set of solutions for a linear system with many solutions.

\end{example}

\section*{Uniqueness of Gauss-Jordan Elimination}

\begin{theorem}Gauss-Jordan Elimination produces a unique augmented matrix in RREF.
\end{theorem}

\begin{proof}
Suppose Alice and Bob compute the RREF for a linear system but get different results, $A$ and $B$.  Working from the left, discard all columns except for the pivots and the first column in which $A$ and $B$ differ.  By the exercise, removing columns does not affect row equivalence.  Call the new, smaller, matrices $\hat{A}$ and $\hat{B}$.  The new matrices should look this: $\hat{A}=\begin{amatrix}{1}
I_N & a\\
0 & 0
\end{amatrix}$ and $\hat{B}=\begin{amatrix}{1}
I_N & b\\
0 & 0
\end{amatrix}$, where $I_N$ is an $N\times N$ identity matrix and $a$ and $b$ are vectors.

Now if $\hat{A}$ and $\hat{B}$ have the same solution, then we must have $a=b$.  But this is a contradiction!  Then $A=B$.
\end{proof}

\section*{References}

Hefferon, Chapter One, Section 1.1 and 1.2

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

Wikipedia, \href{http://en.wikipedia.org/wiki/Elementary_matrix_transformations}{Elementary Matrix Operations}

\section*{Review Problems}

\begin{enumerate}
\item Explain why row equivalence is not affected by removing columns.  Is row equivalence affected by removing rows?  Prove or give a counter-example.

\item (Gaussian Elimination) Another method for solving linear systems is to use row operations to bring the augmented matrix to row-echelon form.  In row echelon form, the pivots are not necessarily set to one, and we only require that all entries left of the pivots are zero, not necessarily entries above a pivot.  Provide a counterexample to show that row-echelon form is not unique.

Once a system is in row echelon form, it can be solved by ``back substitution.''  Write the following row echelon matrix as a system of equations, then solve the system using back-substitution.

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

\item Explain why the linear system has no solutions:

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

For which values of $k$ does the system below have a solution?

    \begin{equation*}
      \begin{linsys}{2}
            x  & -3y  &  &=  & 6  \\
            x  &  & +3z   &=  & -3 \\
            2x & +ky & +(3-k)z   &=  &1  
      \end{linsys}
    \end{equation*}



\end{enumerate}

\newpage

