\documentstyle[12pt]{article}
\input amssym.def
\input amssym

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{DEF}[theorem]{Definition}

\newenvironment{define}{\begin{DEF}\bf}{\end{DEF}}

\newtheorem{exercise}[theorem]{Exercise}

\def\span{{\rm span}}
\def\col{{\rm col}}
\def\entry{{\rm entry}}
\def\proof{\par\noindent proof:\par }
\def\qed{\par\noindent QED\par}
\def\reals{{\Bbb R}}
\def\complex{{\Bbb C}}
\def\dim{{\rm dim}}

\begin{document}

\begin{flushright}
  A. Miller\\
  M340 \\
  April 97
\end{flushright}

\begin{center}
  Vector Spaces
\end{center}

A vector space, $V$, is a set with two operations, vector addition
(written $u+v$) and scalar multiplication (written
$av$).  The elements of
$V$ will be denoted using $u,v,w$, etc.  The formula
`$u\in V$' is short hand
for `$u$ is an element of V' or `$u$ in V' or just `$u$ is a vector'.
Vector spaces will
be written using capital letters $V,W$, etc.
Scalars are elements of some field,
which in this class is either the real numbers, $\reals$,
or the complex numbers, $\complex$.   Scalars will be written using
the letters $a,b,c$, etc.

\medskip

\centerline{{\bf Closure axioms:}}
\begin{enumerate}
\item If $u\in V$ and $v\in V$, then $u+v\in V$.
\item If $u\in V$ and $a$ a scalar, then $au\in V$.
\end{enumerate}

\centerline{{\bf Associative, commutative, distributive axioms:}}
\begin{enumerate}
  \item For all $u,v,w\in V$  $\;\;\;\;\; (u+v)+w=u+(v+w)$.
  \item For all $u,v\in V$  $\;\;\;\;\; u+v=v+u$.
  \item For all scalars $a$ and $b$ and vectors $u\in V$
  $\;\;\;\;\; (ab)u=a(bu)$.
  \item For all scalars $a$ and $b$ and vectors $u\in V$
   $\;\;\;\;\; (a+b)u=au+bu$.
  \item For all scalars $a$ and vectors $u,v\in V$
   $\;\;\;\;\; a(u+v)=au+av$.
\end{enumerate}

\centerline{{\bf Zero vector, additive inverse, identity axioms:}}
\begin{enumerate}
\item  There exists a vector $z\in V$ such that for all $u\in V$
   $\;\;\;\;\; z+u=u+z=u$.
\item For every $u\in V$ there exists a vector $v\in V$ (for which
  we write $v=-u$) such that $u+v=v+u=z$.
\item For every $u\in V$, $\;\;\;\;\; 1u=u$.
\end{enumerate}

Any abstract set $V$ with two operations, vector addition
and scalar multiplication which satisfy all the above axioms
is a vector space.

Most author's use either ${\bf 0}$ or $\vec{0}$ to denote the zero
vector but students persistently confuse the zero vector
with the zero scalar, so I decided to write the zero vector as $z$.

\begin{exercise} \label{zero}
  Prove that $0u=z$ for any $u\in V$ a vector space.
\end{exercise}

\begin{exercise} \label{minus}
  Prove that $(-1)u=-u$ for any $u\in V$ a vector space.
\end{exercise}

\begin{define}
  For $W$ a subset of a vector space $V$ (written $W\subseteq V$)
  we say that
  $W$ is a $\underline{subspace}$ of $V$ iff
  \begin{enumerate}
    \item for every $u,v\in V$ if $u\in W$ and $v\in W$, then $u+v\in W$, and
    \item for every $u\in V$ and scalar $a$ if $u\in W$, then $au\in W$.
  \end{enumerate}
\end{define}
I usually add to the definition that $W$ be a nonempty set, but this
semester I have decided not to worry about the empty set or should I say
I have no worries? or should I say my set of worries is the empty set?


\begin{theorem}
  If $W$ is a subspace of $V$, then $W$ is itself a vector space under
  the operations defined in $V$.
\end{theorem}
\proof
The closure axioms are easy since they are practically the same as the
definition of subspace.  The associative, commutative, distributive axioms are
true in $W$ because they are true in $V$ and $W$ is a subset of $V$.
The zero vector $z$ is in $W$ because 0u=z (exercise \ref{zero})
so (assuming $W$ is nonempty) if anything is in $W$, then
$z$ is in $W$. Similarly
$(-1)u=-u$ (exercise \ref{minus}), so if $u\in W$, then also $-u\in W$.
\qed

\begin{theorem}
  Suppose $W$ is a subset of $V$ (i.e., $W\subseteq V$).  Then
\begin{enumerate}
  \item $W$ is a subspace of $V$

   iff

  \item for every $u,v\in W$ and scalars
  $a,b$ we have $au+bv\in W$.
\end{enumerate}
\end{theorem}
\proof

(1) implies (2):

Assume $W$ is a subspace of $V$.  Suppose $u,v\in W$ and
$a,b$ are scalars. By the second axiom of subspaces we have
that $au\in W$ and $bv\in W$.  Letting $w_1=au$ and
$w_2=bv$ we have that $w_1\in W$ and $w_2\in W$, therefore
by the first axiom of subspaces we have that
$w_1+w_2\in W$ and so $au+bv\in W$.


(2) implies (1):

Assume (2): for every $u,v\in W$ and scalars $a,b$ we have $au+bv\in W$.
We must show the two axioms of a subspace hold for $W$.
Suppose $u,v\in W$.  Then letting $a=b=1$ we have
that $1u+1v\in W$, so $1u+1v=u+v\in W$.  For the second axiom,
suppose
$u\in W$ and $a$ any scalar, then we have that
$au+0u\in W$ by (2), but $au=au+z=au+0u$ so $au\in W$.
\qed



\begin{define}
  For $u_1,\ldots,u_n$ elements of a vector space $V$, define their
  \underline{span}:
  $$\span(\{u_1,u_2,\ldots,u_n\})=\{a_1u_1+a_2u_2+\cdots+a_nu_n:
  a_1,a_2,...,a_n \mbox{ scalars}\}$$
\end{define}

Each of the vectors $a_1u_1+a_2u_2+\cdots+a_nu_n$ is called a linear
combination of the $u$'s so we could also say that the span
is the set of all linear combinations.
If $W=\span(\{u_1,u_2,\ldots,u_n\})$,
we say that `$W$ is spanned by $u_1,u_2,\ldots,u_n$' or
`$u_1,u_2,\ldots,u_n$ span $W$'.  The closure axioms of a vector
space $V$ guarantee that if $u_1,u_2,\ldots,u_n\in V$, then
$\span(\{u_1,u_2,\ldots,u_n\})\subseteq V$.  This is true because
the second closure axiom says each $a_iu_i$ is in $V$, while the first axiom
guarantees that their sum is in $V$, e.g., if we write $v_i=a_iu_i$,
$v_1,v_2\in V$ implies $v_1+v_2\in V$ and so
$v_1+v_2,v_3\in V$ implies $v_1+v_2+v_3=(v_1+v_2)+v_3\in V$, and so on.


\begin{theorem}
 Suppose $u_1,u_2,\ldots,u_n$ are elements of $W$ which is a subspace of
 $V$.  Then $\span(\{u_1,u_2,\ldots,u_n\})\subseteq W$.
\end{theorem}
\proof
 Suppose $v\in \span(\{u_1,u_2,\ldots,u_n\})$.  Then for some
 scalars, $a_1,\ldots,a_n$ we have that
 $$v=a_1u_1+\cdots+a_nu_n.$$
Since $W$ is a subspace of $V$ we have that $a_iu_i\in W$ for
each $i$.  Now let $v_i=a_iu_i$ to simplify our writing.
Since $v_1\in W$ and $v_2\in W$ we have by the first axiom of
subspaces that $v_1+v_2\in W$.  Thus we have
that the two vectors $v_1+v_2$ and $v_3$ are elements of $W$.
This means there sum $(v_1+v_2)+v_3$ is in $W$.  Continuing
on like this we see that $v_1+v_2+\cdots+v_k\in W$ for
each $k$ and so
$$v=a_1u_1+\cdots+a_nu_n=v_1+v_2+\cdots+v_n\in W$$
as we needed to show.\qed


\begin{theorem}
Suppose $u_1,u_2,\ldots,u_n$ are elements of a vector space $V$.
Then $\span(\{u_1,u_2,\ldots,u_n\})$ is a subspace of $V$.
\end{theorem}
\proof
We verify each of the axioms of a subspace. Let
$$W=\span(\{u_1,u_2,\ldots,u_n\}).$$

Suppose $v,w$ are elements of $W$.  Then since $W$ is the span
of the $u's$ there exists scalars $c_1,\ldots,c_n$ and
$d_1,\ldots,d_n$ such that
$$v=c_1u_1+\cdots+c_nu_n \mbox{ and } w= d_1u_1+\cdots+d_nu_n.$$
But then
$$v+w= (c_1+d_1)u_1+(c_2+d_2)u_2+\cdots+(c_n+d_n)u_n$$
and so $v+u\in \span(\{u_1,u_2,\ldots,u_n\})=W$

For the second axiom, suppose $v\in W$ and $a$ a scalar.
Then for some scalars $c_1,\ldots,c_n$

$$v=c_1u_1+\cdots+c_nu_n$$
but then
$$av=a(c_1u_1+\cdots+c_nu_n)= (ac_1)u_1+\cdots+(ac_n)u_n$$
and so $av\in \span(\{u_1,u_2,\ldots,u_n\})=W$.

\qed



It follows from these last two theorems that $\span(\{u_1,u_2,\ldots,u_n\})$
is the smallest subspace of $V$ which contains the vectors
$u_1,u_2,\ldots,u_n$.


\begin{theorem} \label{span}
Suppose $u\in\span(\{u_1,\ldots,u_n\})$ then
$$\span(\{u,u_1,\dots,u_n\})=\span(\{u_1,\dots,u_n\})$$
\end{theorem}
\proof

\medskip

\begin{center}\begin{tabular}{|c|}
\hline
To show two sets $A$ and $B$ are equal, $A=B$, \\
show that \\
$A\subseteq B$ and $B\subseteq A$.\\
\hline
\end{tabular} \end{center}

\medskip
\begin{center}\begin{tabular}{|c|}
\hline
To show that
$A\subseteq B$ \\
suppose that  $x\in A$ and then show $x \in B$. \\
\hline
\end{tabular}\end{center}

\medskip

First we show $\span(\{u,u_1,\dots,u_n\})\subseteq
\span(\{u_1,\dots,u_n\})$.
Since $u\in\span(\{u_1,\ldots,u_n\})$ there exists scalars
$b_1,\ldots, b_n$ so that $u=b_1u_1+\cdots+b_nu_n$.  Now
let $w$ be any element of $\span(\{u,u_1,\dots,u_n\})$.
This means there are scalars $a,a_1,\ldots,a_n$ such that
$$w=au+a_1u_1+\cdots+a_nu_n.$$
But then substituting for $u$:
$$w=a(b_1u_1+\cdots+b_nu_n)+a_1u_1+\cdots+a_nu_n$$
$$\;\;\;\;\;=(ab_1+a_1)u_1+\cdots+(ab_n+a_n)u_n$$
and so $w\in \span(\{u_1,\ldots,u_n\})$ as was to be shown.

Second we show $\span(\{u_1,\dots,u_n\})\subseteq
\span(\{u,u_1,\ldots,u_n\})$.
This is easier. Suppose $w\in \span(\{u_1,\ldots,u_n\})$. Then
there are scalars $c_1,\ldots,c_n$ so that
$$w=c_1u_1+\cdots+c_nu_n$$
but then
$$w=0u+ c_1u_1+\cdots+c_nu_n$$
so $w\in \span(\{u,u_1,\ldots,u_n\})$ as was to be shown.
\qed


\begin{define}
  For $v_1,v_2,\dots,v_n$ vectors in a vector space $V$ we say
  that they are \underline{linearly independent} iff
  for any scalars $a_1,a_2,\dots,a_n$
  $$a_1v_1+a_2v_2+\cdots+a_nv_n=z \to a_1=a_2=\cdots=a_n=0$$
\end{define}

\begin{define}
  We say $v_1,v_2,\dots,v_n$
  are \underline{linearly dependent} iff $v_1,\dots,v_n$ are
  not linearly independent.
\end{define}


\begin{define}
  $v_1,v_2,\ldots,v_n$ is a \underline{basis} for the vector space
  $V$ iff
  \begin{enumerate}
   \item $v_1,v_2,\ldots,v_n$ are linearly independent and
   \item $V=\span(\{v_1,v_2,\ldots,v_n\})$.
  \end{enumerate}
\end{define}



\begin{theorem}
  Let $A$ be any $n \times n$ matrix.  Then
  $A$ is invertible iff the set of columns of $A$ is
  a basis for $\reals^n$, i.e., $\col_1(A),\col_2(A),\ldots,\col_n(A)$ is
  a basis for $\reals^n$.
\end{theorem}
\proof
Before proving this result we first prove the following Lemma.

\begin{lemma}
  Suppose $A$ is an $m \times n$ matrix and
  $$B=\left[\begin{array}{c} b_1\\b_2\\ \vdots \\ b_n\end{array}\right]$$
  is $n\times 1$. Then
  $$AB=A\left[\begin{array}{c} b_1\\b_2\\ \vdots \\ b_n\end{array}\right]
      =b_1\col_1(A)+b_2\col_2(A)+\cdots+b_n\col_n(A)
      =\sum_{k=1}^n b_k\col_k(A)$$
\end{lemma}
\proof
Write the matrix $A$ as follows:
$$A=\left[
\begin{array}{ccccc}
a_{1,1} &  a_{1,2} & a_{1,3} & \cdots & a_{1,n} \\
a_{2,1} &  a_{2,2} & a_{2,3} & \cdots & a_{2,n} \\
a_{3,1} &  a_{3,2} & a_{3,3} & \cdots & a_{3,n} \\
 \vdots &  \vdots  &         &        &  \vdots \\
a_{m,1} &  a_{m,2} & a_{m,3} & \cdots & a_{m,n} \\
\end{array}\right]$$
i.e., $a_{i,j}=\entry_{i,j}(A)$.
Then

$$
\begin{array}{lcl}
AB & = &\left[
\begin{array}{ccccc}
a_{1,1} &  a_{1,2} & a_{1,3} & \cdots & a_{1,n} \\
a_{2,1} &  a_{2,2} & a_{2,3} & \cdots & a_{2,n} \\
a_{3,1} &  a_{3,2} & a_{3,3} & \cdots & a_{3,n} \\
 \vdots &  \vdots  &         &        &  \vdots \\
a_{m,1} &  a_{m,2} & a_{m,3} & \cdots & a_{m,n} \\
\end{array}\right]
\left[\begin{array}{c} b_1\\b_2\\ \vdots \\ b_n\end{array}\right]\\
& & \\
& = &
\left[
\begin{array}{c}
a_{1,1}b_1 +  a_{1,2}b_2 + a_{1,3}b_3 + \cdots + a_{1,n}b_n\\
a_{2,1}b_1 +  a_{2,2}b_2 + a_{2,3}b_3 + \cdots + a_{2,n}b_n\\
a_{3,1}b_1 +  a_{3,2}b_2 + a_{3,3}b_3 + \cdots + a_{3,n}b_n\\
 \vdots  \\
a_{m,1}b_1 +  a_{m,2}b_2 + a_{m,3}b_3 + \cdots + a_{m,n}b_n \\
\end{array}\right]_{m \times 1} \\
& & \\
& = &
b_1
\left[ \begin{array}{c}
a_{1,1}\\
a_{2,1}\\
a_{3,1}\\
\vdots \\
a_{m,1}\\
\end{array} \right]
+
b_2
\left[ \begin{array}{c}
a_{1,2}\\
a_{2,2}\\
a_{3,2}\\
\vdots \\
a_{m,2}\\
\end{array} \right]
+
b_3
\left[ \begin{array}{c}
a_{1,3}\\
a_{2,3}\\
a_{3,3}\\
\vdots \\
a_{m,3}\\
\end{array} \right]
+\cdots+
b_n
\left[ \begin{array}{c}
a_{1,n}\\
a_{2,n}\\
a_{3,n}\\
\vdots \\
a_{m,n}\\
\end{array} \right]\\
\end{array}
$$
This proves the Lemma.
\qed
Now to prove the Theorem we first assume that $A$ is invertible
and show that the columns of $A$ are a basis for $\reals^n$.
To see that they are independent, suppose
that
$$b_1\col_1(A)+\cdots+b_n\col_n(A)=Z$$
where $Z_{n\times 1}$ is the zero vector.
By the lemma
$$AB=Z$$
where $B$ is the column vector made from $b_1,\ldots,b_n$.
Since $A$ is invertible we have that $B=A^{-1}Z=Z$ so
$B=Z$ and so $b_i=0$ for all $i$ with $1\leq i\leq n$. This
shows the the columns of $A$ are linearly independent.
To see that they span $\reals^n$,  let $C$ be an arbitrary
element of $\reals^n$ so that
$$
C=\left[\begin{array}{c} c_1\\c_2\\ \vdots \\ c_n\end{array}\right].
$$
Since $A$ is invertible if we set $B=A^{-1}C$ then
we know that $AB=C$ and by the lemma we have
that
$$b_1\col_1(A)+\cdots+b_n\col_n(A)=C$$
and so $C$ is in the span of the columns of $A$.  This shows
that if $A$ is invertible then its columns are a basis.  Next
we prove the converse, using the contrapositive.
\medskip

\begin{center}
  \begin{tabular}{|c|} \hline
   The contrapositive of the implication: \\
   P implies Q\\
   is \\
   (Not Q) implies (Not P)\\
   They are logically equivalent.\\
  \hline
  \end{tabular}
\end{center}

\medskip

Assume that $A$ is not invertible.  Then as was shown the algorithm
for attempting to invert $A$ produces a $B_{n\times 1}\not=Z$
such that $AB=Z$.  This means by the
Lemma that
$$b_1\col_1(A)+\cdots+b_n\col_n(A)=Z$$
and since $B\not=Z$ at least one $b_i\not=0$.  But this
means that the columns of $A$ are linearly dependent and
hence not a basis.
This finishes the proof of the Theorem.
\qed

\begin{theorem}
  $v_1,v_2,\dots,v_n$ are linearly dependent iff there are scalars
  $$a_1,a_2,\dots,a_n$$ such that $a_1v_1+a_2v_2+\cdots+a_nv_n=z$ and
  for at least one $i$ we have $a_i\not=0$.
\end{theorem}
\proof

\medskip

\begin{center}
  \begin{tabular}{|c|} \hline
   Not For ALL x Statement(x)\\
   is logically equivalent to \\
   There exists x such that Not Statement(x) \\
  \hline
  \end{tabular}
\end{center}

\medskip

So negating linear independence gives us:

There exists scalars $a_1,\ldots, a_n$ such that

Not [ $a_1v_1+\cdots+a_n=z$ implies $a_1=a_2=\cdots=a_n=0$ ].

\medskip
\begin{center}
  \begin{tabular}{|c|} \hline
    The negation of an implication\\
    Not [P implies Q]\\
    is logically equivalent to \\
    P and Not Q.\\
  \hline
  \end{tabular}
\end{center}
\medskip

So in this case we get

$a_1v_1+\cdots+a_n=z$ and Not [$a_1=a_2=\cdots=a_n=0$].

But Not [$a_1=a_2=\cdots=a_n=0$] is the same as saying `at least
one of the $a_i$ is not equal to $0$. \qed

