\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{wasysym}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Saturday, December 07, 2019 17:42:23}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{ComputeDefs=
%$A=\left(
%\begin{array}
%[c]{cccc}%
%1 & 5 & 2 & 8\\
%-1 & -5 & 1 & 1\\
%1 & 5 & 1 & 5
%\end{array}
%\right)  $
%$\phi=\dfrac{1+\sqrt{5}}{2}$
%$\psi=\dfrac{1-\sqrt{5}}{2}$
%$U=\left(
%\begin{array}
%[c]{cc}%
%1 & 1\\
%1 & -1
%\end{array}
%\right)  $
%$D=\left(
%\begin{array}
%[c]{cc}%
%2 & 0\\
%0 & 0
%\end{array}
%\right)  $
%}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows}
\newcounter{exer}
\newcounter{exera}
\numberwithin{exer}{subsection}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[subsection]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{teachingnote}[1][Teaching note]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\newenvironment{teachingnote}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\excludecomment{teachingnote}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\lf}[2]{#1^{\underline{#2}}}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\nnn}{\nonumber\\}
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}}
\allowdisplaybreaks
\iffalse
\UNEXPAND{\today}{\today}
\fi
\ihead{Fall 2019 Math 201-003 at Drexel: blackboard notes of 2019-12-04}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{Fall 2019 Math 201-003 at Drexel: blackboard notes of 2019-12-04}
\author{Darij Grinberg}
\date{\today}
\maketitle

\section{Vector spaces}

\subsection{Finite-dimensional vector spaces and dimension (continued)}

As before, $\mathbb{K}$ denotes a field.

Recall the following from last lecture:

\begin{definition}
Let $V$ be a vector space. We say that $V$ is \textbf{finite-dimensional} (for
short, \textbf{fin-dim}) if there exists a finite list of vectors $\left(
v_{1},v_{2},\ldots,v_{k}\right)  $ that spans $V$.
\end{definition}

