\section{ Basis and Dimension }

In the last section, we established the notion of a linearly independent set of vectors in a vector space $V$, and of a set of vectors that span $V$.  We saw that any set of vectors that span $V$ can be reduced to some minimal collection of linearly independent vectors; such a set is called a \emph{basis} of the subspace $V$.  

\begin{definition}
Let $V$ be a vector space.  Then a set $S$ is a \emph{basis}\index{Basis} for $V$ if $S$ is linearly independent and $\spa S=V$.

If $S$ is a basis of $V$ and $S$ has only finitely many elements, then we say that $V$ is \emph{finite-dimensional}.  The number of vectors in $S$ is the \emph{dimension}\index{Dimension} of~$V$.
\end{definition}

Suppose $V$ is a \emph{finite-dimensional}\index{Vector space!finitedimensional} vector space, and $S$ and $T$ are two different bases for $V$.  One might worry that $S$ and $T$ have a different number of vectors; then we would have to talk about the dimension of $V$ in terms of the basis $S$ or in terms of the basis $T$.  Luckily this isn't what happens.
Later in this section, we will show that $S$ and $T$ must have the same number of vectors.  This means that the dimension of a vector space does not depend on the basis.  In fact, dimension is a very important way to characterize of any vector space $V$.

\begin{example}
$P_n(t)$ has a basis $\{1,t,\ldots , t^n \}$, since every polynomial of degree less than or equal to $n$ is a sum
\[
a^0\,1+a^1\,t+\ldots +a^n\,t^n, \qquad a^i\in \Re
\]
so $P_n(t)=\spa \{1,t,\ldots , t^n \}$.  This set of vectors is linearly independent:  If the polynomial $p(t)=c^01+c^1t+\ldots +c^nt^n=0$, then $c^0=c^1=\ldots =c^n=0$, so $p(t)$ is the zero polynomial.  

Then $P_n(t)$ is finite dimensional, and $\dim P_n(t)=n+1$.
\end{example}



\begin{theorem}
Let $S=\{v_1, \ldots, v_n \}$  be a basis for a vector space $V$.  Then every vector $w \in V$ can be written \emph{uniquely} as a linear combination of vectors in the basis $S$:
\[
w=c^1v_1+\ldots + c^nv_n.
\]
\end{theorem}

\begin{proof}
Since $S$ is a basis for $V$, then $\spa S=V$, and so there exists constants~$c^i$ such that $w=c^1v_1+\ldots + c^nv_n$.

Suppose there exists a second set of constants $d^i$ such that 
$$w=d^1v_1+\ldots + d^nv_n\, .$$  Then:
\begin{eqnarray*}
0_V&=&w-w\\
&=&c^1v_1+\ldots + c^nv_n-d^1v_1+\ldots + d^nv_n \\
&=&(c^1-d^1)v_1+\ldots + (c^n-d^n)v_n. \\
\end{eqnarray*}
If it occurs exactly once that $c^i\neq d^i$, then the equation reduces to $0=(c^i-d^i)v_i$, which is a contradiction since the vectors $v_i$ are assumed to be non-zero.

If we have more than one $i$ for which $c^i\neq d^i$, we can use this last equation to write one of the vectors in $S$ as a linear combination of other vectors in $S$, which contradicts the assumption that $S$ is linearly independent.  Then for every $i$, $c^i=d^i$.
\end{proof}


Next, we would like to establish a method for determining whether a collection of vectors forms a basis for $\Re^n$.  But first, we need to show that any two bases for a finite-dimensional vector space has the same number of vectors.

\begin{lemma}
If $S=\{v_1, \ldots, v_n \}$ is a basis for a vector space $V$ and $T=\{w_1, \ldots, w_m \}$ is a linearly independent set of vectors in $V$, then $m\leq n$.
\end{lemma}

\begin{proof}
The idea is to start with the set $S$ and replace vectors in $S$ one at a time with vectors from $T$, such that after each replacement we still have a basis for $V$.

