\section{Solution Sets for Systems of Linear Equations }

For a system of equations with $r$ equations and $k$ unknowns, one can have a number of different outcomes.  For the sake of visualization, consider the case of $r$ equations in three variables.  Geometrically, then, each of our equations is the equation of a plane in three-dimensional space.  To find solutions to the system of equations, we look for the common intersection of the planes (if an intersection exists).  Here we have five different possibilities:

\begin{enumerate}
\item \textbf{No solutions.}  Some of the equations are contradictory, so no solutions exist.

\item \textbf{Unique Solution.}  The planes have a unique point of intersection.

\item \textbf{Line.}  The planes intersect in a common line; any point on that line then gives a solution to the system of equations.

\item \textbf{Plane.}  Perhaps you only had one equation to begin with, or else all of the equations coincide geometrically.  In this case, you have a plane of solutions, with two free parameters.

\item \textbf{All of $\mathbb{R}^3$.}  If you start with no information, then any point in $\mathbb{R}^3$ is a solution.  There are three free parameters.
\end{enumerate}

In general, for systems of equations with $k$ unknowns, there are $k+2$ possible outcomes, corresponding to the number of free parameters in the solutions set, plus the possibility of no solutions.  These types of ``solution sets''\index{Solution set} are hard to visualize, but luckily ``hyperplanes''\index{Hyperplane}  behave like planes in $\mathbb{R}^3$ in many ways.

\subsection{Non-Leading Variables}

Variables that are not a pivot in the reduced row echelon form of a linear system are \emph{free}.  Se set them equal to arbitrary parameters $\mu_1, \mu_2, \ldots$.

\begin{example}
$\begin{amatrix}{4} 
1 &  0 & 1 & -1 & 1\\ 
 0 & 1 & -1& 1  & -1\\
 0 &0   & 0  & 0   &0 \\
\end{amatrix}$
Here, $x_1$ and $x_2$ are the pivot variables and $x_3$ and $x_4$ are non-leading variables\index{Non-leading variables}, and thus free.  The solutions are then of the form $x_3=\mu_1$, $x_4=\mu_2$, $x_2=1 + \mu_1 - \mu_2$, $x_1=1-\mu_1+\mu_2$.

The preferred way to write a solution set is with set notation\index{Solution set!set notation}.  Let $S$ be the set of solutions to the system.  Then:

\[S = \{\colvec{x_1\\x_2\\x_3\\x_4} = \colvec{1\\1\\ 0\\0 } + \mu_1 \colvec{1\\-1\\ 0 \\1 } + \mu_2 \colvec{-1\\1\\1\\0 } \} \]
\end{example}
It's worth noting that if we knew how to multiply matrices of any size, we could write the previous system as $MX=V$, where

\[M=    \begin{pmatrix}
      1  & 0  & 1 & -1  \\
       0  & 1 & -1 & 1  \\
        0 &0   & 0  & 0    \\
    \end{pmatrix}, \qquad
X= \colvec{x_1\\x_2\\x_3\\x_4}, \qquad V=\colvec{1\\-1\\0 \\ }
\]
Given two vectors we can \emph{add} them term-by-term:

\[
\colvec{a^1\\a^2\\a^3\\ \vdots \\ a^r} + \colvec{b^1\\b^2\\b^3\\ \vdots \\ b^r} = \colvec{a^1+b^1\\a^2+b^2\\a^3+b^3\\ \vdots \\ a^r+b^r}
\]
We can also multiply a vector by a scalar, like so:

\[
\lambda \colvec{a^1\\a^2\\a^3\\ \vdots \\ a^r} = \colvec{\lambda a^1\\\lambda a^2\\\lambda a^3\\ \vdots \\ \lambda a^r}
\]
Then yet another way to write the solution set for the example is:

\[X= X_0 + \mu_1 Y_1 + \mu_2 Y_2 \]
where 

\[X_0= \colvec{1\\1\\0 \\0 }, Y_1= \colvec{1\\-1\\0 \\1 }, Y_2= \colvec{-1\\1\\1\\0 }
\]

\begin{definition} Let $X$ and $Y$ by vectors and $\alpha$ and $\beta$ be scalars.  A function $f$ is \emph{linear}\index{Linear!function} if 
\[f(\alpha X + \beta Y) = \alpha f(X) + \beta f(Y) \]
This is called the {\it linearity property}\index{Linearity property} for matrix multiplication. 
\end{definition}
Soon we'll show that matrix multiplication is linear.  Then we will know that:

\[M(\alpha X + \beta Y) = \alpha MX + \beta MY\]
Then the two equations 
$MX=V$ and $X= X_0 + \mu_1 Y_1 + \mu_2 Y_2$ together say that:

