\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:50:12}
%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-16}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

\section{Gaussian elimination (continued)}

\subsection{Invertibility (continued)}

Recall:

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

\begin{theorem}
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{corollary}
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{corollary}
If $A$ has an inverse, then this inverse is unique.
\end{corollary}

\begin{definition}
If a matrix $A$ has an inverse, then this inverse is denoted by $A^{-1}$.
(This notation is harmless, because the previous corollary 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}

Once again: Left inverses don't have to exist nor be unique; right inverses
don't have to exist nor be unique; inverses (in the two-sided sense) don't
have to exist, but at least they are unique.

\begin{lemma}
Let $A$ be a matrix. Then, $A$ has a right inverse if and only if $A^{T}$ has
a left inverse.
\end{lemma}

\begin{proof}
We have to prove the \textquotedblleft if\textquotedblright\ part and the
\textquotedblleft only if\textquotedblright\ part.

\textit{\textquotedblleft if\textquotedblright\ part:} Assume that $A^{T}$ has
a left inverse. We must prove that $A$ has a right inverse.

We have assumed that $A^{T}$ has a left inverse; let $B$ be such a left
inverse. Thus, $BA^{T}=I$. (Recall that $I$ denotes an identity matrix of any
size.) But any two matrices $X$ and $Y$ satisfy $\left(  XY\right)  ^{T}%
=Y^{T}X^{T}$ (provided that $XY$ makes sense). Applying this to $X=B$ and
$Y=A^{T}$, we find $\left(  BA^{T}\right)  ^{T}=\underbrace{\left(
A^{T}\right)  ^{T}}_{=A}B^{T}=AB^{T}$. Thus, $AB^{T}=\left(
\underbrace{BA^{T}}_{=I}\right)  ^{T}=I^{T}=I$. In other words, $B^{T}$ is a
right inverse of $A$. Thus, $A$ has a right inverse. This proves the
\textquotedblleft if\textquotedblright\ part.

\textit{\textquotedblleft only if\textquotedblright\ part:} Assume that $A$
has a right inverse. We must prove that $A^{T}$ has a left inverse.

We have assumed that $A$ has a right inverse; let $R$ be such a right inverse.
Thus, $AR=I$. But any two matrices $X$ and $Y$ satisfy $\left(  XY\right)
^{T}=Y^{T}X^{T}$ (provided that $XY$ makes sense). Applying this to $X=A$ and
$Y=R$, we find $\left(  AR\right)  ^{T}=R^{T}A^{T}$. Thus, $R^{T}A^{T}=\left(
\underbrace{AR}_{=I}\right)  ^{T}=I^{T}=I$. In other words, $R^{T}$ is a left
inverse of $A^{T}$. Thus, $A^{T}$ has a left inverse. This proves the
\textquotedblleft only if\textquotedblright\ part.
\end{proof}

This proof actually shows something more:

\begin{corollary}
Let $A$ be a matrix. Then, a right inverse of $A$ is the same as the transpose
of a left inverse of $A^{T}$.
\end{corollary}

\subsection{The Inverse Matrix Theorem}

The \textquotedblleft Inverse Matrix Theorem\textquotedblright\ is not so much
a specific theorem, but a cloud of theorems, each of which has the form
\textquotedblleft a matrix is invertible if and only if (a bunch of equivalent
conditions hold)\textquotedblright. In other words, the Inverse Matrix Theorem
is a set of (necessary and sufficient) criteria for a matrix to be invertible.
The exact criteria\ depend on the author.

For us, the Inverse Matrix Theorem is the following theorem (a slightly
restated version of \cite[Theorem 11.5]{Strickland}):

\begin{theorem}
(The Inverse Matrix Theorem.)

Let $A$ be an $n\times n$-matrix.

Then, the following statements are equivalent (i.e., if any of them holds,
then so do all the others):

\begin{itemize}
\item \textbf{(a)} The matrix $A$ can be row-reduced to $I_{n}$.

\item \textbf{(b)} The columns of $A$ are linearly independent.

\item \textbf{(c)} The columns of $A$ span $\mathbb{R}^{n}$.

\item \textbf{(d)} The columns of $A$ form a basis of $\mathbb{R}^{n}$.

\item \textbf{(e)} The matrix $A^{T}$ can be row-reduced to $I_{n}$.

\item \textbf{(f)} The columns of $A^{T}$ are linearly independent.

\item \textbf{(g)} The columns of $A^{T}$ span $\mathbb{R}^{n}$.

\item \textbf{(h)} The columns of $A^{T}$ form a basis of $\mathbb{R}^{n}$.

