
\documentclass[12pt]{article}
% Friday May 4 2001 Afternoon
\usepackage{amsthm,amsfonts,amsmath,amssymb,latexsym,epsfig}
%
\title{Equivalence of Matrices}
\author{Math 542}
%\date{Due on or before Monday April 16 2001}
%
\newif\iftell
\tellfalse
%
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\B}{\mathbb{B}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\U}{\mathbb{U}}
\newcommand{\GL}{\mathbb{GL}}
%
\newcommand{\Proof}[1]{\par\medskip\par\noindent{\it Proof#1.}}
\newcommand{\QED}{\hfill QED\par\medskip\par}
\newcommand{\jdef}[1]{{\bf #1}\index{#1}}
\newcommand{\tr}{^*}
\newcommand{\ctr}{^\dagger}
\newcommand{\dig}{\phantom{0}} % For alignment
\newcommand{\sig}{\phantom{+}} %      "
%
%
\newcommand{\row}{\mathrm{row}}
\newcommand{\col}{\mathrm{col}}
\newcommand{\entry}{\mathrm{entry}}
\newcommand{\diag}{\mathrm{diag}}
%
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cR}{\mathcal{R}}
%
\newcommand{\Mat}{\left[\begin{array}}
\newcommand{\Rix}{\end{array}\right]}
%
\newcommand{\Span}{\mathrm{Span}}
\newcommand{\Aut}{\mathrm{Aut}}
\newcommand{\Scale}{\mathrm{Scale}}
\newcommand{\Shear}{\mathrm{Shear}}
\newcommand{\Swap}{\mathrm{Swap}}
\newcommand{\rank}{\mathrm{rank}}
%
\newtheorem{PARA}{}[section]
\newcommand{\para}{\begin{PARA}\rm }
\newcommand{\arap}{\end{PARA}}
\newtheorem{theorem}[PARA]{Theorem}
\newtheorem{corollary}[PARA]{Corollary}
\newtheorem{lemma}[PARA]{Lemma}
\newtheorem{proposition}[PARA]{Proposition}
%
\newcommand{\medskipnoindent}{\par\medskip\par\noindent}
\begin{document}

   \maketitle


\iftell
\begin{quote}\em
Use this document to guide you in writing your term paper.
Your reader is a student who has taken Math~340 and
Math~541 and understands these subjects well. Beyond this
do not assume your reader knows anything you don't tell him/her.
Do not assume s/he has this document or that s/he is familiar with
the particular text book you used. However, you may cite one or more
text books. It will be particularly helpful to your reader
if you give exact page numbers.

You may choose a different topic if you discuss it with me first.
You should hand in a first draft two weeks before the
final exam at the latest. I will probably suggest revisions;
if so, the revised version is due on the day of the final exam.
When you hand in your paper I will give you my version.
My version is a completion of the outline in this document.
\end{quote}
\else
\fi
\section{Introduction}

\iftell
\begin{quote}\em
In this section give a discussion of what is in the paper and
why it is interesting. At the end of this section acknowledge
any discussions you had with any other person which are relevant to
this paper.
\end{quote}
\else

The first thing taught in Math~340 is Gaussian Elimination,
i.e. the process of transforming a matrix to reduced row
echelon form by elementary row operations.
Because this process has the effect of
multiplying the matrix by an invertible matrix it has
produces a new matrix for which the solution space
of the corresponding linear system is unchanged.
This is made precise by Theorem~\ref{thm:LEqu} below.

The theory of Gaussian elimination has the following features:
\begin{enumerate}
\item There is an equivalence relation which respects
the essential properties of some class of problems.
Here the equivalence relation is called {\em row equivalence}
by most authors; we call it {\em left equivalence}.
\item The equivalence classes of this relation are the orbits of a group
action. In the case of left equivalence the group is the general linear group
acting by left multiplication.
\item There is a characterization of the equivalence relation
in terms of some invariant (or invariants) associated to a matrix.
In the case of left equivalence the characterization is provided by Theorem~\ref{thm:LEqu}
which says that two matrices of the same size are left equivalent
if and only if they have the same null space.
\item There is a normal form and a theorem which says that
each matrix is equivalent to a unique matrix in normal form.
In the case of left equivalence the normal form is {\em reduced
row echelon form} (not explained in this paper).
\end{enumerate}

Our aim in this paper is to give other examples of equivalence
relations which fit this pattern. Two examples ({\em right
[column] equivalence} and {\em left right equivalence}) are (or
should be) standard parts of the undergraduate curriculum; two
others ({\em lower equivalence} and {\em lower upper equivalence})
are not as well known but not appreciably more difficult.

This paper is the result of a term paper I assigned in my Math~542 class
in the spring semester of 2001 at the University of Wisconsin.
I provided the students with an outline, criticized their first
draft, and wrote this paper to fulfill a promise that they would
have my version of the term paper when they handed in their
final draft. You can generate the outline by modifying
the \LaTeX\ file that produced this document:
replace the command  \verb$\tellfalse$ by \verb$\telltrue$.
\fi

\section{Statement of the Theorems}

\iftell
\begin{quote}\em
Here you give precise statements of the theorems you are
going to prove. You should include those definitions which
are necessary to understand the statements of the theorems.
You might also state related theorems which you will not prove
but which serve  to help the reader understand the big picture.
Be sure to give a reference for anything you claim but do not prove.
The reader wants to know why it is true.
\end{quote}
\else
\fi

\para
Throughout $\F$ is a field and $\F^{m\times n}$ is the vector space
(over $\F$) of all $m\times n$ matrices with entries from $\F$.
We write $\F^n$ instead of $\F^{n\times 1}$.
 A  square matrix is
\jdef{diagonal}
iff  all the entries  off the diagonal vanish,
\jdef{upper triangular}
iff  all the entries  below the diagonal vanish,
\jdef{lower triangular}
iff  all the entries above the diagonal vanish, and
\jdef{unitriangular} iff it is upper triangular
and its diagonal entries are one.
In other words,  a matrix
\begin{itemize}
 \item $P$ is diagonal iff  $\entry_{ij}(P)=0$ for $i\ne j$,
 \item $P$ is upper triangular iff $\entry_{ij}(P)=0$ for $i>j$,
 \item $Q$ is lower triangular iff $\entry_{ij}(Q)=0$ for $i<j$, and
 \item $P$ is unitriangular iff
     $\entry_{ij}(P)=0$ for $i>j$ and $\entry_{ii}(P)=1$.
\end{itemize}
\arap

\para
The \jdef{general linear group} in dimension $n$ is the set
$\GL_n(\F)$
of all invertible $n\times n$ matrices with entries from $F$. Define
{\renewcommand{\arraystretch}{2}
\begin{eqnarray*}
   \D_n(\F)&=& \{P\in\GL_n(\F): P \mbox{ is diagonal}\},\\
   \B_n(\F)&=& \{P\in\GL_n(\F): P \mbox{ is upper triangular}\},\\
   \B'_n(\F)&=& \{P\in\GL_n(\F): P \mbox{ is lower triangular}\},\\
   \U_n(\F)&=& \{P\in\GL_n(\F): P \mbox{ is unitriangular}\}.
\end{eqnarray*}
}
\arap



\para{\bf Definition.}\label{def:Equ}
  Let  $A,B\in\F^{m\times n}$ be two matrices of the same size.
  We say that
 \begin{itemize}
\item $A$ is  \jdef{left equivalent} to $B$
iff there exists $Q\in\GL_m(\F)$ such that
 $$
     A=QB.
 $$
\item $A$ is  \jdef{right equivalent} to $B$
iff there exists $P\in\GL_n(\F)$ such that
 $$
     A=BP^{-1}.
 $$
\item $A$ is  \jdef{right left equivalent} to $B$
iff there  exist $Q\in\GL_m(\F)$ and $P\in\GL_n(\F)$
such that
 $$
     A=QBP^{-1}.
 $$
\item $A$ is  \jdef{lower equivalent} to $B$
iff there exists $Q\in\B_m'(\F)$ such that
 $$
     A=QB.
 $$
\item $A$ is  \jdef{lower upper equivalent} to $B$
iff there exist $Q\in\B_m'(\F)$ and $P\in\U_n(\F)$
such that
 $$
     A=QBP^{-1}.
 $$
 \end{itemize}
These are all equivalence relations, i.e.
where $A\equiv B$ denotes any of these four relations we have
$$
A\equiv A; \phantom{A\equiv B,\;B\equiv C\implies }\; \eqno\mbox{(Reflexive Law)}
$$
$$
A\equiv B\implies B\equiv A;\phantom{\;B\equiv C} \eqno\mbox{(Symmetric Law)}
$$
$$
    A\equiv B,\;B\equiv C\implies A\equiv C.  \eqno\mbox{(Transitive Law)}
$$
This follows immediately from the fact that
$\GL_m(\F)$ and $\GL_n(\F)$ are groups the sets
$\B_m'(\F)\subset\GL_m(\F)$ and $\U_n(\F)\subset\GL_n(\F)$ are   subgroups.
(See Corollary~\ref{TheseAreGroups} below.)
\arap

\begin{theorem}\label{thm:LEqu}
  Suppose that $A,B\in\F^{m\times n}$. Then $A$ and $B$ are
left equivalent if and only if they have the same null space.
\end{theorem}

\begin{theorem}\label{thm:REqu}
  Suppose that $A,B\in\F^{m\times n}$. Then $A$ and $B$ are
right equivalent if and only if they have the same range.
\end{theorem}


\begin{theorem}\label{thm:RLEqu}
  Suppose that $A,B\in\F^{m\times n}$. Then $A$ and $B$ are
right left equivalent if and only if they have the same rank.
\end{theorem}

\para{\bf Definition.}
For  $A\in\F^{m\times n}$, $p=1,\ldots,m$, $q=1,\ldots,n$, let
$A_{pq}\in\F^{p\times q}$ denote the $p\times q$ matrix which
forms upper left hand corner of $A$ so that
$$
    \entry_{ij}(A_{pq})=\entry_{ij}(A)
$$
for $i=1,\ldots,p$, $j=1,\ldots, q$.
The $(p,q)$ \jdef{corner rank} of $A$ is defined by
$$
  \delta_{pq}(A)=\rank(A_{pq}).
$$
\arap


\begin{theorem}\label{thm:LUEqu}
  Suppose that $A,B\in\F^{m\times n}$. Then $A$ and $B$ are
lower upper equivalent if and only if they have the same corner ranks.
\end{theorem}




\para{\bf Definition.} Let $W$ be a vector space of dimension $m$ over
the field  $\F$. A \jdef{flag} in $W$ is a sequence
of subspaces
$$
   \{0\}=W_0\subset W_1\subset W_2\subset\cdots\subset W_m=W
$$
such that $\dim(W_k)=k$ for $k=0,1,2,\ldots,m$.
The \jdef{standard flag} in $\F^m$ is defined by
$$
   W_k=\Span(e_1,e_2,\ldots, e_k)
$$
where $(e_1,e_2,\ldots, e_m)$ is the \jdef{standard basis}, i.e.
$e_i$ is the $i$th column of the identity matrix $I_m$.
The \jdef{reverse standard flag} in $\F^m$ is defined by
$$
   W_k'=\Span(e_{m-k+1},e_{m-k+2},\ldots,e_m).
$$
\arap

\begin{theorem}\label{thm:LOEqu}
  Suppose that $A,B\in\F^{m\times n}$.
Then $A$ and $B$ are lower equivalent if and only if
$$
    A^{-1}(W_k') = B^{-1}(W_k')
$$
for $k=0,1,2,\ldots,m$ where
$W_0',W_1',\ldots, W_m'$ is the reverse standard flag in $\F^m$.
\end{theorem}


Theorems~\ref{thm:LEqu}, \ref{thm:REqu}, and~\ref{thm:RLEqu}
are proved in Section~\ref{sec:LA};
Theorem~\ref{thm:LUEqu} is proved in Section~\ref{sec:rook}; and
Theorem~\ref{thm:LOEqu} is proved in Section~\ref{sec:flag}.

\iftell\else
\para{\bf Remark.} Theorem~\ref{thm:LOEqu} is Exercise~345E
in~\cite{ROBBIN}. The hint given there is only appropriate
when the matrices $A$ and $B$ have rank $m$.
\arap
\fi

\section{Elementary Matrices}


\para  Recall from  Math~340
that there are three kinds of
\jdef{elementary matrices} as follows.
\begin{description}
\item[\jdef{Scale}]
    The elementary matrix $\Scale(I_m,p,c)$ results from the
$m\times m$ identity matrix $I_m$
by  multiplying the $p$th row by $c$.
\item[\jdef{Swap}]
The elementary matrix  $\Swap(I_m,p,q)$ results from the
$m\times m$ identity matrix $I_m$
by interchanging rows $p$ and $q$.
\item[\jdef{Shear}]
The elementary matrix $\Shear(I_m,p,q,c)$ results from the
$m\times m$ identity matrix $I_m$
by adding $c$ times the $q$th row to the $p$th row.
\end{description}
Shears and swaps are defined only if $p\ne q$.
The {\em Fundamental Theorem on Row Operations}
(see~\cite{LEON} page~54)
says that
the matrix which results by  multiplying a matrix $A\in\F^{m\times n}$ on the left by an
elementary matrix is the same as the matrix which results by applying the
corresponding elementary row operation to $A$, i.e.
\begin{itemize}
\item
     $E=\Scale(I_m,p,c)$ $\;\implies\;$  $EA$ results from $A$ by
 multiplying the $p$th row by $c$;
\item
   $E=\Swap(I_m,p,q)$ $\;\implies\;$ $EA$  results from $A$ by
interchanging rows $p$ and $q$;
\item
 $E=\Shear(I_m,p,q,c)$ $\;\implies\;$ $EA$ results from $A$
by adding $c$ times the $q$th row to the $p$th row.
\end{itemize}
The {\em Fundamental Theorem  on Column Operations}
says that
multiplying on the right performs the corresponding column operation, i.e.
\begin{itemize}
\item
     $E=\Scale(I_n,p,c)$ $\;\implies\;$ $AE$ results from $A$ by
 multiplying the $p$th column by $c$;
\item
   $E=\Swap(I_n,p,q)$ $\;\implies\;$ $AE$  results from $A$ by
interchanging columns $p$ and $q$;
\item
  $E=\Shear(I_n,p,q,c)$ $\;\implies\;$ $AE$ results from $A$
by adding $c$ times the $p$th column to the $q$th column.
\end{itemize}
 An \jdef{upper shear}  is  an upper triangular shear matrix.
 A \jdef{lower shear}   is  a  lower triangular shear matrix.

\arap

\iftell\else
\para Elementary matrices are invertible; in fact,
the inverse of an elementary matrix is an
elementary matrix of the same type:
\begin{itemize}
\item
     $E=\Scale(I_n,p,c)\implies E^{-1}=\Scale(I_n,p,1/c)$;
\item
   $E=\Swap(I_n,p,q)\implies E^{-1}=E$;
\item
  $E=\Shear(I_n,p,q,c)\implies E^{-1}=\Shear(I_n,p,q,-c)$
\end{itemize}
\arap
\fi


\para
A set $S$ of invertible matrices is said
to \jdef{generate} a group $G$ of invertible matrices iff
(1)~$S\subseteq G$, and
(2)~every element of $G$ is the product of a finite number
of elements of $S$. It  is an easy consequence of
the Fundamental Theorem that

\medskip\noindent{\bf Theorem. }{\em
The elementary matrices generate $\GL_n(\F)$.
}

\medskip
  For the proof see~\cite{LEON} Page~59 for example,
or modify the arguments described below.
The following theorem is a refinement.
\arap



\para{\bf  Factorization Theorem.}\em
\begin{description}
\item[(i)] The invertible scales generate $\D_n(\F)$.
\item[(ii)] The upper shears generate $\U_n(\F)$.
\item[(iii)] The invertible scales and upper shears generate $\B_n(\F)$.
\item[(iv)] The invertible scales and lower shears generate $\B_n'(\F)$.
\end{description}
\arap



\begin{proof}
\iftell BLAH BLAH \else
An element $D\in\D_n(F)$ is a product
$D=E_1E_2\cdots E_n$ of elementary scales where
$E_i=\Scale(I_n,i,d_i)$ and $d_i$ is the $i$th diagonal entry of $D$.
This proves~(i).

To prove~(ii) note first that if $U\in U_n(\F)$ and $E$ is an upper shear
then $EU\in U_n(\F)$. This follows from the Fundamental Theorem;
subtracting a row of $U$ from a row above leaves entries to the left
of the diagonal unchanged. Now let $E_{p,q}=\Shear(I_n,p,q,-u_{p,q})$.
Then, by the Fundamental Theorem,  the matrix
$E_{1,n}E_{2,n}\cdots E_{n-1,n}U$
agrees with $U$ except in the $n$th column which is replaced by
the $n$th column of the identity matrix $I_n$. Repeat this process for
columns $n-1,n-2,\ldots,3,2$ (in that order) and we obtain
$$
   E_{1,2}(E_{1,3}E_{2,3})(E_{1,4}E_{2.4}E_{3,4})\cdots
(E_{1,n}E_{2,n}\cdots E_{n-1,n})U=I_n
$$
which (as the inverse of an elementary matrix is an elementary matrix of the same
type) proves~(ii). In case $n=3$ the above factorization takes the form
$$
\Mat{ccc}1&a&b\\0&1&c\\0&0&1\Rix=
\Mat{ccc}1&0&0\\0&1&c\\0&0&1\Rix
\Mat{ccc}1&0&b\\0&1&0\\0&0&1\Rix
\Mat{ccc}1&a&0\\0&1&0\\0&0&1\Rix.
$$

Item~(iii) follows from~(i) and~(ii) as every element of
$\B_n(\F)$ is the product of an element of $\D_n(\F)$
and an element of $\U_n(\F)$. Item~(iv) follows from
item~(iii) as the transpose of an element of $\B_n(\F)$
is an element of $\B'_n(\F)$ (and vice versa) and the transpose of an
upper shear is a lower shear.
\fi
\end{proof}


\begin{corollary}\label{TheseAreGroups} The sets
  $\D_n(\F)$, $\B_n(\F)$, $\B_n'(\F)$, and $\U_n(\F)$ are  all subgroups
of the group $\GL_n(\F)$.
\end{corollary}

\begin{proof}
\iftell BLAH BLAH \else
It is easy to see that each of these sets
contains the identity matrix and is closed under multiplication.
That these sets are closed under the inverse operation follows
from the Factorization Theorem and the fact that
the inverse of an elementary matrix is an elementary matrix of the same type.
\fi
\end{proof}


\section{Null Space, Range, and Rank}\label{sec:LA}

In this section we prove
Theorems~\ref{thm:LEqu}, \ref{thm:REqu}, and~\ref{thm:RLEqu}.
Recall that the \jdef{null space} of a matrix $A\in\F^{m\times n}$
is the subspace
$$
\cN(A)= \{v\in\F^n: Av=0\},
$$
the \jdef{range} of $A$ is the subspace
$$
\cR(A)= \{Av: v\in\F^n\},
$$
the \jdef{nullity} of $A$ is the dimension of $\cN(A)$,
and the \jdef{rank} of $A$ is the dimension of $\cR(A)$.

\begin{lemma}\label{lem:rn}
Suppose that $\gamma_1,\ldots\gamma_{r+k}\in\F^n$
satisfy
\begin{description}
\item[(i)] $A\gamma_1,\ldots,A\gamma_r$ form a basis for $\cR(A)$, and
\item[(ii)] $\gamma_{r+1},\ldots\gamma_{r+k}$ form a basis for $\cN(A)$.
\end{description}
Then $\gamma_1,\ldots\gamma_{r+k}$ forms a basis for $\F^n$.
\end{lemma}

\begin{proof}
{\em We show $\gamma_1,\ldots\gamma_{r+k}$ are linearly independent.}
Assume $c_1,\ldots,c_{r+k}\in\F$ satisfy
$$
   c_1\gamma_1+\cdots+c_r\gamma_r+
   c_{r+1}\gamma_{r+1}+\cdots+c_{r+k}\gamma_{r+k}=0.\eqno(1)
$$
Multiply by $A$: as $\gamma_{r+1},\ldots\gamma_{r+k}\in\cN(A)$ we
obtain
$$
   c_1A\gamma_1+\cdots+c_rA\gamma_r=0.
$$
By~(i) $c_1=\cdots=c_r=0$. Hence~(1) becomes
$c_{r+1}\gamma_{r+1}+\cdots+c_{r+k}\gamma_{r+k}=0$
so by~(ii) we get $c_{r+1}=\cdots=c_{r+k}=0$.

{\em We show $\gamma_1,\ldots\gamma_{r+k}$ span $\F^n$.}
Choose $v\in\F^n$. Then $Av\in\cR(A)$ so by~(i) there
exist $c_1,\ldots,c_r\in\F$ such that
$$
   Av= c_1A\gamma_1+\cdots c_rA\gamma_r.
$$
Hence $v-(c_1\gamma_1+\cdots +c_r\gamma_r)\in\cN(A)$
so by~(ii) there exist
$c_{r+1},\ldots,c_{r+k}\in\F$ with
$$
v-(c_1\gamma_1+\cdots +c_r\gamma_r)
=c_{r+1}\gamma_{r+1}+\cdots+c_{r+k}\gamma_{r+k}
$$
so $v$ is a linear combination of  $\gamma_1,\ldots,\gamma_{r+k}$
as required.
\end{proof}

\begin{corollary}[Rank Nullity Relation]
For $A\in\F^{m\times n}$ the rank of $A$ plus the nullity of $A$
is $n$.
\end{corollary}

\begin{proof}[Proof of~\ref{thm:LEqu}]
Assume that $A$ and $B$ are left equivalent, i.e. that
$A=QB$ where $Q\in\GL_m(\F)$.
\iftell  We must show that $\cN(A)=\cN(B)$. BLAH BLAH \else
Then as $Q$ is invertible we have
$$
   Av=0\iff QBv=0\iff Bv=0
$$
Therefore $\cN(A)=\cN(B)$ as required.
\fi

Conversely, assume that $\cN(A)=\cN(B)$.
\iftell BLAH BLAH  {\em (Your argument should define $Q$ and
prove that $A=QB$.) }\else
Let $\gamma_{r+1},\ldots,\gamma_n$ be a basis for $\cN(A)=\cN(B)$
and extend to a basis $\gamma_1,\ldots,\gamma_n$.
Then $A\gamma_1,\ldots,A\gamma_r$ are linearly independent
for otherwise some linear combination of $\gamma_1,\ldots,\gamma_r$
would lie in the null space of $A$ contradicting the independence of
$\gamma_1,\ldots,\gamma_n$.
Let $\alpha_i=A\gamma_i$ for $i=1,\ldots,r$
and extend to a basis $\alpha_1,\ldots\alpha_m$ of
$\F^m$. Similarly there is a basis $\beta_1,\ldots\beta_m$ of $\F^m$
such that $\beta_i=B\gamma_i$ for $i=1,\ldots,r$. Define $Q$
by $Q\beta_i=\alpha_i$ for $i=1,\ldots,m$. Then for
$i=1,\ldots,r$ we have
$$
A\gamma_i=\alpha_i=Q\beta_i=QB\gamma_i.
$$
This also holds for $i=r+1,\ldots,n$ as both sides are zero.
\fi
Hence $A=QB$ so $A$ and $B$ are left equivalent as required.
\end{proof}

\begin{proof}[Proof of~\ref{thm:REqu}]
Assume that $A$ and $B$ are right equivalent, i.e. that
$A=BP^{-1}$ where $P\in\GL_n(\F)$.
\iftell
We must show that $\cR(A)=\cR(B)$.
 BLAH BLAH
Therefore $\cR(A)=\cR(B)$ as required.
\else
Then $P(F^n)=\F^n$ as $P$ is invertible, so
$$
  \cR(A)=A(\F^n)=A(P(\F^n))=AP(F^n)=B(F^n)=\cR(B)
$$
as required.

Conversely assume $\cR(A)=\cR(B)$.
Let $\phi_1,\ldots,\phi_r$ be a basis for this space
and choose $\gamma_1,\ldots,\gamma_r$ and $\gamma_1',\ldots,\gamma_r'$
so that
$$
    A\gamma_i=\phi_i=B\gamma_i'\eqno(2)
$$
for $i=1,\ldots,r$.
Let $\gamma_{r+1},\ldots\gamma_n$ be a basis for $\cN(A)$
and $\gamma_{r+1}',\ldots\gamma_n'$ be a basis for $\cN(B)$.
By~\ref{lem:rn} $\gamma_1,\ldots,\gamma_n$ is a basis for $\F^n$ as is
$\gamma_1',\ldots,\gamma_n'$.
Then~(2) holds for $i=r+1,\ldots,n$ since both sides are zero.
Define $P$ by $\gamma_i=P\gamma_i'$
for $i=1,2,\ldots,n$. Then
$AP\gamma_i'=A\gamma_i=B\gamma_i'$ for $i=1,2,\ldots,n$
so $AP=B$ as required.
\fi
\end{proof}


\begin{proof}[Proof of~\ref{thm:RLEqu}]
\iftell BLAH BLAH \fi
Assume that $A$ and $B$ are left right equivalent, i.e. that
$A=QBP^{-1}$ where $Q\in\GL_m(\F)$ and $P\in\GL_n(\F)$.
Then
$$
  \cR(A)=A(\F^n)=QBP^{-1}(\F^n)=QB(\F^n)=Q\cR(B),
$$
i.e. the isomorphism $Q:\F^m\to\F^m$ restricts to an isomorphism
from $\cR(A)$ to $\cR(B)$. Hence
$$
   \rank(A)=\dim\cR(A)=\dim\cR(B)=\rank(B)
$$
as required.

For the converse we introduce the matrix
$$
      D_{m,n,r} =\Mat{ll}
              I_r&0_{r\times(n-r)}\\
              0_{(m-r)\times r}& 0_{(m-r)\times(n-r)}
                      \Rix. \eqno(3)
$$
It is easy to see that for any matrix $A\in\F^{m\times n}$
there is a basis $\gamma_1,\ldots,\gamma_n$ as in~Lemma~\ref{lem:rn}.
Moreover if $\gamma_1,\ldots,\gamma_n$ are the columns of the identity matrix $I_n$
and $A\gamma_1,\ldots,A\gamma_r$ are the first $r$ columns of the
the identity matrix $I_m$ then $A=D_{m,n,r}$. It follows as in the
proofs of~\ref{thm:LEqu} and~\ref{thm:REqu} that
that any matrix is right left equivalent to some $D_{m,n,r}$.
But the rank of $D_{m,n,r}$ is $r$. Hence if $A$ and $B$ have the same rank $r$
they are each right left equivalent to $D_{m,n,r}$ and hence to each other.
\end{proof}

\section{Rook Matrices}\label{sec:rook}


In this section we prove Theorem~\ref{thm:LUEqu}.

\para \label{def:rook}
A matrix is called a  \jdef{rook matrix},
iff all its entries are either $0$ or $1$ and it
has at most one nonzero entry
in every row and  at most one nonzero entry in every column.
An invertible rook matrix is also called a \jdef{permutation matrix}.
The matrix $D_{m,n,r}\in\F^{m\times n}$ defined by~(3) above
is an example of a rook matrix.
\arap

\para{\bf Remark.} The $n\times n$
permutation matrices  form a finite group isomorphic
to the group $S_n$ of permutations of the finite set
$\{1,2,\ldots,n\}$. Just as the transpositions generate the
latter, the swap matrices generate the former.
\arap

In Math~340 it is proved that every matrix is left equivalent
to a matrix $R$ in reduced row echelon form; one can show that this
matrix $R$ is unique. The following  theorem is analogous.
(Another analog is  Corollary~\ref{cor:Dmnr} below.)

\begin{theorem}[Rook Decomposition] \label{thm:rook}\sloppy
Every matrix  is  lower upper equivalent to a unique  rook matrix.
\end{theorem}


\begin{lemma}\label{lem:tri}
If $Q\in\B_m'(F)$ then $Q_{pp}\in\B_p'(\F)$
for $p=1,2,\ldots,m$. Similarly,
If $P\in\B_n(F)$ then $P_{qq}\in\B_q(\F)$
for $q=1,2,\ldots,n$.
\end{lemma}

\begin{proof}
\iftell BLAH BLAH
\else
It is clear that $Q_{pp}$ is triangular as it is the
upper left hand corner of a triangular matrix.
A triangular matrix is invertible if and only if its
diagonal entries are nonzero; hence the fact that $Q$
is invertible implies that $Q_{pp}$ is. The proof for $P$ is the same.
\fi
\end{proof}

\begin{lemma}\label{lem:corner} \sloppy
 Lower upper equivalent matrices have the same corner ranks.
\end{lemma}


\begin{proof}
\iftell{\em Hint: Block multiplication.}\fi
Assume that $AP=QB$ where $Q\in\B_m'(\F)$ and $P\in\B_n(\F)$.
Then
$$
AP=
\Mat{cc} A_{pq} & * \\ * & * \Rix
\Mat{cc} P_{qq} & * \\ 0 & * \Rix=
\Mat{cc} A_{pq}P_{qq} & * \\ * & * \Rix
$$
and
$$
QB=
\Mat{cc} Q_{pp} & 0 \\ * & * \Rix
\Mat{cc} B_{pq} & * \\ * & * \Rix=
\Mat{cc} Q_{pp}B_{pq} & * \\ * & * \Rix
$$
so $A_{pq}P_{qq}=Q_{pp}B_{pq}$ so $A_{pq}=Q_{pp}B_{pq}P_{qq}^{-1}$
so
$$
\delta_{pq}(A)=\rank(A_{pq})=\rank(B_{pq})=\delta_{pq}(B)
$$
as required.
\end{proof}

\begin{lemma}\label{lem:RookRank}
For a  rook matrix $D$ the corner ranks are given by
$$
 \delta_{pq}(D)  = \sum_{i=1}^p \sum_{j=1}^q \entry_{ij}(D).
$$
\end{lemma}

\begin{proof}
\iftell BLAH BLAH \fi
The sum on the right is the number of nonzero columns of
$D_{pq}$. These columns are independent because they
are distinct columns of the identity matrix $I_p$.
\end{proof}


\begin{corollary} \label{lem:RookEqual}
Two  rook matrices with the same corner ranks are equal.
\end{corollary}

\begin{proof}
\iftell BLAH BLAH \fi
By Lemma~\ref{lem:RookRank} a rook matrix $D$ satisfies
$$
\delta_{pq}(D)=
\delta_{p-1,q}(D)+\delta_{p,q-1}(D)-\delta_{p-1,q-1}(D)+\entry_{pq}(D).
$$
\end{proof}

\begin{proof}[Proof of~\ref{thm:rook}]
\iftell BLAH BLAH \else
The theorem says that every matrix $A$ can be transformed to a rook matrix
by  elementary row and column operations where the only
row operations allowed are scales and lower shears and the
only column operations allowed are upper shears and that the resulting
rook matrix is independent of the order of the operations.
Figure~\ref{fig:rook} gives an algorithm for doing this.
Uniqueness is proved as follows.
If $A$ is lower upper equivalent
to rook matrices $D$ and $D'$ then,  by Lemma~\ref{lem:corner},
$A$ and $D$ have the same
corner ranks as do $A$ and $D'$.
Hence $D=D'$ by Lemma~\ref{lem:RookEqual}.

\begin{figure}
\begin{verbatim}
for q=1:n %  loop on columns
  for p=1:m
     if (A(p,q)!=0)
         A(p,:) = A(p,:)/A(p,q)      % scale
         for i=p+1:m                 % shear
             A(i,:) = A(i,:) - A(i,q)*A(p,:)
         end
         go to next_Col
     end
  end next_Col
end
for p=1:m  %  loop on rows
    q=1;
    while (A(p,q)==0) q=q+1  end
    for j=q+1:n                      % shear
       A(:,j) = A(:,j) - A(p,j)*A(:,q)
    end
end
\end{verbatim}
\caption{Computing the rook matrix}
\label{fig:rook}
\end{figure}
\fi
\end{proof}


\begin{corollary}[Bruhat Decomposition]\label{cor:Bruhat}\sloppy
Every invertible matrix  is
lower upper equivalent to a unique permutation matrix.
\end{corollary}

\begin{proof}
This is a special case of: see~\ref{def:rook}.
\end{proof}

\begin{proof}[Proof of~\ref{thm:LUEqu}]
\iftell BLAH BLAH \else
`Only if' is Lemma~\ref{lem:corner}.
For the converse assume that $A,B\in\F^{m\times n}$
have the same corner ranks. By Theorem~\ref{thm:rook}
there are rook matrices $D$ and $D'$ with
$A$ right left equivalent to $D$ and
$B$ right left equivalent to $D'$. By
Lemma~\ref{lem:corner} $D$ and $D'$ have the same corner ranks,
so by Lemma~\ref{lem:RookEqual} $D=D'$. Hence $A$ is
right left equivalent to $B$.
\fi
\end{proof}


\begin{corollary} \label{cor:Dmnr}
Every $A\in\F^{m\times n}$ is
left right equivalent to a unique matrix $D_{m,n,r}$.
\end{corollary}

\iftell\else
\begin{proof} This was proved in the proof  of~\ref{thm:RLEqu}.
We can also deduce it from~\ref{thm:rook} as follows.
According to the Fundamental Theorem
left (resp. right) multiplication by a permutation matrix
permutes the rows (resp. columns) accordingly. More precisely,
for each permutation $\sigma\in S_n$ in the symmetric group
$S_n$ on $n$ symbols,  the permutation matrix $Q$  determined  by
$$
    \row_i(Q)=\row_{\sigma(i)}(I_m)
$$
for $i=1,2,\dots,m$ satisfies
$$
      \row_i(QA) = \row_{\sigma(i)}(A)
$$
for $A\in\F^{m\times n}$.
A similar statement holds for columns; namely if
$$
      \col_j(P)=\col_{\tau(j)}(I_m)
$$
for $i=1,2,\dots,m$ and $\tau\in S_m$, then
$$
      \col_j(AP)=\col_{\tau(j)}(A).
$$
Now it is clear that for any rook matrix $D$
there are permutation matrices
$Q$ and $P$ such that $QDP^{-1}=D_{m,n,r}$
which proves existence in~\ref{cor:Dmnr}.
Uniqueness follows from~\ref{thm:RLEqu} and the fact that
the rank of $D_{m,n,r}$ is $r$.
\end{proof}
\fi


\section{Flags}\label{sec:flag}

In this section we prove Theorem~\ref{thm:LOEqu}.
\iftell\else
As a warmup, consider the case $n=1$ and $m=2$.
Then
$$
   A= \Mat{c}a_1\\ a_2\Rix, \qquad B = \Mat{c} b_1\\ b_2\Rix
$$
and a typical element $Q\in \B_2'(\F)$ has form
$$
    Q=\Mat{cc} q_1 & 0 \\ q_2 & q_3\Rix
$$
where $q_1q_3\ne 0$. Then $A^{-1}(W_2')=\{0\}$ if and only
if $a_1\ne 0$ and the equation $A=QB$ can be solved for
$Q\in \B_2'(\F)$ if and only if either $a_1b_1\ne 0$
or $a_1=b_1=0$ and $a_2b_2\ne 0$ or $A=B=0$.
\fi


\begin{lemma}\label{lem:BB}
Suppose that $Q\in\GL_m(\F)$ is invertible.
Then
$$
  Q\in\B_m(\F)\iff  QW_k = W_k \mbox{ for } k=1,2,\ldots,m
$$
where $W_0,\ldots,W_m$ is the standard flag.
Similarly
$$
  Q\in\B_m'(\F)\iff  QW_k' = W_k' \mbox{ for } k=1,2,\ldots,m
$$
for $k=1,2,\ldots,m$ where $W_0',\ldots,W_m'$ is the reverse standard flag.
\end{lemma}

\begin{proof} \iftell BLAH BLAH\else
Recall that $W_k=\Span(e_1,\ldots,e_k)$ where $e_i$ is the $i$th column
of the identity matrix. For any matrix $Q$ we have
$$
       Qe_k = \sum_{i=1}^m \entry_{ik}(Q) e_i
$$
and $Q$ is upper triangular if and only if
$$
       Qe_k = \sum_{i=1}^k \entry_{ik}(Q) e_i,
$$
for all $k$ i.e. if and only if $Qe_k\in W_k$ for all $k$.
The proof in the lower triangular case is essentially the same.
 \fi
\end{proof}

\begin{proof}[Proof of~\ref{thm:LUEqu}]
Assume that $A=QB$ where $Q\in \B_m'(F)$.
\iftell BLAH BLAH \else
Then by Lemma~\ref{lem:BB}
we have
$$
   A^{-1}(W_k') = B^{-1}(Q^{-1}(W_k'))=B^{-1}(W_k')
$$
as required.
\fi

Conversely assume the preimages by $A$ and $B$ of the subspace $W_k$ are
equal  and denote this preimage by $V_k$.
Thus
$$
      V_k= A^{-1}(W_k')=B^{-1}(W_k')
$$
and
$$
   \cN(A)=\cN(B)=
V_0\subseteq V_1\subseteq V_2\subseteq\cdots\subseteq V_m=\F^{n\times 1}.
$$
Let
$$
   n_k=\dim(V_k).
$$
\medskipnoindent{\bf Claim.}
There are  bases $(\alpha_1\ldots,\alpha_m)$ and
$(\beta_1,\ldots,\beta_m)$ of $\F^{m\times 1}$
and a basis
$(\gamma_1,\ldots,\gamma_n)$ of $\F^{n\times 1}$
such that for $k=0,1,\ldots,m$
\begin{description}
\item[(i)] $W_k'=\Span(\alpha_1,\ldots,\alpha_k)=\Span(\beta_1,\ldots,\beta_k)$;
\item[(ii)] $(\gamma_1,\ldots,\gamma_{n_k})$ is a basis for $V_k$; and
\item[(iii)] $A\gamma_{n_k}=\alpha_k$ and $B\gamma_{n_k}=\beta_k$ if $n_{k-1}<n_k$.
\end{description}
\iftell BLAH BLAH \else To prove the claim take
$(\gamma_1,\ldots,\gamma_{n_0})$ to be any basis for the common
null space $V_0$ of $A$ and $B$. Now proceed inductively: assume
that $\alpha_i$ and $\beta_i$ have been defined for $i\le k-1$ and that
$\gamma_j$ has been defined for $j\le n_{k-1}$.

\medskipnoindent{\bf Subclaim.} Either $n_k=n_{k-1}$ or $n_k=n_{k-1}+1$.
Indeed, otherwise there are vectors
$v_1$ and $v_2$ in $V_k$ such that
$\gamma_1,\ldots,\gamma_{n_{k-1}}, v_1,v_2$ are independent.
Now $Av_1$ and $Av_2$ lie in $W_k'$ so some linear
combination $c_1Av_1+c_2Av_2$ lies in $W_{k-1}'$.
But then $c_1v_1+c_2v_2$ lies in $W_{k-1}'$ and is thus a linear combination
of $\gamma_{n_1},\ldots,\gamma_{n_{k-1}}$ contradicting the assumption
that $\gamma_1,\ldots,\gamma_{n_{k-1}}, v_1,v_2$ are independent.
This proves the subclaim.

Now if $n_{k-1}=n_k$ let $\alpha_k=\beta_k=e_k$
the $(n-k+1)$st column of the $m\times m$ identity matrix.
Otherwise extend the basis $\gamma_1,\ldots,\gamma_{n_{k-1}}$
of $V_{k-1}$ to a basis $(\gamma_1,\ldots,\gamma_{n_k})$  of $V_k$
and define $\alpha_k=A\gamma_{n_k}$ and $\beta_k=B\gamma_{n_k}$.
In either case $\alpha_k$ and $\beta_k$ are in $W_k'$ but
not in $W_{k-1}'$.
Since
$(\alpha_1,\ldots,\alpha_{k-1})$ and $(\beta_1,\ldots,\beta_{k-1})$
are bases of $W_{k-1}'$
it follows that
$(\alpha_1,\ldots,\alpha_k)$ and $(\beta_1,\ldots,\beta_k)$
are bases of $W_k'$. This proves the claim.

Since $(\beta_1,\ldots,\beta_m)$ is a basis for $\F^{m\times 1}$
there is a unique matrix $Q$
such that $Q\beta_k=\alpha_k$ for $k=1,2,\ldots,m$, and since
$(\alpha_1\ldots,\alpha_m)$ is also a basis,
the matrix $Q$ is invertible.
By~(i) and Lemma~\ref{lem:BB} $Q\in\B_m'(\F)$.
By~(iii) we have $QB\gamma_j=A\gamma_j$ for $j=n_1,\ldots,n_m=n$
and by~(ii) (with $k=0$) we have
$QB\gamma_j=A\gamma_j=0$ for $j=1,\ldots,n_0$.
Hence $QB\gamma_j=A\gamma_j$
for all $j$. By~(ii) (with $k=m$)
the sequence $(\gamma_1,\ldots,\gamma_n)$ is a basis
for $\F^{n\times 1}$  so $QB=A$.
\fi
\end{proof}


\begin{thebibliography}{99}
\bibitem{LEON} Steven J. Leon:
{\em Linear Algebra with Applications (4th Edition)},
Prentice Hall, 1994.

\bibitem{ROBBIN} J. W. Robbin:
{\em Matrix Algebra Using MINImal MATlab},
A.K. Peters, 1995.
\iftell
\begin{quote}\em
(In mathematical research papers it is customary to put
in the bibliography the references mentioned in the text and
no others.)
\end{quote}
\else
\fi
\end{thebibliography}
\end{document}
