gr1.tex

% Chapter 1, Section 1 _Linear Algebra_ Jim Hefferon
%  http://joshua.smcvt.edu/linearalgebra
%  2001-Jun-09
\chapter{Linear Systems}
\section{Solving Linear Systems}
Systems of linear equations are common in science and mathematics.
These two examples from high school science \cite{Onan}
give a sense of how they arise.

The first example is from 
\hypertarget{ex:Statics}{Statics}.\index{Statics problem}
Suppose that we have three objects,
we know that one has a mass of 2~kg,
and we want to find the two unknown masses.
Suppose further that
experimentation with a meter stick produces these two balances.
\begin{center}
  \includegraphics{ch1.1}
  \qquad
  \includegraphics{ch1.2}
\end{center}
For the masses to balance we must have that
the sum of moments on the left equals the sum of moments on
the right, where the moment of an object is its mass times its distance 
from the balance point. 
That gives a system of two linear equations.
\begin{align*}  % odd formatting to match chem problem below
      40h + 15c &= 100  \\
            25c &= 50+50h
\end{align*}

The second example
is from Chemistry.\index{Chemistry problem}
We can mix, under controlled conditions, toluene $\hbox{C}_7\hbox{H}_8$ and 
nitric acid $\hbox{H}\hbox{N}\hbox{O}_3$ to produce
trinitrotoluene $\hbox{C}_7\hbox{H}_5\hbox{O}_6\hbox{N}_3$
along with the byproduct water
(conditions have to be very well controlled\Dash trinitrotoluene 
is better known as TNT).
In what proportion should we mix them?
The number of atoms of each element present before the reaction
\begin{equation*}
    x\,{\rm C}_7{\rm H}_8\ +\ y\,{\rm H}{\rm N}{\rm O}_3
    \quad\longrightarrow\quad
    z\,{\rm C}_7{\rm H}_5{\rm O}_6{\rm N}_3\ +\ w\,{\rm H}_2{\rm O}
\tag*{}\end{equation*}
must equal the number present afterward.
Applying that in turn to the elements C, H, N, and O gives
this system.
\begin{align*}  % odd formatting to state more naturally
      7x      &= 7z  \\
      8x +1y  &= 5z+2w  \\
      1y      &= 3z  \\
      3y      &= 6z+1w
\end{align*}

Both examples come down to solving a system of equations.
In each system, the equations involve only the first power of each variable.
This chapter shows how to solve any such system.