\item \textbf{(i)} The matrix $A$ has a left inverse.

\item \textbf{(j)} The matrix $A$ has a right inverse.

\item \textbf{(k)} The matrix $A$ has an inverse (i.e., $A$ is invertible).
\end{itemize}
\end{theorem}

\begin{proof}
The equivalence \textbf{(d)} $\Longleftrightarrow$ \textbf{(h)} follows from
Proposition 1.2.6 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{2019-10-09}.

The equivalence \textbf{(b)} $\Longleftrightarrow$ \textbf{(c)}
$\Longleftrightarrow$ \textbf{(d)} follows from Proposition 1.2.7 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{2019-10-09}.
(Here we are using that our matrix $A$ is square, so that its columns are $n$
vectors in $\mathbb{R}^{n}$.)

The equivalence \textbf{(a)} $\Longleftrightarrow$ \textbf{(b)} follows from
Theorem 1.1.7 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-07.pdf}{2019-10-07}.
Indeed, this theorem entails that the columns of $A$ are independent if and
only if the RREF of $A$ has a pivot in each column. But the RREF of $A$ is a
square matrix, and thus has a pivot in each column if and only if it is
$I_{n}$ (by Lemma 1.1.14 \textbf{(b)} from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-07.pdf}{2019-10-07}).

Now, we know the equivalence \textbf{(a)} $\Longleftrightarrow$ \textbf{(b)}
$\Longleftrightarrow$ \textbf{(c)} $\Longleftrightarrow$ \textbf{(d)}
$\Longleftrightarrow$ \textbf{(h)}.

Applying the same reasoning to $A^{T}$ instead of $A$, we obtain \textbf{(e)}
$\Longleftrightarrow$ \textbf{(f)} $\Longleftrightarrow$ \textbf{(g)}
$\Longleftrightarrow$ \textbf{(h)} $\Longleftrightarrow$ \textbf{(d)} (since
$\left(  A^{T}\right)  ^{T}=A$).

Next we shall prove the equivalence \textbf{(a)} $\Longleftrightarrow$
\textbf{(i)}. To do so, we will prove the implications \textbf{(a)}
$\Longrightarrow$ \textbf{(i)} and \textbf{(i)} $\Longrightarrow$ \textbf{(a)}.

\textit{Proof of \textbf{(a)} }$\Longrightarrow$ \textit{\textbf{(i)}:} Assume
that \textbf{(a)} holds. That is, the matrix $A$ can be row-reduced to $I_{n}%
$. So $I_{n}$ can be obtained from $A$ by a sequence of row operations. Hence,
Corollary 1.3.4 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{2019-10-09}
yields that $I_{n}=UA$ for some matrix $U$ that can be written as a product of
elementary matrices. Consider this $U$. Thus, $U$ is a left inverse of $A$.
Thus, $A$ has a left inverse. In other words, \textbf{(i)} holds.

\textit{Proof of \textbf{(i)} }$\Longrightarrow$ \textit{\textbf{(a)}:} Assume
that \textbf{(i)} holds. That is, the matrix $A$ has a left inverse $B$. We
must prove that \textbf{(a)} holds. Since we already know that \textbf{(a)}
$\Longleftrightarrow$ \textbf{(b)}, it suffices to prove that \textbf{(b)}
holds. In other words, we have to prove that the columns of $A$ are independent.

Let $v_{1},v_{2},\ldots,v_{n}$ be the columns of $A$. Thus, $A=\left[
v_{1}\mid v_{2}\mid\cdots\mid v_{n}\right]  $. Hence, for each vector
$\lambda=\left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{n}%
\end{array}
\right)  $, we have%
\[
A\lambda=\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{n}v_{n}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{by Lemma 1.1.6 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-07.pdf}{2019-10-07}%
}\right)  .
\]
Thus, if
\[
\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{n}v_{n}=0
\]
is some relation between the $v_{1},v_{2},\ldots,v_{n}$, then%
\begin{align*}
A\lambda &  =0,\ \ \ \ \ \ \ \ \ \ \text{and thus}\\
B\underbrace{A\lambda}_{=0}  &  =B\cdot0=0,\ \ \ \ \ \ \ \ \ \ \text{hence}\\
0  &  =\underbrace{BA}_{\substack{=I_{n}\\\text{(since }B\text{ is a left
inverse of }A\text{)}}}\lambda=I_{n}\lambda=\lambda=\left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{n}%
\end{array}
\right)  ,
\end{align*}
so that $\lambda_{1}=\lambda_{2}=\cdots=\lambda_{n}=0$. That is, any relation
between $v_{1},v_{2},\ldots,v_{n}$ is trivial. This means that $v_{1}%
,v_{2},\ldots,v_{n}$ are independent. In other words, \textbf{(b)} holds.
Since \textbf{(a)} $\Longleftrightarrow$ \textbf{(b)}, this shows that
\textbf{(a)} holds.