\begin{theorem}
[Steinitz's theorem]Let $V$ be a vector space. Let $n\in\mathbb{N}$. Let
$v_{1},v_{2},\ldots,v_{n}$ be $n$ vectors in $V$. Then, any $n+1$ combinations
of $v_{1},v_{2},\ldots,v_{n}$ are dependent.
\end{theorem}

We proved this theorem last time. Now, let us draw some consequences from it:

\begin{definition}
Let $V$ be a fin-dim vector space. Then, the \textbf{dimension} of $V$ is
defined to be the smallest length of a list of vectors $\left(  v_{1}%
,v_{2},\ldots,v_{k}\right)  $ that spans $V$.

We denote the dimension of $V$ by $\dim V$.
\end{definition}

(The \textbf{length} of a list is simply its number of entries. For example,
the list $\left(  3,2,4,4,4\right)  $ of numbers has length $5$.)

Next, let us define the notion of a basis of a vector space. This is just a
straightforward generalization of how we defined a basis of $\mathbb{R}^{n}$
(in \href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{the
class notes from 2019-10-09}):

\begin{definition}
Let $V$ be a vector space. A \textbf{basis} of $V$ means a list $\left(
v_{1},v_{2},\ldots,v_{m}\right)  $ of vectors in $V$ that is both independent
and spans $V$.
\end{definition}

Let us also define \textquotedblleft spanning lists\textquotedblright\ and
\textquotedblleft independent lists\textquotedblright\ (just shorthands for
lists that span $V$ or are linearly independent, respectively):

\begin{definition}
Let $V$ be a vector space. A \textbf{spanning list} of $V$ means a list
$\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ of vectors in $V$ that spans $V$.
We shall also use \textquotedblleft spanning\textquotedblright\ as an
adjective (i.e., we say that a list $\left(  v_{1},v_{2},\ldots,v_{m}\right)
$ of vectors in $V$ is \textbf{spanning} if it is a spanning list).
\end{definition}

\begin{definition}
Let $V$ be a vector space. An \textbf{independent list} of $V$ means a list
$\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ of vectors in $V$ that is independent.
\end{definition}

Thus, a basis of a vector space $V$ is the same as an independent list that is
a spanning list at the same time.

\begin{theorem}
\label{thm.vs.span-ind-bas}Let $V$ be a fin-dim vector space with $\dim V=n$.

\textbf{(a)} Any spanning list of $V$ can be shrunk to a basis.
(\textquotedblleft Shrinking\textquotedblright\ a list of vectors\ means
removing some vectors from it. The word \textquotedblleft
some\textquotedblright\ includes the options \textquotedblleft
none\textquotedblright\ and \textquotedblleft all\textquotedblright. For
example, shrinking $\left(  v_{1},v_{2},v_{3},v_{4}\right)  $ can lead to
$\left(  v_{1},v_{3}\right)  $ or to $\left(  v_{2},v_{3},v_{4}\right)  $ or
to the empty list $\left(  {}\right)  $ or to the full list $\left(
v_{1},v_{2},v_{3},v_{4}\right)  $.)

\textbf{(b)} Any independent list of $V$ can be extended to a basis.
(\textquotedblleft Extending\textquotedblright\ a list of vectors means
inserting some new vectors at the end of it. Again, \textquotedblleft
some\textquotedblright\ includes the option \textquotedblleft
none\textquotedblright.)

\textbf{(c)} Any basis of $V$ has length $n$.

\textbf{(d)} There exists a basis of $V$.

\textbf{(e)} Any spanning list of $V$ has length $\geq n$.

\textbf{(f)} Any spanning list of $V$ that has length $n$ must be a basis of
$V$.

\textbf{(g)} Any independent list of $V$ has length $\leq n$.

\textbf{(h)} Any independent list of $V$ that has length $n$ must be a basis
of $V$.
\end{theorem}

\begin{proof}
\textbf{(e)} Recall that $\dim V=n$. Hence, the definition of dimension shows
that $n$ is the smallest length of a spanning list of $V$. So any spanning
list of $V$ has length $\geq n$.

\textbf{(a)} Let us first prove the following fact:

\begin{statement}
\textit{Fact 1:} If a spanning list of $V$ is dependent, then there is a
vector in it that we can remove and still obtain a spanning list of $V$.
\end{statement}

[\textit{Proof of Fact 1:} Let $\left(  v_{1},v_{2},\ldots,v_{k}\right)  $ be
a spanning list of $V$ that is dependent. Thus, Proposition 1.1.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-25.pdf}{the class
notes from 2019-11-25} shows that one of $v_{1},v_{2},\ldots,v_{k}$ is a
combination of the others. Let $v_{i}$ be this one vector. Thus,%
\[
v_{i}=\alpha_{1}v_{1}+\alpha_{2}v_{2}+\cdots+\alpha_{i-1}v_{i-1}+\alpha
_{i+1}v_{i+1}+\cdots+\alpha_{k}v_{k}%
\]
for some scalars $\alpha_{j}\in\mathbb{K}$. Now, I claim that $\left(
v_{1},v_{2},\ldots,v_{i-1},v_{i+1},\ldots,v_{k}\right)  $ is a spanning list
of $V$.

Indeed, $\left(  v_{1},v_{2},\ldots,v_{k}\right)  $ is a spanning list of $V$.
Hence, every vector in $V$ is a combination of $v_{1},v_{2},\ldots,v_{k}$. In
other words, every vector in $V$ can be written as%
\begin{align*}
&  \lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k}v_{k}\\
&  =\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{i-1}v_{i-1}\\
&  \ \ \ \ \ \ \ \ \ \ +\lambda_{i}\underbrace{v_{i}}_{=\alpha_{1}v_{1}%
+\alpha_{2}v_{2}+\cdots+\alpha_{i-1}v_{i-1}+\alpha_{i+1}v_{i+1}+\cdots
+\alpha_{k}v_{k}}\\
&  \ \ \ \ \ \ \ \ \ \ +\lambda_{i+1}v_{i+1}+\cdots+\lambda_{k}v_{k}\\
&  =\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{i-1}v_{i-1}\\
&  \ \ \ \ \ \ \ \ \ \ +\lambda_{i}\left(  \alpha_{1}v_{1}+\alpha_{2}%
v_{2}+\cdots+\alpha_{i-1}v_{i-1}+\alpha_{i+1}v_{i+1}+\cdots+\alpha_{k}%
v_{k}\right) \\
&  \ \ \ \ \ \ \ \ \ \ +\lambda_{i+1}v_{i+1}+\cdots+\lambda_{k}v_{k}\\
&  =\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{i-1}v_{i-1}\\
&  \ \ \ \ \ \ \ \ \ \ +\lambda_{i}\alpha_{1}v_{1}+\lambda_{i}\alpha_{2}%
v_{2}+\cdots+\lambda_{i}\alpha_{i-1}v_{i-1}+\lambda_{i}\alpha_{i+1}%
v_{i+1}+\cdots+\lambda_{i}\alpha_{k}v_{k}\\
&  \ \ \ \ \ \ \ \ \ \ +\lambda_{i+1}v_{i+1}+\cdots+\lambda_{k}v_{k}\\
&  =\left(  \lambda_{1}+\lambda_{i}\alpha_{1}\right)  v_{1}+\left(
\lambda_{2}+\lambda_{i}\alpha_{2}\right)  v_{2}+\cdots+\left(  \lambda
_{i-1}+\lambda_{i}\alpha_{i-1}\right)  v_{i-1}\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \lambda_{i+1}+\lambda_{i}\alpha_{i+1}\right)
v_{i+1}+\cdots+\left(  \lambda_{k}+\lambda_{i}\alpha_{k}\right)  v_{k},
\end{align*}
which means that it is a combination of $v_{1},v_{2},\ldots,v_{i-1}%
,v_{i+1},\ldots,v_{k}$. Thus, \newline$\left(  v_{1},v_{2},\ldots
,v_{i-1},v_{i+1},\ldots,v_{k}\right)  $ is a spanning list of $V$. This proves
Fact 1.]

Now, start with any spanning list of $V$. Fact 1 shows that if this list is
dependent, then we can shrink it by removing some vector from it and still
obtain a spanning list. By iterating this, we can keep shrinking our spanning
list further and further until it becomes independent. This procedure cannot
go on forever, because the list gets shorter by $1$ at each step. Thus, this
procedure must eventually come to an end. At the end, we obtain a spanning
list of $V$ that is independent -- i.e., a basis of $V$.

