\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=Thursday, December 05, 2019 22:48:37}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%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-10-09}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

\section{Gaussian elimination (continued)}

\subsection{Spanning (continued)}

\subsubsection{Connecting independence and spanning}

Recall our method for checking for linear dependence (\cite[Method
8.8]{Strickland}):

\begin{theorem}
Let $v_{1},v_{2},\ldots,v_{m}$ be $m$ vectors in $\mathbb{R}^{n}$. To see
whether they are dependent, the following algorithm works:

\textbf{(a)} Form the $n\times m$-matrix $A$ whose columns are $v_{1}%
,v_{2},\ldots,v_{m}$. This is usually written as follows:%
\[
A=\left[  v_{1}\mid v_{2}\mid\cdots\mid v_{m}\right]  .
\]


\textbf{(b)} Row-reduce $A$ to get an $n\times m$-matrix $B$ in RREF.

\textbf{(c)} If every column of $B$ has a pivot, then $v_{1},v_{2}%
,\ldots,v_{m}$ are independent.

\textbf{(d)} If some column of $B$ has no pivot, then $v_{1},v_{2}%
,\ldots,v_{m}$ are dependent. Moreover, solutions to the system $B\lambda=0$
(where $\lambda=\left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{m}%
\end{array}
\right)  $) correspond precisely to the relations between $v_{1},v_{2}%
,\ldots,v_{m}$.
\end{theorem}

Recall our method for checking whether a list of vectors spans $\mathbb{R}%
^{n}$ (\cite[Method 9.7]{Strickland}):

\begin{theorem}
Let $\mathcal{V}=\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ be a list of
vectors in $\mathbb{R}^{n}$. We can check whether this list spans
$\mathbb{R}^{n}$ as follows:

\textbf{(a)} Form the $m\times n$-matrix%
\[
C=\left[
\begin{array}
[c]{c}%
v_{1}^{T}\\
v_{2}^{T}\\
\vdots\\
v_{m}^{T}%
\end{array}
\right]  .
\]
This is the matrix whose rows are $v_{1}^{T},v_{2}^{T},\ldots,v_{m}^{T}$ (the
transposes of the vectors in $\mathcal{V}$).

\textbf{(b)} Row-reduce $C$ to get a matrix $D$ in RREF.

\textbf{(c)} If $D$ has a pivot in each column, then $\mathcal{V}$ spans
$\mathbb{R}^{n}$.

\textbf{(d)} If $D$ has no pivot in some column, then $\mathcal{V}$ does not
span $\mathbb{R}^{n}$.
\end{theorem}

Note that the matrix $C$ in the latter theorem is the transpose of the matrix
$A$ in the former theorem. This does not mean that the answers to the
\textquotedblleft are $v_{1},v_{2},\ldots,v_{m}$ dependent?\textquotedblright%
\ and \textquotedblleft do $v_{1},v_{2},\ldots,v_{m}$ span $\mathbb{R}^{n}$
?\textquotedblright\ questions are directly related. However, it means the following:

\begin{proposition}
\label{prop.lind-P-span-PT}Let $P$ be any $m\times n$-matrix.

\textbf{(a)} The columns of $P$ are linearly independent (in $\mathbb{R}^{m}$)
if and only if the columns of $P^{T}$ span $\mathbb{R}^{n}$.

\textbf{(b)} The columns of $P$ span $\mathbb{R}^{m}$ if and only if the
columns of $P^{T}$ are linearly independent (in $\mathbb{R}^{n}$).
\end{proposition}

\begin{proof}
\textbf{(a)} Compare the two previous theorems. If $v_{1},v_{2},\ldots,v_{m}$
are the columns of $P$, then $P=\left[  v_{1}\mid v_{2}\mid\cdots\mid
v_{m}\right]  $ and $P^{T}=\left[
\begin{array}
[c]{c}%
v_{1}^{T}\\
v_{2}^{T}\\
\vdots\\
v_{m}^{T}%
\end{array}
\right]  $. Therefore, the method for checking whether $v_{1},v_{2}%
,\ldots,v_{m}$ are linearly independent does the exact same thing as the
method for checking whether the columns of $P^{T}$ span $\mathbb{R}^{n}$. This
proves \textbf{(a)}.

\textbf{(b)} follows from \textbf{(a)} by applying \textbf{(a)} to $P^{T}$
instead of $P$, since $\left(  P^{T}\right)  ^{T}=P$.
\end{proof}

\subsection{Bases}

\begin{definition}
A \textbf{basis} of $\mathbb{R}^{n}$ means a list $\left(  v_{1},v_{2}%
,\ldots,v_{m}\right)  $ of vectors in $\mathbb{R}^{n}$ that is both
independent and spans $\mathbb{R}^{n}$.
\end{definition}

\begin{example}
Let%
\[
v_{1}=\left(
\begin{array}
[c]{c}%
1\\
1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ v_{2}=\left(
\begin{array}
[c]{c}%
-1\\
1
\end{array}
\right)  .
\]
I claim that $\left(  v_{1},v_{2}\right)  $ is a basis of $\mathbb{R}^{2}$.

Indeed, to see that it is independent, we row-reduce
\[
A=\left[  v_{1}\mid v_{2}\right]  =\left(
\begin{array}
[c]{cc}%
1 & -1\\
1 & 1
\end{array}
\right)  \longrightarrow\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 2
\end{array}
\right)  ;
\]
this has two pivots, so $\left(  v_{1},v_{2}\right)  $ is independent.

