\documentclass{article}%
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{CSTFile=40 LaTeX article.cst}
%TCIDATA{Created=Tuesday, August 18, 2015 14:51:12}
%TCIDATA{LastRevised=Monday, October 05, 2015 11:19:09}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Standard LaTeX\Blank - Standard LaTeX Article">}
%TCIDATA{Language=American English}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\begin{document}

\title{Math 413/513 Chapter 3 (from Friedberg, Insel, \& Spence)}
\author{David Glickenstein}
\maketitle

\section{Matrices}

\subsection{Main results of this section}

The main theorem of this section is the following:

\begin{theorem}
\label{thm: row,col ops}Let $A$ be an $m\times n$ matrix of rank $r.$ Then
$r\leq m,$ $r\leq n,$ and $A$ can be transformed by row and column operations
into a matrix
\[
D=\left(
\begin{array}
[c]{cc}%
I_{r} & O_{1}\\
O_{2} & O_{3}%
\end{array}
\right)
\]
where $O_{1},O_{2},O_{3}$ are zero matrices. Thus $D_{ij}=1$ if $i=j\leq r$
and $0$ otherwise.
\end{theorem}

\begin{corollary}
\label{cor: row ops matrices}There exist invertible matrices $B\in F^{m\times
m}$ and $C\in F^{n\times n}$ such that $D=BAC.$
\end{corollary}

\begin{corollary}
\label{cor:transpose}Let $A$ be an $m\times n$ matrix. Then

\begin{enumerate}
\item $\operatorname{rank}A=\operatorname{rank}A^{T}.$

\item The rank of $A$ is equal to the maximum number of linear independent
rows, which is equal to the dimension of the row space.

\item The rows and columns of $A$ generate subspaces of the same dimension,
each with dimension equal to the rank of $A.$
\end{enumerate}
\end{corollary}

\begin{corollary}
\label{cor: inv}Every invertible matrix is the product of elementary matrices.
\end{corollary}

\subsection{Explanation and proof of the corollaries}

In order to make sense of these we need to know (1) what rank of a matrix is,
(2) what row and column operations are, (3) what elementary matrices are, and
(4) what the row and column spaces are.

\begin{definition}
If $A\in F^{m\times n},$ then the $\operatorname{rank}A=\operatorname{rank}%
L_{A},$ where $L_{A}$ is the linear transformation $F^{n}\rightarrow F^{m}$
given by $x\rightarrow Ax.$ The column space is the span of the columns of $A$
(so it is the span of $n$ vectors in $F^{m}$)\ and the row space is the span
of the rows of $A$ (so it is the span of $m$ vectors in $F^{m}$).
\end{definition}

\begin{proposition}
The column space of a matrix $A$ is equal to $R\left(  L_{A}\right)  .$ In
particular, the rank of $A$ is equal to the dimension of the column space.
\end{proposition}

\begin{proof}
The $i$th column is simply $Ae_{i}\in R\left(  L_{A}\right)  ,$ thus the
column space is in $R\left(  L_{A}\right)  .$ If $y\in R\left(  L_{A}\right)
,$ then there exists $x\in F^{n}$ such that $y=Ax,$ and so if the columns of
$A$ are labeled $A_{1},\ldots,A_{n},$ we have that
\[
y=x_{1}A_{1}+\cdots+x_{n}A_{n}.
\]

\end{proof}

We already know that row operations are important. It turns out that row
operations correspond to multiplication by certain matrices.

\begin{definition}
If $A\in F^{m\times n},$ the elementary row [column] operations are the following:

\begin{enumerate}
\item interchanging any two rows [columns] of $A;$

\item multiplying any row [column] of $A$ by a nonzero scalar;

\item adding any scalar multiple of a row [column] of $A$ to another row [column].
\end{enumerate}
\end{definition}

\begin{definition}
An $n\times n$ elementary matrix is a matrix obtained by performing one
elementary row operation on $I_{n}.$
\end{definition}

So examples of elementary matrices are
\[
\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0
\end{array}
\right)  ,\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & 2 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{array}
\right)  ,\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
3 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{array}
\right)
\]