Since $S$ spans $V$, then the set $\{w_1, v_1, \ldots, v_n \}$ is linearly dependent.  Then we can write $w_1$ as a linear combination of the $v_i$; using that equation, we can express one of the $v_i$ in terms of $w_1$ and the remaining $v_j$ with $j\neq i$.  Then we can discard one of the $v_i$ from this set to obtain a linearly independent set that still spans $V$.  Now we need to prove that $S_1$ is a basis; we need to show that $S_1$ is linearly independent and that $S_1$ spans $V$.

The set $S_1=\{w_1, v_1, \ldots, v_{i-1}, v_{i+1},\ldots, v_n \}$ is linearly independent:  By the previous theorem, there was a unique way to express $w_1$ in terms of the set $S$.  Now, to obtain a contradiction, suppose there is some $k$ and constants~$c^i$ such that
\[
v_k = c^0w_1+c^1v_1+\ldots + c^{i-1}v_{i-1} + c^{i+1}v_{i+1} + \ldots + c^nv_n.
\]
Then replacing $w_1$ with its expression in terms of the collection $S$ gives a way to express the vector $v_k$ as a linear combination of the vectors in $S$, which contradicts the linear independence of $S$.  On the other hand, we cannot express $w_1$ as a linear combination of the vectors in $\{v_j | j\neq i\}$, since the expression of $w_1$ in terms of $S$ was unique, and had a non-zero coefficient on the vector $v_i$.  Then no vector in $S_1$ can be expressed as a combination of other vectors in $S_1$, which demonstrates that $S_1$ is linearly independent.

The set $S_1$ spans $V$:  For any $u\in V$, we can express $u$ as a linear combination of vectors in $S$.  But we can express $v_i$ as a linear combination of vectors in the collection $S_1$; rewriting $v_i$ as such allows us to express $u$ as a linear combination of the vectors in $S_1$.

Then $S_1$ is a basis of $V$ with $n$ vectors.

We can now iterate this process, replacing one of the $v_i$ in $S_1$ with $w_2$, and so on.  If $m\leq n$, this process ends with the set $S_m=\{w_1,\ldots, w_m$, $v_{i_1},\ldots,v_{i_{n-m}}  \}$, which is fine.

Otherwise, we have $m>n$, and the set $S_n=\{w_1,\ldots, w_n \}$ is a basis for~$V$.  But we still have some vector 
$w_{n+1}$  in $T$ that is not in $S_n$.  Since $S_n$ is a basis, we can write $w_{n+1}$ as a combination of the vectors in $S_n$, which contradicts the linear independence of the set $T$.  Then it must be the case that $m\leq n$, as desired.
\end{proof}


\begin{corollary}
For a finite dimensional vector space $V$, any two bases for~$V$ have the same number of vectors.
\end{corollary}

\begin{proof}
Let $S$ and $T$ be two bases for $V$.  Then both are linearly independent sets that span $V$.  Suppose $S$ has $n$ vectors and $T$ has $m$ vectors.  Then by the previous lemma, we have that $m\leq n$.  But (exchanging the roles of $S$ and $T$ in application of the lemma) we also see that $n\leq m$.  Then $m=n$, as desired.
\end{proof}


\subsection{Bases in $\Re^n$.}

From one of the review questions, we know that
\[
\Re^n = \spa \left\{ \colvec{1\\0\\ \vdots \\ 0}, 
\colvec{0\\1\\ \vdots \\ 0}, \ldots, \colvec{0\\0\\ \vdots \\ 1}\right\},
\]
and that this set of vectors is linearly independent.  So this set of vectors is a basis for $\Re^n$, and $\dim \Re^n=n$.  This basis is often called the \emph{standard} or \emph{canonical basis}\index{Standard basis}\index{Canonical Basis} for $\Re^n$.  The vector with a one in the $i$th position and zeros everywhere else is written 
$e_i$.  It points in the direction of the $i$th coordinate axis, and has unit length.  In multivariable calculus classes, this basis is often written $\{ i, j, k \}$ for $\Re^3$.