\begin{exercise} \label{lindep}
 Prove that $v_1,\ldots,v_n$ are linearly dependent iff
 $v_1=z$ or $v_j\in\span(\{v_1,\ldots,v_{j-1})$ for some $j$
 with $1<j\leq n$.
\end{exercise}


\begin{lemma}
  (Exchange) Suppose $v_1,v_2,\ldots,v_{k+1},w_1,\ldots,w_m$ are
  vectors in a vector space $V$ and
  \begin{enumerate}
    \item $v_1,v_2,\ldots,v_{k+1}$ are linearly independent, and
    \item $\span(\{v_1,v_2,\ldots,v_{k},w_1,\ldots,w_m\})=V$.
  \end{enumerate}
  Then for some $i$ with $1\leq i\leq m$
   $$\span(\{v_1,v_2,\ldots,v_{k+1},w_1,w_2\ldots,
     w_{i-1},w_{i+1},\ldots w_m\})=V$$
  (i.e., we have added $v_{k+1}$ and removed $w_i$.)
\end{lemma}
\proof
By (2) there are scalars $a_i$, $b_j$ such that
 $$v_{k+1}=a_1v_1+a_2v_2+\cdots +a_kv_k+ b_1w_1+b_2w_2+\cdots+b_mw_m.$$
It must be that for some $i$ with $1\leq i\leq m$ that $b_i\not=0$,
because otherwise we would have that
 $$v_{k+1}=a_1v_1+a_2v_2+\cdots +a_kv_k$$
and therefore
$$z=a_1v_1+a_2v_2+\cdots +a_kv_k+(-1)v_{k+1}$$
contradicting their independence (1).

Therefore  we have that
$$
\begin{array}{cccl}
-b_iw_i & = & & a_1v_1+\cdots +a_kv_k+ (-1)v_{k+1}+\\
& & + & b_1w_1+ \cdots+b_{i-1}w_{i-1}+b_{i+1}w_{i+1}+\cdots+b_mw_m\\
\end{array}
$$

and since $b_i\not=0$

$$
\begin{array}{cccl}
w_i & = & & {a_1\over -b_i}v_1+\cdots +{a_k\over -b_i}v_k+
{(-1)\over -b_i}v_{k+1}+\\
& & + & {b_1\over -b_i}w_1+
\cdots+{b_{i-1}\over -b_i}w_{i-1}+{b_{i+1}\over -b_i}w_{i+1}
+\cdots+{b_m\over -b_i}w_m.\\
\end{array}
$$


Hence
$$w_i\in \span(\{v_1,\ldots,v_{k+1},w_1,\ldots,w_{i-1},w_{i+1},\ldots,w_m\})$$
and so by Theorem \ref{span} we have
$$ \span(\{v_1,v_2,\ldots,v_{k+1},w_1,w_2\ldots,
     w_{i-1},w_{i+1},\ldots w_m\})$$
$$\;\;\;\;\;=\span(\{v_1,v_2,\ldots,v_{k+1},w_1,w_2\ldots, w_m\})$$
and by (2) we have
$$\span(\{v_1,v_2,\ldots,v_{k+1},w_1,w_2\ldots, w_m\})=V$$
and so we are done.
\qed


\begin{theorem} \label{main} (Main Theorem)
  If a vector space $V$ can be spanned by $n$ vectors, then
  any set of $n+1$ vectors in $V$ is linearly dependent.
\end{theorem}
\proof
Suppose for contradiction that $\span(\{u_1,\ldots,u_n\})=V$ and
$v_1,\ldots,v_{n+1}$ are linearly independent.

\medskip

Step 1. Apply the Exchange Lemma  with $k=0$ to obtain
$i$ so that $\span(\{v_1,u_1,\ldots,u_{i-1},u_{i+1},\ldots u_n\})=V$.

\medskip

Step 2. Rename (relabel? reorder?) the $u$'s so that
$$(w_1,\ldots,w_{n-1})=(u_1,\ldots,u_{i-1},u_{i+1},\ldots u_n)$$
and apply the Exchange Lemma with $k=1$ to obtain $i$ so
that $$\span(\{v_1,v_2,w_1,\ldots,w_{i-1},w_{i+1},\ldots w_{n-1}\})=V.$$

\medskip

Step k. Given $\{w_1,\ldots,w_{n-k}\}\subseteq \{u_1,\ldots,u_n\}$ such
that
$$\span(\{v_1,v_2,\ldots,v_k,w_1,\ldots, w_{n-k}\})=V,$$
apply
the Exchange Lemma to find $i$ so that
$$\span(\{v_1,v_2,\ldots,v_k,v_{k+1},w_1,
\ldots,w_{i-1},w_{i+1},\ldots w_{n-k}\})=V$$

\medskip

Last Step: Given that $\span(\{v_1,v_2,\ldots,v_{n-1},w_1\})=V$, apply
the Exchange Lemma to get that
$$\span(\{v_1,v_2,\ldots,v_{n}\})=V.$$

\medskip

But this is a contradiction, since $v_{n+1}\in\span(\{v_1,v_2,\ldots,v_{n}\})$
implies that
$$v_{n+1}=a_1v_1+\cdots+a_nv_n$$
for some scalars $a_i$, but then
$$z=(-1)v_{n+1}+a_1v_1+\cdots+a_nv_n$$
and therefore $v_1,\ldots,v_{n+1}$ would be linearly dependent,
a contradiction.
\qed


\begin{define}
  The \underline{dimension} of a vector space V is $n$,
  written $\dim(V)=n$ iff $V$ has a basis of size $n$.
\end{define}

\begin{theorem}
Any two bases for a vector space $V$ have the same size.
\end{theorem}
\proof
Otherwise, if $u_1,\ldots,u_m$ is a basis for $V$ and
$v_1,\ldots,v_n$ is another basis for $V$ and $m<n$, then
since the $u$'s span $V$ it must be that the $v$'s are
linearly dependent (by \ref{main}), contradicting that they are a basis.
\qed

\begin{theorem} \label{indbasis}
  If $V$ is a vector space, $\dim(V)=n$, and $u_1,\ldots,u_n\in V$
  are linearly independent, then $u_1,\ldots,u_n$ are a basis
  for $V$.
\end{theorem}
\proof
It is enough to show $\span(\{u_1,\ldots,u_n\})=V$.
By the main theorem (\ref{main}) for any $v\in V$ we know that
$u_1,u_2,\ldots,u_n,v$ are linearly dependent. Hence there are
scalars $a_1,a_2,\ldots,a_n,a$ (at least one of which is nonzero)
such that
$$a_1u_1+a_2u_2+\cdots+a_nu_n+av=z.$$
Since $u_1,\ldots,u_n$ are linearly independent, it cannot be that
$a=0$ and so
$$v=-{1\over a}( a_1u_1+a_2u_2+\cdots+a_nu_n)$$
and so $v\in\span(\{u_1,\ldots,u_n\})$ and since $v$ was an arbitrary element
of $V$ we have that $\span(\{u_1,\ldots,u_n\})=V$.\qed


\begin{theorem}
 Suppose $\dim(V)=n$ and $$\span(\{u_1,...,u_n\})=V.$$  Then
 $u_1,...,u_n$ is a basis for $V$.
\end{theorem}
\proof
It is enough to prove that $u_1,...,u_n$ are linearly independent.

\begin{center}\begin{tabular}{|c|}
\hline
In a proof by contradiction \\
assume the negation of what you are trying to prove \\
and then reason to a contradiction.\\
It follows logically\\
that what you are trying to prove must be true\\
\hline
\end{tabular} \end{center}

Suppose for contradiction that they are linearly dependent.
Then
there are scalars $a_1,\ldots,a_n$ such that
$$a_1u_1+\cdots+a_nu_n=z$$
and for some $i$ we have $a_i\not=0$.  But then we have that
$$u_i\in\span(\{u_1,\ldots, u_{i-1},u_{i+1},\ldots,u_n\})$$
and so by Theorem \ref{span}, we have that
$V$ is spanned by $n-1$ vectors.  This would imply
by the main theorem (\ref{main}) that any set of
$n$ vectors is linearly dependent, contradicting the fact
the dimension of $V$ is $n$.\qed


\begin{theorem}
 Every vector space has a basis.
\end{theorem}
\proof
This theorem is true in general but requires a more sophisticated proof
for the infinite dimensional case.  Here we prove it just for the
case that our vector space $W$ is a subspace of a vector space
$V$ with finite dimension.  Suppose the dimension of $V$ is $n$.

If $W=\{z\}$, then the dimension of $W$ is $0$ and the empty set
is a basis for it.  Otherwise let $v_1\in W$ be an arbitrary
vector in $W$ not equal to the zero vector, $z$.
If $v_1$ spans $W$, then the dimension of $W$ is $1$ and
$v_1$ is a basis for it.  Otherwise choose any $v_2\in W$ such
that $v_2\notin\span\{v_1\}$.  Continue this procedure. That is
given $v_1,\ldots,v_k\in W$, if $v_1,\ldots,v_k$ span
$W$, then stop.  Otherwise choose $v_{k+1}\in W$ arbitrary but
not in the span of $v_1,\ldots,v_k$.  By an exercise \ref{lindep}
$v_1,\ldots,v_k$ are linearly independent for every $k$.  By
the  main theorem $k\leq n$ so this process must stop after
$\leq n$ steps and when it stops we have found a basis for $W$.
\qed

\begin{exercise} Prove: \par
  If $\dim(V)=n$ and $u_1,\ldots,u_m\in V$ are linearly independent,
  then we can extend this sequence to a basis of $V$. That is,
  we can find $u_{m+1},u_{m+2},\ldots, u_n$ so that
  $u_1,\ldots,u_n$ is a basis for $V$.
\end{exercise}

\begin{exercise}
  If $u_1,\ldots,u_n$ span a vector space $V$, then
  there exists
  $$\{v_1,\ldots,v_m\}\subseteq\{u_1,\ldots,u_n\}$$
  such that $v_1,\ldots,v_m$ is a basis for $V$.  In other
  words, any spanning set contains a basis.
\end{exercise}

%\proof
%By removing one vector at a time find a set
%$$\{v_1,\ldots,v_m\}\subseteq\{u_1,\ldots,u_n\}$$
%such that
%$$\span(\{v_1,\ldots,v_m\})=V$$
%but for every $i$ with $1\leq i\leq m$
%$$\span(\{v_1,\ldots,v_{i_1},v_{i+1},\ldots, v_m\})\not=V.$$
%The $v$'s form a `minimal' spanning set. It is enough to see
%that they must be linearly independent.  If they are
%not then some $v_i$ is in the span of $v_1,\ldots,v_{i-1},v_{i+1},\ldots,v_m$.
%But by Theorem \ref{span}, this would imply
%$$\span(\{v_1,\ldots,v_{i_1},v_{i+1},\ldots, v_m\})=V$$
%which would contradict the fact that the $v$'s form a minimal
%spanning set.\qed

\begin{theorem}
  If $W$ is a subspace of $V$ and $\dim(V)=n$, then
  $\dim(W)=m$ for some $m\leq n$.  If $m=n$ then $W=V$.
\end{theorem}
\proof
Any basis for $W$ is a set of $m$ linearly independent vectors
in $V$. But the main theorem (\ref{main}) implies that
$m\leq n$.  Suppose $m=n$, then let $u_1,\ldots,u_n$ be
a basis for $W$.
Since they are  linearly independent vectors in $V$,
by Theorem \ref{indbasis}
they must also be a basis for $V$, and so
$$W=\span(\{u_1,\ldots,u_n\})=V.$$
\qed


\end{document}