\subsection{Gauss's Method}
\begin{definition}\label{def:linearcombination}
%<*df:linearcombination>
A \definend{linear combination}\index{linear combination} of
\( x_1 \), \ldots, \( x_n \) has the form
\begin{equation*}
   a_1x_1+a_2x_2+a_3x_3+\cdots+a_nx_n
\end{equation*}
where the numbers \( a_1, \ldots ,a_n\in\Re \) are the combination's
\definend{coefficients}\index{linear equation!coefficients}.
%</df:linearcombination>
%<*df:linearequations>
A \definend{linear equation}\index{linear equation} 
in the variables $x_1$, \ldots, $x_n$ 
has the form
$a_1x_1+a_2x_2+a_3x_3+\cdots+a_nx_n=d$
where
\( d\in\Re \) is the \definend{constant}\index{linear equation!constant}.

An \( n \)-tuple \( (s_1,s_2,\ldots ,s_n)\in\Re^n \) is a 
\definend{solution}\index{linear equation!solution of} %
of, or \definend{satisfies}, that equation if substituting the numbers
$s_1$, \ldots, $s_n$ for the variables
gives a true statement:
$a_1s_1+a_2s_2+\cdots+a_ns_n=d$.
A \definend{system of linear equations}\index{linear equation!system of}%
\index{system of linear equations} 
\begin{equation*}
  \begin{linsys}{4}
    a_{1,1}x_1 &+ &a_{1,2}x_2  &+  &\cdots &+ &a_{1,n}x_n &=  &d_1  \\
    a_{2,1}x_1 &+ &a_{2,2}x_2  &+  &\cdots &+ &a_{2,n}x_n &=  &d_2  \\
             &  &           &   &       &  &          &\vdotswithin{=}  \\
    a_{m,1}x_1 &+ &a_{m,2}x_2  &+  &\cdots &+ &a_{m,n}x_n &=  &d_m
  \end{linsys}
\end{equation*}
has the solution
\( (s_1,s_2,\ldots ,s_n) \) if that $n$-tuple is a solution of all
of the equations.
%</df:linearequations>
\end{definition}


\begin{example}
The combination \( 3x_1 + 2x_2 \) of $x_1$ and $x_2$ is linear.
The combination \( 3x_1^2 + 2\sin(x_2) \) is not linear, nor is
\( 3x_1^2 + 2x_2 \).  
\end{example}

\begin{example}
The ordered pair \( (-1,5) \) is a solution of this system.
\begin{equation*}
  \begin{linsys}{2}
    3x_1 &+ &2x_2 &= &7  \\
    -x_1 &+ &x_2  &= &6
  \end{linsys}
\end{equation*}
In contrast, \( (5,-1) \) is not a solution.
\end{example}

Finding the set of all solutions is 
\definend{solving}\index{system of linear equations!solving} 
the system.
We don't need 
guesswork or good luck, 
there is an algorithm that always works.
This algorithm is  
\definend{Gauss's Method}\index{Gauss's Method}%
\index{system of linear equations!Gauss's Method} 
(or \definend{Gaussian elimination}\index{Gaussian elimination}%
\index{system of linear equations!Gaussian elimination}
or \definend{linear elimination}\index{linear elimination}%
\index{system of linear equations!linear elimination}%
\index{system of linear equations!elimination}%
\index{elimination, Gaussian}).
% It transforms the system, step by step, into one
% with a form that we can easily solve.
% We will first illustrate how it goes and then we will see the 
% formal statement. 

\begin{example}
To solve this system
\begin{equation*}
  \begin{linsys}{3}
                     &   &      &   &3x_3  &=  &9  \\
                 x_1 &+  &5x_2  &-  &2x_3  &=  &2  \\
      \frac{1}{3}x_1 &+  &2x_2  &   &      &=  &3  
  \end{linsys}
\end{equation*}
we transform it, step by step, until it is in a form that
we can easily solve.

The first transformation
rewrites the system by interchanging the first and third row.
\begin{align*}
  \quad
  &\grstep{ \text{swap row 1 with row 3} }
  \begin{linsys}{3}
        \frac{1}{3}x_1 &+  &2x_2  &   &      &=  &3  \\
                   x_1 &+  &5x_2  &-  &2x_3  &=  &2  \\
                       &   &      &   &3x_3  &=  &9  
    \end{linsys}                                         
\end{align*}
The second transformation rescales the first row by a factor of~$3$.
\begin{align*}
\quad
  &\grstep{ \text{multiply row 1 by 3} }
  \begin{linsys}{3}
        x_1 &+  &6x_2  &   &      &=  &9  \\
        x_1 &+  &5x_2  &-  &2x_3  &=  &2  \\
            &   &      &   &3x_3  &=  &9  
   \end{linsys}                                          
\end{align*}
The third transformation is the only nontrivial one in this example.
We mentally multiply both sides of the first row by \( -1 \),
mentally add that to the second row,
and write the result in as the new second row.
\begin{align*}
  &\grstep{ \text{add \(-1\) times row 1 to row 2} }
  \begin{linsys}{3}
        x_1 &+  &6x_2  &   &      &=  &9  \\
            &   &-x_2  &-  &2x_3  &=  &-7 \\
            &   &      &   &3x_3  &=  &9  
   \end{linsys}
\end{align*}
These steps have brought the system to a
form where we can easily find the value of each variable.
The bottom equation shows that \( x_3=3 \).
Substituting $3$ for \( x_3 \) in the middle equation shows that \( x_2=1 \).
Substituting those two into the top equation
gives that \( x_1=3 \). 
Thus the system has a unique solution; 
the solution set is \set{(3,1,3)}.
\end{example}

Most of this subsection and the next one consists of examples
of solving linear systems by Gauss's Method, which 
we will use throughout the book.
It is fast and easy.
But before we do those examples we will first show that
it is also safe: 
Gauss's Method never loses solutions
(any tuple that is a solution to the system before you apply the method is also
a solution after), nor does it ever 
pick up extraneous solutions
(any tuple that is not a solution before is also not a solution after).

\begin{theorem}[Gauss's Method]
\index{linear equation!solution of!Gauss's Method} \label{th:GaussMethod}
%<*th:GaussMethod>
If a linear system is changed to another by one of these operations
\begin{enumerate}
  \setlength{\itemsep}{0ex}
  \item
    an equation is swapped with another
  \item
    an equation has both sides multiplied by a nonzero constant
  \item
    an equation is replaced by the sum of itself and a multiple of another
\end{enumerate}
then the two systems have the same set of solutions.
%</th:GaussMethod>
\end{theorem}

Each of the three Gauss's Method operations has a restriction.
Multiplying a row by~\( 0 \) is not allowed because obviously that
can change the solution set.
Similarly, adding a multiple of a row to itself is not allowed because
adding~\( -1 \) times the row to itself has the effect of multiplying the row
by~\( 0 \).
We disallow swapping a row with itself
to make some results in the fourth chapter easier,
and also because it's pointless.

\begin{proof}
We will cover the equation swap operation here. 
The other two
cases are \nearbyexercise{ex:ProveGaussMethod}.

%<*pf:GaussMethod0>
Consider a linear system.
\begin{equation*}
  \begin{linsys}{4}
    a_{1,1}x_1  &+  &a_{1,2}x_2 &+  &\cdots  &+ &a_{1,n}x_n  &=  &d_1  \\
                &   &           &   &        &   &     &\vdotswithin{=}  \\
    a_{i,1}x_1  &+  &a_{i,2}x_2 &+  &\cdots  &+ &a_{i,n}x_n  &=  &d_i  \\
                &   &           &   &        &   &     &\vdotswithin{=}  \\
    a_{j,1}x_1  &+  &a_{j,2}x_2 &+  &\cdots  &+ &a_{j,n}x_n  &=  &d_j  \\
                &   &           &   &        &   &     &\vdotswithin{=} \\
    a_{m,1}x_1  &+  &a_{m,2}x_2 &+  &\cdots  &+ &a_{m,n}x_n  &=  &d_m  
  \end{linsys}
\end{equation*} 
The tuple \( (s_1,\ldots\,,s_n) \)
satisfies this system  
if and only if substituting the values for the
variables, the $s$'s for the $x$'s, gives a conjunction of true statements:
$a_{1,1}s_1+a_{1,2}s_2+\cdots+a_{1,n}s_n=d_1$
and \ldots\ 
$a_{i,1}s_1+a_{i,2}s_2+\cdots+a_{i,n}s_n=d_i$
and \ldots\  $a_{j,1}s_1+a_{j,2}s_2+\cdots+a_{j,n}s_n=d_j$
and \ldots\  $a_{m,1}s_1+a_{m,2}s_2+\cdots+a_{m,n}s_n=d_m$.
%</pf:GaussMethod0>

%<*pf:GaussMethod1>
In a list of statements joined with `and' we can  
rearrange the order of the statements. 
Thus
this requirement is met if and only if
$a_{1,1}s_1+a_{1,2}s_2+\cdots+a_{1,n}s_n=d_1$
and \ldots\  $a_{j,1}s_1+a_{j,2}s_2+\cdots+a_{j,n}s_n=d_j$
and \ldots\  $a_{i,1}s_1+a_{i,2}s_2+\cdots+a_{i,n}s_n=d_i$
and \ldots\  $a_{m,1}s_1+a_{m,2}s_2+\cdots+a_{m,n}s_n=d_m$.
This is exactly the requirement that \( (s_1,\ldots\,,s_n) \) 
solves the system after the row swap.
%</pf:GaussMethod1>
\end{proof}

\begin{definition} \label{df:GaussMethod}
%<*df:GaussMethod>
The three operations from 
\nearbytheorem{th:GaussMethod}
are the
\definend{elementary reduction 
operations},\index{Gauss's Method!elementary operations}%
\index{elementary reduction operations}
or \definend{row operations}\index{elementary row operations},
or \definend{Gaussian operations}.
They are
\definend{swapping}\index{elementary reduction operations! swapping}%
\index{swapping rows},
\definend{multiplying by a scalar} (or
\definend{rescaling}\index{elementary reduction operations! rescaling}%
\index{rescaling rows}), and
\definend{row combination}\index{elementary reduction operations! row combination}%
\index{combining rows}\index{adding rows}.
%</df:GaussMethod>
\end{definition}

When writing out the calculations, we will 
abbreviate `row \(i\)' by `\( \rho_i \)'.
For instance, we will denote a row combination operation by 
\( k\rho_i+\rho_j \), 
with the row that changes written second.
To save writing we will 
often combine addition steps when they use the same $\rho_i$ as in the
next example.

\begin{example}
Gauss's Method systematically applies the row operations to solve a system.
Here is a typical case.
\begin{equation*}
  \begin{linsys}{3}
    x  &+  &y  &   &   &=  &0  \\
   2x  &-  &y  &+  &3z &=  &3  \\
    x  &-  &2y &-  &z  &=  &3  
  \end{linsys}
\end{equation*}
We begin by using the first row to 
eliminate the $2x$ in the second row and the $x$ in the third.
To get rid of the $2x$ we mentally multiply the entire first row by $-2$, 
add that to the
second row, and write the result in as the new second row.
To eliminate the~$x$ in the third row we multiply the first row by
$-1$, add that to the third row, and write the result in as the
new third row.
\begin{align*}
  &\grstep[-\rho_1 +\rho_3]{-2\rho_1 +\rho_2}
  \begin{linsys}{3}
     x  &+  &y  &   &   &=  &0  \\
        &   &-3y&+  &3z &=  &3  \\
        &   &-3y&-  &z  &=  &3  
  \end{linsys}   
\end{align*}
% In this version of the system, the last two equations involve only two unknowns.
We finish by transforming the second system into a third, where the
bottom equation involves only one unknown. 
We do that by using 
the second row to eliminate the $y$~term from the third row.
\begin{equation*}
  \grstep{-\rho_2 +\rho_3}
  \begin{linsys}{3}
     x  &+  &y  &   &   &=  &0  \\
        &   &-3y&+  &3z &=  &3  \\
        &   &   &   &-4z&=  &0
   \end{linsys}
\end{equation*}
Now finding the system's solution is easy.
The third row gives \( z=0 \).
Substitute that back\index{Gauss's Method!back-substitution}%
\index{back-substitution}
into the second row to get \( y=-1 \).
Then substitute back into the first row to get \( x=1 \).
\end{example}

\begin{example}
For the Physics problem\index{Statics problem} from the start of this
chapter, Gauss's Method gives this.
\begin{equation*}
   \begin{linsys}{2}
     40h  &+  &15c  &=  &100      \\
     -50h &+  &25c  &=  &50         
   \end{linsys}
   \grstep{5/4\rho_1 +\rho_2}
   \begin{linsys}{2}
      40h  &+  &15c       &=  &100      \\
           &   &(175/4)c  &=  &175 
    \end{linsys}
\end{equation*}
So \( c=4 \), and back-substitution gives that \( h=1 \).
(We will solve the Chemistry problem later.)
\end{example}

\begin{example}
The reduction
\begin{align*}
   \begin{linsys}{3}
        x  &+  &y  &+  &z  &=  &9  \\
       2x  &+  &4y &-  &3z &=  &1  \\
       3x  &+  &6y &-  &5z &=  &0  
   \end{linsys}
   &\grstep[-3\rho_1 +\rho_3]{-2\rho_1 +\rho_2}
   \begin{linsys}{3}
      x  &+  &y  &+  &z  &=  &9  \\
         &   &2y &-  &5z &=  &-17\\
         &   &3y &-  &8z&=  &-27
    \end{linsys}                                    \\
   &\grstep{-(3/2)\rho_2+\rho_3}
   \begin{linsys}{3}
      x  &+  &y  &+  &z            &=  &9  \\
         &   &2y &-  &5z           &=  &-17\\
         &   &   &   &-(1/2)z      &=  &-(3/2) 
    \end{linsys}
\end{align*}
shows that \( z=3 \), \( y=-1 \), and \( x=7 \).
\end{example}

As illustrated above, the point of Gauss's Method 
is to use the elementary reduction
operations to set up back-substitution.

\begin{definition} \label{df:EchelonForm}
%<*df:EchelonForm>
In each row of a system, 
the first variable with a nonzero coefficient is the row's
\definend{leading variable}\index{echelon form!leading variable}%
\index{leading!variable}. % 
A system is in \definend{echelon form}\index{echelon form}
if each leading variable
is to the right of the leading variable in the row above it,
except for the leading variable in the first row,
and any all-zero rows are at the bottom.
%</df:EchelonForm>
\end{definition}

\begin{example} 
The prior three examples only used the operation of row combination.
This linear system requires the swap operation
to get it into echelon form because 
after the first combination
\begin{align*}
   \begin{linsys}{4}
                x  &-  &y  &   &   &   &   &=  &0  \\
               2x  &-  &2y &+  &z  &+  &2w &=  &4  \\
                   &   &y  &   &   &+  &w  &=  &0  \\
                   &   &   &   &2z &+  &w  &=  &5  
   \end{linsys}
   &\grstep{-2\rho_1 +\rho_2}
   \begin{linsys}{4}
      x  &-  &y  &\spaceforemptycolumn   &   &   &   &=  &0  \\
         &   &   &   &z  &+  &2w &=  &4  \\
         &   &y  &   &   &+  &w  &=  &0  \\
         &   &   &   &2z &+  &w  &=  &5  
   \end{linsys}    
\end{align*}
the second equation has no leading $y$.
We exchange it for a lower-down row that has a leading $y$.
\begin{align*}
   &\grstep{\rho_2 \leftrightarrow\rho_3}
   \begin{linsys}{4}
      x  &-  &y  &\spaceforemptycolumn   &   &   &   &=  &0  \\
         &   &y  &   &   &+  &w  &=  &0  \\
         &   &   &   &z  &+  &2w &=  &4  \\
         &   &   &   &2z &+  &w  &=  &5  
    \end{linsys}    
\end{align*}
(Had there been more than one suitable row below the second
then we could have used any one.)
With that, Gauss's Method proceeds as before.
\begin{align*}
   &\grstep{-2\rho_3 +\rho_4}
   \begin{linsys}{4}
      x  &-  &y  &\spaceforemptycolumn   &   &   &   &=  &0  \\
         &   &y  &   &   &+  &w  &=  &0  \\
         &   &   &   &z  &+  &2w &=  &4  \\
         &   &   &   &   &   &-3w&=  &-3 
    \end{linsys}
\end{align*}
Back-substitution gives \( w=1 \), \( z=2 \) , \( y=-1 \), and \( x=-1 \).
\end{example}

Strictly speaking, to solve linear systems we don't need 
the row rescaling operation.  
We have introduced it here because it is convenient and because we will use it 
later in this chapter as part of a variation of Gauss's Method, 
the Gauss-Jordan Method.

All of the systems so far have the same number of equations as unknowns.
All of them have a solution and for all of them there is only one solution.
We finish this subsection by seeing
other things that can happen.

\begin{example} \label{ex:MoreEqsThanUnks}
This system 
has more equations than variables.
\begin{equation*}
    \begin{linsys}{2}
      x  &+  &3y  &=  &1  \\
     2x  &+  &y   &=  &-3 \\
     2x  &+  &2y  &=  &-2 
    \end{linsys}  
\end{equation*}
Gauss's Method helps us understand this system also, since this
\begin{align*}
    &\grstep[-2\rho_1 +\rho_3]{-2\rho_1 +\rho_2}
    \begin{linsys}{2}
       x  &+  &3y  &=  &1  \\
          &   &-5y &=  &-5 \\
          &   &-4y &=  &-4 
     \end{linsys}
\end{align*}
shows that one of the equations is redundant.
Echelon form
\begin{equation*}
    \grstep{-(4/5)\rho_2 +\rho_3}
    \begin{linsys}{2}
       x  &+  &3y  &=  &1  \\
          &   &-5y &=  &-5 \\
          &   &0   &=  &0  
     \end{linsys}
\end{equation*}
gives that \( y=1 \) and \( x=-2 \).
The `\( 0=0 \)' reflects the redundancy.
\end{example}

Gauss's Method is also useful on systems with more variables than equations.
The next subsection has many examples.

Another way that linear systems can differ from the examples shown above 
is that some linear systems do not have a unique solution.
This can happen in two ways.
The first is that a system can fail to have any solution at all.

\begin{example} \label{ex:MoreEqsThanUnksInconsis}
Contrast the system in the last example with this one.
\begin{equation*}
    \begin{linsys}{2}
      x  &+  &3y  &=  &1  \\
     2x  &+  &y   &=  &-3 \\
     2x  &+  &2y  &=  &0  
    \end{linsys}
    \grstep[-2\rho_1 +\rho_3]{-2\rho_1 +\rho_2}
    \begin{linsys}{2}
       x  &+  &3y  &=  &1  \\
          &   &-5y &=  &-5 \\
          &   &-4y &=  &-2
     \end{linsys}
\end{equation*}
Here the system is inconsistent:~no pair of numbers $(s_1,s_2)$ satisfies 
all three equations simultaneously.
Echelon form makes the inconsistency obvious.
\begin{equation*}
  \grstep{-(4/5)\rho_2 +\rho_3}
  \begin{linsys}{2}
     x  &+  &3y  &=  &1  \\
        &   &-5y &=  &-5 \\
        &   &0   &=  &2 
   \end{linsys}
\end{equation*}
The solution set is empty.
\end{example}

\begin{example}
The prior system has more equations than unknowns but
that is not what causes the inconsistency\Dash 
\nearbyexample{ex:MoreEqsThanUnks}
has more equations than unknowns and yet is consistent.
Nor is having more equations than unknowns necessary for
inconsistency, as we see with this inconsistent system that has the 
same number of equations as unknowns.
\begin{equation*}
  \begin{linsys}{2}
    x  &+  &2y  &=  &8  \\
   2x  &+  &4y  &=  &8  
  \end{linsys}
  \grstep{-2\rho_1 + \rho_2}
  \begin{linsys}{2}
     x  &+  &2y  &=  &8  \\
        &   &0   &=  &-8
   \end{linsys}
\end{equation*}
Instead, 
inconsistency has to do with the interaction of the left and right sides;
in the first system above the left side's second equation is twice the
first but the right side's second constant is not twice the first.
Later we will have more to say about dependencies between a system's 
parts.
\end{example}

The other way that 
a linear system can fail to have a unique solution, besides having no solutions,
is to have many solutions.

\begin{example}
In this system
\begin{equation*}
  \begin{linsys}{2}
    x  &+  &y   &=  &4  \\
   2x  &+  &2y  &=  &8  
  \end{linsys}
\end{equation*}
any pair of numbers satisfying the first equation also
satisfies the second.
The solution set 
% \( \{ (x,y)\suchthat x+y=4 \} \) 
\( \set{ (x,y)\suchthat x+y=4} \) 
is infinite; some example
member pairs are~$(0,4)$, $(-1,5)$, and $(2.5,1.5)$.

The result of applying Gauss's Method here contrasts with the prior example
because we do not get a contradictory equation.
\begin{equation*}
  \grstep{-2\rho_1 + \rho_2}
  \begin{linsys}{2}
    x  &+  &y   &=  &4  \\
       &   &0   &=  &0  
   \end{linsys}
\end{equation*}
\end{example}

Don't be fooled by that example:~a $0=0$ equation  
is not the signal that a system has many solutions.

\begin{example}  \label{ex:NoZerosInfManySols}
The absence of a \( 0=0 \) equation does not keep a system from having
many different solutions.
This system is in echelon form,
has no $0=0$, but has infinitely many solutions,
including $(0,1,-1)$, 
$(0,1/2,-1/2)$, $(0,0,0)$, and $(0,-\pi,\pi)$
(any triple whose first component is $0$ and whose second component is the 
negative of the third is a solution).
\begin{equation*}
  \begin{linsys}{3}
     x  &+  &y  &+  &z  &=  &0  \\
        &   &y  &+  &z  &=  &0  
   \end{linsys}
\end{equation*}

Nor does the presence of \( 0=0 \) mean that the system must have 
many solutions.
\nearbyexample{ex:MoreEqsThanUnks} shows that.
So does this system, which does not have 
any solutions at all despite that 
in echelon form it has a $0=0$ row.
\begin{align*}
  \begin{linsys}{3}
    2x  &   &   &-   &2z  &=  &6  \\
        &   &y  &+   &z   &=  &1  \\
    2x  &+  &y  &-   &z   &=  &7  \\
        &   &3y &+   &3z  &=  &0  
  \end{linsys}
  &\grstep{-\rho_1 +\rho_3}
  \begin{linsys}{3}
     2x  &\spaceforemptycolumn   &   &-   &2z  &=  &6  \\
         &   &y  &+   &z   &=  &1  \\
         &   &y  &+   &z   &=  &1  \\
         &   &3y &+   &3z  &=  &0  
  \end{linsys}                                    \\
  &\grstep[-3\rho_2 +\rho_4]{-\rho_2 +\rho_3}
  \begin{linsys}{3}
     2x  &\spaceforemptycolumn    &   &-   &2z  &=  &6  \\
         &   &y  &+   &z   &=  &1  \\
         &   &   &    &0   &=  &0  \\
         &   &   &    &0   &=  &-3 
   \end{linsys}
\end{align*}
\end{example}

In summary,
Gauss's Method uses the row operations to 
set a system up for back substitution.
If any step shows a contradictory equation then we can stop with the
conclusion that the system has no solutions.
If we reach echelon form without a contradictory equation,
and each variable is a leading variable in its
row, then the system has a unique solution and we find it by
back substitution.
Finally, if we reach echelon form without a contradictory equation,
and there is not a unique solution\Dash
that is, at least one variable is not a leading variable\Dash
then the system has many solutions.

The next subsection explores the third case.
We will see that such a system must have infinitely many solutions
and we will describe the
solution set.


\medskip
\noindent\textbf{Note.}\hspace*{.2em}
\textit{Here, and in the rest of the book,
you must justify all of your exercise answers.
For instance, if a question asks whether a system has a solution then you
must justify a yes response by producing the solution and must justify 
a no response by showing that no solution exists.}
\begin{exercises}
  \recommended \item 
    Use Gauss's Method to find the unique solution for each system.
    \begin{exparts*}
      \partsitem 
        $\begin{linsys}{2}
          2x  &+  &3y  &=  &13  \\
          x   &-  &y   &=  &-1
        \end{linsys}$
      \partsitem 
        $\begin{linsys}{3}
          x   &  &  &-  &z  &=  &0  \\
          3x  &+ &y &   &   &=  &1  \\
          -x  &+ &y &+  &z  &=  &4
        \end{linsys}$
    \end{exparts*}
    \begin{answer}
      \begin{exparts}
        \partsitem Gauss's Method
          \begin{equation*}
            \grstep{-(1/2)\rho_1+\rho_2}
            \begin{linsys}{2}
               2x  &+  &3y      &=  &13  \\
                   &-  &(5/2)y  &=  &-15/2              
            \end{linsys}
          \end{equation*}
          gives that the solution is $y=3$ and $x=2$.
        \partsitem Gauss's Method here
          \begin{equation*}
            \grstep[\rho_1+\rho_3]{-3\rho_1+\rho_2}
            \begin{linsys}{3}
              x   &  &  &-  &z  &=  &0  \\
                  &  &y &+  &3z &=  &1  \\
                  &  &y &   &   &=  &4
            \end{linsys}
            \grstep{-\rho_2+\rho_3}
            \begin{linsys}{3}
              x   &  &  &-  &z    &=  &0  \\
                  &  &y &+  &3z   &=  &1  \\
                  &  &  &   &-3z  &=  &3
            \end{linsys}
          \end{equation*}
          gives $x=-1$, $y=4$, and $z=-1$.
      \end{exparts}
    \end{answer}
  \recommended \item  
    Use Gauss's Method to solve each system
    or conclude `many solutions' or `no solutions'.
    \begin{exparts*}
      \partsitem \(
               \begin{linsys}[t]{2}
                  2x  &+  &2y  &=  &5  \\
                   x  &-  &4y  &=  &0  
               \end{linsys}
             \)
      \partsitem \(
               \begin{linsys}[t]{2}
                  -x  &+  &y   &=  &1  \\
                   x  &+  &y   &=  &2  
               \end{linsys}
             \) 
      \partsitem  \(
               \begin{linsys}[t]{3}
                   x  &-  &3y  &+  &z  &=  &1  \\
                   x  &+  &y   &+  &2z &=  &14 
                \end{linsys}
             \) 
      \partsitem  \(
               \begin{linsys}[t]{2}
                  -x  &-  &y   &=  &1  \\
                 -3x  &-  &3y  &=  &2  
               \end{linsys}
             \) 
      \partsitem  \(
               \begin{linsys}[t]{3}
                      &   &4y  &+  &z  &=  &20 \\
                  2x  &-  &2y  &+  &z  &=  &0  \\
                   x  &   &    &+  &z  &=  &5  \\
                   x  &+  &y   &-  &z  &=  &10 
                \end{linsys}
             \)
      \partsitem \( \begin{linsys}[t]{4}
                 2x  &   &   &+  &z  &+  &w  &=  &5  \\
                     &   &y  &   &   &-  &w  &=  &-1 \\
                 3x  &   &   &-  &z  &-  &w  &=  &0  \\
                 4x  &+  &y  &+  &2z &+  &w  &=  &9  
               \end{linsys}
            \)
    \end{exparts*}
    \begin{answer} 
      \begin{exparts}
       \partsitem Gaussian reduction
        \begin{equation*}
          \grstep{-(1/2)\rho_1+\rho_2}
          \begin{linsys}{2}
             2x  &+  &2y  &=  &5  \\
                 &   &-5y &=  &-5/2  
          \end{linsys}
        \end{equation*}
        shows that \( y=1/2 \) and \( x=2 \) is the unique solution.
      \partsitem Gauss's Method
        \begin{equation*}
          \grstep{\rho_1+\rho_2}
          \begin{linsys}{2}
             -x  &+  &y   &=  &1  \\
                 &   &2y  &=  &3  
           \end{linsys}
        \end{equation*}
        gives \( y=3/2 \) and \( x=1/2 \) as the only solution.
      \partsitem Row reduction
        \begin{equation*}
            \grstep{-\rho_1+\rho_2}
            \begin{linsys}{3}
                x  &-  &3y  &+  &z  &=  &1  \\
                   &   &4y  &+  &z  &=  &13 
             \end{linsys}
        \end{equation*}
        shows, because the variable $z$ is not a leading variable in any
        row, that there are many solutions.
      \partsitem Row reduction
        \begin{equation*}
          \grstep{-3\rho_1+\rho_2}
          \begin{linsys}{2}
             -x  &-  &y   &=  &1  \\
                 &   &0   &=  &-1 
           \end{linsys}
        \end{equation*}
        shows that there is no solution.
      \partsitem Gauss's Method
        \begin{align*}
            \grstep{\rho_1\leftrightarrow\rho_4}
            \begin{linsys}{3}
                x  &+  &y   &-  &z  &=  &10 \\
               2x  &-  &2y  &+  &z  &=  &0  \\
                x  &   &    &+  &z  &=  &5  \\
                   &   &4y  &+  &z  &=  &20 
             \end{linsys}
            &\grstep[-\rho_1+\rho_3]{-2\rho_1+\rho_2}
            \begin{linsys}{3}
                x  &+  &y   &-  &z  &=  &10 \\
                   &   &-4y &+  &3z &=  &-20\\
                   &   &-y  &+  &2z &=  &-5 \\
                   &   &4y  &+  &z  &=  &20 
             \end{linsys}                                      \\
            &\grstep[\rho_2+\rho_4]{-(1/4)\rho_2+\rho_3}
            \begin{linsys}{3}
                x  &+  &y   &-  &z      &=  &10 \\
                   &   &-4y &+  &3z     &=  &-20\\
                   &   &    &   &(5/4)z &=  &0  \\
                   &   &    &   &4z     &=  &0  
             \end{linsys}
        \end{align*}
        gives the unique solution \( (x,y,z)=(5,5,0) \).
      \partsitem Here Gauss's Method gives
         \begin{align*}
            &\grstep[-2\rho_1+\rho_4]{-(3/2)\rho_1+\rho_3}
            \begin{linsys}{4}
               2x  &\spaceforemptycolumn   &   &+  &z       &+  &w       &=  &5  \\
                   &   &y  &   &        &-  &w       &=  &-1 \\
                   &   &   &-  &(5/2)z  &-  &(5/2)w  &=  &-15/2  \\
                   &   &y  &   &        &-  &w       &=  &-1  
             \end{linsys}                                             \\ 
            &\grstep{-\rho_2+\rho_4}
            \begin{linsys}{4}
               2x  &\spaceforemptycolumn   &   &+  &z       &+  &w       &=  &5  \\
                   &   &y  &   &        &-  &w       &=  &-1 \\
                   &   &   &-  &(5/2)z  &-  &(5/2)w  &=  &-15/2  \\
                   &   &   &   &        &   &0       &=  &0 
             \end{linsys}
         \end{align*}
         which shows that there are many solutions.
      \end{exparts} 
    \end{answer}
  \recommended \item 
    We can solve linear systems by methods other 
    than Gauss's.
    One often taught in high school is to solve one of the 
    equations for a variable, then substitute the resulting expression into
    other equations.
    Then we repeat that step until there is an equation with only one
    variable.
    From that we get the first number in the solution and then we get the
    rest with  
    back-substitution.
    This method takes longer than Gauss's Method, since it involves
    more arithmetic operations, and is also more
    likely to lead to errors.
    To illustrate how it can lead to wrong conclusions, we will use the system 
    \begin{equation*}
      \begin{linsys}{2}
            x  &+  &3y  &=  &1  \\
            2x  &+  &y   &=  &-3 \\
            2x  &+  &2y  &=  &0  
      \end{linsys}
    \end{equation*}
    from \nearbyexample{ex:MoreEqsThanUnksInconsis}.
    \begin{exparts}
      \partsitem Solve the first equation for $x$ and 
        substitute that expression into the second equation.
        Find the resulting $y$.
      \partsitem Again solve the first equation for $x$, 
        but this time substitute that expression into the third equation.
        Find this $y$.
    \end{exparts}
    What extra step must a user of this method take to avoid 
    erroneously concluding a system has a solution?
    \begin{answer}
      \begin{exparts}
        \partsitem From $x=1-3y$ we get that $2(1-3y)+y=-3$, giving $y=1$.
        \partsitem From $x=1-3y$ we get that $2(1-3y)+2y=0$, leading to 
           the conclusion that $y=1/2$.
      \end{exparts}
      Users of this method must check any potential solutions by
      substituting back into all the equations.
    \end{answer}
  \recommended \item 
    For which values of \( k \) are
    there no solutions, many solutions, or a unique solution
    to this system?
    \begin{equation*}
       \begin{linsys}{2}
          x  &-  &y  &=  &1  \\
         3x  &-  &3y &=  &k  
       \end{linsys}
    \end{equation*}
    \begin{answer}
      Do the reduction
      \begin{equation*}
        \grstep{-3\rho_1+\rho_2}
        \begin{linsys}{2}
          x  &-  &y  &=  &1\hfill  \\
             &   &0  &=  &-3+k\hfill  
        \end{linsys}
      \end{equation*}
      to conclude this system has no solutions if \( k\neq 3 \) and if
      \( k=3 \) then it has infinitely many solutions.
      It never has a unique solution.  
    \end{answer}
  \recommended \item 
    This system is not linear in that it says $\sin\alpha$ instead of $\alpha$
    \begin{equation*}
      \begin{linsys}{3}
         2\sin\alpha  &-  &\cos\beta  &+  &3\tan\gamma  &=  &3  \\
         4\sin\alpha  &+  &2\cos\beta &-  &2\tan\gamma  &=  &10  \\
         6\sin\alpha  &-  &3\cos\beta &+  &\tan\gamma   &=  &9  
      \end{linsys}
    \end{equation*}
    and yet we can apply Gauss's Method.
    Do so.
    Does the system have a solution?
    \begin{answer}
      Let \( x=\sin\alpha \), \( y=\cos\beta \), and \( z=\tan\gamma \):
      \begin{equation*}
        \begin{linsys}{3}
           2x  &-  &y  &+  &3z  &=  &3  \\
           4x  &+  &2y &-  &2z  &=  &10  \\
           6x  &-  &3y &+  &z   &=  &9  
        \end{linsys}
         \grstep[-3\rho_1+\rho_3]{-2\rho_1+\rho_2}
         \begin{linsys}{3}
           2x  &-  &y  &+  &3z  &=  &3  \\
               &   &4y &-  &8z  &=  &4   \\
               &   &   &   &-8z &=  &0  
         \end{linsys}
      \end{equation*}
      gives \( z=0 \), \( y=1 \), and \( x=2 \).
      Note that no \( \alpha \) satisfies that requirement.  
      \end{answer}
  \recommended \item 
    % \cite{Anton}
    What conditions must the constants, the $b$'s,
    satisfy so that each of these systems has a solution?
    \textit{Hint.} 
    Apply Gauss's Method and see what happens to the right side.
    \begin{exparts*}
      \partsitem  \(
        \begin{linsys}[t]{2}
           x  &-  &3y  &=  &b_1 \\
          3x  &+  &y   &=  &b_2 \\
           x  &+  &7y  &=  &b_3 \\
          2x  &+  &4y  &=  &b_4 
        \end{linsys}   \)
      \partsitem \(
        \begin{linsys}[t]{3}
           x_1  &+  &2x_2  &+  &3x_3  &=  &b_1  \\
          2x_1  &+  &5x_2  &+  &3x_3  &=  &b_2  \\
           x_1  &   &      &+  &8x_3  &=  &b_3  
        \end{linsys}   \)
    \end{exparts*}
    \begin{answer} 
      \begin{exparts}
       \partsitem Gauss's Method
         \begin{equation*}
           \grstep[-\rho_1+\rho_3 \\ -2\rho_1+\rho_4]{-3\rho_1+\rho_2}
           \begin{linsys}{2}
              x  &-  &3y  &=  &b_1\hfill \\
                 &   &10y &=  &-3b_1+b_2\hfill \\
                 &   &10y &=  &-b_1+b_3\hfill \\
                 &   &10y &=  &-2b_1+b_4\hfill 
            \end{linsys}         
           \grstep[-\rho_2+\rho_4]{-\rho_2+\rho_3}
           \begin{linsys}{2}
              x  &-  &3y  &=  &b_1\hfill \\
                 &   &10y &=  &-3b_1+b_2\hfill \\
                 &   &0   &=  &2b_1-b_2+b_3\hfill \\
                 &   &0   &=  &b_1-b_2+b_4\hfill 
            \end{linsys}
         \end{equation*}
         shows that this system is consistent if and only if both
         \( b_3=-2b_1+b_2 \) and \( b_4=-b_1+b_2 \).
       \partsitem Reduction
         \begin{align*}
            &\grstep[-\rho_1+\rho_3]{-2\rho_1+\rho_2}
            \begin{linsys}{3}
              x_1  &+  &2x_2  &+  &3x_3  &=  &b_1\hfill  \\
                   &   &x_2   &-  &3x_3  &=  &-2b_1+b_2\hfill  \\
                   &   &-2x_2 &+  &5x_3  &=  &-b_1+b_3\hfill  
             \end{linsys}                                          \\
            &\grstep{2\rho_2+\rho_3}
            \begin{linsys}{3}
              x_1  &+  &2x_2  &+  &3x_3  &=  &b_1\hfill  \\
                   &   &x_2   &-  &3x_3  &=  &-2b_1+b_2\hfill  \\
                   &   &      &   &-x_3  &=  &-5b_1+2b_2+b_3\hfill  
             \end{linsys}
         \end{align*}
         shows that each of \( b_1 \), \( b_2 \), and \( b_3 \) can be any
         real number\Dash this system always has a unique solution.
      \end{exparts}   
      \end{answer}
  \item 
    True or false: a system with more unknowns than equations
    has at least one solution.
    (As always, to say `true' you must prove it, while to say 
    `false' you must produce a counterexample.)
    \begin{answer}
      This system with more unknowns than equations
      \begin{equation*}
        \begin{linsys}{3}
          x  &+  &y  &+  &z  &=  &0  \\
          x  &+  &y  &+  &z  &=  &1  
        \end{linsys}
      \end{equation*}
      has no solution.   
      \end{answer}
  \item 
    Must any Chemistry\index{Chemistry problem} problem like
    the one that starts this subsection\Dash
    a balance the reaction problem\Dash have infinitely many solutions?
    \begin{answer}
      Yes.
      For example, the fact that we can have the same reaction 
      in two different flasks shows that twice any solution is another,
      different, solution (if a physical reaction occurs then there must be
      at least one nonzero solution).
    \end{answer}
  \recommended \item 
    Find the coefficients
    \( a \), \( b \), and \( c \) so that the graph of \( f(x)=ax^2+bx+c \) 
    passes through the points \( (1,2) \), \( (-1,6) \), and \( (2,3) \).
    \begin{answer}
      Because \( f(1)=2 \), \( f(-1)=6 \), and \( f(2)=3 \) we get
      a linear system.
      \begin{equation*}
        \begin{linsys}{3}
          1a  &+  &1b  &+  &c  &=  &2  \\
          1a  &-  &1b  &+  &c  &=  &6  \\
          4a  &+  &2b  &+  &c  &=  &3  
         \end{linsys}
      \end{equation*}
      Gauss's Method
      \begin{equation*}
         \grstep[-4\rho_1+\rho_3]{-\rho_1+\rho_2}
         \begin{linsys}{3}
            a  &+  &b  &+  &c  &=  &2  \\
               &   &-2b&   &   &=  &4  \\
               &   &-2b&-  &3c &=  &-5 
          \end{linsys}               
         \grstep{-\rho_2+\rho_3}
         \begin{linsys}{3}
            a  &+  &b  &+  &c  &=  &2  \\
               &   &-2b&   &   &=  &4  \\
               &   &   &   &-3c&=  &-9 
           \end{linsys}
      \end{equation*}
      shows that the solution is \( f(x)=1x^2-2x+3 \).  
      \end{answer}
  \item After \nearbytheorem{th:GaussMethod} we note that multiplying a 
   row by~$0$ is not allowed because that could change a solution set. 
   Give an example of a system with solution set~$S_0$ where after 
   multiplying a row by~$0$ the new system has a solution set~$S_1$
   and $S_0$ is a proper subset of $S_1$.
   Give an example where $S_0=S_1$. 
   \begin{answer}
     Here $S_0=\set{(1,1)}$
     \begin{equation*}
         \begin{linsys}{2}
            x  &+  &y  &=  &2  \\
            x  &-  &y  &=  &0
          \end{linsys}               
         \grstep{0\rho_2}
         \begin{linsys}{2}
            x  &+  &y  &=  &2  \\
               &   &0  &=  &0
          \end{linsys}               
     \end{equation*}
     while $S_1$ is a proper superset because it
     contains at least two points: $(1,1)$ and~$(2,0)$.
     In this example the solution set does not change.  
     \begin{equation*}
         \begin{linsys}{2}
            x  &+  &y  &=  &2  \\
           2x  &+  &2y &=  &4
          \end{linsys}               
         \grstep{0\rho_2}
         \begin{linsys}{2}
            x  &+  &y  &=  &2  \\
               &   &0  &=  &0
          \end{linsys}               
     \end{equation*}
   \end{answer}
  \item 
    Gauss's Method works by combining the equations in a system to make new
    equations.
    \begin{exparts}
      \partsitem Can we derive the equation \( 3x-2y=5 \) by a sequence of
        Gaussian reduction steps from the equations in this system?
        \begin{equation*}
          \begin{linsys}{2}
             x  &+  &y  &=  &1  \\
            4x  &-  &y  &=  &6
          \end{linsys}
        \end{equation*}
      \partsitem Can we derive the equation \( 5x-3y=2 \) with a sequence of
        Gaussian reduction steps from the equations in this system?
        \begin{equation*}
          \begin{linsys}{2}
            2x  &+  &2y &=  &5  \\
            3x  &+  &y  &=  &4
          \end{linsys}
        \end{equation*}
      \partsitem Can we derive \( 6x-9y+5z=-2 \)  
        by a sequence of
        Gaussian reduction steps from the equations in the system?
        \begin{equation*}
          \begin{linsys}{3}
            2x  &+  &y  &-  &z  &=  &4  \\
            6x  &-  &3y &+  &z  &=  &5
          \end{linsys}
        \end{equation*}
    \end{exparts}
    \begin{answer} 
       \begin{exparts} 
        \partsitem Yes, by inspection the given equation results from
          \( -\rho_1+\rho_2 \).
        \partsitem No.
          The pair \( (1,1) \) satisfies the given equation. 
          However, that pair 
          does not satisfy the first equation in the system.
        \partsitem Yes.
          To see if the given row is \( c_1\rho_1+c_2\rho_2 \), solve
          the system of equations relating the coefficients of $x$, $y$,
          $z$, and the constants:
          \begin{equation*}
            \begin{linsys}{2}
               2c_1  &+  &6c_2  &=  &6  \\
                c_1  &-  &3c_2  &=  &-9 \\
               -c_1  &+  &c_2   &=  &5  \\
               4c_1  &+  &5c_2  &=  &-2 
            \end{linsys}
          \end{equation*}
          and get $c_1=-3$ and $c_2=2$, so the given row is
          \( -3\rho_1+2\rho_2 \).
      \end{exparts}  
     \end{answer}
  \item 
    Prove that, where \( a,b,\ldots,e \) are real numbers
    and \( a\neq 0 \), if
    \begin{equation*}
       ax+by=c
    \end{equation*}
    has the same solution set as
    \begin{equation*}
       ax+dy=e
    \end{equation*}
    then they are the same equation.
    What if \( a=0 \)?
    \begin{answer}
      If \( a\neq 0 \) then the solution set of the first equation is
      \( \set{(x,y)\suchthat x=(c-by)/a} \).
      Taking $y=0$ gives the solution $(c/a,0)$, and since the second
      equation is supposed to have the same solution set, substituting into
      it gives that $a(c/a)+d\cdot 0=e$, so $c=e$.
      Then taking $y=1$ in $x=(c-by)/a$ gives that $a((c-b)/a)+d\cdot 1=e$,
      which gives that $b=d$.
      Hence they are the same equation.

      When \( a=0 \) the equations can be different and still have the 
      same solution set:~e.g.,
      \( 0x+3y=6 \) and \( 0x+6y=12 \).   
     \end{answer}
  \recommended \item 
    Show that if \( ad-bc\neq 0 \) then
    \begin{equation*}
      \begin{linsys}{2}
        ax  &+  &by  &=  &j  \\
        cx  &+  &dy  &=  &k  
      \end{linsys}
    \end{equation*}
    has a unique solution.
    \begin{answer}
      We take three cases: that $a\neq 0$, that $a=0$ and 
      $c\neq 0$, and that both $a=0$ and $c=0$.

      For the first, we assume that \( a\neq 0 \).
      Then the reduction
      \begin{equation*}
        \grstep{-(c/a)\rho_1+\rho_2}
        \begin{linsys}{2}
          ax  &+  &by                  &=  &j \hfill\hbox{} \\
              &   &(-(cb/a)+d)y  &=  &-(cj/a)+k \hfill  
         \end{linsys}
      \end{equation*}
      shows that this system has a unique solution if and only if
      \( -(cb/a)+d\neq 0   \); remember that \( a\neq 0 \) so 
      that back substitution yields a unique \( x \)
      (observe, by the way, that \( j \) and \( k \) play no role in the
      conclusion that there is a unique solution, although if there is a 
      unique solution then they contribute to its value).
      But \( -(cb/a)+d = (ad-bc)/a \) and a fraction is not equal to \( 0 \) 
      if and only if its numerator is not equal to \( 0 \).
      Thus, in this first case, there is a unique solution if and only if
      $ad-bc\neq 0$.

      In the second case, if \( a=0 \) but \( c\neq 0 \), then we swap
      \begin{equation*}
        \begin{linsys}{2}
          cx  &+  &dy  &=  &k  \\
              &   &by  &=  &j  
        \end{linsys}
      \end{equation*}
      to conclude that the system has a unique solution if and only if 
      \( b\neq 0 \)
      (we use the case assumption that \( c\neq 0 \) to get a unique
      \( x \) in back substitution).
      But\Dash where \( a=0 \) and \( c\neq 0 \)\Dash
      the condition ``\( b\neq 0 \)''
      is equivalent to the condition ``\( ad-bc\neq 0 \)''.
      That finishes the second case.

      Finally, for the third case,
      if both \( a \) and \( c \) are \( 0 \) then the system
      \begin{equation*}
        \begin{linsys}{2}
          0x  &+  &by  &=  &j  \\
          0x  &+  &dy  &=  &k  
        \end{linsys}
      \end{equation*}
      might have no solutions (if the second equation is not a multiple of the
      first) or it might have infinitely many solutions (if the second
      equation is a multiple of the first then for each \( y \) satisfying
      both equations, any pair \( (x,y) \) will do), but it never has a unique
      solution.
      Note that \( a=0 \) and \( c=0 \) gives that \( ad-bc=0 \).  
    \end{answer}
  \recommended \item 
    In the system
    \begin{equation*}
      \begin{linsys}{2}
         ax  &+  &by  &=  &c  \\
         dx  &+  &ey  &=  &f  
      \end{linsys}
    \end{equation*}
    each of the equations describes a line in the \( xy \)-plane.
    By geometrical reasoning, show that there are three possibilities:
    there is a unique solution, there is no solution, 
    and there are infinitely many solutions.
    \begin{answer}
      Recall that if a pair of lines share two distinct points then
      they are the same line. 
      That's because two points determine a line, so these
      two points determine each of the two lines, 
      and so they are the same line.

      Thus the lines can share one point (giving a unique solution), 
      share no points (giving no solutions), or
      share at least two points (which makes them the same line).  
    \end{answer}
  \item \label{ex:ProveGaussMethod}
    Finish the proof of \nearbytheorem{th:GaussMethod}.
    \begin{answer}
     For the reduction operation of multiplying $\rho_i$ by a nonzero
     real number $k$, we have that \( (s_1,\ldots,s_n) \) satisfies
     this system
     \begin{equation*}
       \begin{linsys}{4}
         a_{1,1}x_1  &+  &a_{1,2}x_2 &+  &\cdots  &+  &a_{1,n}x_n  &=  &d_1  \\
                   &   &          &  &        &   &           &\vdotswithin{=}   \\
        ka_{i,1}x_1  &+  &ka_{i,2}x_2 &+  &\cdots  &+  &ka_{i,n}x_n &=  &kd_i  \\
                   &   &           &   &        &   &            &\vdotswithin{=}   \\
         a_{m,1}x_1  &+  &a_{m,2}x_2 &+  &\cdots  &+  &a_{m,n}x_n  &=  &d_m  
       \end{linsys}
     \end{equation*}
     if and only if
     % \begin{align*}
     %    a_{1,1}s_1+a_{1,2}s_2+\cdots+a_{1,n}s_n
     %    &=d_1                                              \\
     %    &\alignedvdots                                     \\
     %    \text{and\ } ka_{i,1}s_1+ka_{i,2}s_2+\cdots+ka_{i,n}s_n
     %    &=kd_i                                              \\
     %    &\alignedvdots                                      \\
     %    \text{and\ } a_{m,1}s_1+a_{m,2}s_2+\cdots+a_{m,n}s_n
     %    &=d_m
     % \end{align*}
     $a_{1,1}s_1+a_{1,2}s_2+\cdots+a_{1,n}s_n=d_1$ 
     and \ldots{} $ka_{i,1}s_1+ka_{i,2}s_2+\cdots+ka_{i,n}s_n=kd_i$
     and \ldots{} 
     $a_{m,1}s_1+a_{m,2}s_2+\cdots+a_{m,n}s_n=d_m$
     by the definition of `satisfies'.
     Because \( k\neq 0 \), that's true if and only if
     % \begin{align*}
     %    a_{1,1}s_1+a_{1,2}s_2+\cdots+a_{1,n}s_n
     %    &=d_1                                              \\
     %    &\alignedvdots                                     \\
     %    \text{and\ } a_{i,1}s_1+a_{i,2}s_2+\cdots+a_{i,n}s_n
     %    &=d_i                                              \\
     %    &\alignedvdots                                      \\
     %    \text{and\ } a_{m,1}s_1+a_{m,2}s_2+\cdots+a_{m,n}s_n
     %    &=d_m
     % \end{align*}
     $a_{1,1}s_1+a_{1,2}s_2+\cdots+a_{1,n}s_n=d_1$
     and \ldots{}
     $a_{i,1}s_1+a_{i,2}s_2+\cdots+a_{i,n}s_n=d_i$
     and \ldots{}
     $a_{m,1}s_1+a_{m,2}s_2+\cdots+a_{m,n}s_n=d_m$
     (this is straightforward canceling on both sides of the $i$-th equation),
     which says that \( (s_1,\ldots,s_n) \) solves
     \begin{equation*}
       \begin{linsys}{4}
         a_{1,1}x_1  &+  &a_{1,2}x_2 &+  &\cdots  &+  &a_{1,n}x_n  &=  &d_1  \\
                     &   &           &   &        &   &            &\vdotswithin{=}   \\
         a_{i,1}x_1  &+  &a_{i,2}x_2 &+  &\cdots  &+  &a_{i,n}x_n  &=  &d_i  \\
                     &   &           &   &        &   &            &\vdotswithin{=}   \\
         a_{m,1}x_1  &+  &a_{m,2}x_2 &+  &\cdots  &+  &a_{m,n}x_n  &=
              &d_m  
         \end{linsys}
     \end{equation*}
     as required.

     For the combination operation $k\rho_i+\rho_j$, the tuple
     \( (s_1,\ldots,s_n) \) satisfies
     \begin{equation*}
       \begin{linsys}{4}
         a_{1,1}x_1             &+  &\cdots  &+  &a_{1,n}x_n  &=  &d_1\hfill\hbox{} \\
                                &   &        &   &            &\vdotswithin{=}   \\
         a_{i,1}x_1             &+  &\cdots  &+  &a_{i,n}x_n  &=  &d_i\hfill\hbox{} \\
                                &   &        &   &            &\vdotswithin{=}   \\
         (ka_{i,1}+a_{j,1})x_1  &+  &\cdots  &+  &(ka_{i,n}+a_{j,n})x_n
               &=  &kd_i+d_j \hfill \\
                                &   &        &   &            &\vdotswithin{=}   \\
         a_{m,1}x_1             &+   &\cdots  &+  &a_{m,n}x_n  &=  
          &d_m\hfill\hbox{} 
        \end{linsys}
     \end{equation*}
     if and only if
     $a_{1,1}s_1+\cdots+a_{1,n}s_n=d_1$
     and \ldots{}
     $a_{i,1}s_1+\cdots+a_{i,n}s_n=d_i$
     and \ldots{} 
     $(ka_{i,1}+a_{j,1})s_1+\cdots+(ka_{i,n}+a_{j,n})s_n=kd_i+d_j$
     and \ldots{}
     $a_{m,1}s_1+a_{m,2}s_2+\cdots+a_{m,n}s_n=d_m$
     again by the definition of `satisfies'.
     Subtract \( k \) times the equation~\( i \) from equation~\( j \).
     (Here is where we need \( i\neq j \); if \( i=j \) then the two
     \( d_i \)'s above are not equal.)
     The previous compound statement holds if and only if
     $a_{1,1}s_1+\cdots+a_{1,n}s_n=d_1$
     and \ldots{}
     $a_{i,1}s_1+\cdots+a_{i,n}s_n=d_i$
     and\ldots{} $
     (ka_{i,1}+a_{j,1})s_1+\cdots+(ka_{i,n}+a_{j,n})s_n
         -(ka_{i,1}s_1+\cdots+ka_{i,n}s_n)
         =kd_i+d_j-kd_i$
      and\ldots{} $a_{m,1}s_1+\cdots+a_{m,n}s_n=d_m$,
     which after cancellation says that \( (s_1,\ldots,s_n) \) solves
     \begin{equation*}
       \begin{linsys}{4}
         a_{1,1}x_1  &+   &\cdots  &+  &a_{1,n}x_n  &=  &d_1  \\
                     &    &        &   &            &\vdotswithin{=}   \\
         a_{i,1}x_1  &+   &\cdots  &+  &a_{i,n}x_n  &=  &d_i  \\
                     &    &        &   &            &\vdotswithin{=}   \\
         a_{j,1}x_1  &+  &\cdots  &+  &a_{j,n}x_n  &=  &d_j  \\
                     &   &        &   &            &\vdotswithin{=}   \\
         a_{m,1}x_1  &+  &\cdots  &+  &a_{m,n}x_n  &=
              &d_m\hfill\hbox{}
       \end{linsys}
     \end{equation*}  
     as required.
   \end{answer}
  \item 
    Is there a two-unknowns
    linear system whose solution set is all of \( \Re^2 \)?
    \begin{answer}
      Yes, this one-equation system:
      \begin{equation*}
         0x+0y=0
      \end{equation*}
      is satisfied by every \( (x,y)\in\Re^2 \).  
    \end{answer}
  \recommended \item 
    Are any of the operations used in Gauss's Method
    redundant?
    That is, can we make any of the operations from a combination
    of the others?
    \begin{answer}
      Yes.
      This sequence of operations swaps rows \( i \) and \( j \)
      \begin{equation*}
         \grstep{\rho_i+\rho_j}
         \repeatedgrstep{-\rho_j+\rho_i}
         \repeatedgrstep{\rho_i+\rho_j}
         \repeatedgrstep{-1\rho_i}
      \end{equation*}  
      so the row-swap operation is redundant in the presence of the other two.
     \end{answer}
  \item 
    Prove that each operation of Gauss's Method is reversible.
    That is, show that if two systems are related by a row operation
    $S_1\rightarrow S_2$ then there is a row operation to go back
    $S_2\rightarrow S_1$.
    \begin{answer}
      Reverse a row swap $\rho_i\leftrightarrow\rho_j$ by swapping 
      back $\rho_j\leftrightarrow\rho_i$.
      Reverse the $k\rho_i$ step of multiplying  \( k\neq 0  \) 
      on both sides of a row
      by  dividing through~$(1/k)\rho_i$.

      The row combination case is the nontrivial one.
      The operation $k\rho_i+\rho_j$
      results in this $j$-th row.
      \begin{equation*}
        k\cdot a_{i,1}+a_{j,1}+\cdots+k\cdot a_{i,n}+a_{j,n}=k\cdot d_i+d_j
      \end{equation*}
      The $i$-th row unchanged because of the $i\neq j$ restriction.
      Because the $i$-th row is unchanged, the operation $-k\rho_i+\rho_j$ 
      returns the $j$-th row to its original state.

      (Observe that the \( i=j \) conditino on the $k\rho_i+\rho_j$ 
       is needed, or else this could happen
       \begin{equation*}
         \begin{linsys}{2}
           3x  &+  &2y  &=  &7  
         \end{linsys}
         \grstep{2\rho_1+\rho_1}
         \begin{linsys}{2}
           9x  &+  &6y  &=  &21 
          \end{linsys}                 
         \grstep{-2\rho_1+\rho_1}
         \begin{linsys}{2}
          -9x  &-  &6y  &=  &-21 
         \end{linsys}
       \end{equation*}
       and so the result wouldn't hold.)
    \end{answer}
  \puzzle \item  
    \cite{Anton}
    A box holding pennies, nickels and dimes contains
    thirteen coins with a total value of \( 83 \) cents.
    How many coins of each type are in the box?
    (These are US coins;
    a penny is $1$~cent, a nickel is $5$~cents, and
    a dime is $10$~cents.)
    \begin{answer}
      Let \( p \), \( n \), and \( d \) be the number of
      pennies, nickels, and dimes.
      For variables that are real numbers, this system
      \begin{equation*}
         \begin{linsys}{3}
              p  &+ &n   &+  &d   &=  &13   \\
              p  &+ &5n  &+  &10d &=  &83    
         \end{linsys}
         \grstep{-\rho_1+\rho_2}
         \begin{linsys}{3}
              p  &+ &n   &+  &d   &=  &13   \\
                 &  &4n  &+  &9d  &=  &70    
          \end{linsys}
      \end{equation*}
      has more than one solution; in fact, it has infinitely many of them.
      However, it has a limited number of solutions in which \( p \), \( n \),
      and \( d \) are non-negative integers.
      Running through \( d=0 \), \ldots, \( d=8 \) shows that 
      \( (p,n,d)=(3,4,6) \)
      is the only solution using natural numbers.  
    \end{answer}
  \puzzle \item 
    \cite{ContestProb1955no38}
    Four positive integers are given.
    Select any three of the integers, find their arithmetic average,
    and add this result to the fourth integer.
    Thus the numbers 29, 23, 21, and 17 are obtained.
    One of the original integers is:
    \begin{exparts*}
      \partsitem 19
      \partsitem 21
      \partsitem 23
      \partsitem 29
      \partsitem 17
    \end{exparts*}
    \begin{answer}
      Solving the system 
      \begin{equation*}
        \begin{linsys}{2}
        (1/3)(a+b+c)  &+  &d  &=  &29  \\
        (1/3)(b+c+d)  &+  &a  &=  &23  \\
        (1/3)(c+d+a)  &+  &b  &=  &21  \\
        (1/3)(d+a+b)  &+  &c  &=  &17
        \end{linsys}
      \end{equation*}
      we obtain $a=12$, $b=9$, $c=3$, $d=21$.
      Thus the second item, 21, is the correct answer.
     \end{answer}
  \puzzle \recommended \item  
      \cite{Monthly35p47}
      Laugh at this:  \( \mbox{AHAHA}+\mbox{TEHE}=\mbox{TEHAW} \).
      It resulted from substituting a code letter for each digit of a simple
      example in addition, and it is required to identify the letters
      and prove the solution unique.
      \begin{answer}
        \answerasgiven
        A comparison of the units and hundreds columns of this
        addition shows that there must be a carry from the tens column.
        The tens column then tells us that \( A<H \), so there
        can be no carry from the units or hundreds columns.
        The five columns then give the following five equations.
        \begin{align*}
          A+E  &=  W  \\
          2H   &=  A+10  \\
          H    &=  W+1  \\
          H+T  &=  E+10  \\
          A+1  &=  T
        \end{align*}
        The five linear equations in five unknowns, if solved simultaneously,
        produce the unique solution: \( A=4 \), \( T=5 \), \( H=7 \),
        \( W=6 \) and \( E=2 \), so that the original example in addition
        was \( 47474+5272=52746 \).  
      \end{answer}
  \puzzle \item 
     \cite{Wohascum2}
     The Wohascum County Board of Commissioners, which has 20 members, 
     recently had to elect a President.
     There were three candidates ($A$, $B$, and $C$); on each ballot
     the three
     candidates were to be listed in order of preference, with no abstentions.
     It was found that 11 members, a majority, preferred $A$ over $B$
     (thus the other 9 preferred $B$ over $A$).
     Similarly, it was found that 12 members preferred $C$ over $A$.
     Given these results, it was suggested that $B$ should withdraw, to enable
     a runoff election between $A$ and $C$.
     However, $B$ protested, and it was then found that 14 members preferred
     $B$ over $C$!
     The Board has not yet recovered from the resulting confusion.
     Given that every possible order of $A$, $B$, $C$ appeared on at least 
     one ballot, how many members voted for $B$ as their first choice?
     \begin{answer}
       \answerasgiven{} 
       \textit{Some additional material was added from \cite{joriki}.}
       Eight commissioners voted for $B$.
       To see this, we will use the given information to study how many voters
       chose each order of $A$, $B$, $C$.

       The six orders of preference are $ABC$, $ACB$, $BAC$, $BCA$, $CAB$,
       $CBA$; assume they receive $a$, $b$, $c$, $d$, $e$, $f$ votes 
       respectively.
       We know that
       \begin{equation*}
         \begin{linsys}{3}
           a  &+  &b  &+  &e  &=  &11  \\
           d  &+  &e  &+  &f  &=  &12  \\
           a  &+  &c  &+  &d  &=  &14
         \end{linsys}
       \end{equation*}
       from the number preferring $A$ over $B$, the number preferring
       $C$ over $A$, and the number preferring $B$ over $C$.
       Because 20 votes were cast, 
       $a+b+\cdots+f=20$.
       Subtracting the sum of the three above equations from the 
       prior equation gives $b+c+f=3$, and because each preference order got at 
       least one vote (and vote totals are natural numbers),
       that means $b=c=f=1$. 

       From the above three equations the complete solution is then 
       $a=6$, $b=1$, $c=1$, $d=7$, $e=4$, and~$f=1$.
       The number of commissioners voting for $B$ as their first choice 
       is therefore $c+d=1+7=8$.

       \par\noindent {\em Comments.}
       The answer to this question would have been the same had we known only
       that {\em at least\/} 14 commissioners preferred $B$ over $C$.

       The seemingly paradoxical nature of the commissioner's preferences
       ($A$ is preferred to $B$, and $B$ is preferred to $C$, and $C$ is 
       preferred to $A$), an example of ``non-transitive dominance'', is not
       uncommon when individual choices are pooled.
     \end{answer}
  \puzzle \item   
     \cite{Monthly63p93}
    ``This system
     of \( n \) linear equations with
     \( n \) unknowns,'' said the Great Mathematician, ``has a curious
     property.''

     ``Good heavens!'' said the Poor Nut,  ``What is it?''

     ``Note,'' said the Great Mathematician, ``that the constants are in
     arithmetic progression.''

     ``It's all so clear when you explain it!'' said the Poor Nut.
     ``Do you mean like \( 6x+9y=12 \) and \( 15x+18y=21 \)?''

     ``Quite so,'' said the Great Mathematician, pulling out his bassoon.
     ``Indeed, the system has a unique solution.
     Can you find it?''

     ``Good heavens!'' cried the Poor Nut, ``I am baffled.''

     Are you?
     \begin{answer}
       \answerasgiven
       \textit{We have not used ``dependent'' yet; 
       it means here that Gauss's
       Method shows that there is not a unique solution.}
       If \( n\geq 3 \) the system is dependent and the solution is not
       unique.
       Hence \( n<3 \).
       But the term ``system'' implies \( n>1 \).
       Hence \( n=2 \).
       If the equations are
       \begin{equation*}
         \begin{linsys}{2}
              ax  &+ &(a+d)y  &=  &a+2d  \\
         (a+3d)x  &+ &(a+4d)y &=  &a+5d  
         \end{linsys}
       \end{equation*}
       then \( x=-1 \), \( y=2 \).  
    \end{answer}
\end{exercises}







\subsection{Describing the Solution Set}
A linear system with a unique solution has a solution set with one element.
A linear system with no solution has a solution set that is empty.
In these cases the solution set is easy to describe.
Solution sets are a challenge to describe only when they contain many elements.

\begin{example}
This system has many solutions because in echelon form
\begin{align*}
  \begin{linsys}{3}
    2x  &   &   &+  &z  &=  &3 \\
     x  &-  &y  &-  &z  &=  &1 \\
    3x  &-  &y  &   &   &=  &4 
  \end{linsys}
  &\grstep[-(3/2)\rho_1 +\rho_3]{-(1/2)\rho_1+\rho_2}
  \begin{linsys}{3}
     2x  &   &   &+  &z      &=  &3    \\
         &   &-y &-  &(3/2)z &=  &-1/2 \\
         &   &-y &-  &(3/2)z &=  &-1/2 
   \end{linsys}                                   \\
  &\grstep{-\rho_2+\rho_3}
  \begin{linsys}{3}
     2x  &   &   &+  &z      &=  &3    \\
         &   &-y &-  &(3/2)z &=  &-1/2 \\
         &   &   &   &0      &=  &0    
   \end{linsys}
\end{align*}
not all of the variables are leading variables.
\nearbytheorem{th:GaussMethod} shows that an $(x,y,z)$  
satisfies the first system if and only if it satisfies the
third.
So we can describe the solution set  
$\set{(x,y,z)\suchthat\text{$2x+z=3$ and $x-y-z=1$ and $3x-y=4$}}$
in this way.
\begin{equation*}
  \set{(x,y,z)\suchthat\text{$2x+z=3$ and $-y-3z/2=-1/2$}}
  \tag{$*$}
\end{equation*}
This description is better because 
it has two equations instead of three 
but it is not optimal
because it still has some hard to understand interactions among the variables.

To improve it, use the 
variable that does not lead any equation, $z$, to describe
the variables that do lead, $x$ and $y$.
The second equation gives
$y=(1/2)-(3/2)z$ 
and the first equation gives
$x=(3/2)-(1/2)z$.
Thus we can describe the solution set in this way.   
\begin{equation*}
  \set{ (x,y,z)=
       ((3/2)-(1/2)z,(1/2)-(3/2)z,z)\suchthat z\in\Re}
  \tag{$**$}
\end{equation*}
\end{example}

Compared with ($*$), 
the advantage of ($**$) 
is that $z$ can be any real number.
This makes the job of deciding which tuples are in the solution set 
much easier.
For instance, taking $z=2$ shows that $(1/2,-5/2,2)$ is a solution.

\begin{definition} \label{df:FreeVars}
%<*df:FreeVars>
In an echelon form linear system the variables that are not leading
are   
\definend{free}.\index{echelon form!free variable}\index{free variable}
%</df:FreeVars>
\end{definition}

\begin{example}   \label{ex:Parametrize2}
Reduction of a linear system can end with more than one variable free.
Gauss's Method on this system
\begin{align*}
   \begin{linsys}{4}
               x  &+  &y   &+  &z   &-  &w   &=  &1  \\
                  &   &y   &-  &z   &+  &w   &=  &-1 \\
              3x  &   &    &+  &6z  &-  &6w  &=  &6  \\
                  &   &-y  &+  &z   &-  &w   &=  &1  
   \end{linsys}
  &\grstep{-3\rho_1 +\rho_3}
  \begin{linsys}{4}
     x  &+  &y   &+  &z   &-  &w   &=  &1  \\
        &   &y   &-  &z   &+  &w   &=  &-1 \\
        &   &-3y &+  &3z  &-  &3w  &=  &3  \\
        &   &-y  &+  &z   &-  &w   &=  &1  
  \end{linsys}                                      \\
  &\grstep[\rho_2 +\rho_4]{3\rho_2 +\rho_3}
  \begin{linsys}{4}
     x  &+  &y   &+  &z   &-  &w   &=  &1  \\
        &   &y   &-  &z   &+  &w   &=  &-1 \\
        &   &    &   &    &   &0   &=  &0  \\
        &   &    &   &    &   &0   &=  &0  
   \end{linsys}
\end{align*}
leaves  \( x \) and \( y \) leading and both \( z \) and~\( w \) free.
To get the description that we prefer, we work from the bottom.
We first express the leading variable $y$ in terms of
$z$ and $w$, as $y=-1+z-w$.
Moving up to the top equation,
substituting for $y$ gives
$x+(-1+z-w)+z-w=1$ and solving for $x$ leaves $x=2-2z+2w$.
The solution set 
\begin{equation*}
   \set{(2-2z+2w,-1+z-w,z,w)\suchthat z,w\in\Re}
  \tag{$**$}
\end{equation*}
has the leading variables in terms of the variables that are free.
\end{example}

\begin{example}    \label{ex:Parametrize1}
The list of leading variables may skip over some columns.
After this reduction
\begin{align*}
  \begin{linsys}{4}
              2x  &-  &2y  &   &    &   &    &=  &0  \\
                  &   &    &   &z   &+  &3w  &=  &2  \\
              3x  &-  &3y  &   &    &   &    &=  &0  \\
               x  &-  &y   &+  &2z  &+  &6w  &=  &4  
  \end{linsys}
  &\grstep[-(1/2)\rho_1+ \rho_4]{-(3/2)\rho_1 +\rho_3}
  \begin{linsys}{4}
     2x  &-  &2y  &\spaceforemptycolumn   &    &   &    &=  &0  \\
         &   &    &   &z   &+  &3w  &=  &2  \\
         &   &    &   &    &   &0   &=  &0  \\
         &   &    &   &2z  &+  &6w  &=  &4  
   \end{linsys}                                    \\
  &\grstep{-2\rho_2 +\rho_4}
  \begin{linsys}{4}
     2x  &-  &2y  &\spaceforemptycolumn   &    &   &    &=  &0  \\
         &   &    &   &z   &+  &3w  &=  &2  \\
         &   &    &   &    &   &0   &=  &0  \\
         &   &    &   &    &   &0   &=  &0  
   \end{linsys}
\end{align*}
$x$ and $z$ are the leading variables, not $x$ and~$y$.
The free variables are $y$ and~$w$ and so we can describe the solution set as
$\set{ (y,y,2-3w,w)\suchthat y,w\in\Re }$.
For instance, \( (1,1,2,0) \) satisfies the system\Dash take 
$y=1$ and $w=0$.
The four-tuple \( (1,0,5,4) \) is not a solution
since its first coordinate does not equal its second.
\end{example}

%<*df:Parameter>
A variable that we use to describe a family of solutions
is a \definend{parameter}.\index{parameter}  
%</df:Parameter>
We say that the solution set in the prior example 
is \definend{parametrized\/}\index{parametrized} 
with $y$ and $w$.

(The terms `parameter' and `free variable' do not mean the same thing.
In the prior example
$y$ and~$w$ are free because in the echelon form system they
do not lead while
they are parameters because of how 
we used them to describe the set of solutions.
Had we instead 
rewritten the second equation as $w=2/3-(1/3)z$ then
the free variables would still be $y$ and~$w$ but the parameters 
would be $y$ and~$z$.)

In the rest of this book 
we will solve linear systems by bringing them to
echelon form and then parametrizing with the free variables.

\begin{example}
This is another system with infinitely many solutions.
\begin{align*}
   \begin{linsys}{4}
               x  &+  &2y  &   &   &   &   &=  &1  \\
              2x  &   &    &+  &z  &   &   &=  &2  \\
              3x  &+  &2y  &+  &z  &-  &w  &=  &4  
   \end{linsys}
  &\grstep[-3\rho_1 +\rho_3]{-2\rho_1+\rho_2}
  \begin{linsys}{4}
     x  &+  &2y  &   &   &   &   &=  &1  \\
        &   &-4y &+  &z  &   &   &=  &0  \\
        &   &-4y &+  &z  &-  &w  &=  &1  
   \end{linsys}                                    \\
  &\grstep{-\rho_2+\rho_3}
  \begin{linsys}{4}
     x  &+  &2y  &   &   &   &   &=  &1  \\
        &   &-4y &+  &z  &   &   &=  &0  \\
        &   &    &   &   &   &-w &=  &1  
   \end{linsys}
\end{align*}
The leading variables are \( x \), \( y \), and \( w \).
The variable \( z \) is free.
Notice that, although there are infinitely many 
solutions, the value of $w$ doesn't vary but is constant at $-1$.
To parametrize, write \( w \) in terms of \( z \) with \( w=-1+0z \).
Then \( y=(1/4)z \).
Substitute for \( y \) in the first 
equation to get \( x=1-(1/2)z \).
The solution set is $\set{(1-(1/2)z,(1/4)z,z,-1)\suchthat z\in\Re}$.
\end{example}

Parametrizing solution sets shows that systems with 
free variables have infinitely many solutions.
For instance, above $z$ takes on all of infinitely many real number values, 
each associated with a different solution.

We finish this subsection by developing a streamlined 
notation for linear systems 
and their solution sets.

\begin{definition}\label{df:matrix}
%<*df:matrix>
An \( \nbym{m}{n} \) \definend{matrix}\index{matrix}
is a rectangular array of numbers
with \( m \)~\definend{rows}\index{matrix!row}\index{row} 
and \( n \)~\definend{columns}\index{matrix!column}\index{column}.
Each number in the matrix is an 
\definend{entry}\index{matrix!entry}\index{entry, matrix}.
%</df:matrix>
\end{definition}

We usually denote a matrix with an upper case roman letters.
For instance,
\begin{equation*}
  A=
  \begin{mat}[r]
    1  &2.2  &5  \\
    3  &4    &-7
  \end{mat}
\end{equation*}
has $2$~rows and $3$~columns and so
is a \( \nbym{2}{3} \) matrix.
Read that aloud as ``two-by-three'';
the number of rows is always given first.
(The matrix has parentheses on either side
so that when 
two matrices are adjacent
we can tell where one ends and the other begins.)
We name matrix entries with the corresponding lower-case letter
so that \( a_{2,1}=3 \) is the entry in the second row and first column 
of the above array.
Note that the order of the subscripts matters: 
$a_{1,2}\neq a_{2,1}$ since \( a_{1,2}=2.2 \). 
% Matrices occur throughout this book.
We denote
the set of all \( \nbym{n}{m} \)
matrices by \( \matspace_{\nbym{n}{m}} \).\index{matrices, set of}

We use matrices to do Gauss's Method in essentially the same
way that we did it for systems of equations:
where a row's
\definend{leading entry}\index{echelon form!leading entry}%
\index{leading!entry}. % 
is its first nonzero entry (if it has one),
we perform row operations to arrive at 
\definend{matrix echelon form},\index{echelon form!matrix}%
\index{matrix!echelon form}%
where the leading entry in lower rows are to the right of those in 
the rows above.
We switch to this notation because it lightens
the clerical load of Gauss's Method\Dash the copying of variables and the
writing of $+$'s and $=$'s. 

\begin{example}
We can abbreviate this linear system
\begin{equation*}
  \begin{linsys}{3}
    x  &+  &2y  &   &    &=  &4   \\
       &   &y   &-  &z   &=  &0   \\
    x  &   &    &+  &2z  &=  &4   
  \end{linsys}
\end{equation*}
with this matrix.
\begin{equation*}
    \begin{amat}[r]{3}
      1  &2  &0  &4  \\
      0  &1  &-1 &0  \\
      1  &0  &2  &4
    \end{amat}
\end{equation*}
The vertical bar reminds a reader of the difference between the 
coefficients on the system's left hand side and the constants on the right.
With a bar, this is an
\definend{augmented\/}\index{matrix!augmented}\index{augmented matrix} matrix.
\begin{equation*}
    \begin{amat}[r]{3}
      1  &2  &0  &4  \\
      0  &1  &-1 &0  \\
      1  &0  &2  &4
    \end{amat}
  \grstep{-\rho_1 +\rho_3}
  \begin{amat}[r]{3}
       1  &2  &0  &4  \\
       0  &1  &-1 &0  \\
       0  &-2 &2  &0
     \end{amat}                        
  \grstep{2\rho_2 +\rho_3}
  \begin{amat}[r]{3}
       1  &2  &0  &4  \\
       0  &1  &-1 &0  \\
       0  &0  &0  &0
     \end{amat}
\end{equation*}
The second row stands for $y-z=0$ and the first row stands for
$x+2y=4$ so the solution set is
\( \set{(4-2z,z,z)\suchthat z\in\Re} \).
\end{example}

Matrix notation also
clarifies the descriptions of solution sets.
\nearbyexample{ex:Parametrize2}'s
$\set{(2-2z+2w,-1+z-w,z,w)\suchthat z,w\in\Re}$ 
is hard to read.
We will rewrite it to group all of the
constants together, all of the
coefficients of~\( z \) together, and all of the coefficients of~\( w \)
together.
We write them vertically, in one-column matrices.
\begin{equation*}
  \set{\colvec[r]{2 \\ -1 \\ 0 \\ 0}
       +\colvec[r]{-2 \\ 1 \\ 1 \\ 0}\cdot z
       +\colvec[r]{2 \\ -1 \\ 0 \\ 1}\cdot w
       \suchthat z,w\in\Re}
\end{equation*}
For instance, the top line says that \( x=2-2z+2w \)
and the second line says that \( y= -1+z-w \).
(Our next section gives a geometric interpretation that will help 
picture the solution sets.)

\begin{definition}\label{df:vector}
%<*df:vector>
A \definend{vector}\index{vector} 
(or \definend{column vector})\index{column!vector}\index{vector!column}
is a matrix with a single column.
A matrix with a single row is a
\definend{row vector}\index{row!vector}\index{vector!row}.
The entries of a vector are its
\definend{components}\index{component of a vector}\index{vector!component}.
A column or row vector whose components are all zeros is a 
\definend{zero vector}.\index{zero vector}\index{vector!zero}
%</df:vector>
\end{definition}

Vectors are an exception to the convention of representing matrices with 
capital roman letters.
We use lower-case roman or greek letters overlined
with an arrow:
\( \vec{a} \), \( \vec{b} \), \ldots\, or
\( \vec{\alpha} \), \( \vec{\beta} \), \ldots\
(boldface is also common:
{\boldmath \( a \)} or {\boldmath \( \alpha \)}).
For instance, this is a column vector
with a third component of \( 7 \).
\begin{equation*}
  \vec{v}=
  \colvec[r]{ 1  \\  3  \\ 7}
\end{equation*}
A zero vector is denoted \( \zero \).
There are many different zero vectors\Dash the
one-tall zero vector, the two-tall zero vector, etc.\Dash but
nonetheless we will often say ``the'' zero vector, expecting 
that the size will be clear from the context.

\begin{definition}
The linear equation
\( a_1x_1+a_2x_2+\,\cdots\,+a_nx_n=d \)
with unknowns \( x_1,\ldots\,,x_n \)
is \definend{satisfied}\index{vector!satisfies an equation}%
\index{linear equation!satisfied by a vector} by
\begin{equation*}
  \vec{s}=\colvec{s_1 \\ \vdotswithin{s_1} \\ s_n}
\end{equation*}
if \( a_1s_1+a_2s_2+\,\cdots\,+a_ns_n=d \).
A vector satisfies a linear system if it satisfies each equation in 
the system.
\end{definition}

The style of description of solution sets that we use
involves adding the vectors, and 
also multiplying them by real numbers.
Before we give the examples showing the style 
we first need to define these operations.

\begin{definition} \label{df:VectorSum}
%<*df:VectorSum>
The 
\definend{vector sum}\index{vector!sum}\index{sum!vector}\index{addition of vectors} 
of
\( \vec{u} \) and \( \vec{v} \) is the vector of the sums.
\begin{equation*}
  \vec{u}+\vec{v}=
  \colvec{u_1 \\ \vdotswithin{u_1} \\ u_n}
   +
  \colvec{v_1 \\ \vdotswithin{v_1} \\ v_n}
   =
  \colvec{u_1+v_1 \\ \vdotswithin{u_1+v_1} \\ u_n+v_n}
\end{equation*}
%</df:VectorSum>
\end{definition}

Note that for the addition to be defined 
the vectors must have the same number of entries.
This entry-by-entry addition works for any pair of matrices, not just vectors, 
provided that they have the same number of rows and 
columns.\index{matrix!sum}\index{sum!matrix}

\begin{definition} \label{df:VectorScalarMultiplication}
%<*df:VectorScalarMultiplication>
The \definend{scalar multiplication\/}\index{vector!scalar multiple}%
\index{scalar multiple!vector} of the real number
\( r \) and the vector \( \vec{v} \) is the vector of the multiples.
\begin{equation*}
  r\cdot\vec{v}=
  r\cdot\colvec{v_1 \\ \vdotswithin{v_1} \\ v_n}
  =
  \colvec{rv_1 \\ \vdotswithin{rv_1} \\ rv_n}
\end{equation*}
%</df:VectorScalarMultiplication>
\end{definition}

As with the addition operation, the entry-by-entry scalar multiplication
operation extends beyond vectors to apply to any 
matrix.\index{matrix!scalar multiplication}\index{scalar multiplication!matrix}

We write scalar multiplication either as \( r\cdot\vec{v} \) or
\( \vec{v}\cdot r \), or even without the `$\cdot$' symbol:~$r\vec{v}$.
(Do not refer to scalar multiplication 
as `scalar product' because we will use that name for a different operation.)

\begin{example}
\begin{equation*}
  \colvec[r]{2 \\ 3 \\ 1}
   +
  \colvec[r]{3 \\ -1 \\ 4}
  =
  \colvec{2+3 \\ 3-1 \\ 1+4}
   =
  \colvec[r]{5 \\ 2 \\ 5}
  \qquad
  7\cdot\colvec[r]{1 \\ 4 \\ -1 \\ -3}
  =
  \colvec[r]{7 \\ 28 \\ -7 \\ -21}
\end{equation*}
\end{example}

Observe that the definitions of addition and scalar multiplication agree
where they overlap; for instance, \( \vec{v} +\vec{v} = 2\vec{v} \).

With these definitions, we are set to use matrix and vector notation to
both solve systems and express the solution.

\begin{example} \label{ex:ManyParamsInfManySolsSystem}
This system
\begin{equation*}
   \begin{linsys}{5}
      2x  &+  &y  &  &  &-  &w  &   &   &=  &4  \\
          &   &y  &  &  &+  &w  &+  &u  &=  &4  \\
       x  &   &   &- &z &+  &2w &   &   &=  &0  
   \end{linsys}
\end{equation*}
reduces in this way.
\begin{align*}
  \begin{amat}[r]{5}
    2  &1  &0  &-1  &0  &4  \\
    0  &1  &0  &1   &1  &4  \\
    1  &0  &-1 &2   &0  &0
  \end{amat}
  &\grstep{-(1/2)\rho_1+\rho_3}
  \begin{amat}[r]{5}
    2  &1     &0  &-1    &0  &4  \\
    0  &1     &0  &1     &1  &4  \\
    0  &-1/2  &-1 &5/2   &0  &-2
  \end{amat}                                 \\
  &\grstep{(1/2)\rho_2+\rho_3}
  \begin{amat}[r]{5}
    2  &1     &0  &-1    &0    &4  \\
    0  &1     &0  &1     &1    &4  \\
    0  &0     &-1 &3     &1/2  &0
  \end{amat}
\end{align*}
The solution set is
\( \set{(w+(1/2)u,4-w-u,3w+(1/2)u,w,u)\suchthat w,u\in\Re} \).
We write that in vector form.
\begin{equation*}
  \set{\colvec{x \\ y \\ z \\ w \\ u}=
       \colvec[r]{0 \\ 4 \\ 0 \\ 0 \\ 0}+
       \colvec[r]{1 \\ -1 \\ 3 \\ 1 \\ 0}w+
       \colvec[r]{1/2 \\ -1 \\ 1/2 \\ 0 \\ 1}u
       \suchthat w,u\in\Re}
\end{equation*}
Note how well vector notation sets off 
the coefficients of each parameter.
For instance, the third row of the vector form shows plainly that if \( u \) is
fixed then \( z \) increases three times as fast as \( w \).
Another thing shown plainly is that setting both \( w \) and \( u \) to zero
gives that
\begin{equation*}
  \colvec{x \\ y \\ z \\ w \\ u}
  =\colvec[r]{0 \\ 4 \\ 0 \\ 0 \\ 0}
\end{equation*}
is a particular solution of the linear system.
\end{example}

\begin{example}
In the same way, the system
\begin{equation*}
   \begin{linsys}{3}
     x  &-  &y  &+  &z  &=  &1  \\
    3x  &   &   &+  &z  &=  &3  \\
    5x  &-  &2y &+  &3z &=  &5  
  \end{linsys}
\end{equation*}
reduces
\begin{align*}
  \begin{amat}[r]{3}
    1  &-1  &1  &1  \\
    3  &0   &1  &3  \\
    5  &-2  &3  &5
  \end{amat}
  &\grstep[-5\rho_1+\rho_3]{-3\rho_1+\rho_2}
  \begin{amat}[r]{3}
    1  &-1  &1  &1  \\
    0  &3   &-2 &0  \\
    0  &3   &-2 &0
  \end{amat}                                    \\
  &\grstep{-\rho_2+\rho_3}
  \begin{amat}[r]{3}
    1  &-1  &1  &1  \\
    0  &3   &-2 &0  \\
    0  &0   &0  &0
  \end{amat}
\end{align*}
to give a one-parameter solution set.
\begin{equation*}
  \set{\colvec[r]{1 \\ 0 \\ 0}
       +\colvec[r]{-1/3 \\ 2/3 \\ 1}z
       \suchthat z\in\Re}
\end{equation*}
As in the prior example, the vector not associated with the parameter
\begin{equation*}
   \colvec[r]{1 \\ 0 \\ 0}
\end{equation*}
is a particular solution of the system.
\end{example}

Before the exercises, we will consider what we have accomplished  
and what we have yet to do.

So far we have done the mechanics of Gauss's Method.
We 
have not stopped to consider any of the interesting questions
that arise,
except for proving \nearbytheorem{th:GaussMethod}\Dash which 
justifies the method by showing that it gives 
the right answers. 

For example, can we 
always describe solution sets as above, with
a particular solution vector added to an unrestricted linear combination of 
some other vectors?
We've noted that the solution sets we described in this way 
have infinitely many solutions
so an answer to this question
would tell us about the size of solution sets.

Many questions arise from our observation that we can do Gauss's Method in 
more than one way (for instance, when swapping rows we may have a choice of 
more than one row).
\nearbytheorem{th:GaussMethod} says that we must get the same solution set
no matter how we proceed but
if we do Gauss's Method in two ways
must we get the same number of free variables in each echelon form system?
Must those be the same variables, that is, is it impossible to
solve a problem
one way to get $y$ and~$w$ free and solve it another way to get $y$ and~$z$ 
free?

In the rest of this chapter we will answer these questions.
The answer to each is `yes'.
In the next subsection 
we do the first one: we will prove that we can always describe solution sets
in that way. 
Then, in this chapter's second section, 
we will use that understanding to describe the geometry of solution sets.
In this chapter's final section,
we will settle the questions about the parameters. 

When we are done, we will not only have a 
solid grounding in the practice of Gauss's Method but 
we will also have a solid grounding in the theory.
We will know exactly what can and cannot happen in a reduction.

\begin{exercises}
  \recommended \item  
    Find the indicated entry of the matrix,
    if it is defined.
    \begin{equation*}
      A=\begin{mat}[r]
        1  &3  &1  \\
        2  &-1 &4
      \end{mat}
    \end{equation*}
    \begin{exparts*}
      \partsitem \( a_{2,1} \)
      \partsitem \( a_{1,2} \)
      \partsitem \( a_{2,2} \)
      \partsitem \( a_{3,1} \)
    \end{exparts*}
    \begin{answer}
      \begin{exparts*}
        \partsitem \( 2 \)
        \partsitem \( 3 \)
        \partsitem \(-1 \)
        \partsitem Not defined.
      \end{exparts*}  
    \end{answer}
  \recommended \item 
    Give the size of each matrix.
    \begin{exparts*}
      \partsitem \(
        \begin{mat}[r]
          1  &0  &4  \\
          2  &1  &5
        \end{mat}  \)
      \partsitem \(
        \begin{mat}[r]
          1  &1  \\
         -1  &1  \\
          3  &-1
        \end{mat}  \)
      \partsitem \(
        \begin{mat}[r]
          5  &10 \\
         10  &5
        \end{mat}  \)
    \end{exparts*}
    \begin{answer}
      \begin{exparts*}
        \partsitem \( \nbym{2}{3} \)
        \partsitem \( \nbym{3}{2} \)
        \partsitem \( \nbym{2}{2} \)
      \end{exparts*}  
    \end{answer}
  \recommended \item 
    Do the indicated vector operation, if it is defined.
    \begin{exparts*}
      \partsitem \( \colvec[r]{2 \\ 1 \\ 1}
               +\colvec[r]{3 \\ 0 \\ 4} \)
      \partsitem \( 5\colvec[r]{4 \\ -1} \)
      \partsitem \( \colvec[r]{1 \\ 5 \\ 1}
               -\colvec[r]{3 \\ 1 \\ 1} \)
      \partsitem \( 7\colvec[r]{2 \\ 1}
               +9\colvec[r]{3 \\ 5} \)
      \partsitem \( \colvec[r]{1 \\ 2}
               +\colvec[r]{1 \\ 2 \\ 3} \)
      \partsitem \( 6\colvec[r]{3 \\ 1 \\ 1}
               -4\colvec[r]{2 \\ 0 \\ 3}
               +2\colvec[r]{1 \\ 1 \\ 5} \)
    \end{exparts*}
    \begin{answer}
      \begin{exparts*}
        \partsitem \( \colvec[r]{5 \\ 1 \\ 5} \)
        \partsitem \( \colvec[r]{20 \\ -5} \)
        \partsitem \( \colvec[r]{-2 \\ 4 \\ 0} \)
        \partsitem \( \colvec[r]{41 \\ 52} \)
        \partsitem Not defined.
        \partsitem \( \colvec[r]{12 \\ 8 \\ 4} \)
      \end{exparts*}  
     \end{answer}
  \recommended \item  \label{exer:SolveInMatrixNotation}
    Solve each system using matrix notation.
    Express the solution using vectors.
    \begin{exparts*}
      \partsitem \( \begin{linsys}[t]{2}
                  3x  &+  &6y  &=  &18  \\
                   x  &+  &2y  &=  &6   
                   \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{2}
                   x  &+  &y   &=  &1  \\
                   x  &-  &y   &=  &-1   
                    \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{3}
                   x_1  &   &     &+  &x_3   &=  &4  \\
                   x_1  &-  &x_2  &+  &2x_3  &=  &5  \\
                  4x_1  &-  &x_2  &+  &5x_3  &=  &17  
                   \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{3}
                   2a   &+  &b    &-  &c     &=  &2  \\
                   2a   &   &     &+  &c     &=  &3  \\
                    a   &-  &b    &   &      &=  &0   
                    \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{4}
                     x  &+  &2y   &-   &z   &    &    &=  &3  \\
                    2x  &+  &y    &    &    &+   &w   &=  &4  \\
                     x  &-  &y    &+   &z   &+   &w   &=  &1  
                    \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{4}
                     x  &   &     &+   &z   &+   &w   &=  &4  \\
                    2x  &+  &y    &    &    &-   &w   &=  &2  \\
                    3x  &+  &y    &+   &z   &    &    &=  &7  
                     \end{linsys}  \)
    \end{exparts*}
    \begin{answer}
      \begin{exparts}
        \partsitem This reduction
          \begin{equation*}
            \begin{amat}[r]{2}
              3  &6  &18 \\
              1  &2  &6
            \end{amat}
            \grstep{(-1/3)\rho_1+\rho_2}
            \begin{amat}[r]{2}
              3  &6  &18 \\
              0  &0  &0
            \end{amat}
          \end{equation*}
          leaves \( x \) leading and \( y \) free.
          Making \( y \) the parameter, gives \( x=6-2y \) and this solution
          set.
          \begin{equation*}
            \set{\colvec[r]{6 \\ 0}+\colvec[r]{-2 \\ 1}y
              \suchthat y\in\Re}
          \end{equation*}
        \partsitem A reduction
          \begin{equation*}
            \begin{amat}[r]{2}
              1  &1  &1  \\
              1  &-1 &-1
            \end{amat}
            \grstep{-\rho_1+\rho_2}
            \begin{amat}[r]{2}
              1  &1  &1  \\
              0  &-2 &-2
            \end{amat}
          \end{equation*}
          gives the unique solution \( y=1 \), \( x=0 \).
          The solution set is this.
          \begin{equation*}
            \set{\colvec[r]{0 \\ 1} }
          \end{equation*}
        \partsitem Gauss's Method
          \begin{equation*}
            \begin{amat}[r]{3}
              1  &0  &1  &4  \\
              1  &-1 &2  &5  \\
              4  &-1 &5  &17
            \end{amat}
            \grstep[-4\rho_1+\rho_3]{-\rho_1+\rho_2}
            \begin{amat}[r]{3}
              1  &0  &1  &4  \\
              0  &-1 &1  &1  \\
              0  &-1 &1  &1
            \end{amat}     
            \grstep{-\rho_2+\rho_3}
            \begin{amat}[r]{3}
              1  &0  &1  &4  \\
              0  &-1 &1  &1  \\
              0  &0  &0  &0
            \end{amat}
          \end{equation*}
          leaves \( x_1 \) and \( x_2 \) leading with \( x_3 \) free.
          The solution set is this.
          \begin{equation*}
            \set{\colvec[r]{4 \\ -1 \\ 0}+\colvec[r]{-1 \\ 1 \\ 1}x_3
              \suchthat x_3\in\Re}
          \end{equation*}
        \partsitem This reduction
          \begin{align*}
            \begin{amat}[r]{3}
              2  &1  &-1 &2  \\
              2  &0  &1  &3  \\
              1  &-1 &0  &0
            \end{amat}
            &\grstep[-(1/2)\rho_1+\rho_3]{-\rho_1+\rho_2}
            \begin{amat}[r]{3}
              2  &1    &-1   &2  \\
              0  &-1   &2    &1  \\
              0  &-3/2 &1/2  &-1
            \end{amat}                                          \\
            &\grstep{(-3/2)\rho_2+\rho_3}
            \begin{amat}[r]{3}
              2  &1  &-1   &2  \\
              0  &-1 &2    &1  \\
              0  &0  &-5/2 &-5/2
            \end{amat}
          \end{align*}
          shows that the solution set is a singleton set.
          \begin{equation*}
            \set{\colvec[r]{1 \\ 1 \\ 1}}
          \end{equation*}
        \partsitem This reduction is easy
          \begin{align*}
            \begin{amat}[r]{4}
              1  &2  &-1 &0  &3 \\
              2  &1  &0  &1  &4 \\
              1  &-1 &1  &1  &1
            \end{amat}
            &\grstep[-\rho_1+\rho_3]{-2\rho_1+\rho_2}
            \begin{amat}[r]{4}
              1  &2  &-1 &0  &3  \\
              0  &-3 &2  &1  &-2 \\
              0  &-3 &2  &1  &-2
            \end{amat}                                       \\
            &\grstep{-\rho_2+\rho_3}
            \begin{amat}[r]{4}
              1  &2  &-1 &0  &3  \\
              0  &-3 &2  &1  &-2 \\
              0  &0  &0  &0  &0
            \end{amat}
          \end{align*}
          and ends with \( x \) and $y$ leading while \( z \) and \( w \) are
          free.
          Solving for \( y \) gives \( y=(2+2z+w)/3 \) and substitution shows
          that \( x+2(2+2z+w)/3-z=3 \) so \( x=(5/3)-(1/3)z-(2/3)w \),
          making this the solution set.
          \begin{equation*}
            \set{\colvec[r]{5/3 \\ 2/3 \\ 0 \\ 0}
                 +\colvec[r]{-1/3 \\ 2/3 \\ 1 \\ 0}z
                 +\colvec[r]{-2/3 \\ 1/3 \\ 0 \\ 1}w
                 \suchthat z,w\in\Re}
          \end{equation*}
        \partsitem The reduction
          \begin{align*}
            \begin{amat}[r]{4}
              1  &0  &1  &1  &4 \\
              2  &1  &0  &-1 &2 \\
              3  &1  &1  &0  &7
            \end{amat}
            &\grstep[-3\rho_1+\rho_3]{-2\rho_1+\rho_2}
            \begin{amat}[r]{4}
              1  &0  &1  &1  &4 \\
              0  &1  &-2 &-3 &-6\\
              0  &1  &-2 &-3 &-5
            \end{amat}                                       \\
            &\grstep{-\rho_2+\rho_3}
            \begin{amat}[r]{4}
              1  &0  &1  &1  &4 \\
              0  &1  &-2 &-3 &-6\\
              0  &0  &0  &0  &1
            \end{amat}
          \end{align*}
          shows that there is no solution\Dash the solution set is empty.
      \end{exparts}  
     \end{answer}
  \recommended \item \label{exer:SlvMatNot}
    Solve each system using matrix notation.
    Give each solution set in vector notation.
    \begin{exparts*}
      \partsitem \( \begin{linsys}[t]{3}
                  2x  &+  &y  &-  &z  &=  &1  \\
                  4x  &-  &y  &   &   &=  &3  
                \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{4}
                   x  &   &   &-  &z  &   &   &=  &1  \\
                      &   &y  &+  &2z &-  &w  &=  &3  \\
                   x  &+  &2y &+  &3z &-  &w  &=  &7  
               \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{4}
                   x  &-  &y  &+  &z  &   &   &=  &0  \\
                      &   &y  &   &   &+  &w  &=  &0  \\
                  3x  &-  &2y &+  &3z &+  &w  &=  &0  \\
                      &   &-y &   &   &-  &w  &=  &0  
               \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{5}
                   a  &+  &2b &+  &3c &+  &d  &-  &e  &=  &1  \\
                  3a  &-  &b  &+  &c  &+  &d  &+  &e  &=  &3  
               \end{linsys}  \)
    \end{exparts*}
    \begin{answer}
      \begin{exparts}
      \partsitem The reduction
        \begin{equation*}
          \begin{amat}[r]{3}
            2  &1  &-1  &1  \\
            4  &-1 &0   &3
          \end{amat}
          \grstep{-2\rho_1+\rho_2}
          \begin{amat}[r]{3}
            2  &1  &-1  &1  \\
            0  &-3 &2   &1
          \end{amat}
        \end{equation*}
        ends with \( x \) and \( y \) leading, and with \( z \) free.
        Solving for \( y \) gives \( y=(1-2z)/(-3) \), and then substitution
        \( 2x+(1-2z)/(-3)-z=1 \) shows that \( x=((4/3)+(1/3)z)/2 \).
        Hence the solution set is this.
        \begin{equation*}
          \set{\colvec[r]{2/3 \\ -1/3 \\ 0}
               +\colvec[r]{1/6 \\ 2/3 \\ 1}z
              \suchthat z\in\Re}
        \end{equation*}
      \partsitem This application of Gauss's Method
        \begin{align*}
          \begin{amat}[r]{4}
            1  &0  &-1  &0  &1 \\
            0  &1  &2   &-1 &3 \\
            1  &2  &3   &-1 &7
          \end{amat}
          &\grstep{-\rho_1+\rho_3}
          \begin{amat}[r]{4}
            1  &0  &-1  &0  &1 \\
            0  &1  &2   &-1 &3 \\
            0  &2  &4   &-1 &6
          \end{amat}                                   \\
          &\grstep{-2\rho_2+\rho_3}
          \begin{amat}[r]{4}
            1  &0  &-1  &0  &1 \\
            0  &1  &2   &-1 &3 \\
            0  &0  &0   &1  &0
          \end{amat}
        \end{align*}
        leaves  \( x \), \( y \), and \( w \)  leading.
        The solution set is here.
        \begin{equation*}
          \set{\colvec[r]{1 \\ 3 \\ 0 \\ 0}
               +\colvec[r]{1 \\ -2 \\ 1 \\ 0}z
              \suchthat z\in\Re}
        \end{equation*}
      \partsitem This row reduction
        \begin{align*}
          \begin{amat}[r]{4}
            1  &-1 &1   &0  &0 \\
            0  &1  &0   &1  &0 \\
            3  &-2 &3   &1  &0 \\
            0  &-1 &0   &-1 &0
          \end{amat}
          &\grstep{-3\rho_1+\rho_3}
          \begin{amat}[r]{4}
            1  &-1 &1   &0  &0 \\
            0  &1  &0   &1  &0 \\
            0  &1  &0   &1  &0 \\
            0  &-1 &0   &-1 &0
          \end{amat}                                       \\
          &\grstep[\rho_2+\rho_4]{-\rho_2+\rho_3}
          \begin{amat}[r]{4}
            1  &-1 &1   &0  &0 \\
            0  &1  &0   &1  &0 \\
            0  &0  &0   &0  &0 \\
            0  &0  &0   &0  &0
          \end{amat}
        \end{align*}
        ends with \( z \) and \( w \) free.
        We have this solution set.
        \begin{equation*}
          \set{\colvec[r]{0 \\ 0 \\ 0 \\ 0}
               +\colvec[r]{-1 \\ 0 \\ 1 \\ 0}z
               +\colvec[r]{-1 \\ -1 \\ 0 \\ 1}w
              \suchthat z,w\in\Re}
        \end{equation*}
      \partsitem Gauss's Method done in this way
        \begin{equation*}
          \begin{amat}[r]{5}
            1  &2  &3   &1  &-1 &1  \\
            3  &-1 &1   &1  &1  &3
          \end{amat}
          \grstep{-3\rho_1+\rho_2}
          \begin{amat}[r]{5}
            1  &2  &3   &1  &-1 &1  \\
            0  &-7 &-8  &-2 &4  &0
          \end{amat}
        \end{equation*}
        ends with \( c \), \( d \), and \( e \) free.
        Solving for \( b \) shows that \( b=(8c+2d-4e)/(-7) \) and then 
        substitution
        \( a+2(8c+2d-4e)/(-7)+3c+1d-1e=1 \) shows that 
        \( a=1-(5/7)c-(3/7)d-(1/7)e \) and we have the solution set.
        \begin{equation*}
          \set{\colvec[r]{1 \\ 0 \\ 0 \\ 0 \\ 0}
               +\colvec[r]{-5/7 \\ -8/7 \\ 1 \\ 0 \\ 0}c
               +\colvec[r]{-3/7 \\ -2/7 \\ 0 \\ 1 \\ 0}d
               +\colvec[r]{-1/7 \\ 4/7 \\ 0 \\ 0 \\ 1}e
              \suchthat c,d,e\in\Re}
        \end{equation*}
    \end{exparts}  
   \end{answer}
  \item 
    Solve each system using matrix notation.
    Express the solution set using vectors.
    \begin{exparts*}
      \partsitem 
        $\begin{linsys}{3}
          3x &+ &2y &+ &z &= &1 \\
          x  &- &y  &+ &z &= &2 \\
          5x &+ &5y &+ &z &= &0
        \end{linsys}$
      \partsitem
        $\begin{linsys}{4}
          x  &+ &y  &- &2z &= &0 \\
          x  &- &y  &  &   &= &-3 \\
          3x &- &y  &- &2z &= &-6  \\
             &  &2y &- &2z &= &3  
        \end{linsys}$
      \partsitem
        $\begin{linsys}{5}
          2x  &- &y  &- &z &+ &w &= &4 \\
           x  &+ &y  &+ &z &  &  &= &-1 
        \end{linsys}$
      \partsitem
         $\begin{linsys}{3}
          x  &+ &y  &- &2z &= &0 \\
          x  &- &y  &  &   &= &-3 \\
          3x &- &y  &- &2z &= &0    
        \end{linsys}$ 
    \end{exparts*}
    \begin{answer}
      \begin{exparts}
        \partsitem This reduction
          \begin{align*}
            \begin{amat}{3}
              3 &2  &1  &1 \\
              1 &-1 &1  &2 \\
              5 &5  &1  &0
            \end{amat}
            &\grstep[-(5/3)\rho_1+\rho_3]{-(1/3)\rho_1+\rho_2}
            \begin{amat}{3}
              3 &2    &1     &1 \\
              0 &-5/3 &2/3   &5/3 \\
              0 &5/3  &-2/3  &-5/3
            \end{amat}                                     \\
            &\grstep{\rho_2+\rho_3}
            \begin{amat}{3}
              3 &2    &1     &1 \\
              0 &-5/3 &2/3   &5/3 \\
              0 &0    &0     &0
            \end{amat}
          \end{align*}
          gives this solution set.
          \begin{equation*}
            \set{\colvec{x \\ y \\ z}=\colvec{1 \\ -1 \\ 0}
                                       +\colvec{-3/5 \\ 2/5 \\ 1}z
                             \suchthat z\in\Re}
          \end{equation*}
        \partsitem
          This is the reduction.
          \begin{align*}
            \begin{amat}{3}
              1 &1   &-2 &0 \\
              1 &-1  &0  &3  \\
              3 &-1  &-2 &-6 \\
              0 &2   &-2 &3
            \end{amat}
            &\grstep[-3\rho_1+\rho_3]{-\rho_1+\rho_2}
            \begin{amat}{3}
              1 &1   &-2 &0 \\
              0 &-2  &2  &-3  \\
              0 &-4  &4  &-6 \\
              0 &2   &-2 &3
            \end{amat}                                  \\
            &\grstep[\rho_2+\rho_4]{-2\rho_2+\rho_3}
            \begin{amat}{3}
              1 &1   &-2 &0 \\
              0 &-2  &2  &-3  \\
              0 &0   &0  &0 \\
              0 &0   &0  &0
            \end{amat}
          \end{align*}
          The solution set is this.
          \begin{equation*}
            \set{\colvec{-3/2 \\ 3/2 \\ 0}
                 +\colvec{1 \\ 1 \\ 1}z
                 \suchthat z\in\Re}
          \end{equation*}
      \partsitem
         Gauss's Method
         \begin{equation*}
           \begin{amat}{4}
             2 &-1 &-1 &1 &4 \\
             1 &1  &1  &0 &-1
           \end{amat}
           \grstep{-(1/2)\rho_1+\rho_2}
           \begin{amat}{4}
             2 &-1   &-1   &1    &4 \\
             0 &3/2  &3/2  &-1/2 &-3
           \end{amat}
         \end{equation*}
         gives the solution set.
         \begin{equation*}
           \set{\colvec{1 \\ -2 \\ 0 \\ 0}
                  +\colvec{0 \\ -1 \\ 1 \\ 0}z
                   \colvec{-1/3 \\ 1/3 \\ 0 \\ 1}w
                 \suchthat z,w\in\Re}
         \end{equation*}
       \partsitem
          Here is the reduction.
          \begin{equation*}
            \begin{amat}{3}
              1 &1  &-2 &0  \\
              1 &-1 &0  &-3 \\
              3 &-1 &-2 &0
           \end{amat}
           \grstep[-3\rho_1+\rho_3]{-\rho_1+\rho_2}
           \begin{amat}{3}
             1 &1  &-2 &0  \\
             0 &-2 &2  &-3 \\
             0 &-4  &4  &0
          \end{amat}
          \grstep{-2\rho_2+\rho_3}
          \begin{amat}{3}
            1 &1  &-2 &0  \\
            0 &-2 &2  &-3 \\
            0 &0  &0  &6
          \end{amat}
        \end{equation*}
        The solution set is empty~$\set{}$.
      \end{exparts}
    \end{answer}
  \recommended \item 
    The vector is in the set.
    What value of the parameters produces that vector?
    \begin{exparts}
      \partsitem $\colvec[r]{5 \\ -5}$,
        $\set{\colvec[r]{1 \\ -1}k\suchthat k\in\Re}$
      \partsitem $\colvec[r]{-1 \\ 2 \\ 1}$,
        $\set{\colvec[r]{-2 \\ 1 \\ 0}i
           +\colvec[r]{3 \\ 0 \\ 1}j\suchthat i,j\in\Re}$
      \partsitem $\colvec[r]{0 \\ -4 \\ 2}$,
        $\set{\colvec[r]{1 \\ 1 \\ 0}m
               +\colvec[r]{2 \\ 0 \\ 1}n\suchthat m,n\in\Re}$
    \end{exparts}
    \begin{answer}
      For each problem we get a system of linear equations by looking at the 
      equations of components.
      \begin{exparts}
       \partsitem $k=5$
       \partsitem The second components show that $i=2$, the third
       components show that $j=1$.
       \partsitem $m=-4$, $n=2$
      \end{exparts} 
    \end{answer}
  \item 
    Decide if the vector is in the set.
    \begin{exparts}
      \partsitem $\colvec[r]{3 \\ -1}$,
        $\set{\colvec[r]{-6 \\ 2}k\suchthat k\in\Re}$
      \partsitem $\colvec[r]{5 \\ 4}$,
        $\set{\colvec[r]{5 \\ -4}j\suchthat j\in\Re}$
      \partsitem $\colvec[r]{2 \\ 1 \\ -1}$,
        $\set{\colvec[r]{0 \\ 3 \\ -7}
             +\colvec[r]{1 \\ -1 \\ 3}r\suchthat r\in\Re}$
      \partsitem $\colvec[r]{1 \\ 0 \\ 1}$,
        $\set{\colvec[r]{2 \\ 0 \\ 1}j
            +\colvec[r]{-3 \\ -1 \\ 1}k\suchthat j,k\in\Re}$
    \end{exparts}
    \begin{answer}
      For each problem we get a system of linear equations by looking at the 
      equations of components.
      \begin{exparts}
        \partsitem Yes; take $k=-1/2$.
        \partsitem No; the system with equations $5=5\cdot j$ and
            $4=-4\cdot j$ has no solution.
        \partsitem Yes; take $r=2$.
        \partsitem No.
           The second components give $k=0$.
           Then the third components give $j=1$.
           But the first components don't check. 
      \end{exparts}
     \end{answer}
  \item \cite{Cleary}
    A farmer with 1200 acres is considering planting three different crops, 
    corn, soybeans, and oats.   
    The farmer wants to use all~$1200$ acres.  
    Seed corn costs \$$20$ per acre, while soybean and oat seed cost 
    \$$50$ and~\$$12$ per acre respectively.  
    The farmer has \$$40\,000$ available to buy seed and intends to 
    spend it all.
    \begin{exparts}  
      \item Use the information above to formulate two linear equations 
        with three unknowns and solve it.
     \item Solutions to the system are choices that the farmer can make.  
        Write down two reasonable solutions.
     \item Suppose that in the fall when the crops mature, the farmer 
        can bring in revenue of \$$100$ per acre for corn, 
        \$$300$ per acre for soybeans and \$$80$ per acre for oats.  
        Which of your two solutions in the prior part would have resulted 
        in a larger revenue? 
    \end{exparts}
    \begin{answer}
      \begin{exparts}
        \item Let $c$ be the number of acres of corn, $s$ be the number of 
          acres of soy, and $a$ be the number of acres of oats.
          \begin{equation*}
            \begin{linsys}{3}
              c   &+   &s   &+   &a   &=   &1200 \\ 
            20c   &+   &50s &+   &12a &=   &40\,000  
            \end{linsys}
            \grstep{-20\rho_1+\rho_2}
            \begin{linsys}{3}
              c   &+   &s   &+   &a   &=   &1200 \\ 
                  &    &30s &-   &8a  &=   &16\,000  
            \end{linsys}
          \end{equation*}
          To describe the solution set we can parametrize using $a$.
          \begin{equation*}
            \set{\colvec{c \\ s \\ a}
                 =\colvec{20\,000/30 \\ 16\,000/30 \\ 0}
                  +\colvec{-38/30 \\ 8/30 \\ 1}a
                 \suchthat a\in\Re}
          \end{equation*}
        \item There are many answers possible here. 
          For instance we can take $a=0$ to get $c=20\,000/30\approx 666.66$ and
          $s=16000/30\approx 533.33$.
          Another example is to take $a=20\,000/38\approx 526.32$, giving
          $c=0$ and $s=7360/38\approx 193.68$.
        \item Plug your answers from the prior part into 
          $100c+300s+80a$.
      \end{exparts}
    \end{answer}
  \item 
    Parametrize the solution set of this one-equation system.
    \begin{equation*}
      x_1+x_2+\cdots+x_n=0
    \end{equation*}
    \begin{answer}
      This system has one equation.
      The leading variable is \( x_1 \), the other variables are free.
      \begin{equation*}
        \set{\colvec{-1 \\ 1 \\ \vdotswithin{-1} \\ 0}x_2
             +\cdots+
             \colvec{-1 \\ 0 \\ \vdotswithin{-1} \\ 1}x_n
             \suchthat x_2,\ldots,x_n\in\Re}
      \end{equation*}  
     \end{answer}
  \recommended \item 
    \begin{exparts}
    \partsitem Apply Gauss's Method to the left-hand side to solve
      \begin{equation*}
        \begin{linsys}{4}
          x  &+  &2y  &    &    &-   &w   &=   &a   \\
         2x  &   &    &+   &z   &    &    &=   &b   \\
          x  &+  &y   &    &    &+   &2w  &=   &c   
        \end{linsys}
      \end{equation*}
      for \( x \), \( y \), \( z \), and \(  w \), in terms of the 
      constants $a$, $b$, and $c$.
    \partsitem Use your answer from the prior part to solve this.
      \begin{equation*}
        \begin{linsys}{4}
          x  &+  &2y  &    &    &-   &w   &=   &3   \\
         2x  &   &    &+   &z   &    &    &=   &1   \\
          x  &+  &y   &    &    &+   &2w  &=   &-2
        \end{linsys}
      \end{equation*}
    \end{exparts}
    \begin{answer}
      \begin{exparts}
        \partsitem Gauss's Method here gives
          \begin{align*}
            \begin{amat}{4}
              1  &2  &0  &-1  &a  \\
              2  &0  &1  &0   &b  \\
              1  &1  &0  &2   &c
            \end{amat}
            &\grstep[-\rho_1+\rho_3]{-2\rho_1+\rho_2}
            \begin{amat}{4}
              1  &2  &0  &-1  &a  \\
              0  &-4 &1  &2   &-2a+b  \\
              0  &-1 &0  &3   &-a+c
            \end{amat}                                  \\
            &\grstep{-(1/4)\rho_2+\rho_3}
            \begin{amat}{4}
              1  &2  &0    &-1  &a  \\
              0  &-4 &1    &2   &-2a+b  \\
              0  &0  &-1/4 &5/2 &-(1/2)a-(1/4)b+c
            \end{amat}
          \end{align*}
          leaving \( w \) free.
          Solve: \(  z=2a+b-4c+10w \),
          and \( -4y=-2a+b-(2a+b-4c+10w)-2w \) so
          \( y=a-c+3w \), and
          \( x=a-2(a-c+3w)+w=-a+2c-5w. \)
          Therefore the solution set is this.
          \begin{equation*}
             \set{\colvec{-a+2c \\ a-c \\ 2a+b-4c \\ 0}
                  +\colvec{-5 \\ 3 \\ 10 \\ 1}w
                  \suchthat w\in\Re}
          \end{equation*}
        \partsitem Plug in with \( a=3 \), \( b=1 \), and \( c=-2 \).
          \begin{equation*}
             \set{\colvec[r]{-7 \\ 5 \\ 15 \\ 0}
                  +\colvec[r]{-5 \\ 3 \\ 10 \\ 1}w
                  \suchthat w\in\Re}
          \end{equation*}
      \end{exparts}  
     \end{answer}
  \recommended \item 
    Why is the comma needed in the notation `\( a_{i,j} \)'
    for matrix entries?
    \begin{answer}
       Leaving the comma out, say by writing \( a_{123} \),
       is ambiguous because it could mean $a_{1,23}$ or $a_{12,3}$.  
    \end{answer}
  \recommended \item 
    Give the \( \nbyn{4} \) matrix whose
    \( i,j \)-th entry is
    \begin{exparts*}
      \partsitem \( i+j \);
      \partsitem \( -1 \) to the \( i+j \) power.
    \end{exparts*}
    \begin{answer}
      \begin{exparts*}
        \partsitem \(
           \begin{mat}[r]
             2  &3  &4  &5  \\
             3  &4  &5  &6  \\
             4  &5  &6  &7  \\
             5  &6  &7  &8
           \end{mat} \)
        \partsitem \(
           \begin{mat}[r]
             1  &-1  &1   &-1  \\
            -1  &1   &-1  &1  \\
             1  &-1  &1   &-1  \\
            -1  &1   &-1  &1
           \end{mat} \)
      \end{exparts*}  
    \end{answer}
  \item  
    For any matrix \( A \), the 
    \definend{transpose}\index{transpose}
    \index{matrix!transpose}
    of \( A \), written
    \( \trans{A} \), is the matrix whose columns are the rows of \( A \).
    Find the transpose of each of these.
    \begin{exparts*}
      \partsitem \( \begin{mat}[r]
                  1  &2  &3  \\
                  4  &5  &6
               \end{mat}  \)
      \partsitem \( \begin{mat}[r]
                  2  &-3 \\
                  1  &1
               \end{mat}  \)
      \partsitem \( \begin{mat}[r]
                  5  &10 \\
                 10  &5
               \end{mat}  \)
      \partsitem \( \colvec[r]{1 \\ 1 \\ 0} \)
    \end{exparts*}
    \begin{answer}
      \begin{exparts*}
        \partsitem \( \begin{mat}[r]
                   1  &4  \\
                   2  &5  \\
                   3  &6
                 \end{mat}  \)
        \partsitem \( \begin{mat}[r]
                   2  &1  \\
                  -3  &1
                 \end{mat}  \)
        \partsitem \( \begin{mat}[r]
                   5  &10 \\
                  10  &5
                 \end{mat}  \)
        \partsitem \( \rowvec{1 &1 &0}  \)
      \end{exparts*}  
     \end{answer}
  \recommended \item 
    \begin{exparts}
      \partsitem Describe all functions \( f(x)=ax^2+bx+c \) 
        such that \( f(1)=2 \) and \( f(-1)=6 \).
      \partsitem Describe all functions \( f(x)=ax^2+bx+c \) 
        such that \( f(1)=2 \).
    \end{exparts}
    \begin{answer}
      \begin{exparts}
        \partsitem Plugging in \( x=1 \) and \( x=-1 \) gives
          \begin{equation*}
            \begin{linsys}{3}
              a  &+  &b   &+  &c  &=  &2  \\
              a  &-  &b   &+  &c  &=  &6  
            \end{linsys}
            \grstep{-\rho_1+\rho_2}
            \begin{linsys}{3}
              a  &+  &b   &+  &c  &=  &2  \\
                 &   &-2b &   &   &=  &4  
              \end{linsys}
          \end{equation*}
          so the set of functions is
          \( \set{f(x)=(4-c)x^2-2x+c\suchthat c\in\Re} \).
        \partsitem Putting in \( x=1 \) gives
          \begin{equation*}
            \begin{linsys}{3}
              a  &+  &b   &+  &c  &=  &2  
            \end{linsys}
          \end{equation*}
          so the set of functions is
          \( \set{f(x)=(2-b-c)x^2+bx+c\suchthat b,c\in\Re} \).
      \end{exparts}  
    \end{answer}
  \item Show that any set of five points from the plane \( \Re^2 \) lie on a
    common conic section, that is, they all satisfy some equation of the
    form \( ax^2+by^2+cxy+dx+ey+f=0 \) where some of \( a,\,\ldots\,,f \)
    are nonzero.
    \begin{answer}
      On plugging in the five pairs $(x,y)$ we get a system with the
      five equations and six unknowns $a$, \ldots, $f$.
      Because there are more unknowns than equations, if no inconsistency
      exists among the equations then there are infinitely many solutions
      (at least one variable will end up free).

      But no inconsistency can exist because $a=0$, \ldots, $f=0$ is a 
      solution (we are only using this zero solution to show that the system
      is consistent\Dash the prior paragraph shows that
      there are nonzero solutions). 
    \end{answer}
  \item 
    Make up a four equations/four unknowns system having
    \begin{exparts}
      \partsitem a one-parameter solution set;
      \partsitem a two-parameter solution set;
      \partsitem a three-parameter solution set.
    \end{exparts}
    \begin{answer}
      \begin{exparts}
      \partsitem Here is one\Dash the fourth equation is redundant 
        but still OK.
        \begin{equation*}
          \begin{linsys}{4}
             x  &+  &y  &-  &z  &+  &w  &=  &0  \\
                &   &y  &-  &z  &   &   &=  &0  \\
                &   &   &   &2z &+  &2w &=  &0  \\
                &   &   &   &z  &+  &w  &=  &0
          \end{linsys}
        \end{equation*}
      \partsitem Here is one.
        \begin{equation*}
          \begin{linsys}{4}
             x  &+  &y  &-  &z  &+  &w  &=  &0  \\
                &   &   &   &   &   &w  &=  &0  \\
                &   &   &   &   &   &w  &=  &0  \\
                &   &   &   &   &   &w  &=  &0
          \end{linsys}
        \end{equation*}
      \partsitem This is one.
        \begin{equation*}
          \begin{linsys}{4}
             x  &+  &y  &-  &z  &+  &w  &=  &0  \\
             x  &+  &y  &-  &z  &+  &w  &=  &0  \\
             x  &+  &y  &-  &z  &+  &w  &=  &0  \\
             x  &+  &y  &-  &z  &+  &w  &=  &0 
          \end{linsys}
        \end{equation*}
    \end{exparts}  
   \end{answer}
  \puzzle \item 
    \cite{Shepelev}
    This  puzzle  is  from  a  Russian   web-site
    \texttt{http://www.arbuz.uz/}  and  there are many solutions
    to it, but mine uses  linear  algebra  and  is  very
    naive.   There's   a   planet  inhabited  by  arbuzoids
   (watermeloners, to  translate  from  Russian). 
   Those creatures are found in three colors: red, green and blue.  
   There  are  $13$~red
   arbuzoids,  $15$~blue  ones, and $17$~green. 
   When
   two differently colored arbuzoids meet,  they
   both change to the third color.

   The question is, can it ever happen that all
   of them assume the same color?
    \begin{answer}
       \answerasgiven
       My solution was to define the numbers  of  arbuzoids
       as $3$-dimensional vectors, and express all possible
       elementary transitions as such vectors, too:
       \begin{center}
         \begin{tabular}{rr}
           R: &$13$  \\
           G: &$15$  \\
           B: &$17$
         \end{tabular}
         \qquad
         Operations:
         $\colvec[r]{-1 \\ -1 \\ 2}$, 
         $\colvec[r]{-1 \\ 2 \\ -1}$, 
         and 
         $\colvec[r]{2 \\ -1 \\ -1}$
       \end{center}
       Now, it is enough to check whether the  solution  to
       one  of  the  following  systems of linear equations
       exists:
       \begin{equation*}
         \colvec[r]{13 \\ 15 \\ 17}
         +x\colvec[r]{-1 \\ -1  \\ 2}
         +y\colvec[r]{-1 \\ 2 \\ -1}
         +\colvec[r]{2 \\ -1 \\ -1}
         =\colvec[r]{0 \\ 0 \\ 45}
         \qquad
         \text{(or $\colvec[r]{0 \\ 45 \\ 0}$ or $\colvec[r]{45 \\ 0 \\ 0}$)}
       \end{equation*}
       Solving
       \begin{equation*}
         \begin{amat}[r]{3}
          -1  &-1 &2  &-13  \\
          -1  &2  &-1 &-15  \\
           2  &-1 &-1 &28
         \end{amat}
         \grstep[2\rho_1+\rho_3]{-\rho_1+\rho_2}
         \repeatedgrstep{\rho_2+\rho_3}
         \begin{amat}[r]{3}
          -1  &-1 &2  &-13  \\
           0  &3  &-3 &-2  \\
           0  &0  &0  &0
         \end{amat}
       \end{equation*}
       gives $y+2/3=z$ so if the number of transformations $z$ is an integer
       then $y$ is not.
       The other two systems give similar conclusions so there is no
       solution.
    \end{answer}
  \puzzle \item 
    \cite{USSROlympiad174}
    \begin{exparts}
      \partsitem Solve the system of equations.
        \begin{equation*}
          \begin{linsys}{2}
            ax  &+  &y  &=  &a^2  \\
             x  &+  &ay &=  &1
         \end{linsys}
        \end{equation*}
        For what values of $a$ does the system fail to have solutions, and
        for what values of $a$ are there infinitely many solutions?
      \partsitem Answer the above question for the system.
        \begin{equation*}
          \begin{linsys}{2}
            ax  &+  &y  &=  &a^3  \\    
             x  &+  &ay &=  &1
          \end{linsys}
        \end{equation*}
    \end{exparts}
    \begin{answer}
       \answerasgiven
       \begin{exparts}
        \partsitem Formal solution of the system yields
          \begin{equation*}
            x=\frac{a^3-1}{a^2-1}  
            \qquad
            y=\frac{-a^2+a}{a^2-1}.
          \end{equation*}
          If $a+1\neq 0$ and $a-1\neq 0$, then the system has the single
          solution
          \begin{equation*}
            x=\frac{a^2+a+1}{a+1}
            \qquad
            y=\frac{-a}{a+1}.
          \end{equation*}
          If $a=-1$, or if $a=+1$, then the formulas are meaningless; in the
          first instance we arrive at the system
          \begin{equation*}
            \left\{ 
            \begin{linsys}{2}
              -x &+  &y  &=  &1 \\
               x &-  &y  &=  &1
            \end{linsys}\right.
          \end{equation*}
          which is a contradictory system.
          In the second instance we have
          \begin{equation*}
            \left\{
            \begin{linsys}{2}
               x &+  &y  &=  &1 \\
               x &+  &y  &=  &1
            \end{linsys}\right.
          \end{equation*}
          which has an infinite number of solutions (for example, for 
          $x$ arbitrary, $y=1-x$).
        \partsitem Solution of the system yields
          \begin{equation*}
            x=\frac{a^4-1}{a^2-1}
            \qquad
            y=\frac{-a^3+a}{a^2-1}.
          \end{equation*}
          Here, is $a^2-1\neq 0$, the system has the single solution
          $x=a^2+1$, $y=-a$.
          For $a=-1$ and $a=1$, we obtain the systems
          \begin{equation*}
            \left\{
            \begin{linsys}{2}
              -x &+  &y  &=  &-1 \\
               x &-  &y  &=  &1
            \end{linsys}\right.
            \qquad
            \left\{
            \begin{linsys}{2}
               x &+  &y  &=  &1 \\
               x &+  &y  &=  &1
            \end{linsys}\right.
         \end{equation*}
         both of which have an infinite number of solutions.
      \end{exparts}
    \end{answer}
  \puzzle \item 
    \cite{MathMag52p48}
    In air a gold-sur\-faced sphere weighs \( 7588 \)
    grams.
    It is known that it may contain one or more of the metals aluminum,
    copper, silver, or lead.
    When weighed successively under standard conditions in water, benzene,
    alcohol, and glycerin its respective weights are \( 6588 \), \( 6688 \),
    \( 6778 \), and \( 6328 \) grams.
    How much, if any, of the forenamed metals does it contain if the
    specific gravities of the designated substances are taken to be as follows?
    \begin{center}
       \begin{tabular}{lrclr}
         Aluminum  &\( 2.7 \)
            &\makebox[3em]{\mbox{}\hfill\mbox{}} &Alcohol &0.81 \\
         Copper    &\( 8.9 \)  &     &Benzene   &\( 0.90 \) \\
         Gold      &\( 19.3 \) &     &Glycerin &\( 1.26 \) \\
         Lead      &\( 11.3 \) &     &Water     &\( 1.00 \) \\
         Silver    &\( 10.8 \)
       \end{tabular}
    \end{center}
    \begin{answer}
      \answerasgiven
      Let \( u \), \( v \), \( x \), \( y \), \( z \) be the volumes in
      \( {\rm cm}^3 \) of Al, Cu, Pb, Ag, and Au, respectively, contained in
      the sphere, which we assume to be not hollow.
      Since the loss of weight in water (specific gravity \( 1.00 \)) is
      \( 1000 \) grams, the volume of the sphere is \( 1000\mbox{ cm}^3 \).
      Then the data, some of which is superfluous, though consistent, leads to
      only \( 2 \) independent equations, one relating volumes and the
      other, weights.
      \begin{equation*}
        \begin{linsys}{5}
           u  &+  &v    &+  &x     &+  &y     &+  &z     &=  &1000  \\
        2.7u  &+  &8.9v &+  &11.3x &+  &10.5y &+  &19.3z &=  &7558
        \end{linsys}
      \end{equation*}
      Clearly the sphere must contain some aluminum to bring its mean specific
      gravity below the specific gravities of all the other metals.
      There is no unique result to this part of the problem, for the amounts
      of three metals may be chosen arbitrarily, provided that the choices
      will not result in negative amounts of any metal.

      If the ball contains only aluminum and gold, there are
      \( 294.5\mbox{ cm}^3 \) of gold and \( 705.5\mbox{ cm}^3 \) of aluminum.
      Another possibility is \( 124.7\mbox{ cm}^3 \) each of Cu, Au, Pb, and
      Ag and \( 501.2\mbox{ cm}^3  \) of Al.   
    \end{answer}
\end{exercises}

























\subsection{\texorpdfstring{$\text{General}=\text{Particular}+\text{Homogeneous}$}{General=Particular+Homogeneous}}
In the prior subsection the descriptions of solution sets
all fit a pattern.
They have a vector that is a particular solution 
of the system added to an unrestricted combination of some other vectors.
The solution set from 
\nearbyexample{ex:ManyParamsInfManySolsSystem} illustrates.
\begin{equation*}
  \set{
   \underbracket[.7pt]{
     \colvec[r]{0 \\ 4 \\ 0 \\ 0 \\ 0}}_{\text{\shortstack{\rule{0pt}{2ex}particular \\
                                                    solution}}}+
   \underbracket[.7pt]{w\colvec[r]{1 \\ -1 \\ 3 \\ 1 \\ 0}+
       u\colvec[r]{1/2 \\ -1 \\ 1/2 \\ 0 \\ 1}}_{\text{\shortstack{\rule{0pt}{2ex}unrestricted\\
                                                                combination}}}
       \suchthat w,u\in\Re}
\end{equation*}
The combination is unrestricted in that 
$w$ and $u$ can be any real numbers\Dash there
is no condition like ``such that $2w-u=0$'' to restrict 
which pairs $w,u$ we can use.

That example shows an infinite solution set fitting the pattern.
The other two kinds of solution sets also fit.
A one-element solution set fits because it 
has a particular solution,
and the unrestricted combination part is trivial. 
(That is, instead of being a combination of two vectors or
of one vector, it is a combination of no vectors.
By convention the sum of an empty set of vectors
is the zero vector.)
An empty solution set fits the pattern because there is no 
particular solution and thus there are no sums of that form at all.

\begin{theorem} \label{th:GenEqPartPlusHomo}
%<*th:GenEqPartPlusHomo>
Any linear system's 
solution set has the form 
\begin{equation*}
   \set{\vec{p}+c_1\vec{\beta}_1+\,\cdots\,+c_k\vec{\beta}_k
     \suchthat c_1,\,\ldots\,,c_k\in\Re}
\end{equation*}
where \( \vec{p} \) is any particular solution  
and where the number of vectors 
$\vec{\beta}_1$, \ldots, $\vec{\beta}_k$ equals
the number of free variables that the system has after a Gaussian reduction.
%</th:GenEqPartPlusHomo>
\end{theorem}

The solution description has two parts, 
the particular solution $\vec{p}$ 
and the unrestricted linear combination of the $\vec{\beta}$'s.
We shall prove the theorem with two corresponding lemmas.

We will focus first on the unrestricted combination.
For that we consider systems that have the vector of zeroes
as a particular solution
so that we can shorten $\vec{p}+c_1\vec{\beta}_1+\dots+c_k\vec{\beta}_k$
to $c_1\vec{\beta}_1+\dots+c_k\vec{\beta}_k$.

\begin{definition} \label{df:HomogeneousEquation}
%<*df:HomogeneousEquation>
A linear equation is \definend{homogeneous}\index{homogeneous equation}%
\index{linear equation!homogeneous} if it has a constant of zero, so
that it can be written as $a_1x_1+a_2x_2+\,\cdots\,+a_nx_n=0$.
%</df:HomogeneousEquation>
\end{definition}

\begin{example}  \label{ex:FirstExHomoSys}
With any linear system like
\begin{equation*}
  \begin{linsys}{2}
    3x  &+  &4y  &=  3  \\
    2x  &-  &y   &=  1  
  \end{linsys}
\end{equation*}
we associate a system of homogeneous equations by setting the right side to
zeros.
\begin{equation*}
  \begin{linsys}{2}
    3x  &+  &4y  &=  0  \\
    2x  &-  &y   &=  0  
  \end{linsys}
\end{equation*}
Compare the reduction of the original system
\begin{equation*}
  \begin{linsys}{2}
    3x  &+  &4y  &=  3  \\
    2x  &-  &y   &=  1  
  \end{linsys}
  \grstep{-(2/3)\rho_1+\rho_2}
  \begin{linsys}{2}
    3x  &+  &4y        &=  3  \\
        &   &-(11/3)y   &=  -1  
   \end{linsys}
\end{equation*}
with the reduction of the associated homogeneous system.
\begin{equation*}
  \begin{linsys}{2}
    3x  &+  &4y  &=  0  \\
    2x  &-  &y   &=  0  
  \end{linsys}
  \grstep{-(2/3)\rho_1+\rho_2}
  \begin{linsys}{2}
    3x  &+  &4y        &=  0  \\
        &   &-(11/3)y   &=  0
   \end{linsys}
\end{equation*}
Obviously the two reductions go in the same way.
We can study how to reduce a linear systems by instead studying how
to reduce the associated homogeneous system.
\end{example}

Studying the associated homogeneous system has a great advantage over
studying the original system.
Nonhomogeneous systems can be inconsistent.
But a homogeneous system must be consistent since there is always at least
one solution, the zero vector.


\begin{example} \label{ex:HomoZeroOnlySol}
Some homogeneous systems have the zero vector as their only solution.
\begin{equation*}
   \begin{linsys}{3}
     3x  &+  &2y  &+  &z  &=  &0  \\
     6x  &+  &4y  &   &   &=  &0  \\
         &   &y   &+  &z  &=  &0  
   \end{linsys}
   \grstep{-2\rho_1 +\rho_2}
   \begin{linsys}{3}
      3x  &+  &2y  &+  &z  &=  &0  \\
          &   &    &   &-2z&=  &0  \\
          &   &y   &+  &z  &=  &0  
    \end{linsys}
   \grstep{\rho_2 \leftrightarrow\rho_3}
   \begin{linsys}{3}
      3x  &+  &2y  &+  &z  &=  &0  \\
          &   &y   &+  &z  &=  &0  \\
          &   &    &   &-2z&=  &0
    \end{linsys}
\end{equation*}
\end{example}

\begin{example} \label{ex:SolnChemProb}
Some homogeneous systems have many solutions.
One is the Chemistry problem\index{Chemistry problem} 
from the first page of the first subsection.
\begin{align*}
  \begin{linsys}{4}
              7x  &   &   &-  &7z  &   &   &=  &0  \\
              8x  &+  &y  &-  &5z  &-  &2w &=  &0  \\
                  &   &y  &-  &3z  &   &   &=  &0  \\
                  &   &3y &-  &6z  &-  &w  &=  &0  
  \end{linsys}
  &\grstep{-(8/7)\rho_1+\rho_2}
  \begin{linsys}{4}
                7x &   &   &-  &7z  &   &   &=  &0  \\
                   &   &y  &+  &3z  &-  &2w &=  &0  \\
                   &   &y  &-  &3z  &   &   &=  &0  \\
                   &   &3y &-  &6z  &-  &w  &=  &0  
   \end{linsys}                                        \\
  &\grstep[-3\rho_2+\rho_4]{-\rho_2+\rho_3}
  \begin{linsys}{4}
                7x &   &   &-  &7z  &   &   &=  &0  \\
                   &   &y  &+  &3z  &-  &2w &=  &0  \\
                   &   &   &   &-6z &+  &2w &=  &0  \\
                   &   &   &   &-15z&+  &5w &=  &0  
   \end{linsys}                                        \\
  &\grstep{-(5/2)\rho_3+\rho_4}
  \begin{linsys}{4}
                7x &   &   &-  &7z  &   &   &=  &0  \\
                   &   &y  &+  &3z  &-  &2w &=  &0  \\
                   &   &   &   &-6z &+  &2w &=  &0  \\
                   &   &   &   &    &   &0  &=  &0  
   \end{linsys}
\end{align*}
The solution set
\begin{equation*}
  \set{\colvec[r]{1/3 \\ 1 \\ 1/3 \\ 1}w \suchthat w\in\Re}
\end{equation*}
has many vectors besides the zero vector
(if we interpret \( w \) as a number of molecules then solutions
make sense only when \( w \) is a nonnegative multiple of $3$).
\end{example}

% We now have the terminology to prove the two parts of 
% \nearbytheorem{th:GenEqPartPlusHomo}.
% The first lemma deals with unrestricted combinations.

\begin{lemma} \label{le:HomoSltnSpanVecs}
%<*le:HomoSltnSpanVecs>
For any  homogeneous linear system there exist
vectors $\vec{\beta}_1$, \ldots, $\vec{\beta}_k$ such that the 
solution set of the system is
\begin{equation*}
  \set{c_1\vec{\beta}_1+\cdots+c_k\vec{\beta}_k \suchthat c_1,\ldots,c_k\in\Re}
\end{equation*}
where $k$ is the
number of free variables in an echelon form version of the system.
%</le:HomoSltnSpanVecs>
\end{lemma}

We will make two points before the proof.
The first is that the basic idea of the proof is straightforward.
%<*ex:HomoSystemGivesSpanningSet>
Consider this system of homogeneous equations in echelon form.
\begin{equation*}
  \begin{linsys}{5}
     x  &+  &y   &+  &2z  &+  &u  &+  &v  &=  &0  \\
        &   &y   &+  &z  &+  &u  &-  &v  &=  &0  \\
        &   &    &   &   &   &u  &+  &v  &=  &0  
  \end{linsys}
\end{equation*}
Start with the bottom equation. 
Express its leading variable in terms of the free variables with $u=-v$.
For the next row up,
substitute for the leading variable~$u$ of the row below
$y+z+(-v)-v=0$ and solve for this row's leading variable
$y=-z+2v$.
Iterate: on the next row up, substitute expressions found in lower rows
$x+(-z+2v)+2z+(-v)+v=0$
and solve for the leading variable
$x=-z-2v$.
To finish, write the solution in vector notation
\begin{equation*}
  \colvec{x \\ y \\ z \\ u \\ v}
  =\colvec[r]{-1 \\ -1 \\ 1 \\ 0 \\ 0}z
   +\colvec[r]{-2 \\ 2 \\ 0 \\ -1 \\ 1}v 
  \qquad \text{for $z,v\in\Re$}
\end{equation*}
and recognize that the $\vec{\beta}_1$ and $\vec{\beta}_2$ 
of the lemma are the 
vectors associated with the free variables $z$ and~$v$.
%</ex:HomoSystemGivesSpanningSet>

The prior paragraph is an example, not a proof.
But it does suggest
the second point about the proof, its approach.
The example moves row-by-row up the system, using the equations
from lower rows to do the next row. 
This points to doing the proof by
mathematical induction.\appendrefs{mathematical induction}%
\index{mathematical induction}\index{proof techniques!induction}%
\index{induction}%

Induction is an important and non-obvious proof technique that we shall
use a number of times in this book.
We will do proofs by induction in two steps, a base step and
an inductive step.
In the base step we verify that the statement is true for some first 
instance, here that for the bottom equation we can  
write the leading variable in terms of free variables.
In the inductive step we must establish an implication, that if the statement
is true for all prior cases then it follows for the present case also.
Here we will establish that if for the
bottom-most~\( t \) rows we can express the leading variables 
in terms of the free variables, then for the \( t+1 \)-th
row from the bottom
we can also express the leading variable in terms of those that
are free.

Those two steps together prove the statement for all the rows 
because by the base step it is true for the bottom equation, 
and by the inductive step the fact that it is true for the bottom
equation shows that 
it is true for the next one up. 
Then another application of
the inductive step implies that it is true for the third equation up,
etc.

\begin{proof}
%<*pf:HomoSltnSpanVecs0>
Apply Gauss's Method to get to echelon form.
There may be some \( 0=0 \) equations; 
we ignore these 
(if the
system consists only of \( 0=0 \)~equations then the lemma is trivially true
because there are no leading variables).
But
because the system is homogeneous there are no contradictory equations.

We will use induction to verify that
each leading variable can be expressed in terms of
free variables.
That will finish the proof because 
we can use the free variables as parameters and
the $\vec{\beta}$'s are the vectors of coefficients of those
free variables. 
%</pf:HomoSltnSpanVecs0>

%<*pf:HomoSltnSpanVecs1>
For the base step consider the bottom-most equation
\begin{equation*}
  a_{m,\ell_m}x_{\ell_m}+a_{m,\ell_m+1}x_{\ell_m+1}+\cdots+a_{m,n}x_n=0
   \tag{$*$}
\end{equation*}
where \( a_{m,\ell_m}\neq 0 \).
%</pf:HomoSltnSpanVecs1>
(The `$\ell$' means ``leading'' so that $x_{\ell_m}$ is the leading variable
in row~$m$.) 
%<*pf:HomoSltnSpanVecs2>
This is the bottom row so 
any variables % $x_{\ell_{m}+1}$, \ldots{} 
after the
leading one must be free. 
Move these to the right hand side and divide by $a_{m,\ell_m}$
\begin{equation*}
  x_{\ell_m}
  =(-a_{m,\ell_m+1}/a_{m,\ell_m})x_{\ell_m+1}+\cdots+(-a_{m,n}/a_{m,\ell_m})x_n
\end{equation*}
to express the leading variable in terms of free variables.
%</pf:HomoSltnSpanVecs2>
(There is a tricky technical point here:~if in the bottom equation~($*$)
there are no variables to the right 
of~$x_{l_m}$ then \( x_{\ell_m}=0 \).
This satisfies the statement we are verifying because, 
as alluded to at the start of this subsection, 
it has \( x_{\ell_m} \) written 
as a sum of a number of the free variables, namely as the sum of zero many, 
under the convention that 
a trivial sum totals to~$0$.)

%<*pf:HomoSltnSpanVecs3>
For the inductive step assume that the statement holds for the bottom-most
$t$~rows, with $0\leq t<m-1$.
That is, assume 
that for the \( m \)-th equation,
and the \text{\( (m-1) \)-th}
equation, etc., up to and including the \text{\( (m-t) \)-th}~equation,
we can
express the leading variable in terms of free ones.
We must verify that this then also holds for the next equation up, 
the \( (m-(t+1)) \)-th equation.
For that, take each variable that leads
in a lower equation \( x_{\ell_m} \), \ldots, \( x_{\ell_{m-t}} \) 
and substitute
its expression in terms of free variables.
We only need expressions for leading variables from lower equations
because the system is in echelon form, so the
leading variables in equations above this one do not appear in this equation.
The result has a leading term of   
$a_{m-(t+1),\ell_{m-(t+1)}}x_{\ell_{m-(t+1)}}$ with \( a_{m-(t+1),\ell_{m-(t+1)}}\neq 0 \),
and the rest of the left hand side
is a linear combination of free variables.
Move the free variables to
the right side and divide by
\( a_{m-(t+1),\ell_{m-(t+1)}} \) to end with this equation's leading variable
\( x_{\ell_{m-(t+1)}} \) in terms of free variables.

We have done both the base step and the inductive step so by the
principle of mathematical induction the proposition is true.
%</pf:HomoSltnSpanVecs3>
\end{proof}

This shows, 
as discussed between the lemma and its proof, that 
we can parametrize solution sets
using the free variables.
We say that the set of vectors
$\set{c_1\vec{\beta}_1+\cdots+c_k\vec{\beta}_k \suchthat c_1,\ldots,c_k\in\Re}$
is \definend{generated by}\index{generated by}\index{generated} 
or~\definend{spanned by}\index{spanned by}\index{span} 
the set 
\( \set{\smash{\vec{\beta}_1},\ldots,\smash{\vec{\beta}_k}} \).

% The proof mentions a tricky point.
% We follow the convention that the sum of an empty set of vectors is the 
% zero vector.
% In particular, we needs this where 
% a homogeneous system has a unique solution because it
% takes the \( c \)'s to be the free variables
% and if there is a unique solution then there are no free variables.

To finish the proof of  \nearbytheorem{th:GenEqPartPlusHomo}
the next lemma considers the particular solution part of the 
solution set's description.

\begin{lemma}  \label{th:GenEqPartHomo}
%<*th:GenEqPartHomo>
For a linear system and for any particular solution $\vec{p}\/$,
the solution set equals
% \begin{equation*}
$
  \set{\vec{p}+\vec{h} \suchthat \text{ \( \vec{h} \) satisfies the
                                associated homogeneous system}     }$.
%\end{equation*}
%</th:GenEqPartHomo>
\end{lemma}

% So fixing any particular solution gives the above 
% description of the solution set.

\begin{proof}
We will show mutual set inclusion, that any solution to the system is in
the above set and that anything in the set is a solution of the 
system.\appendrefs{set equality}

%<*pf:GenEqPartHomo0>
For set inclusion the first way, that if a vector solves the system
then it is in the set described above, 
assume that \( \vec{s} \) solves the system.
Then \( \vec{s}-\vec{p} \) solves the associated
homogeneous system since for each equation index \( i \),
\begin{multline*}
  a_{i,1}(s_1-p_1)+\cdots+a_{i,n}(s_n-p_n) \\
  =(a_{i,1}s_1+\cdots+a_{i,n}s_n)       
  -(a_{i,1}p_1+\cdots+a_{i,n}p_n)  
  =d_i-d_i                 
  =0
\end{multline*}
where \( p_j \) and \( s_j \) are the \( j \)-th components of
\( \vec{p} \) and \( \vec{s} \).
Express \( \vec{s} \) in the required \( \vec{p}+\vec{h} \) form
by writing \( \vec{s}-\vec{p} \) as \( \vec{h} \).
%</pf:GenEqPartHomo0>

%<*pf:GenEqPartHomo1>
For set inclusion the other way, take a vector of the form $\vec{p}+\vec{h}$,
where \( \vec{p} \) solves the system and \( \vec{h} \) solves the
associated homogeneous system and note that $\vec{p}+\vec{h}$ 
solves the given system since for any equation index~$i$, 
\begin{multline*}
  a_{i,1}(p_1+h_1)+\cdots+a_{i,n}(p_n+h_n)  \\
  =(a_{i,1}p_1+\cdots+a_{i,n}p_n)      
   +(a_{i,1}h_1+\cdots+a_{i,n}h_n)  
  =d_i+0                                
  =d_i
\end{multline*}
where as earlier \( p_j \) and \( h_j \) are the \( j \)-th components of 
\( \vec{p} \) and \( \vec{h} \).
%</pf:GenEqPartHomo1>
\end{proof}

The two lemmas together establish \nearbytheorem{th:GenEqPartPlusHomo}.
Remember that theorem with the slogan, 
``\( \text{General} = \text{Particular} + \text{Homogeneous} \)''.

\begin{example} \label{ex:IllusGenEqPartHomo}
This system illustrates \nearbytheorem{th:GenEqPartPlusHomo}.
\begin{equation*}
  \begin{linsys}{3}
    x  &+  &2y  &-  &z  &=  &1  \\
    2x &+  &4y  &   &   &=  &2  \\
       &   &y   &-  &3z &=  &0
  \end{linsys}
\end{equation*}
Gauss's Method
\begin{equation*}
  \grstep{-2\rho_1+\rho_2}
  \begin{linsys}{3}
    x  &+  &2y  &-  &z  &=  &1  \\
       &   &    &   &2z &=  &0  \\
       &   &y   &-  &3z &=  &0
  \end{linsys}                           
  \grstep{\rho_2\leftrightarrow\rho_3} 
  \begin{linsys}{3}
      x  &+  &2y  &-  &z  &=  &1  \\      
         &   &y   &-  &3z &=  &0  \\
         &   &    &   &2z &=  &0
   \end{linsys}
\end{equation*}
shows that the general solution is a singleton set.
\begin{equation*}
  \set{\colvec[r]{1 \\ 0 \\ 0} }
\end{equation*}
That single vector is obviously a particular solution.
The associated homogeneous system reduces via the same row operations 
\begin{equation*}
  \begin{linsys}{3}
    x  &+  &2y  &-  &z  &=  &0  \\
    2x &+  &4y  &   &   &=  &0  \\
       &   &y   &-  &3z &=  &0
  \end{linsys}
  \grstep{-2\rho_1+\rho_2}
  \repeatedgrstep{\rho_2\swap\rho_3} 
  \begin{linsys}{3}
      x  &+  &2y  &-  &z  &=  &0  \\      
         &   &y   &-  &3z &=  &0  \\
         &   &    &   &2z &=  &0
   \end{linsys}
\end{equation*}
to also give a singleton set. 
\begin{equation*}
  \set{\colvec[r]{0 \\ 0 \\ 0} }
\end{equation*}
So, as discussed at the start of this subsection, 
in this single-solution case the general solution results 
from taking the particular solution and adding to it the unique solution
of the associated homogeneous system.
\end{example}

\begin{example}
The start of this subsection also discusses that the case where
the general solution set is empty fits the
$\text{General}=\text{Particular}+\text{Homogeneous}$ pattern too.
This system illustrates.
\begin{equation*}
  \begin{linsys}{4}
    x  &   &  &+  &z  &+ &w  &=  &-1  \\
   2x  &-  &y &   &   &+ &w  &=  &3   \\
    x  &+  &y &+  &3z &+ &2w &=  &1   
  \end{linsys}
  \grstep[-\rho_1+\rho_3]{-2\rho_1+\rho_2}
  \begin{linsys}{4}
    x  &   &  &+  &z  &+ &w  &=  &-1  \\
       &   &-y&-  &2z &- &w  &=  &5   \\
       &   &y &+  &2z &+ &w  &=  &2   
   \end{linsys}
\end{equation*}
It has no solutions because the final two equations
conflict.
But the associated homogeneous system does have a solution, as do all 
homogeneous systems.
\begin{equation*}
  \begin{linsys}{4}
    x  &   &  &+  &z  &+ &w  &=  &0   \\
   2x  &-  &y &   &   &+ &w  &=  &0   \\
    x  &+  &y &+  &3z &+ &2w &=  &0   
  \end{linsys}
  \grstep[-\rho_1+\rho_3]{-2\rho_1+\rho_2}
  \grstep{\rho_2+\rho_3}
  \begin{linsys}{4}
    x  &   &  &+  &z  &+ &w  &=  &0   \\
       &   &-y&-  &2z &- &w  &=  &0   \\
       &   &  &   &   &  &0  &=  &0         
  \end{linsys}
\end{equation*}
In fact, the solution set is infinite. 
\begin{equation*}
  \set{\colvec[r]{-1 \\ -2 \\ 1 \\ 0}z+\colvec[r]{-1 \\ -1 \\ 0 \\ 1}w
         \suchthat z,w\in\Re}
\end{equation*}
Nonetheless, because the original system has no particular solution, its
general solution set is empty\Dash there are no vectors of the form
$\vec{p}+\vec{h}$ because there are no $\vec{p}\:$'s.
\end{example}

\begin{corollary} \label{co:ThreeKindsSolutionSets}
%<*co:ThreeKindsSolutionSets>
Solution sets of linear systems are either empty, have one element, or
have infinitely many elements.
%</co:ThreeKindsSolutionSets>
\end{corollary}

\begin{proof}
%<*pf:ThreeKindsSolutionSets0>
We've seen examples of all three happening so we need only prove
that there are no other possibilities.

First observe a homogeneous system with
at least one non-\( \zero \) solution $\vec{v}$ has infinitely many
solutions.
This is because any scalar multiple of~$\vec{v}$ also solves the homogeneous
system and there are infinitely many vectors in the set of scalar 
multiples of $\vec{v}$: if $s,t\in\Re$ are unequal then $s\vec{v}\neq t\vec{v}$,
since $s\vec{v}-t\vec{v}=(s-t)\vec{v}$ is
non-$\zero$ as  any non-$0$ component of $\vec{v}$, when 
rescaled by the non-$0$ factor $s-t$, will give a non-$0$ value.
%</pf:ThreeKindsSolutionSets0>

%<*pf:ThreeKindsSolutionSets1>
Now apply \nearbylemma{th:GenEqPartHomo} to conclude that a solution set
\begin{equation*}
  \set{\vec{p}+\vec{h}\suchthat
    \text{\( \vec{h} \) solves the associated homogeneous system}}
\end{equation*}
is either empty (if there is no particular solution \( \vec{p} \)),
or has one element (if there is a \( \vec{p} \) and the homogeneous system
has the unique solution \( \zero \)), or is infinite (if there is a
\( \vec{p} \) and the homogeneous system has a non-$\zero$ solution,
and thus by the prior paragraph has infinitely many solutions).
%</pf:ThreeKindsSolutionSets1>
\end{proof}

This table summarizes the factors affecting the size of a
general solution.

\smallskip
%<*table:KindsSolutionSets>
\begin{center} % \small 
\begin{tabular}{r@{}c}
  &\hspace*{2.5em}\begin{tabular}{c} 
      \textit{number of solutions of the} \\[-.5ex]
      \textit{homogeneous system}
    \end{tabular}                            \\[1.7ex] 
  \begin{tabular}{r@{\hspace*{.5em}}} 
     \ \\[.6ex]
     \textit{particular} \\[-.55ex]
     \textit{solution}   \\[-.5ex]
     \textit{exists?}   
  \end{tabular}
  &\begin{tabular}{r|c@{\hspace*{1em}}c} % \cline{2-3}   
     \multicolumn{1}{c}{\ }
         &\textit{one}    &\textit{infinitely many}                    \\ 
     \cline{2-3}
     \textit{yes}    
        &\rule{0ex}{16pt}\begin{tabular}{@{}c@{}} unique \\[-.5ex] solution \end{tabular}
        &\begin{tabular}{@{}c@{}} infinitely many \\[-.5ex] solutions \end{tabular}
         \\[2ex] % \hline  
     \textit{no}    
        &\begin{tabular}{@{}c@{}} no \\[-.5ex] solutions \end{tabular}
        &\begin{tabular}{@{}c@{}} no \\[-.5ex] solutions \end{tabular} 
         \\ % \hline
   \end{tabular}
\end{tabular}
\end{center}
%</table:KindsSolutionSets>
\smallskip

The dimension on the top of the table is the simpler one.
When we perform Gauss's Method on a linear system, ignoring the
constants on the right side and so paying attention only
to the coefficients on the left-hand side,
we either end with every variable leading some row or else 
we find some variable that does not lead a row, that is,
we find some variable that is free. 
(We formalize ``ignoring the constants on the right'' by
considering the associated homogeneous system.)

A notable special case is
systems having the same number of equations as unknowns. 
Such a system will have a solution, and that solution will be unique, 
if and only if it
reduces to an echelon form system where every variable leads its row
(since there are the same number of variables as rows),
which will happen if and only if
the associated homogeneous system has a unique solution.

\begin{definition} \label{df:Nonsingular}
%<*df:Nonsingular>
A square matrix is \definend{nonsingular}\index{nonsingular!matrix}
\index{matrix!nonsingular}
if it is the matrix of coefficients of a
homogeneous system with a unique solution.
It is
\definend{singular}\index{singular!matrix}\index{matrix!singular} otherwise,
that is,
if it is the matrix of coefficients of a homogeneous system with 
infinitely many solutions.
%</df:Nonsingular>
\end{definition}

\begin{example}
The first of these matrices is nonsingular while the second is singular
\begin{equation*}
  \begin{mat}[r]
    1  &2  \\
    3  &4
  \end{mat}
  \qquad
  \begin{mat}[r]
    1  &2  \\
    3  &6
  \end{mat}
\end{equation*}
because the first of these homogeneous systems has a unique solution 
while the second has infinitely many solutions.
\begin{equation*}
  \begin{linsys}[b]{2}
    x &+  &2y  &=  &0  \\
   3x &+  &4y  &=  &0  
  \end{linsys}
  \qquad
  \begin{linsys}[b]{2}
    x &+  &2y  &=  &0  \\
   3x &+  &6y  &=  &0
  \end{linsys}
\end{equation*}  
We have made the distinction in the definition because a system
with the same number of equations as variables
behaves in one of two ways, depending on whether its matrix of coefficients
is nonsingular or singular.
Where the matrix of coefficients is nonsingular the system 
has a unique solution for any constants on the right 
side:~for instance, Gauss's Method shows that this system
\begin{equation*}
  \begin{linsys}{2}
    x  &+  &2y  &=  &a \\
    3x &+  &4y  &=  &b
  \end{linsys}
\end{equation*}
has the unique solution $x=b-2a$ and  $y=(3a-b)/2$.
On the other hand, where the matrix of coefficients is
singular the system never has a unique solution\Dash it 
has either no solutions or else has infinitely many, as with these.
\begin{equation*}
  \begin{linsys}[b]{2}
    x  &+  &2y  &=   &1   \\
   3x  &+  &6y  &=   &2   
  \end{linsys}
  \qquad
  \begin{linsys}[b]{2}
    x  &+  &2y  &=   &1   \\
   3x  &+  &6y  &=   &3
  \end{linsys}
\end{equation*} 
\end{example}

The definition uses the word `singular' because it 
means ``departing from general expectation.''
People often, naively, expect that systems 
with the same number of variables as equations will have a unique solution.
Thus, we can think of the word as connoting 
``troublesome,'' or at least ``not ideal.''
(That `singular' applies to those systems that never have exactly one solution 
is ironic, but it is the standard term.)

\begin{example}
The systems from \nearbyexample{ex:FirstExHomoSys},
\nearbyexample{ex:HomoZeroOnlySol},
and \nearbyexample{ex:IllusGenEqPartHomo}
each have an associated homogeneous system with a unique solution.
Thus these matrices are nonsingular.
\begin{equation*}
  \begin{mat}[r]
    3  &4  \\
    2  &-1
  \end{mat}
  \qquad
  \begin{mat}[r]
    3  &2   &1  \\
    6  &-4  &0  \\
    0  &1   &1
  \end{mat}
  \qquad
  \begin{mat}[r]
    1  &2  &-1 \\
    2  &4  &0  \\
    0  &1  &-3
  \end{mat}
\end{equation*}
The Chemistry problem from \nearbyexample{ex:SolnChemProb} 
is a homogeneous system with more than one solution so its matrix
is singular. 
\begin{equation*}
  \begin{mat}[r]
    7  &0  &-7 &0  \\
    8  &1  &-5 &-2 \\
    0  &1  &-3 &0  \\
    0  &3  &-6 &-1
  \end{mat}
\end{equation*}
\end{example}

The table above has two dimensions.
We have considered the one on top:~we can tell
into which column a given linear system goes
solely by considering the system's left-hand side; the 
constants on the right-hand side play no role in this.

The table's other dimension, 
determining whether a particular solution exists, is tougher.
Consider these two systems with the same left side but different right sides.
\begin{equation*}
  \begin{linsys}[b]{2}
    3x &+ &2y &= &5  \\
    3x &+ &2y &= &5
  \end{linsys}
  \qquad
  \begin{linsys}[b]{2}
    3x &+ &2y &= &5  \\
    3x &+ &2y &= &4
  \end{linsys}
\end{equation*}
The first has a solution while the second does not, so
here the constants on the right side decide if the system has a solution.
We could conjecture that the left side of a linear system determines
the number of solutions while the right side determines if solutions
exist but that guess is not correct.
Compare these two,
with the same right sides but different left sides.
\begin{equation*}
  \begin{linsys}[b]{2}
    3x &+ &2y &= &5  \\
    4x &+ &2y &= &4
  \end{linsys}
  \qquad
  \begin{linsys}[b]{2}
    3x &+ &2y &= &5  \\
    3x &+ &2y &= &4
  \end{linsys}
\end{equation*}
The first has a solution but the second does not.
Thus the constants on the right side of a system 
don't alone determine whether a solution exists.
Rather, that depends on some interaction between the left and
right.

For some intuition about that interaction,
consider this system with one of the coefficients left unspecified, as  
the variable~$c$.
\begin{equation*}
  \begin{linsys}{3}
    x  &+  &2y  &+  &3z  &=  &1  \\
    x  &+  &y   &+  &z   &=  &1  \\
   cx  &+  &3y  &+  &4z  &=  &0
  \end{linsys}
\end{equation*}
If \( c=2 \) then this system has no solution because the left-hand side 
has the third row as the sum of the first two, while the right-hand does not.
If \( c\neq 2 \) then this system has a unique solution (try it with \( c=1 \)).
For a system to have a solution, if one row of the matrix of coefficients on
the left is a linear combination of other rows
then on the right the constant from that row must be the same
combination of constants from the same rows.

More intuition about the interaction comes from studying linear
combinations.
That will be our focus in the second chapter, after we finish the study
of Gauss's Method itself in the rest of this chapter.

\begin{exercises}
  \item Solve this system.
    Then solve the associated homogeneous system.
    \begin{equation*}
      \begin{linsys}{4}
        x  &+ &y  &- &2z &= &0 \\
        x  &- &y  &  &   &= &-3 \\
        3x &- &y  &- &2z &= &-6  \\
           &  &2y &- &2z &= &3  
      \end{linsys}
   \end{equation*}
   \begin{answer}
     This reduction solves the system.
     \begin{align*}
       \begin{amat}{3}
         1 &1   &-2 &0 \\
         1 &-1  &0  &3  \\
         3 &-1  &-2 &-6 \\
         0 &2   &-2 &3
       \end{amat}
       &\grstep[-3\rho_1+\rho_3]{-\rho_1+\rho_2}
       \begin{amat}{3}
         1 &1   &-2 &0 \\
         0 &-2  &2  &-3  \\
         0 &-4  &4  &-6 \\
         0 &2   &-2 &3
       \end{amat}                                 \\
       &\grstep[\rho_2+\rho_4]{-2\rho_2+\rho_3}
       \begin{amat}{3}
         1 &1   &-2 &0 \\
         0 &-2  &2  &-3  \\
         0 &0   &0  &0 \\
         0 &0   &0  &0
       \end{amat}
     \end{align*}
     The solution set is this.
     \begin{equation*}
       \set{\colvec{-3/2 \\ 3/2 \\ 0}
            +\colvec{1 \\ 1 \\ 1}z
            \suchthat z\in\Re}
     \end{equation*}
     Similarly we can reduce the associated homogeneous system
     \begin{align*}
       \begin{amat}{3}
         1 &1   &-2 &0 \\
         1 &-1  &0  &0  \\
         3 &-1  &-2 &0 \\
         0 &2   &-2 &0
       \end{amat}
       &\grstep[-3\rho_1+\rho_3]{-\rho_1+\rho_2}
       \begin{amat}{3}
         1 &1   &-2 &0 \\
         0 &-2  &2  &0  \\
         0 &-4  &4  &0 \\
         0 &2   &-2 &0
       \end{amat}                                         \\
       &\grstep[\rho_2+\rho_4]{-2\rho_2+\rho_3}
       \begin{amat}{3}
         1 &1   &-2 &0 \\
         0 &-2  &2  &0  \\
         0 &0   &0  &0 \\
         0 &0   &0  &0
       \end{amat}
     \end{align*}
     to get its solution set.
     \begin{equation*}
       \set{
            \colvec{1 \\ 1 \\ 1}z
            \suchthat z\in\Re}
     \end{equation*}
   \end{answer}
  \recommended \item 
    Solve each system.
    Express the solution set using vectors.
    Identify the particular solution and the solution set of the
    homogeneous system.
    (These systems also appear in \nearbyexercise{exer:SolveInMatrixNotation}.)
    \begin{exparts*}
      \partsitem \( \begin{linsys}[t]{2}
                  3x  &+  &6y  &=  &18  \\
                   x  &+  &2y  &=  &6   
                   \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{2}
                   x  &+  &y   &=  &1  \\
                   x  &-  &y   &=  &-1   
                    \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{3}
                   x_1  &   &     &+  &x_3   &=  &4  \\
                   x_1  &-  &x_2  &+  &2x_3  &=  &5  \\
                  4x_1  &-  &x_2  &+  &5x_3  &=  &17  
                    \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{3}
                   2a   &+  &b    &-  &c     &=  &2  \\
                   2a   &   &     &+  &c     &=  &3  \\
                    a   &-  &b    &   &      &=  &0   
                    \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{4}
                     x  &+  &2y   &-   &z   &    &    &=  &3  \\
                    2x  &+  &y    &    &    &+   &w   &=  &4  \\
                     x  &-  &y    &+   &z   &+   &w   &=  &1  
                    \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{4}
                     x  &   &     &+   &z   &+   &w   &=  &4  \\
                    2x  &+  &y    &    &    &-   &w   &=  &2  \\
                    3x  &+  &y    &+   &z   &    &    &=  &7  
                    \end{linsys}  \)
    \end{exparts*}
    \begin{answer}
      For the arithmetic to these, see the answers from the prior
      subsection.

      \begin{exparts}
        \partsitem
          This is the solution set.
          \begin{equation*}
            S=\set{\colvec[r]{6 \\ 0}+\colvec[r]{-2 \\ 1}y
              \suchthat y\in\Re}
          \end{equation*}
          Here are the particular solution and the solution set 
          for the associated
          homogeneous system.
          \begin{equation*}
            \colvec[r]{6 \\ 0}
              \quad\text{and}\quad
            \set{\colvec[r]{-2 \\ 1}y
              \suchthat y\in\Re}
          \end{equation*}
          \textit{Note.}
          There are two possible points of confusion here.
          First, the set $S$ given above is equal to this set 
          \begin{equation*}
            T=\set{\colvec[r]{4 \\ 1}+\colvec[r]{-2 \\ 1}y
              \suchthat y\in\Re}
          \end{equation*}
          because the two sets contain the same members.
          All of these are correct answers to, 
          ``What is a particular solution?''
          \begin{equation*}
            \colvec{6 \\ 0},\quad
            \colvec{4 \\ 1},\quad
            \colvec{2 \\ 2},\quad
            \colvec{1 \\ 2.5}
          \end{equation*}
          The second point of confusion is that the letter we use 
          in the set doesn't matter.
          This set also equals $S$.
          \begin{equation*}
            U=\set{\colvec[r]{6 \\ 0}+\colvec[r]{-2 \\ 1}u
                   \suchthat u\in\Re}
          \end{equation*}
        \partsitem
          This is the solution set.
          \begin{equation*}
            \set{\colvec[r]{0 \\ 1} }
          \end{equation*}
          These are a particular solution, 
          and the solution set for the associated
          homogeneous system.
          \begin{equation*}
            \colvec[r]{0 \\ 1}
              \qquad
            \set{\colvec[r]{0 \\ 0} }
          \end{equation*}
        \partsitem
          The solution set is infinite.
          \begin{equation*}
            \set{\colvec[r]{4 \\ -1 \\ 0}+\colvec[r]{-1 \\ 1 \\ 1}x_3
              \suchthat x_3\in\Re}
          \end{equation*}
          This is a particular solution and the solution set for the associated
          homogeneous system.
          \begin{equation*}
            \colvec[r]{4 \\ -1 \\ 0}
              \qquad
            \set{\colvec[r]{-1 \\ 1 \\ 1}x_3
              \suchthat x_3\in\Re}
          \end{equation*}
        \partsitem
          The solution set is a singleton.
          \begin{equation*}
            \set{\colvec[r]{1 \\ 1 \\ 1}}
          \end{equation*}
          A particular solution and the solution set for the associated
          homogeneous system are here.
          \begin{equation*}
            \colvec[r]{1 \\ 1 \\ 1}
              \qquad
            \set{\colvec[r]{0 \\ 0 \\ 0}}
          \end{equation*}
        \partsitem
          The solution set is infinite.
          \begin{equation*}
            \set{\colvec[r]{5/3 \\ 2/3 \\ 0 \\ 0}
                 +\colvec[r]{-1/3 \\ 2/3 \\ 1 \\ 0}z
                 +\colvec[r]{-2/3 \\ 1/3 \\ 0 \\ 1}w
                 \suchthat z,w\in\Re}
          \end{equation*}
          A particular solution and the solution set for the associated
          homogeneous system are here.
          \begin{equation*}
            \colvec[r]{5/3 \\ 2/3 \\ 0 \\ 0}
              \qquad
            \set{\colvec[r]{-1/3 \\ 2/3 \\ 1 \\ 0}z
                 +\colvec[r]{-2/3 \\ 1/3 \\ 0 \\ 1}w
                 \suchthat z,w\in\Re}
          \end{equation*}
        \partsitem This system's solution set is empty.
          Thus, there is no particular solution.
          The solution set of the associated homogeneous system is this.
          \begin{equation*}
            \set{\colvec[r]{-1 \\ 2 \\ 1 \\ 0}z
                 +\colvec[r]{-1 \\ 3 \\ 0 \\ 1}w
                 \suchthat z,w\in\Re}
          \end{equation*}
      \end{exparts}  
    \end{answer}
  \item 
    Solve each system, giving
    the solution set in vector notation.
    Identify the particular solution and the solution of the
    homogeneous system.
    \begin{exparts*}
      \partsitem \( \begin{linsys}[t]{3}
                  2x  &+  &y  &-  &z  &=  &1  \\
                  4x  &-  &y  &   &   &=  &3  
                  \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{4}
                   x  &   &   &-  &z  &   &   &=  &1  \\
                      &   &y  &+  &2z &-  &w  &=  &3  \\
                   x  &+  &2y &+  &3z &-  &w  &=  &7  
                   \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{4}
                   x  &-  &y  &+  &z  &   &   &=  &0  \\
                      &   &y  &   &   &+  &w  &=  &0  \\
                  3x  &-  &2y &+  &3z &+  &w  &=  &0  \\
                      &   &-y &   &   &-  &w  &=  &0  
                  \end{linsys}  \)
      \partsitem \( \begin{linsys}[t]{5}
                   a  &+  &2b &+  &3c &+  &d  &-  &e  &=  &1  \\
                  3a  &-  &b  &+  &c  &+  &d  &+  &e  &=  &3  
                  \end{linsys}  \)
    \end{exparts*}
    \begin{answer}
    The answers from the prior subsection show the row operations.
    Each answer here just lists the solution set, the particular solution,
    and the homogeneous solution.
    \begin{exparts}
      \partsitem
        The solution set is this.
        \begin{equation*}
          \set{\colvec[r]{2/3 \\ -1/3 \\ 0}
               +\colvec[r]{1/6 \\ 2/3 \\ 1}z
              \suchthat z\in\Re}
        \end{equation*}
        A particular solution and the solution set for the associated
        homogeneous system are here.
        \begin{equation*}
          \colvec[r]{2/3 \\ -1/3 \\ 0}
            \qquad
        \set{\colvec[r]{1/6 \\ 2/3 \\ 1}z
            \suchthat z\in\Re}
        \end{equation*}
      \partsitem
        The solution set is infinite.
        \begin{equation*}
          \set{\colvec[r]{1 \\ 3 \\ 0 \\ 0}
               +\colvec[r]{1 \\-2 \\ 1 \\ 0}z
              \suchthat z\in\Re}
        \end{equation*}
        Here are 
        a particular solution and the solution set for the associated
        homogeneous system.
        \begin{equation*}
          \colvec[r]{1 \\ 3 \\ 0 \\ 0}
            \qquad
          \set{\colvec[r]{1 \\ -2 \\ 1 \\ 0}z
              \suchthat z\in\Re}
        \end{equation*}
      \partsitem
        This is the solution set.
        \begin{equation*}
          \set{\colvec[r]{0 \\ 0 \\ 0 \\ 0}
               +\colvec[r]{-1 \\ 0 \\ 1 \\ 0}z
               +\colvec[r]{-1 \\ -1 \\ 0 \\ 1}w
              \suchthat z,w\in\Re}
        \end{equation*}
        Here is
        a particular solution and the solution set for the associated
        homogeneous system.
        \begin{equation*}
          \colvec[r]{0 \\ 0 \\ 0 \\ 0}
            \qquad
          \set{\colvec[r]{-1 \\ 0 \\ 1 \\ 0}z
               +\colvec[r]{-1 \\ -1 \\ 0 \\ 1}w
              \suchthat z,w\in\Re}
        \end{equation*}
      \partsitem
        The solution set is this.
        \begin{equation*}
          \set{\colvec[r]{1 \\ 0 \\ 0 \\ 0 \\ 0}
               +\colvec[r]{-5/7 \\ -8/7 \\ 1 \\ 0 \\ 0}c
               +\colvec[r]{-3/7 \\ -2/7 \\ 0 \\ 1 \\ 0}d
               +\colvec[r]{-1/7 \\ 4/7 \\ 0 \\ 0 \\ 1}e
              \suchthat c,d,e\in\Re}
        \end{equation*}
        And, this is
        a particular solution and the solution set for the associated
        homogeneous system.
        \begin{equation*}
          \colvec[r]{1 \\ 0 \\ 0 \\ 0 \\ 0}
            \qquad
          \set{\colvec[r]{-5/7 \\ -8/7 \\ 1 \\ 0 \\ 0}c
               +\colvec[r]{-3/7 \\ -2/7 \\ 0 \\ 1 \\ 0}d
               +\colvec[r]{-1/7 \\ 4/7 \\ 0 \\ 0 \\ 1}e
              \suchthat c,d,e\in\Re}
        \end{equation*}
    \end{exparts}  
   \end{answer}
  \recommended \item 
    For the system
    \begin{equation*}
      \begin{linsys}{4}
       2x  &-  &y  &   &    &-  &w  &=  &3  \\
           &   &y  &+  &z   &+  &2w &=  &2  \\
        x  &-  &2y &-  &z   &   &   &=  &-1
      \end{linsys}
    \end{equation*}
    which of these can be used as the particular solution part of some
    general solution?
    \begin{exparts*}
      \partsitem   \( \colvec[r]{0 \\ -3 \\ 5 \\ 0} \)
      \partsitem   \( \colvec[r]{2 \\ 1 \\ 1 \\ 0} \)
      \partsitem   \( \colvec[r]{-1 \\ -4 \\ 8 \\ -1} \)
    \end{exparts*}
    \begin{answer}
      Just plug them in and see if they satisfy all three equations.
      \begin{exparts}
        \partsitem No.
        \partsitem Yes.
        \partsitem Yes.
      \end{exparts}  
    \end{answer}
  \recommended \item  
    \nearbylemma{th:GenEqPartHomo} says that we can use any particular solution 
    for $\vec{p}$.
    Find, if possible, a general solution to this system
    \begin{equation*}
      \begin{linsys}{4}
        x  &-  &y  &   &    &+  &w  &=  &4  \\
       2x  &+  &3y &-  &z   &   &   &=  &0  \\
           &   &y  &+  &z   &+  &w  &=  &4  
      \end{linsys}
    \end{equation*}
    that uses the given vector as its particular solution.
    \begin{exparts*}
      \partsitem   \( \colvec[r]{0 \\ 0 \\ 0 \\ 4} \)
      \partsitem   \( \colvec[r]{-5 \\ 1 \\ -7 \\ 10} \)
      \partsitem   \( \colvec[r]{2 \\ -1 \\ 1 \\ 1} \)
    \end{exparts*}
    \begin{answer}
      Gauss's Method on the associated homogeneous system 
      \begin{align*}
        \begin{amat}[r]{4}
           1  &-1  &0  &1  &0  \\
           2  &3   &-1 &0  &0  \\
           0  &1   &1  &1  &0
        \end{amat}
        &\grstep{-2\rho_1+\rho_2}
        \begin{amat}[r]{4}
           1  &-1  &0  &1  &0  \\
           0  &5   &-1 &-2 &0  \\
           0  &1   &1  &1  &0
        \end{amat}                                \\
        &\grstep{-(1/5)\rho_2+\rho_3}
        \begin{amat}[r]{4}
           1  &-1  &0  &1  &0  \\
           0  &5   &-1 &-2 &0  \\
           0  &0   &6/5&7/5&0
        \end{amat}
      \end{align*}
      gives this is the solution to the homogeneous problem.
      \begin{equation*}
        \set{\colvec[r]{-5/6 \\ 1/6 \\ -7/6 \\ 1}w\suchthat w\in\Re}
      \end{equation*}
      \begin{exparts}
        \partsitem That vector is indeed a particular solution, so the required
          general solution is this.
          \begin{equation*}
            \set{\colvec[r]{0 \\ 0 \\ 0 \\ 4}+
                 \colvec[r]{-5/6 \\ 1/6 \\ -7/6 \\ 1}w\suchthat w\in\Re}
          \end{equation*}
        \partsitem That vector is a particular solution so the required
          general solution is this.
          \begin{equation*}
            \set{\colvec[r]{-5 \\ 1 \\ -7 \\ 10}+
                 \colvec[r]{-5/6 \\ 1/6 \\ -7/6 \\ 1}w\suchthat w\in\Re}
          \end{equation*}
        \partsitem That vector is not a solution of the system since
          it does not satisfy the third equation.
          No such general solution exists.
      \end{exparts} 
    \end{answer}
  \item 
     One is nonsingular while the other is singular.
     Which is which?
     \begin{exparts*}
       \partsitem $\begin{mat}[r]
           1  &3   \\
           4  &-12    
         \end{mat}$
       \partsitem $\begin{mat}[r]
           1  &3  \\
           4  &12  
         \end{mat}$
     \end{exparts*}
     \begin{answer}
       The first is nonsingular while the second is singular.
       Just do Gauss's Method and see if the echelon form result has
       non-$0$ numbers in each entry on the diagonal.
     \end{answer}
  \recommended \item 
    Singular or nonsingular?
    \begin{exparts*}
      \partsitem \(
        \begin{mat}[r]
          1  &2  \\
          1  &3
        \end{mat}   \)
      \partsitem \(
        \begin{mat}[r]
          1  &2  \\
         -3  &-6
        \end{mat}   \)
      \partsitem \(
        \begin{mat}[r]
          1  &2  &1  \\
          1  &3  &1
        \end{mat}   \)~(Careful!)
      \partsitem \(
        \begin{mat}[r]
          1  &2  &1  \\
          1  &1  &3  \\
          3  &4  &7
        \end{mat}   \)
      \partsitem \(
        \begin{mat}[r]
          2  &2  &1  \\
          1  &0  &5  \\
         -1  &1  &4
        \end{mat}   \)
    \end{exparts*}
    \begin{answer}
      \begin{exparts}
      \partsitem Nonsingular:
        \begin{equation*}
          \grstep{-\rho_1+\rho_2}
          \begin{mat}[r]
            1  &2  \\
            0  &1
          \end{mat}
        \end{equation*}
        ends with each row containing a leading entry.
      \partsitem Singular:
        \begin{equation*}
          \grstep{3\rho_1+\rho_2}
          \begin{mat}[r]
            1  &2  \\
            0  &0
          \end{mat}
        \end{equation*}
        ends with row \( 2 \) without a leading entry.
      \partsitem Neither.
        A matrix must be square for either word to apply.
      \partsitem Singular.
      \partsitem Nonsingular.
     \end{exparts}  
    \end{answer}
  \recommended \item 
    Is the given vector in the set generated by the
    given set?
      \begin{exparts}
        \partsitem \( \colvec[r]{2 \\ 3}, \)\
          \( \set{\colvec[r]{1 \\ 4},
                \colvec[r]{1 \\ 5}} \)
        \partsitem \( \colvec[r]{-1 \\ 0 \\ 1}, \)\
          \( \set{\colvec[r]{2 \\ 1 \\ 0},
                \colvec[r]{1 \\ 0 \\ 1}} \)
        \partsitem \( \colvec[r]{1 \\ 3 \\ 0}, \)\
          \( \set{\colvec[r]{1 \\ 0 \\ 4},
                \colvec[r]{2 \\ 1 \\ 5},
                \colvec[r]{3 \\ 3 \\ 0},
                \colvec[r]{4 \\ 2 \\ 1}} \)
        \partsitem \( \colvec[r]{1 \\ 0 \\ 1 \\ 1}, \)\
          \( \set{\colvec[r]{2 \\ 1 \\ 0 \\ 1},
                \colvec[r]{3 \\ 0 \\ 0 \\ 2}} \)
      \end{exparts}
      \begin{answer}
        In each case we must decide if the vector is a linear combination
        of the vectors in the set.
        \begin{exparts}
          \partsitem Yes.
            Solve
            \begin{equation*}
              c_1\colvec[r]{1 \\ 4}+c_2\colvec[r]{1 \\ 5}=\colvec[r]{2 \\ 3}
            \end{equation*}
            with
            \begin{equation*}
              \begin{amat}[r]{2}
                1  &1  &2  \\
                4  &5  &3
              \end{amat}
              \grstep{-4\rho_1+\rho_2}
              \begin{amat}[r]{2}
                1  &1  &2  \\
                0  &1  &-5
              \end{amat}
            \end{equation*}
            to conclude that there are $c_1$ and $c_2$ giving the combination. 
          \partsitem No.
            The reduction
            \begin{equation*}
              \begin{amat}[r]{2}
                2  &1  &-1 \\
                1  &0  &0  \\
                0  &1  &1
              \end{amat}
              \grstep{-(1/2)\rho_1+\rho_2}
              \begin{amat}[r]{2}
                2  &1     &-1 \\
                0  &-1/2  &1/2  \\
                0  &1     &1
              \end{amat}
              \grstep{2\rho_2+\rho_3}
              \begin{amat}[r]{2}
                2  &1     &-1 \\
                0  &-1/2  &1/2  \\
                0  &0     &2
              \end{amat}
            \end{equation*}
            shows that
            \begin{equation*}
              c_1\colvec[r]{2 \\ 1 \\ 0}+c_2\colvec[r]{1 \\ 0 \\ 1}
                =\colvec[r]{-1 \\ 0 \\ 1}
            \end{equation*}
            has no solution.
          \partsitem Yes.
            The reduction
            \begin{align*}
              \begin{amat}[r]{4}
                1  &2  &3  &4  &1  \\
                0  &1  &3  &2  &3  \\
                4  &5  &0  &1  &0
              \end{amat}
              &\grstep{-4\rho_1+\rho_3}
              \begin{amat}[r]{4}
                1  &2  &3  &4  &1  \\
                0  &1  &3  &2  &3  \\
                0  &-3 &-12&-15&-4
              \end{amat}                   \\
              &\grstep{3\rho_2+\rho_3}
              \begin{amat}[r]{4}
                1  &2  &3  &4  &1  \\
                0  &1  &3  &2  &3  \\
                0  &0  &-3 &-9 &5
              \end{amat}
            \end{align*}
            shows that there are infinitely many ways
            \begin{equation*}
              \set{\colvec[r]{c_1 \\ c_2 \\ c_3 \\ c_4}=
                   \colvec[r]{-10 \\ 8 \\ -5/3 \\ 0}+
                   \colvec[r]{-9 \\ 7 \\ -3 \\ 1}c_4
                    \suchthat c_4\in\Re}
            \end{equation*}
            to write a combination.
            \begin{equation*}
              \colvec[r]{1 \\ 3 \\ 0}=
              c_1\colvec[r]{1 \\ 0 \\ 4}+
              c_2\colvec[r]{2 \\ 1 \\ 5}+
              c_3\colvec[r]{3 \\ 3 \\ 0}+
              c_4\colvec[r]{4 \\ 2 \\ 1}
            \end{equation*}
          \partsitem No.
            Look at the third components.
        \end{exparts} 
      \end{answer}
  \item 
     Prove that any linear system with a nonsingular matrix of 
     coefficients has a solution, and that the solution is unique.
    \begin{answer}
        Because the matrix of coefficients is nonsingular, Gauss's Method
        ends with an echelon form where each variable leads an equation.
        Back substitution gives a unique solution.

      (Another way to see that the solution is unique is to note that
      with a nonsingular matrix of coefficients the associated
      homogeneous system has a unique solution, by definition.
      Since the general solution is the sum of a particular solution with
      each homogeneous solution, the general solution has 
      at most one element.)
     \end{answer}
  \item 
    In the
    proof of
    \nearbylemma{le:HomoSltnSpanVecs},
    what happens if there are no non-\( 0=0 \) equations?
    \begin{answer}
      In this case the solution set is all of \( \Re^n \) and we can 
      express it in the required form.
      \begin{equation*}
        \set{c_1\colvec[r]{1 \\ 0 \\ \vdotswithin{1} \\ 0}
             +c_2\colvec[r]{0 \\ 1 \\ \vdotswithin{0} \\ 0}
             +\cdots
             +c_n\colvec[r]{0 \\ 0 \\ \vdotswithin{0} \\ 1}
             \suchthat c_1,\ldots,c_n\in\Re}
      \end{equation*}  
     \end{answer}
  \recommended \item 
    Prove that if \( \vec{s} \) and \( \vec{t} \)
    satisfy a homogeneous system then so do these vectors.
    \begin{exparts*}
      \partsitem \( \vec{s}+\vec{t} \)
      \partsitem \( 3\vec{s} \)
      \partsitem \( k\vec{s}+m\vec{t} \) for \( k,m\in\Re \)
    \end{exparts*}
    What's wrong with this argument: ``These three show that if a homogeneous
    system has one solution then it has many solutions\Dash any multiple of 
    a solution is another solution, and any sum of solutions is a solution
    also\Dash so there are no
    homogeneous systems with exactly one solution.''?
    \begin{answer}
      Assume \( \vec{s},\vec{t}\in\Re^n \) and write them as here.
      \begin{equation*}
        \vec{s}=\colvec{s_1 \\ \vdotswithin{s_1} \\ s_n}
          \qquad
        \vec{t}=\colvec{t_1 \\ \vdotswithin{t_1} \\ t_n}
      \end{equation*}
      Also let \( a_{i,1}x_1+\cdots+a_{i,n}x_n=0 \) be the \( i \)-th equation
      in the homogeneous system.
      \begin{exparts}
        \partsitem The check is easy.
          \begin{multline*}
            a_{i,1}(s_1+t_1)+\cdots+a_{i,n}(s_n+t_n)      \\
            =
            (a_{i,1}s_1+\cdots+a_{i,n}s_n)
            +(a_{i,1}t_1+\cdots+a_{i,n}t_n)           
            =
            0+0
          \end{multline*}
        \partsitem This is similar to the prior one.
          \begin{equation*}
            a_{i,1}(3s_1)+\cdots+a_{i,n}(3s_n)
            =3(a_{i,1}s_1+\cdots+a_{i,n}s_n)
            =3\cdot 0=0
          \end{equation*}
        \partsitem This one is not much harder.
          \begin{multline*}
            a_{i,1}(ks_1+mt_1)+\cdots+a_{i,n}(ks_n+mt_n)  \\
            =
            k(a_{i,1}s_1+\cdots+a_{i,n}s_n)
            +m(a_{i,1}t_1+\cdots+a_{i,n}t_n)         
            =
            k\cdot 0+m\cdot 0
          \end{multline*}
      \end{exparts}  
     What is wrong with that argument is that any linear combination 
     involving only the 
     zero vector yields the zero vector.
   \end{answer}
  \item
    Prove that if a system with only rational coefficients
    and constants
    has a solution then it has at least one all-rational solution.
    Must it have infinitely many?
    \begin{answer}
      First the proof.

      Gauss's Method will use only rationals (e.g.,
      \( -(m/n)\rho_i+\rho_j \)).
      Thus we can express the solution set using only rational numbers as
      the components of each vector.
      Now the particular solution is all rational.

      There are infinitely many rational vector solutions if and only if the
      associated homogeneous system has infinitely many 
      real vector solutions.
      That's because setting any parameters to be rationals will produce an
      all-rational solution.  
   \end{answer}
\end{exercises}



















%\typeout{Comparing Set Descriptions ommitted}
\endinput




\subsection{Comparing Set Descriptions}
\emph{This subsection is optional.
Later material will not require the work here.}

A set can be described in many different ways.
Here are two different descriptions of a single set:
\begin{equation*}
  \set{\colvec[r]{1 \\ 2 \\ 3}z\suchthat z\in\Re}
  \quad\text{and}\quad
  \set{\colvec[r]{2 \\ 4 \\ 6}w\suchthat w\in\Re}.
\end{equation*}
For instance, this set contains 
\begin{equation*}
  \colvec[r]{5 \\ 10 \\ 15}
\end{equation*}
(take $z=5$ and $w=5/2$) but does not contain
\begin{equation*}
  \colvec[r]{4 \\ 8 \\ 11}
\end{equation*}
(the first component gives $z=4$ but that clashes with the third component,
similarly the first component gives $w=4/5$ but the third component 
gives something different).
Here is a third description of the same set: 
\begin{equation*}
  \set{\colvec[r]{3 \\ 6 \\ 9}+\colvec[r]{-1 \\ -2 \\ -3}y\suchthat y\in\Re}.
\end{equation*}

We need to decide when two descriptions are describing the same set.
More pragmatically stated,
how can a person tell when an answer to a homework question describes
the same set as the one described in the back of the book?

Sets are equal if and only if they have the same members.
A common way to show that two sets, $S_1$ and $S_2$, are equal is to show 
mutual inclusion:\index{sets!mutual inclusion}\index{mutual inclusion}
any member of $S_1$ is also in $S_2$, and 
any member of $S_2$ is also in $S_1$.\appendrefs{set equality}

\begin{example}
To show that 
\begin{equation*}
  S_1=
  \set{\colvec[r]{1 \\ -1 \\ 0}c+\colvec[r]{1 \\ 1 \\ 0}d\suchthat c,d\in\Re}
\end{equation*}
equals
\begin{equation*}
  S_2=
  \set{\colvec[r]{4 \\ 1 \\ 0}m+\colvec[r]{-1 \\ -3 \\ 0}n\suchthat m,n\in\Re}
\end{equation*}
we show first that $S_1\subseteq S_2$ and then that $S_2\subseteq S_1$. 

For the first half we must check that any vector
from \( S_1 \) is also in \( S_2 \).
We first consider two examples to use them as models for the general argument.
If we make up a member of $S_1$ by trying \( c=1 \) and \( d=1 \),
then to show that it is in $S_2$ we need \( m \) and $n$ such that
\begin{equation*}
  \colvec[r]{4 \\ 1 \\ 0}m
  +\colvec[r]{-1 \\ -3 \\ 0}n
  =\colvec[r]{2 \\ 0 \\ 0}
\end{equation*}
that is, this relation holds between $m$ and $n$.
\begin{equation*}
  \begin{linsys}{2}
    4m  &-  &n  &=  &2  \\
    1m  &-  &3n &=  &0  \\
        &   &0  &=  &0 
  \end{linsys}  
\end{equation*}
Similarly,
if we try \( c=2 \) and \( d=-1 \), then to show that the resulting
member of $S_1$ is in $S_2$ we need \( m \) and $n$ such that
such that 
\begin{equation*}
  \colvec[r]{4 \\ 1 \\ 0}m
  +\colvec[r]{-1 \\ -3 \\ 0}n
  =\colvec[r]{3 \\ -3 \\ 0}
\end{equation*}
that is, this holds.
\begin{equation*}
  \begin{linsys}{2}
    4m  &-  &n  &=  &3  \\
    1m  &-  &3n &=  &-3 \\
        &   &0  &=  &0 
   \end{linsys}
\end{equation*}
In the general case,
to show that any vector from \( S_1 \) is a member of \( S_2 \) we must show
that for any \( c \) and \( d \) there are appropriate \( m \) and \( n \).
We follow the pattern of the examples; fix
\begin{equation*}
  \colvec{c+d \\ -c+d \\ 0}\in S_1
\end{equation*}
and look for \( m \) and \( n \) such that
\begin{equation*}
  \colvec[r]{4 \\ 1 \\ 0}m
  +\colvec[r]{-1 \\ -3 \\ 0}n
  =\colvec{c+d \\ -c+d \\ 0}
\end{equation*}
that is, this is true.
\begin{equation*}
  \begin{linsys}{2}
    4m  &-  &n  &=  &c+d\hfill  \\
     m  &-  &3n &=  &-c+d\hfill  \\
        &   &0  &=  &0\hfill  
  \end{linsys}
\end{equation*}
Applying Gauss's Method
\begin{equation*}
  \begin{linsys}{2}
    4m  &-  &n  &=  &c+d\hfill  \\
     m  &-  &3n &=  &-c+d\hfill  
  \end{linsys}
  \grstep{-(1/4)\rho_1+\rho_2}
  \begin{linsys}{2}
    4m  &-  &n        &=  &c+d\hfill            \\
        &   &-(11/4)n &=  &-(5/4)c+(3/4)d\hfill  
   \end{linsys}
\end{equation*}
gives \( n=(5/11)c-(3/11)d \) and \( m=(4/11)c+(2/11)d \).
This shows that for any choice of $c$ and $d$ there are appropriate 
$m$ and $n$.
We conclude any member of $S_1$ is a member of $S_2$ because 
it can be rewritten in this way:
\begin{equation*}
   \colvec{c+d \\ -c+d \\ 0}
   =\colvec[r]{4 \\ 1 \\ 0}((4/11)c+(2/11)d)+
   \colvec[r]{-1 \\ -3 \\ 0}((5/11)c-(3/11)d).
\end{equation*}

For the other inclusion, \( S_2\subseteq S_1 \), we want to do the opposite.
We want to show that for any choice of $m$ and $n$ there are appropriate
$c$ and $d$.
So fix $m$ and $n$ and solve for \( c \) and \( d \):
\begin{equation*}
   \begin{linsys}{2}
     c  &+ &d  &= &4m-n\hfill \\
    -c  &+ &d  &= &m-3n\hfill 
   \end{linsys}
   \grstep{\rho_1+\rho_2}
   \begin{linsys}{2}
     c  &+ &d  &= &4m-n\hfill \\
        &  &2d &= &5m-4n\hfill 
    \end{linsys}
\end{equation*}
shows that \( d=(5/2)m-2n \) and \( c=(3/2)m+n \).
Thus any vector from \( S_2 \)
\begin{equation*}
  \colvec[r]{4 \\ 1 \\ 0}m+\colvec[r]{-1 \\ -3 \\ 0}n
\end{equation*}
is also of the right form for \( S_1 \)
\begin{equation*}
  \colvec[r]{1 \\ -1 \\ 0}((3/2)m+n)
    +\colvec[r]{1 \\ 1 \\ 0}((5/2)m-2n).
\end{equation*}
\end{example}

\begin{example}
Of course, sometimes sets are not equal.
The method of the prior example will help us see the relationship
between the two sets.
These 
\begin{equation*}
  P=
  \set{\colvec{x+y \\ 2x \\ y}\suchthat x,y\in\Re}
  \quad\text{and}\quad
  R=
  \set{\colvec{m+p \\ n \\ p}\suchthat m,n,p\in\Re}
\end{equation*}
are not equal sets.
While $P$ is a subset of $R$, it is a proper subset of $R$ because
$R$ is not a subset of $P$.

To see that, observe first that given a vector from \( P \)
we can express it in the form for \( R \)\Dash if
we fix $x$ and $y$, we can solve for appropriate $m$, $n$, and $p$:
\begin{equation*}
  \begin{linsys}{3}
     m  &   &   &+  &p  &=  &x+y\hfill  \\
        &   &n  &   &   &=  &2x\hfill   \\
        &   &   &   &p  &=  &y\hfill    
  \end{linsys}
\end{equation*}
shows that we can express any
\begin{equation*}
  \vec{v}=
  \colvec[r]{1 \\ 2 \\ 0}x+
  \colvec[r]{1 \\ 0 \\ 1}y
\end{equation*}
as a member of \( R \) with
\( m=x \), \( n=2x \), and \( p=y \):
\begin{equation*}
  \vec{v}=
  \colvec[r]{1 \\ 0 \\ 0}x+
  \colvec[r]{0 \\ 1 \\ 0}2x+
  \colvec[r]{1 \\ 0 \\ 1}y.
\end{equation*}
Thus \( P\subseteq R \).

But, for the other direction, the reduction
resulting from fixing $m$, $n$, and $p$ and looking for $x$ and $y$
\begin{align*}
  \begin{linsys}{2}
     x  &+  &y  &=  &m+p\hfill  \\
    2x  &   &   &=  &n\hfill    \\
        &   &y  &=  &p\hfill    
  \end{linsys}
  &\grstep{-2\rho_1+\rho_2}
  \begin{linsys}{2}
     x  &+  &y  &=  &m+p\hfill  \\
        &   &-2y&=  &-2m+n-2p\hfill \\
        &   &y  &=  &p\hfill    
   \end{linsys}                                  \\
  &\grstep{(1/2)\rho_2+\rho_3}
  \begin{linsys}{2}
     x  &+  &y  &=  &m+p\hfill  \\
        &   &-2y&=  &-2m+n-2p\hfill \\
        &   &0  &=  &m+(1/2)n\hfill 
    \end{linsys}
\end{align*}
shows that the only vectors
\begin{equation*}
  \colvec{m+p \\ n \\ p}\in R
\end{equation*}
representable in the form
\begin{equation*}
  \colvec{x+y \\ 2x \\ y}
\end{equation*}
are those where \( 0=m+(1/2)n \).
For instance,
\begin{equation*}
  \colvec[r]{0 \\ 1 \\ 0}
\end{equation*}
is in \( R \) but not in \( P \).
\end{example}

\begin{exercises}
  \item 
    Decide if the vector is a member of the set.
    \begin{exparts}
      \partsitem $\colvec[r]{2 \\ 3}$, 
         $\set{\colvec[r]{1 \\ 2}k\suchthat k\in\Re}$
      \partsitem $\colvec[r]{-3 \\ 3}$, 
         $\set{\colvec[r]{1 \\ -1}k\suchthat k\in\Re}$
      \partsitem $\colvec[r]{-3 \\ 3 \\ 4}$, 
             $\set{\colvec[r]{1 \\ -1 \\ 2}k\suchthat k\in\Re}$
      \partsitem $\colvec[r]{-3 \\ 3 \\ 4}$, 
             $\set{\colvec[r]{1 \\ -1 \\ 2}k+\colvec[r]{0 \\ 0 \\ 2}m
                \suchthat k,m\in\Re}$
      \partsitem $\colvec[r]{1 \\ 4 \\ 14}$, 
             $\set{\colvec[r]{2 \\ 2 \\ 5}k+\colvec[r]{-1 \\ 0 \\ 2}m
                \suchthat k,m\in\Re}$
      \partsitem $\colvec[r]{1 \\ 4 \\ 6}$, 
             $\set{\colvec[r]{2 \\ 2 \\ 5}k+\colvec[r]{-1 \\ 0 \\ 2}m
                \suchthat k,m\in\Re}$
    \end{exparts}
    \begin{answer}
      \begin{exparts}
        \partsitem No.
        \partsitem Yes.
        \partsitem No.
        \partsitem Yes.
        \partsitem Yes; use Gauss's Method to get $k=4$ and $m=-3$.
        \partsitem No; use Gauss's Method to conclude that there is no solution.
      \end{exparts}
    \end{answer}
  \item 
     Produce two descriptions of this set that are different than this one. 
     \begin{equation*}
       \set{\colvec[r]{2 \\ -5}k\suchthat k\in\Re}
     \end{equation*}
     \begin{answer}
       One easy thing to do is to double and triple the vector:
       \begin{equation*}
         \set{\colvec[r]{4 \\ -10}k\suchthat k\in\Re}
         \quad\text{and}\quad
         \set{\colvec[r]{6 \\ -55}k\suchthat k\in\Re}.
       \end{equation*}
      \end{answer}
  \recommended \item 
    Show that the three descriptions given at the start of this
    subsection all describe the same set.
    \begin{answer}
      Instead of showing all three equalities, we can show that the first
      equals the second, and that the second equals the third.
      Both equalities are easy, using the methods of this subsection.
    \end{answer}
  \recommended \item 
    Show that these sets are equal
    \begin{equation*}
      \set{\colvec[r]{1 \\ 4 \\ 1 \\ 1}
           +\colvec[r]{-1 \\ 0 \\ 1 \\ 0}z\suchthat z\in\Re  }
      \quad\text{and}\quad
      \set{\colvec[r]{0 \\ 4 \\ 2 \\ 1}
           +\colvec[r]{-1 \\ 0 \\ 1 \\ 0}k\suchthat k\in\Re  },
    \end{equation*}
    and that both describe the solution set of this system.
    \begin{equation*}  
       \begin{linsys}{4}
         x  &-  &y  &+  &z  &+  &w  &=  &-1  \\
            &   &y  &   &   &-  &w  &=  &3   \\
         x  &   &   &+  &z  &+  &2w &=  &4
       \end{linsys}
    \end{equation*}
    \begin{answer}
      That system reduces like this:
      \begin{align*}
         &\grstep{-\rho_1+\rho_2}
         \begin{linsys}{4}
           x  &-  &y  &+  &z  &+  &w  &=  &-1  \\
              &   &y  &   &   &-  &w  &=  &3   \\
              &   &y  &   &   &+  &w  &=  &5   
           \end{linsys}                              \\
         &\grstep{-\rho_2+\rho_3}
         \begin{linsys}{4}
           x  &-  &y  &+  &z  &+  &w  &=  &-1  \\
              &   &y  &   &   &-  &w  &=  &3   \\
              &   &   &   &   &   &2w &=  &2   
          \end{linsys}
      \end{align*}
      showing that \( w=1 \), \( y=4 \) and \( x=2-z \).   
    \end{answer}
  \recommended \item 
    Decide if the sets are equal.
    \begin{exparts}
      \partsitem \( \set{\colvec[r]{1 \\ 2}
                        +\colvec[r]{0 \\ 3}t
                     \suchthat t\in\Re} \)
            and
            \( \set{\colvec[r]{1 \\ 8}
                        +\colvec[r]{0 \\ -1}s
                     \suchthat s\in\Re} \)
      \partsitem \( \set{\colvec[r]{1 \\ 3 \\ 1}t
                        +\colvec[r]{2 \\ 1 \\ 5}s
                     \suchthat t,s\in\Re} \)
            and
            \( \set{\colvec[r]{4 \\ 7 \\ 7}m
                        +\colvec[r]{-4 \\ -2 \\ -10}n
                     \suchthat m,n\in\Re} \)
      \partsitem \( \set{\colvec[r]{1 \\ 2}t
                     \suchthat t\in\Re} \)
            and
            \( \set{\colvec[r]{2 \\ 4}m
                        +\colvec[r]{4 \\ 8}n
                     \suchthat m,n\in\Re} \)
      \partsitem \( \set{\colvec[r]{1 \\ 0 \\ 2}s
                        +\colvec[r]{-1 \\ 1 \\ 0}t
                     \suchthat s,t\in\Re} \)
            and
            \( \set{\colvec[r]{-1 \\ 1 \\ 1}m
                        +\colvec[r]{0 \\ 1 \\ 3}n
                     \suchthat m,n\in\Re} \)
      \partsitem \( \set{\colvec[r]{1 \\ 3 \\ 1}t
                        +\colvec[r]{2 \\ 4 \\ 6}s
                     \suchthat t,s\in\Re} \)
            and
            \( \set{\colvec[r]{3 \\ 7 \\ 7}t
                        +\colvec[r]{1 \\ 3 \\ 1}s
                     \suchthat t,s\in\Re} \)
    \end{exparts}
    \begin{answer}
      For each item, we call the first set \( S_1 \) and the
      other \( S_2 \).
     \begin{exparts}
      \partsitem They are equal.

        To see that \( S_1\subseteq S_2 \), we must show that any
        element of the
        first set is in the second, that is, for any vector of the form
        \begin{equation*}
          \vec{v}=\colvec[r]{1 \\ 2}
                  +\colvec[r]{0 \\ 3}t
        \end{equation*}
        there is an appropriate \( s \) such that
        \begin{equation*}
          \vec{v}=\colvec[r]{1 \\ 8}
                  +\colvec[r]{0 \\ -1}s.
        \end{equation*}
        Restated, given \( t \) we must find \( s \) so that this holds.
        \begin{equation*}
          \begin{linsys}{2}
            1  &+  &0s  &=  &1+0t\hfill  \\
            8  &-  &1s  &=  &2+3t\hfill  
          \end{linsys}
        \end{equation*}
        That system reduces to
        \begin{equation*}
          \begin{linsys}{1}
            1  &= &1 \hfill \\
            s  &= &6-3t
          \end{linsys}
        \end{equation*}
        That is,
        \begin{equation*}
          \colvec[r]{1 \\ 2}
          +\colvec[r]{0 \\ 3}t
          =\colvec[r]{1 \\ 8}
          +\colvec[r]{0 \\ -1}(6-3t)
        \end{equation*}
        and so we can state any vector in the form for \( S_1 \) can 
        also in the form
        needed for inclusion in \( S_2 \).

        For \( S_2\subseteq S_1 \), we look for \( t \) so that
        these equations hold.
        \begin{equation*}
          \begin{linsys}{2}
            1  &+  &0t  &=  &1+0s\hfill  \\
            2  &+  &3t  &=  &8-1s\hfill  
          \end{linsys}
        \end{equation*}
        Rewrite that as
        \begin{equation*}
          \begin{linsys}{1}
            1 &= &1\hfill   \\
            t &= &2-(1/3)s
          \end{linsys}
        \end{equation*}
        and so
        \begin{equation*}
          \colvec[r]{1 \\ 8}
          +\colvec[r]{0 \\ -1}s
          =\colvec[r]{1 \\ 2}
          +\colvec[r]{0 \\ 3}(2-(1/3)s).
        \end{equation*}
      \partsitem These two are equal.

        To show that \( S_1\subseteq S_2 \), we check that for any \( t,s \)
        we can find an appropriate \( m,n \) so that these hold.
        \begin{equation*}
          \begin{linsys}{2}
           4m  &-  &4n   &=  &1t+2s\hfill  \\
           7m  &-  &2n   &=  &3t+1s\hfill  \\
           7m  &-  &10n  &=  &1t+5s\hfill  
          \end{linsys}
        \end{equation*}
        Use Gauss's Method
        \begin{align*}
          \begin{amat}{2}
            4  &-4  &1t+2s  \\
            7  &-2  &3t+1s  \\
            7  &-10 &1t+5s
          \end{amat}
          &\grstep[(-7/4)\rho_1+\rho_3]{(-7/4)\rho_1+\rho_2}
          \begin{amat}{2}
            4  &-4  &1t+2s           \\
            0  &5   &(5/4)t-(10/4)s  \\
            0  &-3  &-(3/4)t+(6/4)s
          \end{amat}                              \\
          &\grstep{(3/5)\rho_2+\rho_3}
          \begin{amat}{2}
            4  &-4  &1t+2s           \\
            0  &5   &(5/4)t-(10/4)s  \\
            0  &0   &0
          \end{amat}
        \end{align*}
        to conclude that
        \begin{equation*}
          \colvec[r]{1 \\ 3 \\ 1}t
          +\colvec[r]{2 \\ 1 \\ 5}s
          =\colvec[r]{4 \\ 7 \\ 7}((1/2)t)
          +\colvec[r]{-4 \\ -2 \\ -10}((1/4)t-(1/2)s)
        \end{equation*}
        and so \( S_1\subseteq S_2 \).

        For \( S_2\subseteq S_1 \), solve
        \begin{equation*}
          \begin{linsys}{2}
           1t  &+  &2s   &=  &4m-4n\hfill  \\
           3t  &+  &1s   &=  &7m-2n\hfill  \\
           1t  &+  &5s   &=  &7m-10n\hfill  
          \end{linsys}
        \end{equation*}
        with Gaussian reduction
        \begin{align*}
          \begin{amat}{2}
            1  &2   &4m-4n  \\
            3  &1   &7m-2n  \\
            1  &5   &7m-10n
          \end{amat}
          &\grstep[-\rho_1+\rho_3]{-3\rho_1+\rho_2}
          \begin{amat}{2}
            1  &2   &4m-4n  \\
            0  &-5  &-5m+10n\\
            0  &3   &3m-6n
          \end{amat}                                    \\
          &\grstep{(3/5)\rho_2+\rho_3}
          \begin{amat}{2}
            1  &2   &4m-4n  \\
            0  &-5  &-5m+10n\\
            0  &0   &0
          \end{amat}
        \end{align*}
        to get
        \begin{equation*}
          \colvec[r]{4 \\ 7 \\ 7}m
          +\colvec[r]{-4 \\ -2 \\ -10}n
          =\colvec[r]{1 \\ 3 \\ 1}(2m)
          +\colvec[r]{2 \\ 1 \\ 5}(m-2n)
        \end{equation*}
        and so we can express any member of \( S_2 \) in the form needed for
        \( S_1 \).
      \partsitem These sets are equal.

        To prove that \( S_1\subseteq S_2 \), we must be able to solve
        \begin{equation*}
          \begin{linsys}{2}
           2m  &+  &4n  &=  &1t\hfill  \\
           4m  &+  &8n  &=  &2t\hfill  
          \end{linsys}
        \end{equation*}
        for \( m \) and \( n \) in terms of \( t \).
        Apply Gaussian  reduction
        \begin{equation*}
          \begin{amat}{2}
            2  &4   &1t  \\
            4  &8   &2t
          \end{amat}
          \onegrstep{-2\rho_1+\rho_2}
          \begin{amat}{2}
            2  &4   &1t  \\
            0  &0   &0
          \end{amat}
        \end{equation*}
        to conclude that
        any pair \( m,n \) where \( 2m+4n=t \) will do.
        For instance,
        \begin{equation*}
          \colvec[r]{1 \\ 2}t
          =\colvec[r]{2 \\ 4}((1/2)t)
          +\colvec[r]{4 \\ 8}(0)
        \end{equation*}
        or
        \begin{equation*}
          \colvec[r]{1 \\ 2}t
          =\colvec[r]{2 \\ 4}((-3/2)t)
          +\colvec[r]{4 \\ 8}(t).
        \end{equation*}
        Thus \( S_1\subseteq S_2 \).

        For \( S_2\subseteq S_1 \), we solve
        \begin{equation*}
          \begin{linsys}{2}
           1t  &=  &2m+4n\hfill  \\
           2t  &=  &4m+8n\hfill  
          \end{linsys}
        \end{equation*}
        with Gauss's Method
        \begin{equation*}
          \begin{amat}{1}
            1  &2m+4n  \\
            2  &4m+8n
          \end{amat}
          \grstep{-2\rho_1+\rho_2}
          \begin{amat}{1}
            1  &2m+4n  \\
            0  &0
          \end{amat}
        \end{equation*}
        to deduce that any vector in \( S_2 \) is also in \( S_1 \).
        \begin{equation*}
          \colvec[r]{2 \\ 4}m
          +\colvec[r]{4 \\ 8}n
          =\colvec[r]{1 \\ 2}(2m+4n)\in S_1.
        \end{equation*}
      \partsitem Neither set is a subset of the other.

        For \( S_1\subseteq S_2 \) to hold we must be able to solve
        \begin{equation*}
          \begin{linsys}{2}
          -1m  &+  &0n   &=  &1s-1t\hfill  \\
           1m  &+  &1n   &=  &0s+1t\hfill  \\
           1m  &+  &3n   &=  &2s+0t\hfill  
          \end{linsys}
        \end{equation*}
        for \( m \) and \( n \) in terms of \( t \) and \( s \).
        Gauss's Method
        \begin{align*}
          \begin{amat}{2}
           -1  &0   &1s-1t  \\
            1  &1   &0s+1t  \\
            1  &3   &2s+0t
          \end{amat}
          &\grstep[\rho_1+\rho_3]{\rho_1+\rho_2}
          \begin{amat}{2}
           -1  &0   &1s-1t  \\
            0  &1   &1s+0t  \\
            0  &3   &3s-1t
          \end{amat}                        \\
          &\grstep{-3\rho_2+\rho_3}
          \begin{amat}{2}
           -1  &0   &1s-1t  \\
            0  &1   &1s+0t  \\
            0  &3   &0s-1t
          \end{amat}
        \end{align*}
        shows that we can only find an appropriate pair \( m,n \) when
        \( t=0 \).
        That is,
        \begin{equation*}
          \colvec[r]{-1 \\ 1 \\ 0}
        \end{equation*}
        has no expression of the form
        \begin{equation*}
           \colvec[r]{-1 \\ 1 \\ 1}m+\colvec[r]{0 \\ 1 \\ 3}n.
        \end{equation*}

        Having shown that \( S_1 \) is not a subset of \( S_2 \), we know
        \( S_1\neq S_2 \) so, strictly speaking, we need not go further.
        But we shall also show that \( S_2 \) is not a subset of \( S_1 \).

        For \( S_2\subseteq S_1 \) to hold, we must be able to solve
        \begin{equation*}
          \begin{linsys}{2}
           1s  &-  &1t   &=  &-1m+0n\hfill  \\
           0s  &+  &1t   &=  &1m+1n\hfill  \\
           2s  &+  &0t   &=  &1m+3n\hfill  
          \end{linsys}
        \end{equation*}
        for \( s \) and \( t \).
        Apply row reduction
        \begin{align*}
          \begin{amat}{2}
            1  &-1  &-1m+0n  \\
            0  &1   &1m+1n  \\
            2  &0   &1m+3n
          \end{amat}
          &\grstep{-2\rho_1+\rho_3}
          \begin{amat}{2}
            1  &-1  &-1m+0n  \\
            0  &1   &1m+1n  \\
            0  &2   &3m+3n
          \end{amat}                                    \\
          &\grstep{-2\rho_2+\rho_3}
          \begin{amat}{2}
            1  &-1  &-1m+0n  \\
            0  &1   &1m+1n  \\
            0  &0   &1m+1n
          \end{amat}
        \end{align*}
        to deduce that the only vectors from \( S_2 \) that are also in
        \( S_1 \) are of the form
        \begin{equation*}
          \colvec[r]{-1 \\ 1 \\ 1}m
          +\colvec[r]{0 \\ 1 \\ 3}(-m).
        \end{equation*}
        For instance,
        \begin{equation*}
          \colvec{-1 \\ 1 \\ 1}
        \end{equation*}
        is in \( S_2 \) but not in \( S_1 \).
      \partsitem These sets are equal.

        First we change the parameters:
        \begin{equation*}
          S_2=\set{\colvec[r]{3 \\ 7 \\ 7}m
                   +\colvec[r]{1 \\ 3 \\ 1}n
                   \suchthat m,n\in\Re}.
        \end{equation*}

        Now, to show that \( S_1\subseteq S_2 \), we solve
        \begin{equation*}
          \begin{linsys}{2}
           3m  &+  &1n   &=  &1t+2s\hfill  \\
           7m  &+  &3n   &=  &3t+4s\hfill  \\
           7m  &+  &1n   &=  &1t+6s\hfill  
          \end{linsys}
        \end{equation*}
        with Gauss's Method
        \begin{align*}
          \begin{amat}{2}
            3  &1   &1t+2s  \\
            7  &3   &3t+4s  \\
            7  &1   &1t+6s
          \end{amat}
          &\grstep[(-7/3)\rho_1+\rho_3]{(-7/3)\rho_1+\rho_2}
          \begin{amat}{2}
            3  &1    &1t+2s  \\
            0  &2/3  &(2/3)t-(2/3)s  \\
            0  &-4/3 &(-4/3)t+(4/3)s
          \end{amat}                                    \\
          &\grstep{2\rho_2+\rho_3}
          \begin{amat}{2}
            3  &1    &1t+2s  \\
            0  &2/3  &(2/3)t-(2/3)s  \\
            0  &0    &0
          \end{amat}
        \end{align*}
        to get that
        \begin{equation*}
          \colvec[r]{1 \\ 3 \\ 1}t
          +\colvec[r]{2 \\ 4 \\ 6}s
          =\colvec[r]{3 \\ 7 \\ 7}(s)
          +\colvec[r]{1 \\ 3 \\ 1}(t-s)
        \end{equation*}
        and so \( S_1\subseteq S_2 \).

        The proof that \( S_2\subseteq S_1 \) involves solving
        \begin{equation*}
          \begin{linsys}{2}
           1t  &+  &2s   &=  &3m+1n\hfill  \\
           3t  &+  &4s   &=  &7m+3n\hfill  \\
           1t  &+  &6s   &=  &7m+1n\hfill  
          \end{linsys}
        \end{equation*}
        with Gaussian reduction
        \begin{align*}
          \begin{amat}{2}
            1  &2   &3m+1n  \\
            3  &4   &7m+3n  \\
            1  &6   &7m+1n
          \end{amat}
          &\grstep[-\rho_1+\rho_3]{-3\rho_1+\rho_2}
          \begin{amat}{2}
            1  &2   &3m+1n  \\
            0  &-2  &-2m    \\
            0  &4   &4m
          \end{amat}                                \\
          &\grstep{2\rho_2+\rho_3}
          \begin{amat}{2}
            1  &2   &3m+1n  \\
            0  &-2  &-2m    \\
            0  &0   &0
          \end{amat}
        \end{align*}
        to conclude
        \begin{equation*}
          \colvec[r]{3 \\ 7 \\ 7}m
          +\colvec[r]{1 \\ 3 \\ 1}n
          =\colvec[r]{1 \\ 3 \\ 1}(m+n)
          +\colvec[r]{2 \\ 4 \\ 6}(m)
        \end{equation*}
        and so any vector in \( S_2 \) is also in \( S_1 \).
    \end{exparts}  
   \end{answer}
\end{exercises}