\documentclass[11pt]{amsart}
% \topmargin -.2in
% \textheight 9in
% \evensidemargin 0.5in
% \oddsidemargin 0.5in
% \textwidth 5.5in

\usepackage{amsmath,amsfonts}
\usepackage{amsthm}
\usepackage{enumerate}

\usepackage[dvips]{color}
% \usepackage[color,notref,notcite]{showkeys}

\definecolor{refkey}{gray}{0.5}
\definecolor{labelkey}{gray}{0.5}

\DeclareMathOperator{\lspan}{span}

% theorem definitions (labeled consecutively)
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{remark}[definition]{Remark}


\theoremstyle{plain}
\newtheorem{lemma}[definition]{Lemma}
\newtheorem{theorem}[definition]{Theorem}
\newtheorem{proposition}[definition]{Proposition}
\newtheorem{corollary}[definition]{Corollary}
%
\newtheorem*{statement}{Statement}

% environment definitions

\newcommand{\nC}{\mathbb C}
\newcommand{\nF}{\mathbb F}
\newcommand{\nK}{\mathbb K}
\newcommand{\nM}{\mathbb M}
\newcommand{\nN}{\mathbb N}
\newcommand{\nP}{\mathbb P}
\newcommand{\nQ}{\mathbb Q}
\newcommand{\nR}{\mathbb R}
\newcommand{\nS}{\mathbb S}
\newcommand{\nZ}{\mathbb Z}

\newcommand{\cV}{{\mathcal V}}
\newcommand{\cU}{{\mathcal U}}
\newcommand{\cW}{{\mathcal W}}



\begin{document}

