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