Thus, we have proven the implications \textbf{(a)} $\Longrightarrow$
\textbf{(i)} and \textbf{(i)} $\Longrightarrow$ \textbf{(a)}. Hence,
\textbf{(a)} $\Longleftrightarrow$ \textbf{(i)}.

Applying the same argument to $A^{T}$ instead of $A$, we obtain the
equivalence \textbf{(e)} $\Longleftrightarrow$ \textbf{(j)}, because we know
(from the Lemma above) that $A$ has a right inverse if and only if $A^{T}$ has
a left inverse.

Next, the implication \textbf{(k)} $\Longrightarrow$ \textbf{(i)} is obvious,
since an inverse of $A$ is automatically a left inverse of $A$.

To prove the implication \textbf{(i)} $\Longrightarrow$ \textbf{(k)}, we
assume that statement \textbf{(i)} holds. Thus, $A$ has a left inverse. But
since we already know that \textbf{(i)} $\Longleftrightarrow$ \textbf{(j)}
(because \textbf{(i)} $\Longleftrightarrow$ \textbf{(a)} $\Longleftrightarrow$
\textbf{(e)} $\Longleftrightarrow$ \textbf{(j)}), we know that statement
\textbf{(j)} holds as well. In other words, $A$ has a right inverse. So we
know that $A$ has both a left inverse and a right inverse. Thus, by Corollary
1.4.4 \textbf{(a)} from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{2019-10-09},
we conclude that $A$ has an inverse. Thus, \textbf{(k)} holds.

So we have proven the implications \textbf{(k)} $\Longrightarrow$ \textbf{(i)}
and \textbf{(i)} $\Longrightarrow$ \textbf{(k)}. Thus, \textbf{(i)}
$\Longleftrightarrow$ \textbf{(k)}.

Combining the equivalences we have shown, we can now conclude that all our
statements are equivalent.
\end{proof}

\begin{example}
Is the matrix $A:=\left(
\begin{array}
[c]{cc}%
1 & 2\\
3 & 4
\end{array}
\right)  $ invertible?

According to the Inverse Matrix Theorem (specifically, the equivalence
\textbf{(a)} $\Longleftrightarrow$ \textbf{(k)}), this boils down to checking
whether $A$ can be row-reduced to $I_{n}=I_{2}$. Let us check this:%
\begin{align*}
&  A=\left(
\begin{array}
[c]{cc}%
1 & 2\\
3 & 4
\end{array}
\right)  \overset{\text{add }-3\cdot\operatorname{row}1\text{ to
}\operatorname{row}2}{\longrightarrow}\left(
\begin{array}
[c]{cc}%
\fbox{$1$} & 2\\
0 & \fbox{$-2$}%
\end{array}
\right)  \overset{\text{scale row }2\text{ by }-1/2}{\longrightarrow}\left(
\begin{array}
[c]{cc}%
\fbox{$1$} & 2\\
0 & \fbox{$1$}%
\end{array}
\right) \\
&  \overset{\text{add }-2\cdot\operatorname{row}2\text{ to }\operatorname{row}%
1}{\longrightarrow}\left(
\begin{array}
[c]{cc}%
1 & 0\\
0 & 1
\end{array}
\right)  =I_{2}.
\end{align*}
This shows that $A$ is invertible.