\title[Bases]{\Large Bases}
\author{Branko \'{C}urgus}
\maketitle

Throughout this note $\cV$ is a vector space over $\nF$ and $j, k, l,
m$, and $n$ are natural numbers.

\begin{definition} \label{dld}
Vectors $v_1,\ldots,v_n \in \cV$ are said to be {\em linearly
dependent} if there exist $\alpha_1,\ldots,\alpha_n \in \nF$ and $k
\in \{1,\ldots,n\}$ such that $\alpha_1 v_1 +\cdots + \alpha_n v_n =
0$ and $\alpha_k \neq 0$.
\end{definition}

The formal negation of the statement in Definition~\ref{dld} is:

For all $\alpha_1,\ldots,\alpha_n \in \nF$ and all $k \in
\{1,\ldots,n\}$ we have $\alpha_1 v_1 +\cdots + \alpha_n v_n \neq 0$
or $\alpha_k = 0$.

The last statement is equivalent to:

For all $\alpha_1,\ldots,\alpha_n \in \nF$ and all $k \in
\{1,\ldots,n\}$ we have $\alpha_1 v_1 +\cdots + \alpha_n v_n = 0$
implies $\alpha_k = 0$.

The last statement can be restated as:

If $\alpha_1,\ldots,\alpha_n \in \nF$ and $\alpha_1 v_1 +\cdots +
\alpha_n v_n = 0$, then $\alpha_k = 0$ for all $k \in
\{1,\ldots,n\}$.

\begin{definition} \label{dli}
Vectors $v_1,\ldots,v_n \in \cV$ are said to be {\em linearly
independent} if $\alpha_1,\ldots,\alpha_n \in \nF$ and $\alpha_1 v_1
+\cdots + \alpha_n v_n = 0$ implies $\alpha_k = 0$ for all $k \in
\{1,\ldots,n\}$.
\end{definition}

\begin{lemma} \label{ldep}
Let $k \leq m$ and let $v_1, \ldots, v_m$ be vectors in $\cV$.  If
the vectors $v_1 , \ldots , v_k$ are linearly dependent, then the
vectors $v_1 , \ldots , v_m$ are linearly dependent.
\end{lemma}
\begin{proof}
Let the vectors $v_1 , \ldots , v_k$ be linearly dependent. Then
there exist $\alpha_1, \ldots , \alpha_k $ in $\nF,$ not all equal to
$0,$ such that $\alpha_1 v_1 + \cdots + \alpha_k  v_k = 0$. Take
$\alpha_{k+1} = \cdots = \alpha_m  = 0$.  Then, not all $\alpha_1,
\ldots , \alpha_k , \ldots , \alpha_m $ are equal to $0$ and
$\alpha_1 v_1 + \cdots + \alpha_k v_k + \cdots + \alpha_m v_m = 0.$
Therefore, $v_1 ,  \ldots , v_m$ are linearly dependent.
\end{proof}
The following corollary is the contrapositive of Lemma~\ref{ldep}.
\begin{corollary} \label{lind}
Let $k \leq m$ and let $v_1, \ldots, v_m$ be vectors in $\cV$.  If
the vectors $v_1 ,  \ldots , v_m$ are linearly independent, then the
vectors $v_1 , \ldots , v_k $ are linearly independent.
\end{corollary}
\begin{lemma} \label{ldl}
Let $m \geq 2$, let $v_1, \ldots, v_m$ be vectors in $\cV$. The
vectors $v_1, \ldots, v_m$ are linearly dependent if and only if
there exists $k \in \{1,2,\ldots,m\}$ such that
\begin{equation} \label{eqeq}
\lspan \bigl\{v_l \, : l \in \{1,\ldots,m\} \setminus \{k\}\, \bigr\}
= \lspan\{v_1,\ldots,v_{m}\}.
\end{equation}
\end{lemma}
\begin{proof}
Assume that $v_1, \ldots, v_m$ are linearly dependent. Then there
exist $\alpha_1,\ldots,\alpha_m \in \nF$ such that $\alpha_1 v_1 +
\cdots + \alpha_m v_m = 0$ and there exists $k \in \{1,\ldots,m\}$
such that $\alpha_k \neq 0$. Now, $\alpha_1 v_1 + \cdots + \alpha_m
v_m = 0$ implies
\[
v_k = -(1/\alpha_k)\bigl(\alpha_1 v_1 + \cdots + \alpha_{k-1} v_{k-1}
+ \alpha_{k+1} v_{k+1} + \cdots + \alpha_m v_m\bigr).
\]
Thus $v_k \in \lspan \bigl\{v_l \, : l \in \{1,\ldots,m\} \setminus
\{k\}\, \bigr\}$. Consequently
\[
\lspan\{v_1,\ldots,v_{m}\} \subseteq \lspan \bigl\{v_l \, : l \in
\{1,\ldots,m\} \setminus \{k\}\, \bigr\}.
\]
Since the converse inclusion is trivial, the ``if'' part of the lemma
is proved.

Assume that there exists $k \in \{1,2,\ldots,m\}$ such that
\eqref{eqeq} holds. Then $v_k \in \lspan \bigl\{v_l \, : l \in
\{1,\ldots,m\} \setminus \{k\}\, \bigr\}$. Therefore there exist
\[
\beta_1,\ldots, \beta_{k-1},\beta_{k+1},\ldots,\beta_m \in \nF
\]
such that
 $ %\[
v_k = \beta_1 v_1 + \cdots + \beta_{k-1} v_{k-1} + \beta_{k+1}
v_{k+1} + \cdots + \beta_m v_m.
 $ % \]
Consequently,
\[
\beta_1 v_1 + \cdots + \beta_{k-1} v_{k-1} + (-1) v_k + \beta_{k+1}
v_{k+1} + \cdots + \beta_m v_m = 0.
\]
Since $- 1 \neq 0$, $v_1, \ldots, v_m$ are linearly dependent.
\end{proof}
\begin{lemma} \label{lw}
If $\cV = \lspan \{ v_1 ,  \ldots , v_m \}$ and $w \in \cV \setminus
\{ 0 \}$, then, after a suitable renumbering of $v_1 , \ldots , v_m$,
we have
\[
\cV = \lspan \{w, v_2, \ldots ,  v_m \}.
\]
\end{lemma}
\begin{proof}
Assume that $v_1 , \ldots , v_m$ span $\cV$ and  $w \in \cV \setminus
\{ 0 \}$. Then there exist $\alpha_1, \ldots \alpha_m$ in $\nF$ such
that $w = \alpha_1 v_1 + \cdots \alpha_m v_m$.  Since $w \neq 0$ not
all $\alpha_1, \ldots \alpha_m$ are equal to $0$. Renumber $v_1 ,
\ldots , v_m$ in such a way that $\alpha_1 \neq 0$. Then
 $$
v_1 = (1/\alpha_1)(w - \alpha_2 v_2 - \cdots - \alpha_m v_m).
 $$
Thus $v_1 \in \lspan\{ w, v_2, \ldots, v_m \}$.  Consequently,
\[
\cV = \lspan \{v_1, \ldots, v_m \} \subseteq \lspan \{ w, v_2,
\ldots, v_m \}.
\]
Since the converse inclusion is obvious, $\cV = \lspan \{ w, v_2,
\ldots, v_m \}$ is proved.
\end{proof}


\begin{lemma} \label{lwk}
Let $2 \leq j \leq m$.  Let $w_1, \ldots, w_j$, and $v_j, v_{j+1} ,
\ldots , v_m,$ be vectors in $\cV$. If
\begin{equation} \label{eqVsp}
\cV = \lspan \{ w_1, \ldots, w_{j-1}, v_j,v_{j+1}, \ldots , v_m \}
\end{equation}
and $w_1 , \ldots , w_j$ are linearly independent, then, after a
suitable renumbering of the vectors $v_j , \ldots , v_m$, we have
\begin{equation} \label{eqlwk}
\cV = \lspan \{w_1 ,  \ldots ,w_{j-1}, w_j, v_{j+1} \ldots , v_m \}.
\end{equation}
\end{lemma}
\begin{proof}
Assume that \eqref{eqVsp} holds and that $w_1, \ldots , w_{j-1}, w_j$
are linearly independent.  Then there exist $\beta_1, \ldots ,
\beta_m$ in $\nF$ such that
\begin{equation} \label{eqwv}
w_j = \beta_1 w_1 + \cdots + \beta_{j-1} w_{j-1} + \beta_j v_j +
\cdots + \beta_m v_m.
\end{equation}
Since $w_1 , \ldots ,w_{j-1}, w_j$ are linearly independent we have
\[
w_j - \beta_1 w_1 - \cdots - \beta_{j-1} w_{j-1} \neq 0.
\]
From \eqref{eqwv} we have
\[
0 \neq w_j - \beta_1 w_1 - \cdots - \beta_{j-1} w_{j-1} = \beta_j v_j
+ \cdots + \beta_m v_m.
\]
Therefore not all $\beta_j, \ldots , \beta_m$ are equal to $0$.
Renumber $v_j , \ldots , v_m$ in such a way that $\beta_j \neq 0$.
Then
\[
 v_j = (1/\beta_j)(- \beta_1 w_1 - \cdots - \beta_{j-1} w_{j-1} + w_j
- \beta_{j+1} v_{j+1} - \cdots - \beta_m v_m).
\]
Thus $v_j \in \lspan \{ w_1, \ldots, w_{j-1}, w_j, \ldots , v_m \}$.
Consequently,
\[
\cV = \lspan \{ w_1, \ldots, w_{j-1}, v_j, \ldots , v_m \} \subseteq
\lspan \{ w_1, \ldots,  w_j, v_{j+1}, \ldots , v_m \}.
\]
Since the converse inclusion is obvious, \eqref{eqlwk} is proved.
\end{proof}


\begin{theorem} \label{tslisp}
Let $k \leq m$.  Let $v_1 ,  \ldots , v_m,$ and $w_1 , \ldots , w_k$
be vectors in $\cV$.  If $\cV = \lspan \{ v_1 ,  \ldots , v_m \}$ and
$w_1 ,  \ldots , w_k,$ are linearly independent, then, after a
suitable renumbering of $v_1 , \ldots , v_m$, we have
\[
\cV = \lspan \{w_1 ,  \ldots , w_k,v_{k+1}, \ldots , v_m \}.
\]
\end{theorem}
\begin{proof}
Assume that $\cV = \lspan \{ v_1 ,  \ldots , v_m \}$ and that  $w_1,
\ldots, w_k$ are linearly independent. Then $w_1 \neq 0$. By Lemma
\ref{lw}, after a suitable renumbering of $v_1 , \ldots , v_m$, we
have  $\cV = \lspan \{ w_1 , v_2,  \ldots , v_m \}$. If $k = 1$ the
theorem is proved. Let $k \geq 2$ and let $2 \leq j \leq k$. By
Corollary~\ref{lind} the vectors $w_1, \ldots, w_j$ are linearly
independent.  In particular $w_1$ and $w_2$ are linearly independent.
Lemma~\ref{lwk} with $j=2$ yields that, after a suitable renumbering
of $v_2 , \ldots , v_m$, we have  $\cV = \lspan \{ w_1 , w_2, v_3,
\ldots , v_m \}$.  Repeated application of Lemma \ref{lwk} (total of
$k-1$ times) yields that, after a suitable renumbering of $v_1,
\ldots, v_m$, we have $\cV = \lspan \{w_1 , \ldots , w_k, v_{k+1},
\ldots , v_m \}$.
\end{proof}
An important special case of the preceding theorem is when $k=m$. We
state it as a corollary.
\begin{corollary} \label{basis}
Let  $v_1 ,  \ldots , v_m$ and $w_1 , \ldots , w_m$ be vectors in
$\cV$. If $w_1 , \ldots , w_m$ are linearly independent and $\ \cV =
\lspan\{ v_1 ,  \ldots , v_m \}$, then
\[
\cV = \lspan\{ w_1 , \ldots , w_m \}.
\]
\end{corollary}

\begin{theorem} \label{lindkm}
Let  $v_1 ,  \ldots , v_m$ and $w_1 , \ldots , w_k$ be vectors in
$\cV$. If $\ w_1 , \ldots , w_k$ are linearly independent and $\cV =
\lspan \{ v_1 ,  \ldots , v_m \}$, then $k \leq m$.
\end{theorem}
This theorem has the following logical structure: $P \wedge Q
\Rightarrow R$. It is not difficult to show (using the truth tables)
that the last implication is equivalent to the implication $P \wedge
\neg R \Rightarrow \neg Q$ and also to $\neg R \wedge Q \Rightarrow
\neg P$.  We state each of these equivalent implications separately.
There is no need to number them since these statements are equivalent
to Theorem~\ref{lindkm}.


\begin{statement}
Let  $v_1 ,  \ldots , v_m$ and $w_1 , \ldots , w_k$ be vectors in
$\cV$. If $\ w_1 , \ldots , w_k$ are linearly independent and $k >
m$, then the vectors $v_1 , \ldots , v_m$ do not span $\cV$.
\end{statement}

\begin{statement}
Let  $v_1 ,  \ldots , v_m$ and $w_1 , \ldots , w_k$ be vectors in
$\cV$.  If $k > m$ and $\cV = \lspan\{ v_1 ,  \ldots , v_m \}$, then
$w_1 , \ldots , w_k$ are linearly dependent.
\end{statement}
\begin{proof}
We will prove the last statement. Assume that $\cV = \lspan\{ v_1 ,
\ldots , v_m \}$ and  $k> m$. We will consider the following two
cases:
\begin{enumerate}[{\bf{Case} 1.}]
\item
The vectors $w_1 , \ldots , w_m$ are linearly dependent.
\item
The vectors $w_1 , \ldots , w_m$ are linearly independent.
\end{enumerate}
In Case 1 by Lemma~\ref{ldep} the vectors $w_1 , \ldots,w_m, w_{m+1},
\ldots, w_k$ are also linearly dependent.

Now consider Case 2. By Corollary~\ref{basis} we have $\cV =
\lspan\{w_1 , \ldots , w_m \}$.  Since $k > m$, we have $k \geq m+1$
and thus, $w_{m+1}$ is a vector in $\cV$ which can be written as a
linear combination of the vectors $w_1 , \ldots , w_m$. Thus the
vectors $w_1 , \ldots , w_m, w_{m+1}$ are linearly dependent.
Consequently
\[
w_1 , \ldots , w_m, w_{m+1}, \ldots,w_k
\]
are linearly dependent.
\end{proof}



\begin{definition}
A vector space $\cV$ over $\nF$ is {\em finite dimensional} if there
exists $m \in \nN$ and vectors $v_1, \ldots, v_m \in \cV$ such that
\[
\cV = \lspan \{v_1, \ldots, v_m \}.
\]
A vector space which is not finite dimensional is said to be {\em
infinite dimensional}.
\end{definition}


\begin{proposition} \label{pidli}
A vector space $\cV$ over $\nF$ is infinite dimensional if and only
if for every $n \in \nN$ there exists linearly independent vectors
$v_1, \ldots, v_n$ in $\cV$.
\end{proposition}
\begin{proof}
We first prove the ``only if'' part. Assume that $\cV$ is an infinite
dimensional vector space over $\nF$. For $n\in\nN$, denote by $P(n)$
the following statement:
\begin{center}
There exist $n$ linearly independent vectors in $\cV$.
\end{center}
We will prove that $P(n)$ holds for for every $n \in \nN$.
Mathematical induction is a natural tool here. Since the space
$\{0_\cV\}$ is finite dimensional, we have $\cV \neq \{0_\cV\}$.
Therefore there exists $v \in \cV$ such that $v \neq 0_\cV$. Hence
$P(1)$ holds. Let $k\in\nN$ and assume that $P(k)$ holds. That is
assume that there exists linearly independent vectors $v_1, \ldots,
v_k$ in $\cV$. Since $\cV$ is an infinite dimensional, $\lspan\{v_1,
\ldots, v_k\}$ is a proper subset of $\cV$. Therefore there exists $v
\in \cV$ such that $v \not\in \lspan\{v_1, \ldots, v_k\}$. Now it is
not difficult to prove (prove it as an exercise) that $k+1$ vectors
$v_1, \ldots, v_k, v$ are linearly independent. Hence $P(k+1)$ holds.

We prove the ``if'' part by proving its contrapositive. Assume that
$\cV$ is a finite dimensional vector space. Then there exists $m \in
\nN$ and $v_1, \ldots, v_m \in \cV$ such that $\cV = \lspan\{v_1,
\ldots, v_m\}$. Let $w_1,\ldots,w_m, w_{m+1}$ be arbitrary vectors in
$\cV$. By Theorem~\ref{lindkm} (more precisely, the second Statement
after it) the vectors $w_1,\ldots,w_m, w_{m+1}$ are linearly
dependent. Thus, for $m+1 \in \nN$, any vectors $w_1,\ldots,w_m,
w_{m+1}\in \cV$ are linearly dependent. This completes the proof.
\end{proof}
\begin{proposition}  \label{psub}
If $\cV$ is a finite dimensional vector space over $\nF$ and $\cU$ is
a subspace of $\cV$, then $\cU$ is a finite dimensional vector space
over $\nF$.
\end{proposition}
\begin{proof}
We proceed with a proof by contradiction. So, we make the following
three assumptions:
\begin{enumerate}[(i)\ ]
\item
$\cV$ is a finite dimensional vector space over $\nF$.
\item
$\cU$ is a subspace of $\cV$.
\item
$\cU$ is an infinite dimensional vector space over $\nF$.
\end{enumerate}
Since $\cV$ is finite dimensional there exists $m \in \nN$ and
$v_1,\ldots,v_m \in \cV$ such that $\cV =\lspan\{v_1,\ldots,v_m\}$.
By Proposition~\ref{pidli} there exists $u_1,\ldots,u_m \in \cU$
which are linearly independent. Since $\cU \subseteq \cV$, we have $
u_1,\ldots,u_m \in \cV. $ Now, Corollary~\ref{basis} implies
$\lspan\{u_1,\ldots,u_m\} = \cV$. Since $\cU$ is infinite dimensional
we have
\[
\lspan\{u_1,\ldots,u_m\} \subset\cU \quad \text{and} \quad
\lspan\{u_1,\ldots,u_m\} \neq \cU.
\]
Hence
\[
\cV \subset \cU \subseteq \cV \quad \text{and} \quad \cV \neq \cU.
\]
This is a contradiction. The proposition is proved.
\end{proof}


\begin{definition}
Let $\cV$ be a finite dimensional vector space over $\nF$.  A set
$\{v_1, \ldots, v_n\}$ is a {\em basis of} $\cV$ if
\[
\cV = \lspan\{v_1, \ldots, v_n\} \ \ \ \text{and} \ \ \ v_1, \ldots,
v_n \ \ \ \text{are linearly independent}.
\]
\end{definition}

The next theorem shows that each nonzero finite dimensional vector
space has a basis.

\begin{theorem} \label{trs}
Let $\cV$ be a vector space over $\nF$. If $\cV =
\lspan\{v_1,\ldots,v_p\}$ and $\cV \neq \{0\}$, then there exist $n
\in \nN, \ n \leq p$, and $j_1,\ldots,j_n \in \{1,\ldots,p\}$ such
that $v_{j_1}, \ldots, v_{j_n}$ is a basis of $\cV$.
\end{theorem}
\begin{proof}
Since $\cV \neq \{0\}$ there exists $l \in \{1,\ldots,p\}$ such that
$v_l \neq 0$.  Put
\[
\nK = \left\{ k \in \nN \, : \ \ \ k \leq p, \ \ \ \begin{matrix}
\exists i_1,\ldots,i_k \in \{1,\ldots,p\} \ \text{such that} \\
v_{i_1}, \ldots, v_{i_k} \ \text{are linearly independent}
\end{matrix} \right\} .
\]
The vector $v_l$ is linearly independent. Therefore $1 \in \nK$;
namely we can choose $i_1 = l$.  Thus $\nK \neq \emptyset$. Since
$\nK$ is a subset of $\nN$ and it is bounded above by $p$, $\nK$ has
a maximum;  denote it by $n$, $n = \max \nK$. Since $n \in \nK$,
there exist $j_1,\ldots,j_n \in \{1,\ldots,p\}$ such that $v_{j_1},
\ldots, v_{j_n}$ are linearly independent. Since $v_{j_1}, \ldots,
v_{j_n}$ are linearly independent the indexes ${j_1}, \ldots, {j_n}$
are distinct. Therefore, if $n = p$, then $\{j_1,\ldots,j_p\} =
\{1,\ldots,p\}$. Consequently, if $n = p$, then the vectors
$v_1,\ldots,v_p$ are linearly independent and $\lspan\{v_{1}, \ldots,
v_{p}\} = \cV$. That is $v_1,\ldots,v_p$ is a basis of $\cV$.

If if $n < p$, then $\{j_1,\ldots,j_p\}$ is a proper subset of
$\{1,\ldots,p\}$. We shall prove that $\lspan\{v_{j_1}, \ldots,
v_{j_n}\} = \cV$. Let
\[
k \in \{1,\ldots,p\} \setminus \{j_1,\ldots,j_n\}
\]
be arbitrary. Since $n+1 \notin \nK$, the vectors ($n+1$ of them)
$v_{j_1}, \ldots, v_{j_n}, v_k$ are linearly dependent. Thus there
exist $\alpha_1, \ldots, \alpha_n, \alpha_{n+1} \in \nF$ not all zero
such that
\[
\alpha_1 v_{j_1} + \cdots + \alpha_n v_{j_n} + \alpha_{n+1} v_k = 0.
\]
Since the vectors $v_{j_1}, \ldots, v_{j_n},$ are linearly
independent, $\alpha_{n+1} = 0$ is not possible.  Thus $\alpha_{n+1}
\neq 0$. Therefore
\begin{equation} \label{e11}
v_k = - \frac{1}{\alpha_{n+1}} \left( \alpha_1 v_{j_1} + \cdots +
\alpha_n v_{j_n} \right).
\end{equation}
Hence
\begin{equation*}
v_k \in \lspan\{ v_{j_1}, \ldots, v_{j_n} \} \ \ \text{for each} \ \
k \in \{1,\ldots,p\} \setminus \{j_1,\ldots,j_n\}.
\end{equation*}
Consequently
\[
\lspan\{v_1, \ldots, v_p\} \subseteq \lspan\{v_{j_1}, \ldots,
v_{j_n}\}.
\]
Since the converse inclusion is obvious, the theorem is proved.
\end{proof}



\begin{theorem} \label{texba}
Let $\cV$ be a nonzero finite dimensional vector space. Then $\cV$
has a basis. If $\{v_1, \ldots, v_m\}$ and $\{w_1, \ldots, w_n\}$ are
two basis of $\cV$, then $m = n$.
\end{theorem}

\begin{proof}
The fact that $\cV$ has a basis is proved in the proof of
Proposition~\ref{psub}. Just set $\cU = \cV$ in that proof.

Let $\{v_1, \ldots, v_m\}$ and $\{w_1, \ldots, w_n\}$ be two bases of
$\cV$. Since
\[
\cV = \lspan\{v_1, \ldots, v_m\}
\]
and $w_1, \ldots, w_n$ are linearly independent, Theorem~\ref{lindkm}
implies $m \geq n$. Since $\cV = \lspan\{w_1, \ldots, w_n\}$ and
$v_1, \ldots, v_m$ are linearly independent Theorem~\ref{lindkm}
implies $m \leq n$. Thus $m=n$.
\end{proof}

\begin{definition}
Let $\cV$ be a nonzero finite dimensional vector space over $\nF$ and
let $\{v_1, \ldots, v_n\}$ be a basis of $\cV$. The number $n$ is
called the {\em dimension of} $\cV$ and it is denoted by $\dim \cV$.
By definition the dimension of the zero vector space is $0$.
\end{definition}



\begin{theorem}
Let $\cV$ be a finite dimensional vector space and let $u_1, \ldots,
u_k$ be linearly independent vectors in $\cV$. Then there exist
vectors $u_{k+1},\ldots, u_n$ in $\cV$ such that $\{u_1, \ldots,
u_n\}$ is a basis of $\cV$.
\end{theorem}
\begin{proof}
By Theorem~\ref{texba} the vector space $\cV$ has a basis. Let
$\{v_1, \ldots, v_n\}$ be a basis for $\cV$. By Theorem~\ref{lindkm}
we have $k \leq n$. By Theorem~\ref{tslisp}, after a suitable
renumbering of $v_1, \ldots, v_n$, we have
\[
\cV = \lspan\{u_1,\ldots,u_k, v_{k+1}, \ldots, v_n \}.
\]
Since $v_1, \ldots, v_n$ are linearly independent, by
Theorem~\ref{lindkm} (see the first Statement) no proper subset of
 \[
\{u_1,\ldots,u_k, v_{k+1}, \ldots, v_n \}
 \]
spans $\cV$. By Lemma~\ref{ldl} this implies that the vectors
$u_1,\ldots,u_k, v_{k+1}, \ldots, v_n$ are linearly independent.
\end{proof}

\begin{proposition} \label{psubs}
Let $\cV$ be a finite dimensional vector space and let $\cU$ be a
subspace of $\cV$. Then $\dim \cU \leq \dim \cV$.  Also, $\cU = \cV$
if and only if $\ \dim \cU = \dim \cV$.
\end{proposition}
\begin{proof}
Let $m = \dim \cU$ and $n = \dim \cV$. Let $u_1, \ldots, u_m$ be a
basis of $\cU$ and let $v_1, \ldots, v_n$ be a basis of $\cV$. Since
$\cV = \lspan\{v_1, \ldots, v_n\}$ and $u_1, \ldots, u_m$ are
linearly independent Theorem~\ref{lindkm} implies $m \leq n$.

If $\cU = \cV$, then clearly $\ \dim \cU = \dim \cV$. Now assume that
$\cU$ is a proper subspace of $\cV$. Then there exists $v \in \cV$
such that $v \notin \cU$. Let again $u_1, \ldots, u_m$ be a basis of
$\cU$. Then $u_1, \ldots, u_m, v$ are linearly independent vectors in
$\cV$. By Theorem~\ref{lindkm} we have $m+1 \leq n$. Thus $m < n$.
\end{proof}

\begin{proposition} \label{p3s}
Let $\cV$ be a finite dimensional vector space over $\nF$ and let
$w_1,\ldots,w_n$ be vectors in $\cV$. Then any two of the following
three statements imply the remaining one.
\begin{enumerate}[{\rm (a)}]
\item \label{ip3sa}
$n = \dim \cV$.
\item \label{ip3sb}
$\lspan \{w_1,\ldots,w_n\} = \cV$.
\item \label{ip3sc}
$w_1,\ldots,w_n$ are linearly independent.
\end{enumerate}
\end{proposition}
\begin{proof}
Assume (\ref{ip3sb}) and (\ref{ip3sc}). Then (\ref{ip3sa}) follows by
the definition of dimension of $\cV$.

Notice that (\ref{ip3sb}) and Theorem~\ref{trs} imply that $n \geq
\dim \cV$. Therefore, the implication ``(\ref{ip3sa}) and
(\ref{ip3sb}) imply (\ref{ip3sc})'' is equivalent to the implication:
If $\lspan \{w_1,\ldots,w_n\} = \cV$ and $w_1,\ldots,w_n$ are
linearly dependent, then $n > \dim \cV$. The last implication is an
immediate consequence of Lemma~\ref{ldl}. Thus (\ref{ip3sa}) and
(\ref{ip3sb}) imply (\ref{ip3sc}).

Notice that (\ref{ip3sc}) and Theorem~\ref{trs} imply that $n \leq
\dim \cV$. Therefore, the implication ``(\ref{ip3sa}) and
(\ref{ip3sc}) imply (\ref{ip3sb})'' is equivalent to the implication:
If $w_1,\ldots,w_n$ are linearly independent and $\lspan
\{w_1,\ldots,w_n\}$ is a proper subspace of $\cV$, then $n < \dim
\cV$. The last implication is a consequence of
Proposition~\ref{psubs}.
\end{proof}



\end{document}
