

\section{Linear Independence }

Consider a plane $P$ that includes the origin in $\Re^3$ and a collection $\{u,v,w\}$ of non-zero vectors in $P$.  If no two of $u, v$ and $w$ are parallel, then certainly $P=\spa \{u,v,w\}$.  But any two vectors determines a plane, so we should be able to span the plane using only two vectors.  Then we could choose two of the vectors in $\{u,v,w\}$ whose span is $P$, and express the other as a linear combination of those two.  Suppose $u$ and $v$ span $P$.  Then there exist constants $d^1, d^2$ (not both zero) such that
$w=d^1u+d^2v$.  Since $w$ can be expressed in terms of $u$ and $v$ we say that it is not independent.
More generally, the relationship
\[
c^1u+c^2v+c^3w=0 \qquad c^i \in \Re, \text{ some $c^i\neq 0$}
\]
expresses the fact that $u,v,w$ are not all independent.

\begin{definition}
We say that the vectors $v_1, v_2, \ldots, v_n$ are \emph{linearly dependent}\index{Linearly dependent} if there exist constants $c^1, c^2, \ldots, c^n$ not all zero such that
\[
c^1v_1 + c^2v_2+ \ldots +c^nv_n=0.
\]
Otherwise, the vectors $v_1, v_2, \ldots, v_n$ are \emph{linearly independent.}\index{Linearly independent} 
\end{definition}


\begin{example}
Consider the following vectors in $\Re^3$:
\[
v_1=\colvec{0\\0\\1}, 
\qquad v_2=\colvec{1\\2\\1},
\qquad v_3=\colvec{1\\2\\3}.
\]
Are they linearly independent?

We need to see whether the system 
\[
c^1v_1 + c^2v_2+ c^3v_3=0.
\]
has any solutions for $c^1, c^2, c^3$.  We can rewrite this as a homogeneous system:
\[
\rowvec{v_1&v_2&v_3}\colvec{c^1\\c^2\\c^3}=0.
\]
This system has solutions if and only if the matrix $M=\rowvec{v_1&v_2&v_3}$ is singular, so we should find the determinant of $M$:
\[
\det M = \det \begin{pmatrix}
0 & 1 & 1 \\
0 & 2 & 2 \\
1 & 1 & 3 \\
\end{pmatrix}
= \det \begin{pmatrix}
1 & 1 \\
2 & 2 \\
\end{pmatrix}
=0.
\]

Therefore nontrivial solutions exist.  At this point we know that the vectors are linearly dependent.  If we need to, we can find coefficients that demonstrate linear independence by solving the system of equations:
\[
\begin{amatrix}{3}
0 & 1 & 1 & 0\\
0 & 2 & 2 & 0\\
1 & 1 & 3 & 0\\
\end{amatrix} \sim
\begin{amatrix}{3}
1 & 1 & 3 & 0\\
0 & 1 & 1 & 0\\
0 & 0 & 0 & 0\\
\end{amatrix} \sim
\begin{amatrix}{3}
1 & 0 & 2 & 0\\
0 & 1 & 1 & 0\\
0 & 0 & 0 & 0\\
\end{amatrix}.
\]
Then $c^3=\mu$, $c^2=-\mu$, and $c^3=-2\mu$.  Now any choice of $\mu$ will produce coefficients $c^1,c^2,c^3$ that satisfy the linear equation.  So we can set $\mu=1$ and obtain: 
\[
c^1v_1 + c^2v_2+ c^3v_3=0 
\Rightarrow -2v_1 - v_2 + v_3=0.
\]
\end{example}


\begin{theorem}[Linear Dependence]\index{Linear dependence theorem}
A set of non-zero vectors $\{ v_1, \ldots, v_n \}$ is linearly dependent if and only if one of the vectors $v_k$ is expressible as a linear combination of the preceeding vectors.
\end{theorem}

\begin{proof}
The theorem is an if and only if statement, so there are two things to show.