To see that it spans $\mathbb{R}^{2}$, we row-reduce%
\[
C=\left[
\begin{array}
[c]{c}%
v_{1}^{T}\\
v_{2}^{T}%
\end{array}
\right]  =\left(
\begin{array}
[c]{cc}%
1 & 1\\
-1 & 1
\end{array}
\right)  \longrightarrow\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 2
\end{array}
\right)  ;
\]
this has two pivots, so $\left(  v_{1},v_{2}\right)  $ spans $\mathbb{R}^{2}$.
\end{example}

\begin{theorem}
\label{thm.span-lind-bas-through-combs}Let $v_{1},v_{2},\ldots,v_{m}$ be
column vectors in $\mathbb{R}^{n}$.

\textbf{(a)} The list $\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ spans
$\mathbb{R}^{n}$ if and only if each $w\in\mathbb{R}^{n}$ can be written as
$w=\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}$ for \textbf{at
least one} $m$-tuple $\left(  \lambda_{1},\lambda_{2},\ldots,\lambda
_{m}\right)  \in\mathbb{R}^{m}$.

\textbf{(b) }The list $\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ is linearly
independent if and only if each $w\in\mathbb{R}^{n}$ can be written as
$w=\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}$ for \textbf{at
most one} $m$-tuple $\left(  \lambda_{1},\lambda_{2},\ldots,\lambda
_{m}\right)  \in\mathbb{R}^{m}$.

\textbf{(c)} The list $\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ is a basis
of $\mathbb{R}^{n}$ if and only if each $w\in\mathbb{R}^{n}$ can be written as
$w=\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}$ for
\textbf{exactly one} $m$-tuple $\left(  \lambda_{1},\lambda_{2},\ldots
,\lambda_{m}\right)  \in\mathbb{R}^{m}$.
\end{theorem}

In the latter case, these $\lambda_{1},\lambda_{2},\ldots,\lambda_{m}$ are
called the \textbf{coordinates} of $w$ with respect to the basis $\left(
v_{1},v_{2},\ldots,v_{m}\right)  $.

\begin{proof}
[Proof of Theorem \ref{thm.span-lind-bas-through-combs}.]\textbf{(a)} We have
the following equivalence:%
\begin{align*}
&  \ \left(  \text{the list }\left(  v_{1},v_{2},\ldots,v_{m}\right)  \text{
spans }\mathbb{R}^{n}\right) \\
&  \Longleftrightarrow\ \left(  \mathbb{R}^{n}=\operatorname*{span}\left(
v_{1},v_{2},\ldots,v_{m}\right)  \right) \\
&  \Longleftrightarrow\ \left(  \mathbb{R}^{n}\subseteq\operatorname*{span}%
\left(  v_{1},v_{2},\ldots,v_{m}\right)  \right) \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{since }%
\operatorname*{span}\left(  v_{1},v_{2},\ldots,v_{m}\right)  \subseteq
\mathbb{R}^{n}\text{ is true either way}\right) \\
&  \Longleftrightarrow\ \left(  \text{each }w\in\mathbb{R}^{n}\text{ lies in
}\operatorname*{span}\left(  v_{1},v_{2},\ldots,v_{m}\right)  \right) \\
&  \Longleftrightarrow\ \left(  \text{each }w\in\mathbb{R}^{n}\text{ is a
combination of }v_{1},v_{2},\ldots,v_{m}\right) \\
&  \Longleftrightarrow\ \left(
\begin{array}
[c]{c}%
\text{each }w\in\mathbb{R}^{n}\text{ can be written as }\lambda_{1}%
v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}\\
\text{for at least one choice of }\lambda_{1},\lambda_{2},\ldots,\lambda_{m}%
\end{array}
\right)  .
\end{align*}


\textbf{(b)} $\Longrightarrow:$ Assume that $\left(  v_{1},v_{2},\ldots
,v_{m}\right)  $ is linearly independent.

We must prove that each $w\in\mathbb{R}^{n}$ can be written as $w=\lambda
_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}$ for \textbf{at most one}
$m$-tuple $\left(  \lambda_{1},\lambda_{2},\ldots,\lambda_{m}\right)
\in\mathbb{R}^{m}$.

So let $w\in\mathbb{R}^{n}$. Let $\left(  \alpha_{1},\alpha_{2},\ldots
,\alpha_{m}\right)  $ and $\left(  \beta_{1},\beta_{2},\ldots,\beta
_{m}\right)  $ be two $m$-tuples of real numbers such that%
\[
w=\alpha_{1}v_{1}+\alpha_{2}v_{2}+\cdots+\alpha_{m}v_{m}%
\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ w=\beta_{1}v_{1}+\beta
_{2}v_{2}+\cdots+\beta_{m}v_{m}.
\]
We must prove that $\left(  \alpha_{1},\alpha_{2},\ldots,\alpha_{m}\right)
=\left(  \beta_{1},\beta_{2},\ldots,\beta_{m}\right)  $; in other words, we
must prove that $\alpha_{i}=\beta_{i}$ for each $i$.