\textbf{(d)} Since $V$ is fin-dim, we know that $V$ has a spanning list. Thus,
part \textbf{(a)} yields that we can shrink this spanning list to a basis.
Hence, $V$ has a basis.

\textbf{(g)} Assume the contrary. Thus, there is an independent list of length
$>n$. This independent list must thus have length $\geq n+1$. Hence, there is
an independent list of length $n+1$ (since any sublist of an independent list
is still an independent list).

On the other hand, there exists a spanning list $\left(  v_{1},v_{2}%
,\ldots,v_{n}\right)  $ of $V$ that has length $n$ (since $n=\dim V$). Thus,
each vector in $V$ is a combination of $v_{1},v_{2},\ldots,v_{n}$. But
Steinitz's theorem shows that any $n+1$ combinations of $v_{1},v_{2}%
,\ldots,v_{n}$ are dependent. In other words, any $n+1$ vectors in $V$ are
dependent (since each vector in $V$ is a combination of $v_{1},v_{2}%
,\ldots,v_{n}$). This contradicts the fact that there is an independent list
of length $n+1$.

This contradiction shows that our assumption was wrong. Thus, Theorem
\ref{thm.vs.span-ind-bas} \textbf{(g)} is proved.

\textbf{(b)} Let us first prove the following fact:

\begin{statement}
\textit{Fact 2:} If an independent list of $V$ is not spanning, then there is
a vector in $V$ that we can insert into this list and still obtain an
independent list of $V$.
\end{statement}

[\textit{Proof of Fact 2:} Let $\left(  v_{1},v_{2},\ldots,v_{k}\right)  $ be
an independent list of $V$ that is not spanning. Thus, there exists a vector
$v\in V$ that is \textbf{not} a combination of $v_{1},v_{2},\ldots,v_{k}$.
Hence, Proposition 1.1.2
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-25.pdf}{the class
notes from 2019-11-25} shows that the $k+1$ vectors $v_{1},v_{2},\ldots
,v_{k},v$ are independent. Thus, we can insert the vector $v$ into our list
$\left(  v_{1},v_{2},\ldots,v_{k}\right)  $ and still obtain an independent
list of $V$. This proves Fact 2.]

Now, start with any independent list of $V$. Fact 2 shows that if this list is
not spanning, then we can extend it by adding some vector to it and still
obtain an independent list. By iterating this, we can keep expanding our
independent list further and further until it becomes spanning. This procedure
cannot go on forever, because the list gets longer by $1$ at each step, but
part \textbf{(g)} shows that it cannot become longer than $n$ (without losing
its independence). Thus, this procedure must eventually come to an end. At the
end, we obtain an independent list of $V$ that is spanning -- i.e., a basis of
$V$.

\textbf{(c)} A basis of $V$ is simultaneously a spanning list and an
independent list. Hence, part \textbf{(e)} shows that its length is $\geq n$,
while part \textbf{(g)} shows that its length is $\leq n$. Combining these, we
conclude that its length is $n$.

\textbf{(f)} Let $\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ be a spanning
list of $V$ that has length $n$. Then, part \textbf{(a)} shows that we can
shrink this list to a basis $\mathbf{b}$ of $V$. But this latter basis
$\mathbf{b}$ must, too, have length $n$ (by part \textbf{(c)}). But the only
way to get a length-$n$ list by shrinking a length-$n$ list is to leave it
unchanged (i.e., to remove no entries)\footnote{since any removal of entries
would make it shorter}. Thus, we must have obtained our basis $\mathbf{b}$
from our spanning list $\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ by leaving
it unchanged. Hence, $\mathbf{b}=\left(  v_{1},v_{2},\ldots,v_{n}\right)  $.
Thus, the original list $\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ is a basis
of $V$ (since $\mathbf{b}$ is a basis of $V$).

\textbf{(h)} This is proved similarly to part \textbf{(f)}, but using part
\textbf{(b)} instead of \textbf{(a)}.
\end{proof}

\begin{example}
Let $n\in\mathbb{N}$. The vector space $\mathbb{K}^{n}$ (of column vectors of
size $n$) has dimension $n$.

To see this, let us construct a basis of $\mathbb{K}^{n}$:

For each $i\in\left\{  1,2,\ldots,n\right\}  $, let $e_{i}$ be the vector
$\left(  0,0,\ldots,0,1,0,0,\ldots,0\right)  ^{T}$ (with the $1$ being placed
in position $i$). Then, $\left(  e_{1},e_{2},\ldots,e_{n}\right)  $ is a basis
of $\mathbb{K}^{n}$, known as the \textbf{standard basis} of $\mathbb{K}^{n}$.
Thus, Theorem \ref{thm.vs.span-ind-bas} \textbf{(c)} shows that the dimension
of $\mathbb{K}^{n}$ is $n$ (since this basis has length $n$).
\end{example}

\begin{example}
Let $n,m\in\mathbb{N}$. The vector space $\mathbb{K}^{n\times m}$ (of $n\times
m$-matrices) has dimension $nm$.

Indeed, we can construct a basis as follows:

For each $i\in\left\{  1,2,\ldots,n\right\}  $ and $j\in\left\{
1,2,\ldots,m\right\}  $, we let $E_{i,j}$ be the $n\times m$-matrix whose
$\left(  i,j\right)  $-th entry is $1$ and whose all other entries are $0$.
For example, if $n=4$ and $m=5$, then%
\[
E_{2,3}=\left(
\begin{array}
[c]{ccccc}%
0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0
\end{array}
\right)  .
\]
This $E_{i,j}$ is called the $\left(  i,j\right)  $\textbf{-th matrix unit}.
There is a total of $nm$ matrix units in $\mathbb{K}^{n\times m}$. Listing up
all these $nm$ matrix units, we obtain a basis of $\mathbb{K}^{n\times m}$.
Since this basis has length $nm$, we conclude that the dimension of
$\mathbb{K}^{n\times m}$ is $nm$.

Let us show this basis in full in the case $n=2$ and $m=2$: In this case, we
have%
\begin{align*}
E_{1,1}  &  =\left(
\begin{array}
[c]{cc}%
1 & 0\\
0 & 0
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ E_{1,2}=\left(
\begin{array}
[c]{cc}%
0 & 1\\
0 & 0
\end{array}
\right)  ,\\
E_{2,1}  &  =\left(
\begin{array}
[c]{cc}%
0 & 0\\
1 & 0
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ E_{2,2}=\left(
\begin{array}
[c]{cc}%
0 & 0\\
0 & 1
\end{array}
\right)  .
\end{align*}
Thus, the list $\left(  E_{1,1},E_{1,2},E_{2,1},E_{2,2}\right)  $ is a basis
of the $4$-dimensional vector space $\mathbb{K}^{2\times2}$.
\end{example}

\begin{example}
Fix $k\in\mathbb{N}$. Let $P_{k}$ be the $\mathbb{R}$-vector space of
polynomials of degree $\leq k$ with real coefficients. Thus,%
\[
P_{k}=\left\{  a_{0}+a_{1}x+a_{2}x^{2}+\cdots+a_{k}x^{k}\ \mid\ a_{0}%
,a_{1},\ldots,a_{k}\in\mathbb{R}\right\}  .
\]
We have $\dim P_{k}=k+1$. Indeed, the list $\left(  1,x,x^{2},\ldots
,x^{k}\right)  $ of length $k+1$ is a basis of $P_{k}$.
\end{example}

The next two examples show that one and the same set can underlie two
different vector spaces of two different dimensions:

\begin{example}
Recall that $\mathbb{C}$ is an $\mathbb{R}$-vector space. Its dimension is
$2$, since the list $\left(  1,i\right)  $ is a basis of this vector space.
\end{example}

\begin{example}
Recall that $\mathbb{C}$ is a $\mathbb{C}$-vector space. Its dimension is $1$,
since the list $\left(  1\right)  $ is a basis of this vector space. More
generally, any field $\mathbb{K}$ is a $\mathbb{K}$-vector space of dimension
$1$, with basis $\left(  1\right)  $.
\end{example}

\begin{proposition}
\label{prop.vs.sub-fin-dim}\textbf{(a)} Any subspace of a fin-dim vector space
is fin-dim.

\textbf{(b)} If $U$ is a subspace of a fin-dim vector space $V$, then $U$ is
fin-dim and satisfies $\dim U\leq\dim V$.

\textbf{(c)} If $U$ is a subspace of a fin-dim vector space $V$ that satisfies
$\dim U=\dim V$, then $U=V$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.vs.sub-fin-dim} (sketched).]\textbf{(b)} Let
$U$ be a subspace of a fin-dim vector space $V$.

Let $n=\dim V$. Any independent list of $U$ is clearly an independent list of
$V$, and thus has length $\leq n$ (by Theorem \ref{thm.vs.span-ind-bas}
\textbf{(g)}). Now, we claim:

\begin{statement}
\textit{Claim 1:} Any independent list of $U$ can be extended to a basis of
$U$.
\end{statement}

[\textit{Proof of Claim 1:} If we knew that $U$ is fin-dim, then this would
follow from Theorem \ref{thm.vs.span-ind-bas} \textbf{(b)} (applied to $U$
instead of $V$). But we don't know yet that $U$ is fin-dim. Nevertheless, we
can apply the same argument that we used to prove Theorem
\ref{thm.vs.span-ind-bas} \textbf{(b)} to $U$ instead of $V$. The only
difference is that we need a new reason why the procedure (of gradually
extending our list by inserting new vectors into it) cannot go on forever. But
we have such a reason: We know that any independent list of $U$ has length
$\leq n$; thus, we cannot insert more than $n$ vectors into our list without
breaking its independence. Thus, Claim 1 is proved.]

But the empty list $\left(  {}\right)  $ is clearly an independent list of
$U$. Thus, Claim 1 shows that this empty list $\left(  {}\right)  $ can be
extended to a basis of $U$. Hence, there exists a basis of $U$. Thus, $U$ is
fin-dim (since a basis of $U$ is clearly a list of vectors that spans $U$).

To prove that $\dim U\leq\dim V$, we start with a basis of $U$ and expand it
to a basis of $V$ (Theorem \ref{thm.vs.span-ind-bas} \textbf{(b)} tells us
that we can do this, since any basis of $U$ is an independent list of $V$).
Since a list can only grow in length when it is being expanded, we thus
conclude that the length of our basis of $U$ is $\leq$ to the length of our
basis of $V$. In other words, $\dim U\leq\dim V$ (since Theorem
\ref{thm.vs.span-ind-bas} \textbf{(c)} shows that the dimension of a fin-dim
vector space is the length of any basis).