\begin{theorem}
Let $A\in F^{m\times n}$ and suppose $B$ is obtained from $A$ by performing an
elementary row [column] operation. Then there exists an $m\times m$ [$n\times
n$] elementary matrix $E$ such that $B=EA$ [$B=AE$], where $E$ is the
elementary matrix obtained from $I$ in the same way. Conversely,
multiplication by elementary matrices correspond to performing row operations.
\end{theorem}

\begin{proof}
The proof relies on verifying this on each type of row/column operation and
each type of elementary matrix. It helps that we know that
\[
Be_{i}=B_{i}%
\]
where $B_{i}$ is the $i$th column, and we can see similarly that $e_{i}^{T}B$
is the $i$th row. The details are left as an exercise.
\end{proof}

It now follows that elementary matrices are invertible (this can also be
verified directly as well) since each row operation is reversible. Thus doing
a sequence of row (column) operations is the same as multiplying on the left
(right) by a sequence of elementary matrices. Thus, the only thing left to
show that Theorem \ref{thm: row,col ops} implies Corollary
\ref{cor: row ops matrices} is that the product of invertible matrices is
invertible. 

\begin{theorem}
Let $A\in F^{m\times n},$ $P\in F^{m\times m},$ and $Q\in F^{n\times n}.$ If
$P$ and $Q$ are invertible, then

\begin{enumerate}
\item $\operatorname{rank}\left(  AQ\right)  =\operatorname{rank}A$

\item $\operatorname{rank}\left(  PA\right)  =\operatorname{rank}A$

\item $\operatorname{rank}\left(  PAQ\right)  =\operatorname{rank}A$
\end{enumerate}
\end{theorem}

\begin{proof}
We can use what we know about linear transformations to see that
\[
R\left(  L_{AQ}\right)  =R\left(  L_{A}L_{Q}\right)  =L_{A}L_{Q}\left(
F^{n}\right)
\]
But since $Q$ is invertible, it is onto, so
\[
L_{A}L_{Q}\left(  F^{n}\right)  =L_{A}\left(  F^{n}\right)  =R\left(
A\right)  .
\]
Thus the ranks of $AQ$ and $A$ are equal. Similarly, since $P$ invertible,
$L_{P}$ is an isomorphism, so
\[
\dim L_{P}\left(  L_{A}\left(  F^{n}\right)  \right)  =\dim L_{A}\left(
F^{n}\right)  ,
\]
or $\operatorname{rank}\left(  PA\right)  =\operatorname{rank}A.$ The last one follows.
\end{proof}

\begin{corollary}
The product of elementary matrices is invertible, and elementary row and
column operations and their compositions are rank preserving.
\end{corollary}

This also allows us to prove Corollary \ref{cor: inv}.

\begin{proof}
[Proof of Corollary \ref{cor: inv}]We have just shown that the product of
elementary matrices is invertible. Now suppose a matrix is invertible. By
Corollary \ref{cor: row ops matrices}, we can convert the matrix into the form
of $D.$ Since this is rank preserving and the original matrix is invertible,
$D$ must be the identity matrix. But then we have that $I=BAC$ where $B$ and
$C$ are products of elementary matrices. It follows that $A=B^{-1}C^{-1},$
which is also a product of elementary matrices (if $B=E_{1}E_{2}\cdots E_{k}$
and $C=E_{k+1}E_{k+1}\cdots E_{\ell}$ then $B^{-1}C^{-1}=E_{k}^{-1}\cdots
E_{1}^{-1}E_{\ell}^{-1}\cdots E_{k+1}^{-1},$ which is a product of elementary
matrices since the inverse of an elementary matrix is an elementary matrix).
\end{proof}

Finally, we can prove Corollary \ref{cor:transpose}.

\begin{proof}
[Proof of Corollary \ref{cor:transpose}]We first note that if $E$ is an
elementary matrix, then $E^{T}$ is also an elementary matrix (check this!) and
also that $D^{T}$ has the same form as $D$ (though the dimensions of the
matrix may differ). So if $D=BAC$ then we have that $D^{T}=C^{T}A^{T}B^{T},$
and the rank of $D^{T}$ is clearly equal to $r=\operatorname{rank}A.$ Since
multiplication by $C^{T}$ and $B^{T}$ is rank preserving (it is the product of
elementary matrices) we have that $\operatorname{rank}A^{T}%
=\operatorname{rank}D^{T}=\operatorname{rank}D=\operatorname{rank}A.$ The
others follow from the fact that $\operatorname{rank}A$ is the dimension of
the column space of $A$ and $\operatorname{rank}A^{T}$ is the dimension of the
row space of $A$ (which is the column space of $A^{T}$).
\end{proof}