Subtracting the two equalities%
\[
w=\alpha_{1}v_{1}+\alpha_{2}v_{2}+\cdots+\alpha_{m}v_{m}%
\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ w=\beta_{1}v_{1}+\beta
_{2}v_{2}+\cdots+\beta_{m}v_{m},
\]
we obtain%
\begin{align*}
0  &  =\left(  \alpha_{1}v_{1}+\alpha_{2}v_{2}+\cdots+\alpha_{m}v_{m}\right)
-\left(  \beta_{1}v_{1}+\beta_{2}v_{2}+\cdots+\beta_{m}v_{m}\right) \\
&  =\left(  \alpha_{1}v_{1}-\beta_{1}v_{1}\right)  +\left(  \alpha_{2}%
v_{2}-\beta_{2}v_{2}\right)  +\cdots+\left(  \alpha_{m}v_{m}-\beta_{m}%
v_{m}\right) \\
&  =\left(  \alpha_{1}-\beta_{1}\right)  v_{1}+\left(  \alpha_{2}-\beta
_{2}\right)  v_{2}+\cdots+\left(  \alpha_{m}-\beta_{m}\right)  v_{m}.
\end{align*}
This is a relation between the $v_{1},v_{2},\ldots,v_{m}$, and thus must be
the trivial relation, because we assumed that the $v_{1},v_{2},\ldots,v_{m}$
are independent (so each relation between them is the trivial relation). This
means that
\[
\alpha_{1}-\beta_{1}=0,\ \ \ \ \ \ \ \ \ \ \alpha_{2}-\beta_{2}%
=0,\ \ \ \ \ \ \ \ \ \ \ldots,\ \ \ \ \ \ \ \ \ \ \alpha_{m}-\beta_{m}=0.
\]
In other words,%
\[
\alpha_{1}=\beta_{1},\ \ \ \ \ \ \ \ \ \ \alpha_{2}=\beta_{2}%
,\ \ \ \ \ \ \ \ \ \ \ldots,\ \ \ \ \ \ \ \ \ \ \alpha_{m}=\beta_{m}.
\]
In other words, $\left(  \alpha_{1},\alpha_{2},\ldots,\alpha_{m}\right)
=\left(  \beta_{1},\beta_{2},\ldots,\beta_{m}\right)  $. This proves that
there is \textbf{at most one} $m$-tuple $\left(  \lambda_{1},\lambda
_{2},\ldots,\lambda_{m}\right)  \in\mathbb{R}^{m}$ such that $w=\lambda
_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}$.

$\Longleftarrow:$ Assume that each $w\in\mathbb{R}^{n}$ can be written as
$w=\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}$ for \textbf{at
most one} $m$-tuple $\left(  \lambda_{1},\lambda_{2},\ldots,\lambda
_{m}\right)  \in\mathbb{R}^{m}$. We must prove that $\left(  v_{1}%
,v_{2},\ldots,v_{m}\right)  $ is linearly independent.

Indeed, let $\mu_{1}v_{1}+\mu_{2}v_{2}+\cdots+\mu_{m}v_{m}=0$ be a relation
between $v_{1},v_{2},\ldots,v_{m}$. Then, the zero vector $0$ can be written
as $0=\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}$ for
\textbf{two }$m$-tuples $\left(  \lambda_{1},\lambda_{2},\ldots,\lambda
_{m}\right)  \in\mathbb{R}^{m}$: namely, for
\[
\left(  \lambda_{1},\lambda_{2},\ldots,\lambda_{m}\right)  =\left(  \mu
_{1},\mu_{2},\ldots,\mu_{m}\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since
}0=\mu_{1}v_{1}+\mu_{2}v_{2}+\cdots+\mu_{m}v_{m}\right)  ,
\]
and also for%
\[
\left(  \lambda_{1},\lambda_{2},\ldots,\lambda_{m}\right)  =\left(
0,0,\ldots,0\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{because }%
0=0v_{1}+0v_{2}+\cdots+0v_{m}\right)  .
\]
But by our assumption, there is \textbf{at most one} such $m$-tuple. Thus, the
two $m$-tuples%
\[
\left(  \mu_{1},\mu_{2},\ldots,\mu_{m}\right)  \ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \left(  0,0,\ldots,0\right)
\]
must be identical. In other words, $\left(  \mu_{1},\mu_{2},\ldots,\mu
_{m}\right)  =\left(  0,0,\ldots,0\right)  $. In other words, $\mu_{i}=0$ for
all $i$. This means that our relation $\mu_{1}v_{1}+\mu_{2}v_{2}+\cdots
+\mu_{m}v_{m}=0$ must be trivial. Hence, we have shown that any relation
between $v_{1},v_{2},\ldots,v_{m}$ is trivial. In other words, $\left(
v_{1},v_{2},\ldots,v_{m}\right)  $ is linearly independent.

\textbf{(c)} The claim of \textbf{(c)} is just obtained by combining
\textbf{(a)} with \textbf{(b)}, because
\[
\text{\textquotedblleft basis\textquotedblright}=\text{\textquotedblleft
span\textquotedblright}\wedge\text{\textquotedblleft linearly
independent\textquotedblright}%
\]
and%
\[
\text{\textquotedblleft exactly one\textquotedblright}=\text{\textquotedblleft
at least one\textquotedblright}\wedge\text{\textquotedblleft at most
one\textquotedblright.}%
\]

