\documentclass[11pt]{article}
\usepackage{amsmath,amsthm,amsfonts}
\newtheorem*{fact}{Fact}
\newtheorem*{theorem}{Theorem}
\renewcommand{\theenumi}{{(\roman{enumi})}}
\renewcommand{\labelenumi}{\textnormal{\theenumi}}

\begin{document}

\title{Elementary Matrices and Matrix Inverses}
\author{Mathematics 3A, Winter 1997}
\maketitle

The following is a complete proof of some important facts about
inverse matrices, and illustrates the role of the elementary matrices
in Linear Algebra. 

\begin{fact}
Every elementary row operation that converts a matrix $A\in M(n\times
n)$ into another matrix $B$ can be written as multiplication with an
elementary matrix $E$:
\begin{equation}
  EA = B.
\end{equation}
\end{fact}

All we need to know about elementary matrices is that they are
invertible, which can be checked by explicit calculation.  The
following theorem states in a precise form that our method for
checking invertibility of a matrix is indeed the correct one.

\begin{theorem}
Given a matrix $A\in M(n\times n)$, the following statements are
equivalent:
\begin{enumerate}
\item $A$ is invertible.
\item There exists a matrix $C$ such that $CA=I$.
\item $A$ can be transformed into the identity matrix $I$ by
elementary row operations (i.e.\ $A$ is \emph{row equivalent} to the
identity matrix).
\end{enumerate}
Moreover, when the inverse of $A$ exists, it is unique.
\end{theorem}

\begin{proof}
The best strategy here is to prove that (i) implies (iii), (iii)
implies (ii), and (ii) implies (i).  We start with the easiest part.
\smallskip

(iii) $\Rightarrow$ (ii): $A$ being row-equivalent to $I_n$ means, by
the above fact, that there are elementary matrices $E_1$, $E_2$,
\ldots, $E_i$ so that
\begin{equation}
  \label{e}
  E_1 E_2 \cdots E_i A = I.
\end{equation}
By simply setting
\begin{equation}
  \label{c}
  C := E_1 E_2 \cdots E_i,
\end{equation}
we obtain statement (ii).
\smallskip

(ii) $\Rightarrow$ (i): What we really need to check here is that
matrix $C$ not only satisfies $CA=I$, but also $AC=I$ (we stated this
as a theorem in class, but never proved it).

  First consider the particular matrix $C$ as defined by equation
\eqref{c}.  Left-multiply equation \eqref{e} with $E_1^{-1}$ and
right-multiply with $E_1$ to obtain
\begin{equation}
  E_2 E_3 \cdots E_i A E_1 = E_1^{-1} E_1 = I,
\end{equation}
then do the same with $E_2$, $E_3$, and so on.  We finally get
\begin{equation}
  A E_1 E_2 \cdots E_i = I.
\end{equation}
Thus we obtain $AC=I$.  We claim that \emph{any} matrix $D$ which
satisfies $DA=I$ must be equal to $C$.  Let's check:
\begin{equation}
  D = D I = D (AC) = (DA) C = I C = C.
\end{equation}
This proves at the same time that the inverse is unique, and that
$A^{-1}=C$.
\smallskip

(i) $\Rightarrow$ (iii): By contradiction.  Suppose that $A$ is not
row-equivalent to $I$.  Then there exist elementary matrices $E_1$, $E_2$,
\ldots, $E_i$ so that the matrix
\begin{equation}
  H :=  E_1 E_2 \cdots E_i A
\end{equation}
has zeros in the last row.  Define a vector
\begin{equation}
  b = E_1^{-1} E_2^{-1} \cdots E_i^{-1} e_n
\end{equation}
where $e_n$ is the unit vector
\begin{equation}
  e_n = \begin{pmatrix} 0 \\ \vdots \\ 0 \\ 1 \end{pmatrix},
\end{equation}
and try to solve the linear system $Ax=b$.  Left-multiplying this
equation with $E_1 E_2 \cdots E_i$ yields the equivalent system
\begin{equation}
  Hx = e_n.
\end{equation}
\enlargethispage{\baselineskip}%
This system does not have a solution because the last row of the
matrix on the left is zero, but the last row of the vector on the
right is one.  So $Ax=b$ does not have a solution for some vector $b
\in \mathbb{R}^n$, so $A$ cannot be invertible.
\end{proof}

\end{document}