\begin{itemize}
\item[$i.$]  First, we show that if $v_k=c^1v_1+\ldots c^{k-1}v_{k-1}$ then the set is linearly dependent.

This is easy.  We just rewrite the assumption:
\[
c^1v_1+\ldots c^{k-1}v_{k-1}-v_k + 0v_{k+1}+\ldots +0v_n=0.
\]
This is a vanishing linear combination of the vectors $\{ v_1, \ldots, v_n \}$ with not all coefficients equal to zero, so $\{ v_1, \ldots, v_n \}$ is a linearly dependent set.
 
\item[$ii.$]  Now, we show that linear dependence implies that there exists $k$ for which $v_k$ is a linear combination of the vectors $\{ v_1, \ldots, v_{k-1} \}$.

The assumption says that
\[
c^1v_1 + c^2v_2+ \ldots +c^nv_n=0.
\]
Take $k$ to be the largest number for which $c_k$ is not equal to zero.  So:
\[
c^1v_1 + c^2v_2+ \ldots +c^{k-1}v_{k-1}+c^kv_k=0.
\]

(Note that $k>1$, since otherwise we would have $c^1v_1=0\Rightarrow v_1=0$, contradicting the assumption that none of the $v_i$ are the zero vector.)

As such, we can rearrange the equation:
\begin{eqnarray*}
c^1v_1 + c^2v_2+ \ldots +c^{k-1}v_{k-1}&=&-c^kv_k\\ \Rightarrow\ 
-\frac{c^1}{c^k}v_1 - \frac{c^2}{c^k}v_2 - \ldots -\frac{c^{k-1}}{c^k}v_{k-1}&=&v_k.
\end{eqnarray*}

Therefore we have expressed $v_k$ as a linear combination of the previous vectors, and we are done.
\end{itemize}
\end{proof}


\begin{example}
Consider the vector space $P_2(t)$ of polynomials of degree less than or equal to $2$.  Set:
\begin{eqnarray*}
v_1 &=& 1+t \\
v_2 &=& 1+t^2 \\
v_3 &=& t+t^2 \\
v_4 &=& 2+t+t^2 \\
v_5 &=& 1+t+t^2. \\
\end{eqnarray*}
The set $\{ v_1, \ldots, v_5 \}$ is linearly dependent, because $v_4 = v_1+v_2$.  

Now suppose vectors 
$v_1,\ldots, v_n$ are linearly dependent, 
\[
c^1v_1 + c^2v_2+ \ldots +c^nv_n=0
\]
with $c^1\neq 0$.  Then:
\[
\spa \{v_1,\ldots, v_n\} = \spa \{ v_2,\ldots, v_n\}
\]
because any $x\in \spa \{v_1,\ldots, v_n\}$ is given by
\begin{eqnarray*}
x &=& a^1v_1 + \ldots a^nv_n \\
&=& a^1( -\frac{c^2}{c_1}v_2- \ldots -\frac{c^n}{c_1}v_n ) + a^2v_2 + \ldots + a^nv_n \\
&=& (a^2-a^1\frac{c^2}{c_1})v_2 + \ldots + (a^n-a^1\frac{c^n}{c_1})v_n.
\end{eqnarray*}
Then $x$ is in $\spa \{v_2,\ldots, v_n\}$.
\end{example}


When we write a vector space as the span of a list of vectors, we would like that list to be as short as possible.
This can be achieved by iterating the above procedure.

\begin{example}
In the above example, we found that $v_4=v_1+v_2$.  In this case, any expression for a vector as a linear combination involving $v_4$ can be turned into a combination without $v_4$ by making the substitution $v_4=v_1+v_2$.