\end{proof}

\begin{example}
Let
\[
v_{1}=\left(
\begin{array}
[c]{c}%
1\\
0\\
0
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{2}=\left(
\begin{array}
[c]{c}%
1\\
1\\
0
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{3}=\left(
\begin{array}
[c]{c}%
1\\
1\\
1
\end{array}
\right)  .
\]
Then, $\left(  v_{1},v_{2},v_{3}\right)  $ is a basis of $\mathbb{R}^{3}$.

Indeed, to see that it is independent, we have to argue that%
\[
\lambda_{1}v_{1}+\lambda_{2}v_{2}+\lambda_{3}v_{3}%
=0\ \ \ \ \ \ \ \ \ \ \Longrightarrow\ \ \ \ \ \ \ \ \ \ \lambda_{1}%
=\lambda_{2}=\lambda_{3}=0.
\]
But this is easy:%
\begin{align*}
&  \ \left(  \lambda_{1}v_{1}+\lambda_{2}v_{2}+\lambda_{3}v_{3}=0\right) \\
&  \Longrightarrow\ \left(  \lambda_{1}\left(
\begin{array}
[c]{c}%
1\\
0\\
0
\end{array}
\right)  +\lambda_{2}\left(
\begin{array}
[c]{c}%
1\\
1\\
0
\end{array}
\right)  +\lambda_{3}\left(
\begin{array}
[c]{c}%
1\\
1\\
1
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
0\\
0\\
0
\end{array}
\right)  \right) \\
&  \Longrightarrow\ \left(  \left(
\begin{array}
[c]{c}%
\lambda_{1}+\lambda_{2}+\lambda_{3}\\
\lambda_{2}+\lambda_{3}\\
\lambda_{3}%
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
0\\
0\\
0
\end{array}
\right)  \right) \\
&  \Longrightarrow\ \left(  \lambda_{1}+\lambda_{2}+\lambda_{3}=0\text{ and
}\lambda_{2}+\lambda_{3}=0\text{ and }\lambda_{3}=0\right) \\
&  \Longrightarrow\ \left(  \lambda_{1}=\lambda_{2}=\lambda_{3}=0\right)  .
\end{align*}


As to why the vectors $v_{1},v_{2},v_{3}$ span $\mathbb{R}^{3}$: We can write
each vector $w=\left(
\begin{array}
[c]{c}%
a_{1}\\
a_{2}\\
a_{3}%
\end{array}
\right)  \in\mathbb{R}^{3}$ as a combination of $v_{1},v_{2},v_{3}$, namely as%
\[
w=\left(  a_{1}-a_{2}\right)  v_{1}+\left(  a_{2}-a_{3}\right)  v_{2}%
+a_{3}v_{3},
\]
since%
\begin{align*}
&  \left(  a_{1}-a_{2}\right)  v_{1}+\left(  a_{2}-a_{3}\right)  v_{2}%
+a_{3}v_{3}\\
&  =\left(  a_{1}-a_{2}\right)  \left(
\begin{array}
[c]{c}%
1\\
0\\
0
\end{array}
\right)  +\left(  a_{2}-a_{3}\right)  \left(
\begin{array}
[c]{c}%
1\\
1\\
0
\end{array}
\right)  +a_{3}\left(
\begin{array}
[c]{c}%
1\\
1\\
1
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{c}%
\left(  a_{1}-a_{2}\right)  +\left(  a_{2}-a_{3}\right)  +a_{3}\\
\left(  a_{2}-a_{3}\right)  +a_{3}\\
a_{3}%
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
a_{1}\\
a_{2}\\
a_{3}%
\end{array}
\right)  =w.
\end{align*}

\end{example}

Let us restate Theorem \ref{thm.span-lind-bas-through-combs} as follows:

\begin{theorem}
\label{thm.span-lind-bas-through-sols}Let $v_{1},v_{2},\ldots,v_{m}$ be column
vectors in $\mathbb{R}^{n}$. Let
\[
A=\left[  v_{1}\mid v_{2}\mid\cdots\mid v_{m}\right]
\ \ \ \ \ \ \ \ \ \ \left(  \text{an }n\times m\text{-matrix}\right)  .
\]


\textbf{(a)} The list $\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ spans
$\mathbb{R}^{n}$ if and only if for each $w\in\mathbb{R}^{n}$, the system
$A\lambda=w$ has \textbf{at least one} solution $\lambda\in\mathbb{R}^{m}$.

\textbf{(b) }The list $\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ is linearly
independent if and only if for each $w\in\mathbb{R}^{n}$, the system
$A\lambda=w$ has \textbf{at most one} solution $\lambda\in\mathbb{R}^{m}$.

\textbf{(c)} The list $\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ is a basis
of $\mathbb{R}^{n}$ if and only if for each $w\in\mathbb{R}^{n}$, the system
$A\lambda=w$ has \textbf{exactly one} solution $\lambda\in\mathbb{R}^{m}$.
\end{theorem}

\begin{proof}
[Proof of Theorem \ref{thm.span-lind-bas-through-sols}.]If we write the vector
$\lambda\in\mathbb{R}^{m}$ as $\lambda=\left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{m}%
\end{array}
\right)  $, then the first lemma from last time says
\[
\underbrace{\left[  v_{1}\mid v_{2}\mid\cdots\mid v_{m}\right]  }%
_{=A}\underbrace{\left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{m}%
\end{array}
\right)  }_{=\lambda}=\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda
_{m}v_{m},
\]
that is,%
\[
A\lambda=\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}.
\]
Thus, a solution to $A\lambda=w$ is the same as a column vector $\left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{m}%
\end{array}
\right)  \in\mathbb{R}^{m}$ satisfying
\[
\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}=w.
\]
Thus, Theorem \ref{thm.span-lind-bas-through-sols} follows from Theorem
\ref{thm.span-lind-bas-through-combs}.
\end{proof}