\subsection{Proof of Theorem \ref{thm: row,col ops}}

We phrase this as a sequence of exercises:

We will induct on $m,$ the number of rows. Before looking at base cases, we
actually think about the inductive step:

1) If $m>1$ and $n>1$ and $A$ is not the zero matrix, show that by a finite
number of row and column operations, $A$ can be transformed into a matrix of
the form:%
\[
B=\left(
\begin{array}
[c]{cccc}%
1 & 0 & \cdots & 0\\
0 &  &  & \\
\vdots &  & B^{\prime} & \\
0 &  &  &
\end{array}
\right)
\]
where $B^{\prime}$ is a matrix of dimension $\left(  m-1\right)  \times\left(
n-1\right)  .$ Note that $\operatorname{rank}B=1+\operatorname{rank}B^{\prime
}\leq m$ and $\leq n$ by the inductive hypothesis.

We now can use the inductive hypothesis on $B^{\prime}.$ We need only prove
the cases of $n=1,$ $m=1,$ and for the zero matrix. Note that the zero matrix
is already in the proper form, and has rank equal to zero (less than $n$ and
$m$).

2) Show that if $n=1$ and $A$ is not the zero matrix, we can transform $A$ to
the appropriate form by a finite sequence of column operations, and
$\operatorname{rank}A=1.$

3) Show that if $m=1$ and $A$ is not the zero matrix, we can transform $A$ to
the appropriate form by a finite sequence of row operations and
$\operatorname{rank}A=1$.

This completes the proof. I suggest you go through the process on an actual
example. The one from the book is:%
\[
A=\left(
\begin{array}
[c]{ccccc}%
0 & 2 & 4 & 2 & 2\\
4 & 4 & 4 & 8 & 0\\
8 & 2 & 0 & 10 & 2\\
6 & 3 & 2 & 9 & 1
\end{array}
\right)  .
\]
You should find that this matrix has rank 3 and that you can transform it by
row and column operations to the matrix%
\[
\left(
\begin{array}
[c]{ccccc}%
1 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 0
\end{array}
\right)  .
\]


\section{Inverse matrix}

We already know that an $n\times n$ matrix is invertible if and only if it has
rank $n,$ and if and only if it is a product of elementary matrices. We can
compute the inverse using augmented matrices.

\begin{definition}
Let $A$ and $B$ be $m\times n$ and $m\times p$ matrices, respectively. The
augmented matrix $\left(  A|B\right)  $ is the $m\times\left(  n+p\right)  $
matrix $\left(  A~B\right)  ,$ i.e., the matrix whose first $n$ columns are
the columns of $A$ and the last $p$ columns are the columns of $B.$
\end{definition}

\begin{proposition}
Suppose $A$ and $B$ both have $n$ rows and suppose $M$ is an $m\times n$
matrix. Then
\[
M\left(  A|B\right)  =\left(  MA|MB\right)  .
\]

\end{proposition}

\begin{proof}
Exercise.
\end{proof}

Now we can use this idea to find the inverse, since we see that
\[
A^{-1}\left(  A|I\right)  =\left(  A^{-1}A|A^{-1}\right)  =\left(
I|A^{-1}\right)  .
\]
Furthermore, we know that if $A$ is invertible, we can use row and column
operations to transform $A$ into $I,$ but in particular, since $A$ is
invertible, we do not need column operations. Thus there is an invertible
matrix $B,$ the product of elementary matrices, such that $BA=I.$ If we apply
this matrix to $\left(  A|I\right)  ,$ we get
\[
B\left(  A|I\right)  =\left(  BA|B\right)  =\left(  I|B\right)  .
\]
Since $BA=I,$ we have that $B=A^{-1}$ and so we can construct the inverse by
converting $\left(  A|I\right)  $ to $\left(  I|A^{-1}\right)  $ via row operations.

\section{Problems}

\begin{itemize}
\item FIS Section 3.1 exercises 2, 3, 5, 7-11 

\item FIS Section 3.2 exercises 2-7, 11, 14, 15, 18, 21. Read the Theorem 3.7
and its proof, 
\end{itemize}


\end{document}