\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{} %TCIDATA{} %TCIDATA{} %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}[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}