This theorem shows that spanning and independence of vectors are directly
related to the kind of solutions that a linear system can have.

The next proposition is \cite[Proposition 10.11]{Strickland}:

\begin{proposition}
\label{prop.bas.col-A-bas-col-AT-bas}Let $A$ be an $n\times n$-matrix. Then,
the columns of $A$ form a basis of $\mathbb{R}^{n}$ if and only if the columns
of $A^{T}$ form a basis of $\mathbb{R}^{n}$.
\end{proposition}

\begin{proof}
This follows from Proposition \ref{prop.lind-P-span-PT}.
\end{proof}

The next proposition is \cite[Proposition 10.12]{Strickland}:

\begin{proposition}
\label{prop.lind-or-span-implies-basis}Let $v_{1},v_{2},\ldots,v_{n}$ be $n$
vectors in $\mathbb{R}^{n}$. (Yes, we need the same $n$ here.)

\textbf{(a)} If $\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ is independent,
then $\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ is a basis of $\mathbb{R}%
^{n}$ (and thus, in particular, spans $\mathbb{R}^{n}$).

\textbf{(b)} If $\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ spans
$\mathbb{R}^{n}$, then $\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ is a basis
of $\mathbb{R}^{n}$ (and thus, in particular, is independent).
\end{proposition}

We will prove this in a moment. First, here is an imprecise but memorable way
to formulate this proposition:

\begin{itemize}
\item \textbf{(a)} Sufficiently many independent vectors always form a basis.

\item \textbf{(b)} Sufficiently few spanning vectors always form a basis.
\end{itemize}

Here, \textquotedblleft sufficiently many\textquotedblright\ means
\textquotedblleft$n$\textquotedblright\ both times, where the vectors are in
$\mathbb{R}^{n}$.

\begin{example}
\textbf{(a)} The three vectors $\left(
\begin{array}
[c]{c}%
1\\
0\\
0
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
1\\
1\\
0
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
1\\
1\\
1
\end{array}
\right)  $ are independent and thus (by part \textbf{(a)} of this proposition)
span $\mathbb{R}^{3}$.

\textbf{(b)} The three vectors $\left(
\begin{array}
[c]{c}%
1\\
-1\\
0
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
1\\
0\\
-1
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
1\\
1\\
1
\end{array}
\right)  $ span $\mathbb{R}^{3}$ and thus (by part \textbf{(b)} of this
proposition) are independent.

\textbf{(c)} The two vectors $\left(
\begin{array}
[c]{c}%
1\\
0\\
0
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
1\\
1\\
0
\end{array}
\right)  $ in $\mathbb{R}^{3}$ are independent, but don't form a basis. This
does not contradict the proposition, because they are just $2$ vectors, not
$3$ vectors.
\end{example}

\begin{proof}
[Proof of Proposition \ref{prop.lind-or-span-implies-basis}.]Let $A=\left[
v_{1}\mid v_{2}\mid\cdots\mid v_{n}\right]  $.

\textbf{(a)} Suppose that $\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ is
independent. Let $B$ be the RREF of $A$. By our method for testing
independence, we thus see that $B$ has a pivot in each column. Hence,
$B=I_{n}$ (since $B$ is an $n\times n$-matrix). Thus, there is a way to
transform the matrix $A$ into $I_{n}$ by row operations.

We must show that $\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ spans
$\mathbb{R}^{n}$. In other words, we must show that the system $A\lambda=w$
has at least one solution for each $w\in\mathbb{R}^{n}$.