\textbf{(a)} This is just the first half of part \textbf{(b)}.

\textbf{(c)} Left to the reader.
\end{proof}

\begin{example}
Here are the subspaces of $\mathbb{R}^{3}$ again:

\begin{itemize}
\item The one-element subspace $\left\{  \overrightarrow{0}\right\}  $. This
has dimension $0$.

\item The lines through the origin. They have dimension $1$.

\item The planes through the origin. They have dimension $2$.

\item The whole space $\mathbb{R}^{3}$. It has dimension $3$.
\end{itemize}
\end{example}

\begin{remark}
The notions of \textquotedblleft basis\textquotedblright\ and of
\textquotedblleft dimension\textquotedblright\ can be extended even to vector
spaces that are not fin-dim. But this would require modifying them (e.g., the
dimension would not longer be a nonnegative integer, but rather a cardinal
number). If we did that, we would be able to claim one of the most celebrated
results of linear algebra: Every vector space has a basis (in the extended
sense of the word).
\end{remark}

\subsection{The fundamental subspaces of a matrix}

Any matrix gives rise to four interesting subspaces:

\begin{definition}
\label{def.vs.mat.four-subs}Let $n,m\in\mathbb{N}$. Let $A\in\mathbb{K}%
^{n\times m}$ be an $n\times m$-matrix.

\textbf{(a)} We define the \textbf{column space} of $A$ to be
\[
\operatorname*{Col}A=\left(  \text{the span of the columns of }A\right)
=\left\{  Av\ \mid\ v\in\mathbb{K}^{m\times1}\right\}  .
\]


\textbf{(b)} We define the \textbf{row space} of $A$ to be%
\[
\operatorname*{Row}A=\left(  \text{the span of the rows of }A\right)
=\left\{  wA\ \mid\ w\in\mathbb{K}^{1\times n}\right\}  .
\]


\textbf{(c)} We define the \textbf{kernel} (or \textbf{nullspace}) of $A$ to
be%
\[
\operatorname*{Ker}A=\left\{  v\in\mathbb{K}^{m\times1}\ \mid\ Av=0_{n\times
1}\right\}  .
\]


\textbf{(d)} We define the \textbf{left kernel} (or \textbf{left nullspace})
of $A$ to be%
\[
\operatorname*{LKer}A=\left\{  w\in\mathbb{K}^{1\times n}\ \mid\ wA=0_{1\times
m}\right\}  .
\]

\end{definition}

It is easy to see:

\begin{proposition}
The four sets we just defined are subspaces of the respective vector spaces:

\begin{itemize}
\item $\operatorname*{Col}A$ is a subspace of $\mathbb{K}^{n\times1}$.

\item $\operatorname*{Row}A$ is a subspace of $\mathbb{K}^{1\times m}$.

\item $\operatorname*{Ker}A$ is a subspace of $\mathbb{K}^{m\times1}$.

\item $\operatorname*{LKer}A$ is a subspace of $\mathbb{K}^{1\times n}$.
\end{itemize}

Moreover, the equality signs in parts \textbf{(a)} and \textbf{(b)} of
Definition \ref{def.vs.mat.four-subs} hold.
\end{proposition}

These four sets are called the \textbf{four fundamental subspaces} of the
matrix $A$.

Note that $\operatorname*{Ker}A$ is the set of all solutions to the system of
equations $Av=0$. Gaussian elimination yields a basis of $\operatorname*{Ker}%
A$.

\subsection{The rank of a matrix}

\begin{definition}
The \textbf{rank} of a matrix $A\in\mathbb{K}^{n\times m}$ is defined to be
$\dim\left(  \operatorname*{Col}A\right)  $. It is denoted by
$\operatorname*{rank}A$.
\end{definition}

The following theorem is far from obvious (see, e.g., \cite[\S 22]{Strickland}
for proofs of some of its parts\footnote{Note that \cite[\S 22]{Strickland}
writes $\operatorname{img}\left(  A\right)  $ for what we call
$\operatorname*{Col}A$, and writes $\ker\left(  A\right)  $ for what we call
$\operatorname*{Ker}A$.}):

\begin{theorem}
\label{thm.rank.abcde}Let $A$ be an $n\times m$-matrix.

\textbf{(a)} We have $\operatorname*{rank}A=\dim\left(  \operatorname*{Col}%
A\right)  =\dim\left(  \operatorname*{Row}A\right)  $.

\textbf{(b)} We have $\operatorname*{rank}A=\operatorname*{rank}\left(
A^{T}\right)  $.

\textbf{(c)} We have $\dim\left(  \operatorname*{Ker}A\right)
=m-\operatorname*{rank}A$ and $\dim\left(  \operatorname*{LKer}A\right)
=n-\operatorname*{rank}A$.

\textbf{(d)} We have $\operatorname*{rank}A=\left(  \text{\# of pivots in the
RREF of }A\right)  $.
\end{theorem}

For the next theorem, we need the notion of \textbf{column operations}:

\begin{definition}
We define \textbf{column operations}\ in the same way as we defined row
operations, just replacing each word \textquotedblleft row\textquotedblright%
\ by \textquotedblleft column\textquotedblright. Thus, the column operations
are the following operations on a matrix:

\begin{itemize}
\item \textbf{ECO1:} Exchange two columns.

\item \textbf{ECO2:} Scale a column by a nonzero constant.

\item \textbf{ECO3:} Add a multiple of a column to another column.
\end{itemize}
\end{definition}

Now, we state the theorem (whose proof can be found in \cite[Proposition
22.11]{Strickland}\footnote{What we call \textquotedblleft rank normal
form\textquotedblright\ is being just called \textquotedblleft normal
form\textquotedblright\ in \cite[\S 22]{Strickland}.}):

\begin{theorem}
\label{thm.rank.norf}Let $A$ be an $n\times m$-matrix. By a sequence of row
\textbf{and} column operations, we can transform $A$ into what is called the
\textbf{rank normal form}: an $n\times m$-matrix whose \textquotedblleft
diagonal\textquotedblright\ entries (i.e., the entries in cells $\left(
1,1\right)  ,\left(  2,2\right)  ,\ldots,\left(  k,k\right)  $, where
$k=\min\left\{  n,m\right\}  $) are%
\[
\underbrace{1,1,\ldots,1}_{\operatorname*{rank}A\text{ many }1\text{'s}%
},0,0,\ldots,0\ \ \ \ \ \ \ \ \ \ \left(  \text{in this order}\right)
\]
and whose all other entries are $0$.
\end{theorem}

\begin{example}
Here is an example for Theorem \ref{thm.rank.norf}:

Let $A$ be the $3\times4$-matrix $\left(
\begin{array}
[c]{cccc}%
1 & 5 & 2 & 8\\
-1 & -5 & 1 & 1\\
1 & 5 & 1 & 5
\end{array}
\right)  $ over the field $\mathbb{Q}$. Its rank is $\operatorname*{rank}A=2$.
Thus, Theorem \ref{thm.rank.norf} claims that by a sequence of row and column
operations, we can transform $A$ into the rank normal form -- i.e., into the
matrix $\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 0
\end{array}
\right)  $ (since $\operatorname*{rank}A=2$).

Let us see how to actually do this. First, we know how to transform $A$ into
RREF using row operations:%
\[
A=\left(
\begin{array}
[c]{cccc}%
1 & 5 & 2 & 8\\
-1 & -5 & 1 & 1\\
1 & 5 & 1 & 5
\end{array}
\right)  \overset{%
\begin{array}
[c]{c}%
\text{a sequence of}\\
\text{row operations}%
\end{array}
}{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 5 & 0 & 2\\
0 & 0 & \fbox{$1$} & 3\\
0 & 0 & 0 & 0
\end{array}
\right)  .
\]
(As usual, the pivots are boxed.) Now, let us use column operations
(specifically, ECO3) to clear out the nonzero entries to the right of the
pivots:%
\begin{align*}
&  \left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 5 & 0 & 2\\
0 & 0 & \fbox{$1$} & 3\\
0 & 0 & 0 & 0
\end{array}
\right)  \underset{\text{from column }2}{\overset{\text{subtract }%
5\cdot\text{column }1}{\longrightarrow}}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & 0 & 2\\
0 & 0 & \fbox{$1$} & 3\\
0 & 0 & 0 & 0
\end{array}
\right) \\
&  \underset{\text{from column }4}{\overset{\text{subtract }2\cdot\text{column
}1}{\longrightarrow}}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & 0 & 0\\
0 & 0 & \fbox{$1$} & 3\\
0 & 0 & 0 & 0
\end{array}
\right)  \underset{\text{from column }4}{\overset{\text{subtract }%
3\cdot\text{column }3}{\longrightarrow}}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & 0 & 0\\
0 & 0 & \fbox{$1$} & 0\\
0 & 0 & 0 & 0
\end{array}
\right)  .
\end{align*}
We have obtained a matrix whose only nonzero entries are its pivots. Finally,
we use column operations (specifically, ECO1) in order to put the pivots into
the first two columns:%
\[
\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & 0 & 0\\
0 & 0 & \fbox{$1$} & 0\\
0 & 0 & 0 & 0
\end{array}
\right)  \overset{\text{swap columns }2\text{ and }3}{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & 0 & 0\\
0 & \fbox{$1$} & 0 & 0\\
0 & 0 & 0 & 0
\end{array}
\right)  .
\]
This is the rank normal form of $A$.
\end{example}

(As you might have noticed, column operation ECO2 is not needed in this procedure.)

We notice another important property of the rank:

\begin{proposition}
The rank of a matrix does not change when we apply row operations or column
operations to the matrix.
\end{proposition}

\subsection{Linear maps}

\begin{definition}
Let $V$ and $W$ be two vector spaces (over a field $\mathbb{K}$). Let
$f:V\rightarrow W$ be a map. Then, we say that $f$ is \textbf{linear} if and
only if it satisfies the following three axioms:

\begin{itemize}
\item We have $f\left(  v+w\right)  =f\left(  v\right)  +f\left(  w\right)  $
for all $v,w\in V$.

\item We have $f\left(  \lambda v\right)  =\lambda\cdot f\left(  v\right)  $
for all $\lambda\in\mathbb{K}$ and $v\in V$.