What is $A^{-1}$ ? Well, let us follow our proof of \textbf{(a)}
$\Longrightarrow$ \textbf{(i)} above, and actually compute the left inverse of
$A$ (which, as we know, will be an inverse of $A$). So we look at our above
way of row-reducing $A$ to $I_{2}$, and rewrite it in terms of multiplication
by elementary matrices (using Proposition 1.3.3 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{2019-10-09}%
):%
\begin{align*}
\left(
\begin{array}
[c]{cc}%
\fbox{$1$} & 2\\
0 & \fbox{$-2$}%
\end{array}
\right)   &  =U_{1}A\ \ \ \ \ \ \ \ \ \ \text{for }U_{1}=E_{2,1}\left(
-3\right)  ;\\
\left(
\begin{array}
[c]{cc}%
\fbox{$1$} & 2\\
0 & \fbox{$1$}%
\end{array}
\right)   &  =U_{2}\left(
\begin{array}
[c]{cc}%
\fbox{$1$} & 2\\
0 & \fbox{$-2$}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{for }U_{2}=D_{2}\left(  -1/2\right)  ;\\
I_{2}  &  =U_{3}\left(
\begin{array}
[c]{cc}%
\fbox{$1$} & 2\\
0 & \fbox{$1$}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{for }U_{3}=E_{1,2}\left(  -2\right)  .
\end{align*}
Thus,%
\[
I_{2}=U_{3}U_{2}U_{1}A.
\]
Hence, $U_{3}U_{2}U_{1}$ is a left inverse of $A$, and therefore must be the
inverse of $A$ (since $A$ is invertible). Thus,
\begin{align*}
A^{-1}  &  =U_{3}U_{2}U_{1}=E_{1,2}\left(  -2\right)  D_{2}\left(
-1/2\right)  E_{2,1}\left(  -3\right) \\
&  =\left(
\begin{array}
[c]{cc}%
1 & -2\\
0 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
1 & 0\\
0 & -1/2
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
1 & 0\\
-3 & 1
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{cc}%
-2 & 1\\
3/2 & -1/2
\end{array}
\right)  .
\end{align*}

\end{example}

\begin{example}
Now, let $A=\left(
\begin{array}
[c]{cc}%
1 & 2\\
3 & 6
\end{array}
\right)  $. Is $A$ invertible?

Again, use statement \textbf{(a)} from the Inverse Matrix Theorem:%
\[
A=\left(
\begin{array}
[c]{cc}%
1 & 2\\
3 & 6
\end{array}
\right)  \overset{\text{add }-3\cdot\operatorname{row}1\text{ to
}\operatorname{row}2}{\longrightarrow}\left(
\begin{array}
[c]{cc}%
\fbox{$1$} & 2\\
0 & 0
\end{array}
\right)  .
\]
This is a RREF, but not $I_{n}$. Thus, statement \textbf{(a)} does
\textbf{not} hold here. Hence, statement \textbf{(k)} does not hold either.
That is, $A$ is not invertible.
\end{example}

\begin{proposition}
Any elementary matrix is invertible.
\end{proposition}

\begin{proof}
(This is \cite[Example 11.8]{Strickland}.)

We need to show that $D_{p}\left(  \lambda\right)  $, $E_{p,q}\left(
\mu\right)  $ and $F_{p,q}$ are invertible.

\begin{itemize}
\item For $D_{p}\left(  \lambda\right)  $, we claim that $D_{p}\left(
\lambda\right)  \cdot D_{p}\left(  \lambda^{-1}\right)  =I_{n}$. Indeed:

\begin{itemize}
\item Proposition 1.3.3 \textbf{(a)} from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{2019-10-09}
shows that $D_{p}\left(  \lambda^{-1}\right)  =D_{p}\left(  \lambda
^{-1}\right)  \cdot I_{n}$ is obtained from $I_{n}$ by scaling the $p$-th row
by $\lambda^{-1}$. (Of course, this is also obvious from the definition of
$D_{p}\left(  \lambda^{-1}\right)  $.)

\item Proposition 1.3.3 \textbf{(a)} from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{2019-10-09}
shows that $D_{p}\left(  \lambda\right)  \cdot D_{p}\left(  \lambda
^{-1}\right)  $ is obtained from $D_{p}\left(  \lambda^{-1}\right)  $ by
scaling the $p$-th row by $\lambda$.
\end{itemize}

Thus, $D_{p}\left(  \lambda\right)  \cdot D_{p}\left(  \lambda^{-1}\right)  $
is obtained from $I_{n}$ by first scaling the $p$-th row by $\lambda^{-1}$ and
then scaling it by $\lambda$ again. Clearly, these two scaling operations undo
each other, so after doing both of them we just get $I_{n}$ back. So
$D_{p}\left(  \lambda\right)  \cdot D_{p}\left(  \lambda^{-1}\right)  =I_{n}$.

Similarly, $D_{p}\left(  \lambda^{-1}\right)  \cdot D_{p}\left(
\lambda\right)  =I_{n}$. Thus, $D_{p}\left(  \lambda^{-1}\right)  $ is an
inverse of $D_{p}\left(  \lambda\right)  $.

\item For $E_{p,q}\left(  \mu\right)  $, we claim that $E_{p,q}\left(
\mu\right)  \cdot E_{p,q}\left(  -\mu\right)  =I_{n}$. Indeed:

\begin{itemize}
\item Proposition 1.3.3 \textbf{(b)} from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{2019-10-09}
shows that $E_{p,q}\left(  -\mu\right)  =E_{p,q}\left(  -\mu\right)  \cdot
I_{n}$ is obtained from $I_{n}$ by adding $-\mu$ times the $q$-th row to the
$p$-th row.

\item Proposition 1.3.3 \textbf{(b)} from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{2019-10-09}
shows that $E_{p,q}\left(  \mu\right)  \cdot E_{p,q}\left(  -\mu\right)  $ is
obtained from $E_{p,q}\left(  -\mu\right)  $ by adding $\mu$ times the $q$-th
row to the $p$-th row.
\end{itemize}

Thus, $E_{p,q}\left(  \mu\right)  \cdot E_{p,q}\left(  -\mu\right)  $ is
obtained from $I_{n}$ by first adding $-\mu$ times the $q$-th row to the
$p$-th row, and then adding $\mu$ times the $q$-th row to the $p$-th row.
Clearly, these two adding operations undo each other, so after doing both of
them we just get $I_{n}$ back. So $E_{p,q}\left(  \mu\right)  \cdot
E_{p,q}\left(  -\mu\right)  =I_{n}$.

Similarly, $E_{p,q}\left(  -\mu\right)  \cdot E_{p,q}\left(  \mu\right)
=I_{n}$. Thus, $E_{p,q}\left(  -\mu\right)  $ is an inverse of $E_{p,q}\left(
\mu\right)  $.

\item For $F_{p,q}$, we claim that $F_{p,q}\cdot F_{p,q}=I_{n}$. The proof is
similar. Thus, $F_{p,q}$ is its own inverse.
\end{itemize}
\end{proof}

So we know how to find inverses of square matrices. What about rectangular matrices?

\begin{theorem}
(The Left Inverse Matrix Theorem)

Let $A$ be an $n\times m$-matrix. Then, the following statements are equivalent:

\begin{itemize}
\item \textbf{(a)} The RREF of $A$ has a pivot in each column.

\item \textbf{(b)} The columns of $A$ are linearly independent.

\item \textbf{(g)} The columns of $A^{T}$ span $\mathbb{R}^{m}$.

\item \textbf{(i)} The matrix $A$ has a left inverse.
\end{itemize}
\end{theorem}

\begin{proof}
\textbf{(a)} $\Longleftrightarrow$ \textbf{(b)} is proved as in the Inverse
Matrix Theorem.

\textbf{(b)} $\Longleftrightarrow$ \textbf{(g)} is Proposition 1.1.3
\textbf{(a)} from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{2019-10-09}.

\textbf{(i)} $\Longrightarrow$ \textbf{(a)} is proved as in the Inverse Matrix Theorem.

Let us now prove \textbf{(a)} $\Longrightarrow$ \textbf{(i)}. So we assume
that \textbf{(a)} holds. That is, the RREF of $A$ has a pivot in each column.
Let us denote this RREF by $B$. Then, $B$ is a RREF matrix with a pivot in
each column. Hence, Lemma 1.1.14 \textbf{(c)} from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-07.pdf}{2019-10-07}
shows that $n\geq m$ and%
\[
B=\left[
\begin{array}
[c]{c}%
I_{m}\\
0_{\left(  n-m\right)  \times m}%
\end{array}
\right]  .
\]
Let $C$ be the $m\times n$-matrix whose leftmost $m$ columns form the identity
matrix $I_{m}$ and its remaining $n-m$ columns are just zero. (Note that
$C=B^{T}$, but we won't need this.) It is easy to see that $CB=I_{m}$.

But $B$ can be obtained from $A$ by a sequence of row operations (since $B$ is
the RREF of $A$). Hence, Corollary 1.3.4 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{2019-10-09}
yields that $B=UA$ for some matrix $U$ that can be written as a product of
elementary matrices. Consider this $U$.

Now, $\left(  CU\right)  A=C\underbrace{UA}_{=B}=CB=I_{m}$. Hence, $CU$ is a
left inverse of $A$. Thus, $A$ has a left inverse. In other words,
\textbf{(i)} holds. This proves the implication \textbf{(a)} $\Longrightarrow$
\textbf{(i)}.

Combining this with \textbf{(i)} $\Longrightarrow$ \textbf{(a)}, we obtain the
equivalence \textbf{(a)} $\Longleftrightarrow$ \textbf{(i)}. By combining what
we have proved, we get the full set of equivalences \textbf{(a)}
$\Longleftrightarrow$ \textbf{(b)} $\Longleftrightarrow$ \textbf{(g)}
$\Longleftrightarrow$ \textbf{(i)}.
\end{proof}

\begin{theorem}
(The Right Inverse Matrix Theorem)

Let $A$ be an $n\times m$-matrix. Then, the following statements are equivalent:

\begin{itemize}
\item \textbf{(e)} The RREF of $A^{T}$ has a pivot in each column.

\item \textbf{(f)} The columns of $A^{T}$ are linearly independent.

\item \textbf{(c)} The columns of $A$ span $\mathbb{R}^{n}$.

\item \textbf{(j)} The matrix $A$ has a right inverse.
\end{itemize}
\end{theorem}

\begin{proof}
Apply the Left Inverse Matrix Theorem to $A^{T}$ instead of $A$. Again, the
trick is that $A$ has a right inverse if and only if $A^{T}$ has a left
inverse (by the first Lemma we proved today).
\end{proof}

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

\textbf{(a)} If $A$ has a left inverse, then $n\geq m$ (that is, $A$ is square
or tall).

\textbf{(b)} If $A$ has a right inverse, then $n\leq m$ (that is, $A$ is
square or wide).

\textbf{(c)} If $A$ has an inverse, then $n=m$ (that is, $A$ is square).
\end{corollary}

\begin{proof}
\textbf{(a)} Assume that $A$ has a left inverse. Then, the Left Inverse Matrix
Theorem says that the columns of $A$ are linearly independent. Thus, they are
$m$ linearly independent vectors in $\mathbb{R}^{n}$. If $m>n$, then Corollary
1.2.9 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{2019-10-09}
would say that this is impossible. Thus, we must have $m\leq n$, that is,
$n\geq m$.

\textbf{(b)} This follows from part \textbf{(a)}, applied to $A^{T}$ instead
of $A$.

\textbf{(c)} Follows by combining \textbf{(a)} with \textbf{(b)} (since an
inverse is both a left inverse and a right inverse).
\end{proof}

\subsection{Finding inverses}

Is there a better algorithm for inverting a matrix (i.e., finding its inverse)
than what we did in the examples above?

Yes. We will use the following notation:

\begin{definition}
Let $B$ be an $n\times m$-matrix, and let $C$ be an $n\times p$-matrix. Then,
$\left[  B\mid C\right]  $ denotes the $n\times\left(  m+p\right)  $-matrix
obtained by gluing $C$ to the right edge of $B$.
\end{definition}

\begin{example}
If $B=\left(
\begin{array}
[c]{cc}%
u & v\\
w & x
\end{array}
\right)  $ and $C=\left(
\begin{array}
[c]{ccc}%
a & b & c\\
d & e & f
\end{array}
\right)  $, then%
\[
\left[  B\mid C\right]  =\left(
\begin{array}
[c]{ccccc}%
u & v & a & b & c\\
w & x & d & e & f
\end{array}
\right)  .
\]

\end{example}

More generally, we can define the notation $\left[  B_{1}\mid B_{2}\mid
\cdots\mid B_{m}\right]  $ for any (finite) sequence of matrices $B_{1}%
,B_{2},\ldots,B_{m}$ with the same number of rows. This generalizes the
notation $\left[  v_{1}\mid v_{2}\mid\cdots\mid v_{m}\right]  $ for $m$ column
vectors $v_{1},v_{2},\ldots,v_{m}$.

\begin{lemma}
Let $A$ be a $q\times n$-matrix. Let $B$ be an $n\times m$-matrix, and let $C$
be an $n\times p$-matrix. Then,%
\[
A\left[  B\mid C\right]  =\left[  AB\mid AC\right]  .
\]

\end{lemma}

\begin{proof}
The definition of $\left[  B\mid C\right]  $ yields%
\[
\left[  B\mid C\right]  =\left[  \operatorname{col}_{1}B\mid\operatorname{col}%
_{2}B\mid\cdots\mid\operatorname{col}_{m}B\mid\operatorname{col}_{1}%
C\mid\operatorname{col}_{2}C\mid\cdots\mid\operatorname{col}_{p}C\right]
\]
(where we use our old notation $\operatorname{col}_{k}D$ for the $k$-th column
of a matrix $D$).

Recall (from Proposition 2.6.2 \textbf{(c)} from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-09-23.pdf}{2019-09-23})
that%
\[
\operatorname{col}_{j}\left(  AB\right)  =A\cdot\operatorname{col}%
_{j}B\ \ \ \ \ \ \ \ \ \ \text{for each }j\in\left\{  1,2,\ldots,m\right\}  ;
\]
thus,%
\[
AB=\left[  A\cdot\operatorname{col}_{1}B\ \mid\ A\cdot\operatorname{col}%
_{2}B\ \mid\ \cdots\ \mid\ A\cdot\operatorname{col}_{m}B\right]  .
\]
Similarly,%
\[
AC=\left[  A\cdot\operatorname{col}_{1}C\ \mid\ A\cdot\operatorname{col}%
_{2}C\ \mid\ \cdots\ \mid\ A\cdot\operatorname{col}_{p}C\right]
\]
and%
\begin{align*}
&  A\left[  B\mid C\right] \\
&  =\left[  A\cdot\operatorname{col}_{1}\left[  B\mid C\right]  \ \mid
\ A\cdot\operatorname{col}_{2}\left[  B\mid C\right]  \ \mid\ \cdots
\ \mid\ A\cdot\operatorname{col}_{m+p}\left[  B\mid C\right]  \right] \\
&  =\left[  A\cdot\operatorname{col}_{1}B\ \mid\ A\cdot\operatorname{col}%
_{2}B\ \mid\ \cdots\ \mid\ A\cdot\operatorname{col}_{m}B\ \mid\ A\cdot
\operatorname{col}_{1}C\ \mid\ A\cdot\operatorname{col}_{2}C\ \mid
\ \cdots\ \mid\ A\cdot\operatorname{col}_{p}C\right] \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left[  B\mid C\right]  =\left[
\operatorname{col}_{1}B\mid\operatorname{col}_{2}B\mid\cdots\mid
\operatorname{col}_{m}B\mid\operatorname{col}_{1}C\mid\operatorname{col}%
_{2}C\mid\cdots\mid\operatorname{col}_{p}C\right]  \right) \\
&  =\left[  AB\mid AC\right]  .
\end{align*}