Fix $w\in\mathbb{R}^{n}$. The augmented matrix of the system $A\lambda=w$ is%
\[
\left[  v_{1}\mid v_{2}\mid\cdots\mid v_{n}\mid w\right]  .
\]
Let us now recall the row operations that were used to transform the matrix
$A$ into $I_{n}$. Applying the same row operations to the augmented matrix
$\left[  v_{1}\mid v_{2}\mid\cdots\mid v_{n}\mid w\right]  $, we obtain%
\[
\left[  I_{n}\mid\ast\right]
\]
(where the asterisk \textquotedblleft$\ast$\textquotedblright\ stands for a
last column that we don't know), because the first $n$ columns of the
augmented matrix $\left[  v_{1}\mid v_{2}\mid\cdots\mid v_{n}\mid w\right]  $
are precisely the $n$ columns of $A$. But this matrix $\left[  I_{n}\mid
\ast\right]  $ is in RREF (no matter what its last column is), and has a pivot
in each of its first $n$ columns, and thus has \textbf{no} pivot in its last
column. Thus, we conclude that the system $A\lambda=w$ has a solution
(according to the Gaussian elimination method). So we have shown that $\left(
v_{1},v_{2},\ldots,v_{n}\right)  $ spans $\mathbb{R}^{n}$. Hence, the list
$\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ is a basis of $\mathbb{R}^{n}$
(since this list is independent).

\textbf{(b)} Suppose that $\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ spans
$\mathbb{R}^{n}$. In other words, the columns of the matrix $A$ span
$\mathbb{R}^{n}$. By part \textbf{(b)} of the first proposition today, this
yields that the columns of $A^{T}$ are linearly independent. Thus, Proposition
\ref{prop.lind-or-span-implies-basis} \textbf{(a)} (applied to these columns)
shows that the columns of $A^{T}$ form a basis of $\mathbb{R}^{n}$. Thus,
Proposition \ref{prop.bas.col-A-bas-col-AT-bas} shows that the columns of $A$
form a basis of $\mathbb{R}^{n}$. In other words, $v_{1},v_{2},\ldots,v_{n}$
form a basis of $\mathbb{R}^{n}$.
\end{proof}

\begin{corollary}
Let $v_{1},v_{2},\ldots,v_{m}$ be $m$ vectors in $\mathbb{R}^{n}$.

\textbf{(a)} If $m<n$, then $\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ cannot
span $\mathbb{R}^{n}$.

\textbf{(b)} If $m>n$, then $\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ cannot
be independent.

\textbf{(c)} If $m\neq n$, then $\left(  v_{1},v_{2},\ldots,v_{m}\right)  $
cannot be a basis of $\mathbb{R}^{n}$.

\textbf{(d)} If $m=n$ and $\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ is
either independent or spans $\mathbb{R}^{n}$, then $\left(  v_{1},v_{2}%
,\ldots,v_{m}\right)  $ is a basis of $\mathbb{R}^{n}$.
\end{corollary}

\begin{proof}
\textbf{(a)} was proven last time.

\textbf{(b)} was proven last time.

\textbf{(c)} follows by combining \textbf{(a)} and \textbf{(b)}.

\textbf{(d)} This is Proposition \ref{prop.lind-or-span-implies-basis}.
\end{proof}

Here is an imprecise \textquotedblleft fact\textquotedblright: If you pick $n$
vectors in $\mathbb{R}^{n}$ \textquotedblleft at random\textquotedblright, it
is almost sure that you get a basis of $\mathbb{R}^{n}$. To \textbf{not} get a
basis, you need a \textquotedblleft coincidence\textquotedblright. (This is
imprecise because there is no such thing as a \textquotedblleft
random\textquotedblright\ real number, thus no \textquotedblleft
random\textquotedblright\ vectors either. Formalizing this rigorously would
take us too far afield.)

\subsection{Elementary matrices}

We have defined row operations as operations in which rows get added, scaled
or swapped. In a way, this means we have been breaking our matrices apart
(into rows, at least) and assembling them back again. Can we achieve the same
result through matrix addition, multiplication etc., without breaking them
apart? In other words, can we rewrite our row operations in terms of matrices,
not in terms of rows?

Yes, but we need some special matrices for this. We follow \cite[Definition
11.1]{Strickland} in the following:

\begin{definition}
Let $n\in\mathbb{N}$. We define the following $n\times n$-matrices:

\textbf{(a)} If $p\in\left\{  1,2,\ldots,n\right\}  $ and if $\lambda
\in\mathbb{R}$ is nonzero, then $D_{p}\left(  \lambda\right)  $ shall mean the
$n\times n$-matrix $\operatorname*{diag}\left(  1,1,\ldots,1,\lambda
,1,1,\ldots,1\right)  $; this is the matrix whose diagonal entries are
$1,1,\ldots,1,\lambda,1,1,\ldots,1$ with the $\lambda$ in position $p$, and
whose off-diagonal entries are $0$. Equivalently, $D_{p}\left(  \lambda
\right)  $ is the $n\times n$-matrix which is $I_{n}$ but with the $\left(
p,p\right)  $-th entry replaced by $\lambda$.

\textbf{(b)} If $p,q\in\left\{  1,2,\ldots,n\right\}  $ are distinct, and if
$\mu\in\mathbb{R}$, then $E_{p,q}\left(  \mu\right)  $ shall mean the $n\times
n$-matrix which is $I_{n}$ but with the $\left(  p,q\right)  $-th entry
replaced by $\mu$.

\textbf{(c)} If $p,q\in\left\{  1,2,\ldots,n\right\}  $ are distinct, then
$F_{p,q}$ shall mean the $n\times n$-matrix which is $I_{n}$ but with rows $p$
and $q$ swapped.
\end{definition}

\begin{example}
Let $n=4$.

\textbf{(a)} We have%
\[
D_{2}\left(  \lambda\right)  =\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & \lambda & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{array}
\right)  .
\]


\textbf{(b)} We have%
\[
E_{2,4}\left(  \mu\right)  =\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & 1 & 0 & \mu\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{array}
\right)  .
\]


\textbf{(c)} We have%
\[
F_{2,4}=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0\\
0 & 1 & 0 & 0
\end{array}
\right)  .
\]

\end{example}

The three kinds of matrices we just defined ($D_{p}\left(  \lambda\right)  $,
$E_{p,q}\left(  \mu\right)  $ and $F_{p,q}$) are called the \textbf{elementary
matrices}. They can be used to re-encode row operations as follows
(\cite[Proposition 11.3]{Strickland}):