\item We have $f\left(  \overrightarrow{0}\right)  =\overrightarrow{0}$. (More
precisely: Applying $f$ to the zero vector of $V$ yields the zero vector of
$W$.)
\end{itemize}
\end{definition}

Linear maps are also called \textbf{homomorphisms of vector spaces}. (Hefferon
uses this latter terminology in \cite{Heffer16}.)

\begin{example}
Let $m,n\in\mathbb{N}$. Let $A\in\mathbb{K}^{n\times m}$. Then, we define the
map%
\begin{align*}
L_{A}:\mathbb{K}^{m}  &  \rightarrow\mathbb{K}^{n},\\
v  &  \mapsto Av.
\end{align*}
This map $L_{A}$ is linear, because:

\begin{itemize}
\item For all $v,w\in\mathbb{K}^{m}$, we have%
\[
L_{A}\left(  v+w\right)  =A\left(  v+w\right)  =Av+Aw=L_{A}\left(  v\right)
+L_{A}\left(  w\right)  .
\]


\item For all $\lambda\in\mathbb{K}$ and $v\in\mathbb{K}^{m}$, we have%
\[
L_{A}\left(  \lambda v\right)  =A\left(  \lambda v\right)  =\lambda\cdot
Av=\lambda\cdot L_{A}\left(  v\right)  .
\]


\item We have%
\[
L_{A}\left(  0_{m\times1}\right)  =A\cdot0_{m\times1}=0_{n\times1}.
\]

\end{itemize}

Moreover, it can be showed that \textbf{any} linear map from $\mathbb{K}^{m}$
to $\mathbb{K}^{n}$ has the form $L_{A}$ for an $n\times m$-matrix $A$.
\end{example}

Thus, the linear maps from $\mathbb{K}^{m}$ to $\mathbb{K}^{n}$ are in 1-to-1
correspondence with the $n\times m$-matrices over $\mathbb{K}$. Linear maps in
general (i.e., not just between $\mathbb{K}^{m}$ and $\mathbb{K}^{n}$) can
thus be regarded as \textquotedblleft generalized matrices\textquotedblright.

A straightforward computation proves the following proposition:

\begin{proposition}
Let $A$ be an $n\times m$-matrix. Let $B$ be an $m\times p$-matrix. Then,%
\[
L_{AB}=L_{A}\circ L_{B}.
\]

\end{proposition}

This proposition motivates the definition of the product of two matrices: it
was tailored to correspond to the composition of the corresponding linear maps.

When a matrix $A$ is invertible, left-invertible or right-invertible, what
does this mean for the corresponding map $L_{A}$? The following proposition
(whose proof we, again, omit) answers this question:

\begin{proposition}
Let $A$ be an $n\times m$-matrix. Then:

\textbf{(a)} The matrix $A$ is invertible if and only if the map $L_{A}$ is
invertible (i.e., bijective). Moreover, if $B$ is the inverse of $A$, then
$L_{B}$ is the inverse of $L_{A}$.

\textbf{(b)} The matrix $A$ is left-invertible if and only if the map $L_{A}$
is injective.

\textbf{(c)} The matrix $A$ is right-invertible if and only if the map $L_{A}$
is surjective.
\end{proposition}

Here are some more examples of linear maps.

\begin{example}
Let $V$ be any vector space. Then, the identity map $\operatorname*{id}%
:V\rightarrow V$ is always linear. Also linear are the maps%
\[
V\rightarrow V,\ \ \ \ \ \ \ \ \ \ v\mapsto0
\]
and%
\[
V\rightarrow V,\ \ \ \ \ \ \ \ \ \ v\mapsto-v.
\]
More generally, for any $\lambda\in\mathbb{R}$, the map%
\[
V\rightarrow V,\ \ \ \ \ \ \ \ \ \ v\mapsto\lambda v
\]
is linear.
\end{example}

\begin{example}
Let $P$ be the $\mathbb{R}$-vector space of all polynomials in one variable
$x$ with real coefficients.

\textbf{(a)} The map $P\rightarrow P,\ f\mapsto f+1$ is \textbf{not} linear.
(Indeed, for example, it fails to send $0$ to $0$.)

\textbf{(b)} The map $P\rightarrow P,\ f\mapsto f^{2}$ is \textbf{not} linear.
(Indeed, for example, it fails to satisfy the first axiom, since two
polynomials $f$ and $g$ do not usually satisfy $\left(  f+g\right)  ^{2}%
=f^{2}+g^{2}$.)

\textbf{(c)} The map $P\rightarrow P,\ f\mapsto f\left(  0\right)  $ is
linear. (Because, for example, $\left(  f+g\right)  \left(  0\right)
=f\left(  0\right)  +g\left(  0\right)  $ for any two polynomials $f$ and $g$.)

\textbf{(d)} The map $P\rightarrow P,\ f\mapsto f^{\prime}=\dfrac{d}{dx}f$ is
linear. (Because, for example, $\left(  f+g\right)  ^{\prime}=f^{\prime
}+g^{\prime}$ for any two polynomials $f$ and $g$.)

\textbf{(e)} The map $P\rightarrow P,\ f\mapsto x\cdot f$ is linear.
\end{example}

\subsection{Representing linear maps by matrices}