\[ MX_0 + \mu_1MY_1 + \mu_2MY_2 = V \]
for \emph{any} $\mu_1, \mu_2 \in \mathbb{R}$.
Choosing $\mu_1=\mu_2=0$, we obtain $$MX_0=V\, .$$  
Here, $X_0$ is an example of what is called a  \emph{particular solution}\index{Particular solution!an example} to the system.

Given the particular solution to the system, we can then deduce that $\mu_1MY_1 + \mu_2MY_2 = 0$.  
Setting $\mu_1=0, \mu_2=1$, and recalling the particular solution $MX_0=V$, we obtain $$MY_1=0\, .$$ 
Likewise, setting $\mu_1=1, \mu_2=0$, we obtain $$MY_2=0\, .$$
Here $Y_1$ and $Y_2$ are examples of what are called  \emph{homogeneous} solutions\index{Homogeneous solution!an example} to the system.
They {\it do not} solve the original equation $MX=V$, but instead its associated homogeneous system of equations $M Y =0$.

\begin{example}
Consider the linear system with the augmented matrix we've been working with.

    \begin{equation*}
      \begin{linsys}{2}
            x  &  \phantom{+y}   & +z  & -w =  & 1  \\[1mm]
               &  y & - z   & +w=  & 1\\
      \end{linsys}
    \end{equation*}
Recall that the system has the following solution set:

\[S = \{\colvec{x_1\\x_2\\x_3\\x_4} = \colvec{1\\1\\0 \\0 } + \mu_1 \colvec{1\\-1\\ 0\\1 } + \mu_2 \colvec{-1\\1\\1\\0 } \} \]
Then $MX_0=V$ says that $\colvec{x_1\\x_2\\x_3\\x_4} = 
\colvec{1\\1\\0 \\ 0}$ solves the original system of equations, which is certainly true, but this is not the only solution.

$MY_1=0$ says that $\colvec{x_1\\x_2\\x_3\\x_4} = 
\colvec{1\\-1\\0 \\1}$ solves the homogeneous system.

$MY_2=0$ says that $\colvec{x_1\\x_2\\x_3\\x_4} = 
\colvec{-1\\1\\1\\ 0}$ solves the homogeneous system.

\noindent
Notice how adding any multiple of a homogeneous solution to the particular solution yields another particular solution.

\end{example}

\begin{definition}
Let $M$ a matrix and $V$ a vector.  Given the linear system $MX=V$, we call $X_0$ a \emph{particular solution}\index{Particular solution} if $MX_0=V$.  We call $Y$ a \emph{homogeneous solution} if $MY=0$.  
The linear system 
$$MX=0$$ is called the (associated) \emph{homogeneous system}\index{Homogeneous system}.
\end{definition}

If $X_0$ is a particular solution, then the general solution\index{General solution} to the system is:

\[S= \{X_0+Y : MY=0 \} \]
In other words, the general solution $=$ particular $+$ homogeneous.

\section*{References}

Hefferon, Chapter One, Section I.2

Wikipedia, \href{http://en.wikipedia.org/wiki/System_of_linear_equations}{Systems of Linear Equations}

\section*{Review Questions}

\begin{enumerate}
\item Write down examples of augmented matrices corresponding to each of the five types of solution sets for systems of equations with three unknowns.

\item Let 

\[ M = \begin{pmatrix}
      a^1_1 & a^1_2  & \ldots & a^1_k  \\
      a^2_1 & a^2_2  & \ldots & a^2_k  \\
      \vdots & \vdots  &     & \vdots  \\
      a^r_1 & a^r_2  & \ldots & a^r_k  \\
    \end{pmatrix}, \qquad X=\colvec{x^1\\x^2\\ \ldots \\x^k}
\]

Propose a rule for $MX$ so that $MX=0$ is equivalent to the linear system: 
    \begin{equation*}
      \begin{linsys}{2}
            a^1_1 x^1  & + a^1_2 x^2  & \ldots  & + a^1_k x^k  & =0  \\
            a^2_1 x^1  & + a^2_2 x^2  & \ldots  & + a^2_k x^k  & =0  \\
	    \vdots     & \vdots       &         & \vdots       & \vdots\\
            a^r_1 x^1  & + a^r_2 x^2  & \ldots  & + a^r_k x^k  & =0  \\
      \end{linsys}
    \end{equation*}

Does your rule for multiplying a matrix times a vector obey the linearity property?  Prove it!

\item  The \emph{standard basis vector} $e_i$ is a column vector with a one in the $i$th row, and zeroes everywhere else.  Using the rule for multiplying a matrix times a vector in the last problem, find a simple rule for multiplying $Me_i$, where $M$ is the general matrix defined in the last problem.

\end{enumerate}




\newpage