\begin{proposition}
\label{prop.row-ops.elemats}Let $A$ be an $n\times m$-matrix, and let
$A^{\prime}$ be obtained from $A$ by a single row operation. Then, $A^{\prime
}=UA$ for some elementary matrix $U$. In more detail:

\textbf{(a)} If $A^{\prime}$ is obtained from $A$ by scaling the $p$-th row by
$\lambda$, then $A^{\prime}=D_{p}\left(  \lambda\right)  A$.

\textbf{(b)} If $A^{\prime}$ is obtained from $A$ by adding $\mu$ times the
$q$-th row to the $p$-th row, then $A^{\prime}=E_{p,q}\left(  \mu\right)  A$.

\textbf{(c)} If $A^{\prime}$ is obtained from $A$ by swapping the $p$-th and
$q$-th rows, then $A^{\prime}=F_{p,q}A$.
\end{proposition}

\begin{proof}
Let $A=\left(
\begin{array}
[c]{cccc}%
a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4}\\
a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4}\\
a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4}\\
a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4}%
\end{array}
\right)  $.

\textbf{(a)} We have%
\[
D_{2}\left(  \lambda\right)  A=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & \lambda & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cccc}%
a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4}\\
a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4}\\
a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4}\\
a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4}%
\end{array}
\right)  =\left(
\begin{array}
[c]{cccc}%
a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4}\\
\lambda a_{2,1} & \lambda a_{2,2} & \lambda a_{2,3} & \lambda a_{2,4}\\
a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4}\\
a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4}%
\end{array}
\right)  .
\]


\textbf{(b)} We have%
\begin{align*}
E_{2,4}\left(  \mu\right)  A  &  =\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & 1 & 0 & \mu\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cccc}%
a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4}\\
a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4}\\
a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4}\\
a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4}%
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{cccc}%
a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4}\\
a_{2,1}+\mu a_{4,1} & a_{2,2}+\mu a_{4,2} & a_{2,3}+\mu a_{4,3} & a_{2,4}+\mu
a_{4,4}\\
a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4}\\
a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4}%
\end{array}
\right)  .
\end{align*}


\textbf{(c)} We have%
\[
F_{2,4}A=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0\\
0 & 1 & 0 & 0
\end{array}
\right)  \left(
\begin{array}
[c]{cccc}%
a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4}\\
a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4}\\
a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4}\\
a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4}%
\end{array}
\right)  =\left(
\begin{array}
[c]{cccc}%
a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4}\\
a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4}\\
a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4}\\
a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4}%
\end{array}
\right)  .
\]

\end{proof}

\textbf{Remark:} My notations $D_{p}\left(  \lambda\right)  $, $E_{p,q}\left(
\mu\right)  $ and $F_{p,q}$ are from Strickland's \cite{Strickland}, except
that he does not place commas between the two subscripts (so he calls them
$D_{p}\left(  \lambda\right)  $, $E_{pq}\left(  \mu\right)  $ and $F_{pq}$).
They correspond to $S_{p}^{\lambda}$, $A_{p,q}^{\mu}$ and $T_{p,q}$ in
\cite{lina}.

\textbf{Remark:} So multiplying elementary matrices to a matrix $A$ on the
left corresponds to row operations on $A$. Likewise, multiplying them to $A$
on the right corresponds to column operations on $A$. (Beware, however:
$E_{p,q}\left(  \mu\right)  $ will now add $\mu$ times the $p$-th column to
the $q$-th column.)

\begin{corollary}
Let $A$ and $B$ be $n\times m$-matrices such that $A$ can be transformed into
$B$ by row operations. Then, $B=UA$ for some matrix $U$ that can be written as
a product of elementary matrices.
\end{corollary}

\begin{proof}
Let%
\[
A\longrightarrow C_{1}\longrightarrow C_{2}\longrightarrow\cdots
\longrightarrow C_{s}\longrightarrow B
\]
be a way to get from $A$ to $B$ by row operations (where each arrow stands for
a single row operation). Then, by Proposition \ref{prop.row-ops.elemats}, we
have%
\begin{align*}
C_{1} &  =U_{1}A,\\
C_{2} &  =U_{2}C_{1},\\
C_{3} &  =U_{3}C_{2},\\
&  \vdots\\
C_{s} &  =U_{s}C_{s-1},\\
B &  =U_{s+1}C_{s}%
\end{align*}
for some elementary matrices $U_{1},U_{2},\ldots,U_{s+1}$. Combining these
equalities, we find%
\[
B=\underbrace{U_{s+1}U_{s}U_{s-1}\cdots U_{1}}_{\text{a product of elementary
matrices}}A.
\]

\end{proof}

\subsection{Invertibility}

We follow partly \cite[\S 11]{Strickland}, partly \cite[\S 3.2]{lina}.

\begin{definition}
Let $A$ be an $m\times n$-matrix.

\textbf{(a)} A \textbf{left inverse} of $A$ means an $n\times m$-matrix $L$
such that $LA=I_{n}$.

\textbf{(b)} A \textbf{right inverse} of $A$ means an $n\times m$-matrix $R$
such that $AR=I_{m}$.