\begin{remark}[Bases are not unique.]
While there exists a unique way to express a vector in terms of any particular basis, bases themselves are far from unique.
For example, both of the sets:
\[
\left\{ \colvec{1\\0}, \colvec{0\\1} \right\} \text{ and }
\left\{ \colvec{1\\1}, \colvec{1\\-1} \right\}
\]
are bases for $\Re^2$.  Rescaling any vector in one of these sets is already enough to show that~$\Re^2$ has infinitely many bases.  But even if we require that all of the basis vectors have unit length, it turns out that there are still infinitely many bases for $\Re^2$.  (See Review Question $3$.)
\end{remark}


To see whether a collection of vectors $S=\{v_1, \ldots, v_m \}$ is a basis for~$\Re^n$, we have to check that they are linearly independent and that they span~$\Re^n$.  From the previous discussion, we also know that $m$ must equal $n$, so assume~$S$ has $n$ vectors.

If $S$ is linearly independent, then there is no non-trivial solution of the equation
\[
0 = x^1v_1+\ldots + x^nv_n.
\]
Let $M$ be a matrix whose columns are the vectors $v_i$.  Then the above equation is equivalent to requiring that there is a unique solution to \[MX=0\, .\]

To see if $S$ spans $\Re^n$, we take an arbitrary vector $w$ and solve the linear system
\[
w=x^1v_1+\ldots + x^nv_n
\]
in the unknowns $c^i$.  For this, we need to find a unique solution for the linear system $MX=w$.  

Thus, we need to show that $M^{-1}$ exists, so that 
\[
X=M^{-1}w
\]
is the unique solution we desire.  Then we see that $S$ is a basis for $V$ if and only if $\det M\neq 0$.

\begin{theorem}
Let $S=\{v_1, \ldots, v_m \}$ be a collection of vectors in $\Re^n$.  Let~$M$ be the matrix whose columns are the vectors in $S$.  Then $S$ is a basis for $V$ if and only if $m$ is the dimension of $V$ and 
\[
\det M \neq 0.
\]
\end{theorem}

\begin{example}
Let 
\[
S=\{ \colvec{1\\0}, \colvec{0\\1} \} \text{ and }
T=\{ \colvec{1\\1}, \colvec{1\\-1} \}.
\]
Then set $M_S=\begin{pmatrix}
1 & 0\\
0 & 1\\
\end{pmatrix}$.  Since $\det M_S=1\neq 0$, then $S$ is a basis for $\Re^2$.

Likewise, set $M_T=\begin{pmatrix}
1 & 1\\
1 & -1\\
\end{pmatrix}$.  Since $\det M_T=-2\neq 0$, then $T$ is a basis for $\Re^2$.
\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 $S$ be a collection of vectors in a vector space $V$.  Show that if every vector $w$ in $V$ can be expressed uniquely as a linear combination of vectors in $S$, then $S$ is a basis of $V$.  (This is the converse to the theorem in the lecture.)

\item Show that the set of all linear transformations mapping 
$\Re^3\rightarrow \Re$ is itself a vector space.  Find a basis for this vector space.  Do you think your proof could be modified to work for linear transformations $\Re^n\rightarrow \Re$?

(Hint: Represent $\Re^3$ as column vectors, and argue that a linear transformation $T: \Re^3\rightarrow \Re$ is just a column vector.)

(Hint: If you are really stuck (or just curious), look up ``dual space.''  This is a big idea, though, and could just be more confusing.)

\item \begin{itemize}
\item[$i.$]  Draw the collection of all unit vectors in $\Re^2$. 
\item[$ii.$]  Let $S_x=\{ \colvec{1\\0}, x \}$, where $x$ is a unit vector in $\Re^2$.  For which $x$ is $S_x$ a basis of $\Re^2$?
\end{itemize}

\item Let $B^n$ be the vector space of column vectors with bit entries $0, 1$.  Write down every basis for $B^1$ and $B^2$.  How many bases are there for $B^3$? $B^4$?  Can you make a conjecture for the number of bases for $B^n$?

(Hint: You can build up a basis for $B^n$ by choosing one vector at a time, such that the vector you choose is not in the span of the previous vectors you've chosen.  How many vectors are in the span of any one vector?  Any two vectors?  How many vectors are in the span of any $k$ vectors, 
for $k\leq n$?)
\end{enumerate}

\newpage