Then:
\begin{eqnarray*}
S &=& \spa \{ 1+t , 1+t^2, t+t^2, 2+t+t^2, 1+t+t^2 \} \\
&=& \spa \{ 1+t , 1+t^2, t+t^2, 1+t+t^2 \}.
\end{eqnarray*}
Now we notice that $1+t+t^2=\frac{1}{2}(1+t) +\frac{1}{2}(1+t^2) + \frac{1}{2}(t+t^2)$.  So the vector $1+t+t^2=v_5$ is also extraneous, since it can be expressed as a linear combination of the remaining three vectors, $v_1, v_2,v_3$.  Therefore 
\[
S = \spa \{ 1+t , 1+t^2, t+t^2 \}.
\]

In fact, you can check that there are no (non-zero) solutions to the linear system
\[
c^1(1+t) + c^2(1+t^2) + c^3(t+t^2)=0.
\]
Therefore the remaining vectors $\{ 1+t , 1+t^2, t+t^2 \}$ are linearly independent, and span the vector space $S$.  Then these vectors are a minimal spanning set\index{Minimal spanning set}, in the sense that no more vectors can be removed since the vectors are linearly independent.
Such a set is called a \emph{basis}\index{Basis!example of} for $S$.
\end{example}




\begin{example}
Let $B^3$ be the space of $3\times 1$ bit-valued matrices (i.e., column vectors).  Is the following subset linearly independent?
\[
\left\{ \colvec{1\\1\\0}, \colvec{1\\0\\1}, 
\colvec{0\\1\\1} \right\}
\]

If the set is linearly dependent, then we can find non-zero solutions to the system:
\[
c^1\colvec{1\\1\\0}+ c^2 \colvec{1\\0\\1} 
+c^3 \colvec{0\\1\\1}=0,
\]
which becomes the linear system
\[
\begin{pmatrix}
1 & 1 & 1 \\
1 & 0 & 1 \\
0 & 1 & 1 \\
\end{pmatrix}\colvec{c^1\\c^2\\c^3}=0.
\]
Solutions exist if and only if the determinant of the matrix is non-zero.  But:
\[
\det \begin{pmatrix}
1 & 1 & 1 \\
1 & 0 & 1 \\
0 & 1 & 1 \\
\end{pmatrix} = 1 \det \begin{pmatrix}
0 & 1 \\
1 & 1 \\
\end{pmatrix} -1 \det \begin{pmatrix}
1 & 0 \\
0 & 1 \\
\end{pmatrix} = -1-1=1+1=0
\]
Therefore non-trivial solutions exist, and the set is not linearly independent.

\end{example}




\section*{References}
\begin{itemize}
\item Hefferon, Chapter Two, Section II: Linear Independence
\item Hefferon, Chapter Two, Section III.1: Basis
\end{itemize}

Wikipedia:
\begin{itemize}
\item \href{http://en.wikipedia.org/wiki/Linear_independence}{Linear Independence}
\item \href{http://en.wikipedia.org/wiki/Basis_(linear_algebra)}{Basis}
\end{itemize}


\section*{Review Questions}

\begin{enumerate}
\item Let $B^n$ be the space of $n\times 1$ bit-valued matrices ({\it i.e.}, column vectors).  
\begin{itemize}
\item[$i.$] How many different vectors are there in $B^n$.
\item[$ii.$] Find a collection $S$ of vectors that span $B^3$ and are linearly independent.  In other words, find a basis of $B^3$.
\item[$iii.$] Write each other vector in $B^3$ as a linear combination of the vectors in the set $S$ that you chose.
\item[$iv.$] Would it be possible to span $B^3$ with only two vectors?
\end{itemize}

\item Let $e_i$ be the vector in $\Re^n$ with a $1$ in the $i$th position and $0$'s in every other position.  Let $v$ be an arbitrary vector in $\Re^n$.
\begin{itemize}
\item[$i.$] Prove that the collection $\{e_1, \ldots, e_n \}$ is linearly independent.
\item[$ii.$] Show that $v=\sum_{i=1}^n (v\dotprod e_i)e_i$.
\item[$iii.$] What does this say about the $\spa \{e_1, \ldots, e_n \}$?
\end{itemize}
\end{enumerate}


\newpage