\textbf{(c)} An \textbf{inverse} (or \textbf{two-sided inverse}) of $A$ means
an $n\times m$-matrix $B$ such that $BA=I_{n}$ and $AB=I_{m}$.
\end{definition}

Thus, an inverse of $A$ is the same as a matrix that is simultaneously a left
inverse and a right inverse of $A$.

\begin{example}
If $A=\left(
\begin{array}
[c]{cc}%
1 & 3
\end{array}
\right)  $, then $\left(
\begin{array}
[c]{c}%
-2\\
1
\end{array}
\right)  $ is a right inverse of $A$, since%
\[
\left(
\begin{array}
[c]{cc}%
1 & 3
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
-2\\
1
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
1\cdot\left(  -2\right)  +3\cdot1
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
1
\end{array}
\right)  =I_{1}.
\]
But $\left(
\begin{array}
[c]{c}%
1\\
0
\end{array}
\right)  $ is also a right inverse of $A$ in this case. So right inverses are
not unique.

Nor do they always exist; for example, $\left(
\begin{array}
[c]{cc}%
0 & 0\\
0 & 0
\end{array}
\right)  $ has none.

Similarly for left inverses.
\end{example}

Note that if $L$ is a left inverse of $A$, then $L^{T}$ is a right inverse of
$A^{T}$, and vice versa; therefore, the properties of right inverses mirror
the properties of left inverses.

\begin{theorem}
\label{thm.inv.L=R}Let $A$ be a matrix. Let $L$ be a left inverse of $A$. Let
$R$ be a right inverse of $A$. Then, $L=R$, and furthermore this matrix $L=R$
is an inverse of $A$.
\end{theorem}

\begin{proof}
Comparing
\[
\underbrace{LA}_{=I_{n}}R=I_{n}R=R\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ L\underbrace{AR}_{=I_{m}}=LI_{m}=L,
\]
we get $L=R$. Now, $LA=I_{n}$ and $A\underbrace{L}_{=R}=AR=I_{m}$, so we
conclude that $L$ is an inverse of $A$.
\end{proof}

\begin{corollary}
\label{cor.inv.L=R2}Assume that a matrix $A$ has both a left inverse and a
right inverse. Then:

\textbf{(a)} The matrix $A$ has a \textbf{unique} inverse.

\textbf{(b)} This inverse is the \textbf{only} left inverse of $A$ and the
\textbf{only} right inverse of $A$.
\end{corollary}

\begin{proof}
We have assumed that $A$ has a left inverse and a right inverse. Call them $L$
and $R$. Then, Theorem \ref{thm.inv.L=R} shows that $L=R$, and that
furthermore this matrix $L=R$ is an inverse of $A$. Now, if $L^{\prime}$ is
any other left inverse of $A$, then Theorem \ref{thm.inv.L=R} (applied to
$L^{\prime}$ instead of $L$) also shows that $L^{\prime}=R$, whence
$L^{\prime}=R=L$. This shows that the inverse $L=R$ is the \textbf{only} left
inverse of $A$. Similarly, it is the \textbf{only} right inverse of $A$. This
proves part \textbf{(b)}. From this, the uniqueness part of part \textbf{(a)}
follows (since any other inverse would also be a left inverse).
\end{proof}

\begin{corollary}
\label{cor.inverse.unique}If $A$ has an inverse, then this inverse is unique.
\end{corollary}

\begin{proof}
An inverse is both a left inverse and a right inverse. Thus, this corollary
follows from Corollary \ref{cor.inv.L=R2} \textbf{(a)}.
\end{proof}

\begin{definition}
If a matrix $A$ has an inverse, then this inverse is denoted by $A^{-1}$.
(This notation is harmless, because Corollary \ref{cor.inverse.unique} says
that this inverse is unique.)

A matrix is said to be \textbf{invertible} if it has an inverse.
\end{definition}

\begin{proposition}
Let $A$ and $B$ be two invertible matrices. Then, their product $AB$ is also
invertible, and its inverse is $\left(  AB\right)  ^{-1}=B^{-1}A^{-1}$.
\end{proposition}

\begin{proof}
We have to check that $B^{-1}A^{-1}$ is an inverse of $AB$. In other words, we
have to check that $\left(  B^{-1}A^{-1}\right)  \left(  AB\right)  =I$ and
$\left(  AB\right)  \left(  B^{-1}A^{-1}\right)  =I$ (where $I$ stands for the
identity matrix of the appropriate size). But this follows from%
\begin{align*}
\left(  B^{-1}A^{-1}\right)  \left(  AB\right)   &  =B^{-1}\underbrace{A^{-1}%
A}_{=I}B=B^{-1}\underbrace{IB}_{=B}=B^{-1}B=I\ \ \ \ \ \ \ \ \ \ \text{and}\\
\left(  AB\right)  \left(  B^{-1}A^{-1}\right)   &  =A\underbrace{BB^{-1}%
}_{=I}A^{-1}=\underbrace{AI}_{=A}A^{-1}=AA^{-1}=I.
\end{align*}

\end{proof}

\begin{thebibliography}{9999999999}                                                                                       %


\bibitem[lina]{lina}Darij Grinberg, \textit{Notes on linear algebra}, version
of 13 December 2016.\newline\url{https://github.com/darijgr/lina}

\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}