\end{proof}

\begin{example}
If $A=\left(
\begin{array}
[c]{cc}%
1 & 2
\end{array}
\right)  $ and $B=\left(
\begin{array}
[c]{cc}%
u & v\\
w & x
\end{array}
\right)  $ and $C=\left(
\begin{array}
[c]{ccc}%
a & b & c\\
d & e & f
\end{array}
\right)  $, then%
\[
AB=\left(
\begin{array}
[c]{cc}%
u+2w & v+2x
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ AC=\left(
\begin{array}
[c]{ccc}%
a+2d & b+2e & c+2f
\end{array}
\right)  ,
\]
thus%
\[
\left[  AB\mid AC\right]  =\left(
\begin{array}
[c]{ccccc}%
u+2w & v+2x & a+2d & b+2e & c+2f
\end{array}
\right)  .
\]
On the other hand,%
\begin{align*}
\left[  B\mid C\right]   &  =\left(
\begin{array}
[c]{ccccc}%
u & v & a & b & c\\
w & x & d & e & f
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \text{so that}\\
A\left[  B\mid C\right]   &  =\left(
\begin{array}
[c]{ccccc}%
u+2w & v+2x & a+2d & b+2e & c+2f
\end{array}
\right)  .
\end{align*}

\end{example}

The following method for inverting a matrix is \cite[Method 11.11]{Strickland}:

\begin{theorem}
Let $A$ be an $n\times n$-matrix. Form the $n\times\left(  2n\right)  $-matrix
$\left[  A\mid I_{n}\right]  $. Apply row operations to bring the latter
matrix into RREF; let this RREF be $\left[  T\mid B\right]  $, where $T$ is
its \textquotedblleft left half\textquotedblright\ (i.e., the first $n$
columns) and $B$ is its \textquotedblleft right half\textquotedblright\ (i.e.,
the last $n$ columns).

\textbf{(a)} If $T=I_{n}$, then $A$ is invertible and its inverse is
$A^{-1}=B$.

\textbf{(b)} If $T\neq I_{n}$, then $A$ is not invertible.
\end{theorem}

\begin{example}
Let $n=2$ and $A=\left(
\begin{array}
[c]{cc}%
1 & 2\\
3 & 4
\end{array}
\right)  $. Let us bring $\left[  A\mid I_{n}\right]  $ to RREF:%
\begin{align*}
\left[  A\mid I_{n}\right]   &  =\left(
\begin{array}
[c]{cccc}%
1 & 2 & 1 & 0\\
3 & 4 & 0 & 1
\end{array}
\right)  \overset{\text{add }-3\cdot\operatorname{row}1\text{ to
}\operatorname{row}2}{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 2 & 1 & 0\\
0 & \fbox{$-2$} & -3 & 1
\end{array}
\right) \\
&  \overset{\text{scale row }2\text{ by }-1/2}{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 2 & 1 & 0\\
0 & \fbox{$1$} & 3/2 & -1/2
\end{array}
\right) \\
&  \overset{\text{add }-2\cdot\operatorname{row}2\text{ to }\operatorname{row}%
2}{\longrightarrow}\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & -2 & 1\\
0 & \fbox{$1$} & 3/2 & -1/2
\end{array}
\right) \\
&  =\left[  T\mid B\right]  \ \ \ \ \ \ \ \ \ \ \text{for }T=\left(
\begin{array}
[c]{cc}%
\fbox{$1$} & 0\\
0 & \fbox{$1$}%
\end{array}
\right)  \text{ and }B=\left(
\begin{array}
[c]{cc}%
-2 & 1\\
3/2 & -1/2
\end{array}
\right)  .
\end{align*}
Since $T=I_{2}$, we thus conclude that $A$ is invertible, and its inverse is
$A^{-1}=B=\left(
\begin{array}
[c]{cc}%
-2 & 1\\
3/2 & -1/2
\end{array}
\right)  $.
\end{example}

\begin{proof}
[Proof of Theorem.]We have obtained $\left[  T\mid B\right]  $ from $\left[
A\mid I_{n}\right]  $ by row operations. Thus, Corollary 1.3.4 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-09.pdf}{2019-10-09}
shows that
\[
\left[  T\mid B\right]  =U\left[  A\mid I_{n}\right]
\]
for some matrix $U$ that can be written as a product of elementary matrices.
Consider this $U$. Now,%
\[
\left[  T\mid B\right]  =U\left[  A\mid I_{n}\right]  =\left[  UA\mid
UI_{n}\right]  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the last Lemma}\right)  .
\]
In other words, $T=UA$ and $B=UI_{n}$. Hence, $B=UI_{n}=U$.

