
\documentclass[12pt]{amsart}

\usepackage{241}

\title{21-241 Matrices and Linear Transformations \\
       Summer 1 2012 \\
       Course notes \\
       Day 4}
\author{Paul McKenney}


\begin{document}

\maketitle

\begin{defn}
  A matrix $A$ is in \emph{reduced row echelon form (rref)} if
  \begin{enumerate}
    \item  Every zero row in $A$ is below every nonzero row.
    \item  The leading term in any nonzero row in $A$ is strictly to the right of all the leading terms in the rows above it.
    \item  The leading term in a nonzero row in $A$ is a $1$, and is the only nonzero entry in its column.
  \end{enumerate}

  A system of linear equations $Ax = b$ is in reduced row echelon form if and only if $A$ is.
\end{defn}

\begin{defn}
  Let $A$ be an $m\times n$ matrix.
  \begin{enumerate}
    \item  An $n\times m$ matrix $B$ such that $BA = I_n$ is called a \emph{left inverse} for $A$.
    \item  An $n\times m$ matrix $C$ such that $AC = I_m$ is called a \emph{right inverse} for $A$.
    \item  An $n\times m$ matrix $D$ which is both a left inverse and a right inverse for $A$ is called an \emph{inverse} for $A$.
  \end{enumerate}
  If $A$ has a left inverse or right inverse, $A$ is called \emph{left-invertible} or \emph{right-invertible} respectively.  $A$ is called \emph{invertible} if it is both left-invertible and right-invertible.
\end{defn}

Notice that, on the face of it, a matrix may be invertible but have no inverse.  The following result should correct our doubt about that.

\begin{fact}
  Suppose $A$ is invertible, and $B$ and $C$ are a left inverse and a right inverse for $A$, respectively.  Then $B = C$, and hence $A$ has an inverse.
\end{fact}
\begin{proof}
  We have
  \[
    B = BI = B(AC) = (BA)C = IC = C
  \]
\end{proof}

We also get a uniqueness theorem out of this, which will allow us to make the following definition.
\begin{cor}
  Suppose $A$ is invertible.  Then there is exactly one inverse for $A$.
\end{cor}
\begin{proof}
  If $B$ and $C$ are inverses for $A$, then in particular, $B$ is a left inverse and $C$ a right inverse.  Then $B = C$ by the above fact.
\end{proof}

\begin{defn}
  If $A$ is an invertible matrix, then $A^{-1}$ is the unique inverse of $A$.
\end{defn}

\begin{thm}
  Let $A$ be an $m\times n$ matrix.  Then the following are equivalent.
  \begin{enumerate}
    \item\label{surj.system}  For any choice of constants $b_1,\ldots,b_m$, the system of linear equations
    \begin{LinearSystems}{5}
      a_{11} x_1 + \cdots + a_{1n} x_n = b_1 \\
      a_{21} x_1 + \cdots + a_{2n} x_n = b_2 \\
        &           &        &        \vdots \\
      a_{m1} x_1 + \cdots + a_{mn} x_n = b_m \\
    \end{LinearSystems}
    has at least one solution.
    \item\label{surj.matrix}  For every $b\in\RR^m$, there is some $s\in\RR^n$ such that $As = b$.
    \item\label{surj.transformation}  $T_A : \RR^n\to\RR^m$ is surjective.
    \item\label{surj.inverse}  $A$ is right-invertible.
  \end{enumerate}
\end{thm}

\begin{proof}
  The equivalence of~\eqref{surj.system},~\eqref{surj.matrix}, and~\eqref{surj.transformation} is just a recapitulation of the definitions in play.  The real work is in proving they're equivalent to~\eqref{surj.inverse}.
  
  I'll prove~\eqref{surj.matrix} is equivalent to~\eqref{surj.inverse}.  First, assume~\eqref{surj.matrix}; we'll prove~\eqref{surj.inverse}.  Consider the standard basis vectors in $\RR^m$;
  \[
    e_1 = \begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}
    e_2 = \begin{pmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{pmatrix}
    \cdots
    e_m = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{pmatrix}
  \]
  By our assumption, there are vectors $s_1,\ldots,s_m\in\RR^n$ such that $As_1 = e_1, \ldots, As_m = e_m$.  Now let $B$ be the matrix with columns $s_1,\ldots,s_m$, in that order.  Then $B$ is $n\times m$, and for any $i,j$, $B_{ij} = (s_j)_i$, the $i$th entry of column vector $s_j$.  Then for all $i,j\le m$, we have
  \[
    (AB)_{ij} = \sum_{k=1}^n A_{ik} B_{kj} = \sum_{k=1}^n A_{ik} (s_j)_k = (As_j)_i = (e_j)_i = I_{ij}
  \]
  so $AB = I$.

  Now assume~\eqref{surj.inverse}, and let $B$ be a right inverse for $A$.  Let $b\in\RR^m$ be given.  Then
  \[
    A(Bb) = (AB)b = Ib = b
  \]
  and so there is some $s\in\RR^n$ such that $As = b$, namely $s = Bb$.
\end{proof}

\end{document}