We have seen above that the linear maps from $\mathbb{K}^{m}$ to
$\mathbb{K}^{n}$ correspond to $n\times m$-matrices. But even more generally,
linear maps between fin-dim vector spaces correspond to matrices, although we
need to choose bases of both domain and codomain in order to set up the
correspondence (and the correspondence we obtain will depend on the basis we
chose). Here is how this works:

\begin{definition}
Let $V$ and $W$ be two fin-dim vector spaces.

Let $\mathbf{v}=\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ be a basis of $V$.

Let $\mathbf{w}=\left(  w_{1},w_{2},\ldots,w_{n}\right)  $ be a basis of $W$.

Let $f:V\rightarrow W$ be a linear map.

The \textbf{matrix repesenting }$f$ \textbf{with respect to the bases
}$\mathbf{v}$ \textbf{and }$\mathbf{w}$ is the $n\times m$-matrix
$M_{\mathbf{v},\mathbf{w},f}$ defined as follows: For each $j\in\left\{
1,2,\ldots,m\right\}  $, we write the vector $f\left(  v_{j}\right)  $ as a
linear combination of the vectors $w_{1},w_{2},\ldots,w_{n}$ as follows:%
\[
f\left(  v_{j}\right)  =a_{1,j}w_{1}+a_{2,j}w_{2}+\cdots+a_{n,j}w_{n}.
\]
Then, $M_{\mathbf{v},\mathbf{w},f}$ is defined to be the $n\times m$-matrix
$\left(  a_{i,j}\right)  _{1\leq i\leq n,\ 1\leq j\leq m}$. (Note that the
coefficients $a_{i,j}$ exist and are uniquely determined, since $\mathbf{w}%
=\left(  w_{1},w_{2},\ldots,w_{n}\right)  $ is a basis of $W$.)
\end{definition}

Note that Hefferon, in \cite{Heffer16}, denotes this matrix $M_{\mathbf{v}%
,\mathbf{w},f}$ by $\operatorname*{Rep}\nolimits_{\mathbf{v},\mathbf{w}%
}\left(  f\right)  $.

The point of this construction is: Unlike the map $f$, the matrix
$M_{\mathbf{v},\mathbf{w},f}$ is a finite object that we can calculate with.
It uniquely determines $f$ (as long as $\mathbf{v}$ and $\mathbf{w}$ are known).

This way of constructing a matrix $M_{\mathbf{v},\mathbf{w},f}$ from a linear
map $f$ is inverse to the above construction of a linear map $L_{A}$ from a
matrix $A$, if the bases are chosen appropriately.

\begin{proposition}
Let $m,n\in\mathbb{N}$. Let $\mathbf{e}=\left(  e_{1},e_{2},\ldots
,e_{m}\right)  $ be the standard basis of $\mathbb{K}^{m}$. Let $\mathbf{f}$
be the standard basis of $\mathbb{K}^{n}$. Let $h:\mathbb{K}^{m}%
\rightarrow\mathbb{K}^{n}$ be a linear map, and let $A\in\mathbb{K}^{n\times
m}$ be an $n\times m$-matrix. Then, we have the following equivalence:%
\[
\left(  M_{\mathbf{e},\mathbf{f},h}=A\right)  \ \Longleftrightarrow\ \left(
h=L_{A}\right)  .
\]

\end{proposition}

Also, composition of linear maps corresponds to multiplication of the matrices
representing them, provided that we choose the \textquotedblleft
right\textquotedblright\ bases for it:

\begin{theorem}
Let $U$, $V$ and $W$ be three fin-dim vector spaces. Let $f:V\rightarrow W$
and $g:U\rightarrow V$ be two linear maps. Let $\mathbf{u}$, $\mathbf{v}$ and
$\mathbf{w}$ be bases of $U$, $V$ and $W$, respectively. Then,%
\[
M_{\mathbf{v},\mathbf{w},f}\circ M_{\mathbf{u},\mathbf{v},g}=M_{\mathbf{u}%
,\mathbf{w},f\circ g}.
\]

\end{theorem}

Here we have to stop, since the quarter is over.

\textbf{Further reading:}

\begin{itemize}
\item Strickland's \cite[\S 19--\S 22]{Strickland} for a hands-on study of the
subspaces of $\mathbb{R}^{n}$ (including algorithms for finding bases).

\item Strickland's \cite[\S 23]{Strickland} for an introduction to the notions
of orthogonal and symmetric matrices. (This relies on the notion of
\textbf{dot product}, which he defines at the beginning of \cite[\S 3]%
{Strickland}.)

\item Hefferon's \cite{Heffer16} (especially Chapters Two, Three and Five) for
a thorough treatment of vector spaces. (In particular, \cite[\S Five.II]%
{Heffer16} explains diagonalization as finding a basis in which a given linear
map has a particularly simple representation.)
\end{itemize}

\begin{thebibliography}{9999999999}                                                                                       %


\bibitem[Heffer16]{Heffer16}Jim Hefferon, \textit{Linear Algebra}, 3rd edition
2017.\newline\url{http://joshua.smcvt.edu/linearalgebra/}

\bibitem[Strickland]{Strickland}Neil Strickland, \textit{MAS201 Linear
Mathematics for Applications}, lecture notes, 28 September 2013.\newline\url{http://neil-strickland.staff.shef.ac.uk/courses/MAS201/}
\end{thebibliography}


\end{document}