\textbf{(a)} If $T=I_{n}$, then we thus have $I_{n}=T=\underbrace{U}_{=B}%
A=BA$, which shows that $B$ is a left inverse of $A$, and thus $A$ has an
inverse (by the Inverse Matrix Theorem), which must therefore be $B$ (since
$I_{n}=BA$).

\textbf{(b)} Assume that $T\neq I_{n}$. We must show that $A$ is not invertible.

We know that $\left[  T\mid B\right]  $ can be obtained from $\left[  A\mid
I_{n}\right]  $ by row operations.

Thus, $T$ can be obtained from $A$ by the same row operations. Moreover, since
$\left[  T\mid B\right]  $ is in RREF, $T$ must also be in RREF, because $T$
is the left half of $\left[  T\mid B\right]  $. Thus, $T$ is the RREF of $A$.
Since $T\neq I_{n}$, we conclude that $A$ cannot be row-reduced to $I_{n}$.
Thus, statement \textbf{(a)} of the Inverse Matrix Theorem is false. Hence,
statement \textbf{(k)} is false. In other words, $A$ is not invertible.
\end{proof}

\begin{example}
Let
\[
A=\left(
\begin{array}
[c]{ccc}%
1 & a & b\\
0 & 1 & c\\
0 & 0 & 1
\end{array}
\right)  .
\]
Then, $A$ is easily seen to be invertible; what is its inverse?%
\begin{align*}
\left[  A\mid I_{n}\right]   &  =\left(
\begin{array}
[c]{cccccc}%
1 & a & b & 1 & 0 & 0\\
0 & 1 & c & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 0 & 1
\end{array}
\right)  \\
&  \longrightarrow\left(
\begin{array}
[c]{cccccc}%
1 & a & b & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 1 & -c\\
0 & 0 & 1 & 0 & 0 & 1
\end{array}
\right)  \\
&  \longrightarrow\left(
\begin{array}
[c]{cccccc}%
1 & a & 0 & 1 & 0 & -b\\
0 & 1 & 0 & 0 & 1 & -c\\
0 & 0 & 1 & 0 & 0 & 1
\end{array}
\right)  \\
&  \longrightarrow\left(
\begin{array}
[c]{cccccc}%
1 & 0 & 0 & 1 & -a & -b-a\left(  -c\right)  \\
0 & 1 & 0 & 0 & 1 & -c\\
0 & 0 & 1 & 0 & 0 & 1
\end{array}
\right)  .
\end{align*}
Thus, $A$ is invertible, and its inverse is%
\[
A^{-1}=\left(
\begin{array}
[c]{ccc}%
1 & -a & -b-a\left(  -c\right)  \\
0 & 1 & -c\\
0 & 0 & 1
\end{array}
\right)  =\left(
\begin{array}
[c]{ccc}%
1 & -a & ac-b\\
0 & 1 & -c\\
0 & 0 & 1
\end{array}
\right)  .
\]
In the same way, you can see that \textbf{any} upper-triangular matrix with
nonzero entries on the diagonal is invertible, and its inverse is again an
upper-triangular matrix with nonzero entries on the diagonal.
\end{example}



\begin{thebibliography}{9999999999}                                                                                       %
\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}