\documentclass[12pt]{amsart}

\usepackage{241}

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


\begin{document}

\maketitle

The following theorem is the usual reason why we care about a basis; it represents a nice way of coding a subspace.
\begin{thm}
  \label{unique-lc}
  Let $\SA = \{a_1,\ldots,a_k\}$ be a basis for some subspace $S$ of $\RR^n$; then for any $b\in S$, there is a \emph{unique} sequence of coefficients $\lambda_1,\ldots,\lambda_k\in\RR$ such that
  \[
    b = \lambda_1 a_1 + \cdots + \lambda_k a_k
  \]
\end{thm}
\begin{proof}
  Since $\SA$ is a basis for $S$, $\lspan\SA = S$, and so there is some sequence of coefficients $\lambda_1,\ldots,\lambda_k\in\RR$ such that
  \[
    b = \lambda_1 a_1 + \cdots + \lambda_k a_k
  \]
  Now if $\mu_1,\ldots,\mu_k\in\RR$ is another sequence of coefficients such that
  \[
    b = \mu_1 a_1 + \cdots + \mu_k a_k
  \]
  then we have
  \[
    (\lambda_1 - \mu_1)a_1 + \cdots + (\lambda_k - \mu_k)a_k = 0
  \]
  Thus by linear independence of $\SA$, $\lambda_i - \mu_i = 0$ for all $i$, and so $\lambda_i = \mu_i$ for all $i$.
\end{proof}

We've already (essentially) seen the proofs of the following lemmas, through various other results throughout the course, but they deserve another look.  They'll also play an important role in the theorems we prove today.
\begin{lemma}
  \label{rref-null}
  Let $R$ be an $m\times n$ matrix in reduced row-echelon form.  If $m < n$, then there is a nonzero vector $s\in\RR^n$ such that $Rs = 0$.  In other words,
  \[
    \nul(R) \neq \{0\}
  \]
\end{lemma}
\begin{proof}
  The number of variables in the system $Rx = 0$ is exactly $n$.  There can be at most $m$-many of them that are leading variables (since there can only be one leading variable per row); hence if $m < n$, then there are some variables in this system which are free.  Then by choosing any nonzero value for this free variable, and solving for the others, we get a nonzero solution to $Rx = 0$.  
\end{proof}

\begin{lemma}
  \label{roweq-null}
  Let $A$ and $B$ be $m\times n$ matrices which are row-equivalent.  Then $\nul(A) = \nul(B)$.
\end{lemma}
\begin{proof}
  Suppose $A$ and $B$ are row-equivalent.  Then there are elementary matrices $E_1,\ldots,E_k$ such that $B = E_k\cdots E_1 A$.  So if $s\in\nul(A)$, then
  \[
    Bs = (E_k\cdots E_1 A)s = E_k\cdots E_1 (As) = E_k\cdots E_1 0 = 0
  \]
  and so $s\in\nul(B)$.  This shows $\nul(A)\subseteq \nul(B)$.  Similarly, there are elementary matrices $F_1,\ldots,F_\ell$ such that $A = F_\ell\cdots F_1 B$, and the same argument proves that $\nul(B) \subseteq \nul(A)$.
\end{proof}

\begin{cor}
  \label{non-null}
  If $A$ is an $m\times n$ matrix and $m < n$, then $\nul(A) \neq \{0\}$.
\end{cor}
\begin{proof}
  Let $R$ be the reduced row echelon form of $A$.  Then by Lemma~\ref{rref-null}, $\nul(R)\neq \{0\}$, since $R$ has more columns than rows.  Since $A$ and $R$ are row-equivalent, by Lemma~\ref{roweq-null}, $\nul(A) = \nul(R)$.  So we're done.
\end{proof}

\begin{thm}
  \label{basis-invertibility}
  Let $a_1,\ldots,a_n\in\RR^m$ be distinct vectors, and let $A$ be the $m\times n$ matrix whose columns are $a_1,\ldots,a_n$.  Then the following are equivalent;
  \begin{enumerate}[(i)]
    \item\label{LI.1}  $\{a_1,\ldots,a_n\}$ is linearly independent,
    \item\label{LI.2}  $A$ is left-invertible.
  \end{enumerate}
  The following are also equivalent (though not equivalent to the above two statements)
  \begin{enumerate}[(1)]
    \item  $\lspan\{a_1,\ldots,a_n\} = \RR^m$,
    \item  $A$ is right-invertible.
  \end{enumerate}
\end{thm}
\begin{proof}
  I'll just prove~\eqref{LI.1} is equivalent to~\eqref{LI.2}.  First, suppose $\{a_1,\ldots,a_n\}$ is linearly independent.  Note that for all $s\in\RR^n$,
  \[
    As = s_1 a_1 + \cdots + s_n a_n
  \]
  and therefore if $As = 0$, by linear independence it must be that $s = 0$; in other words, $\nul(A) = \{0\}$.  Now let $R$ be the reduced row echelon form of $A$; then $\nul(R) = \nul(A) = \{0\}$ by Lemma~\ref{roweq-null}.  It follows that $R$ has the following form;
  \[
    \begin{pmatrix}
      1 & 0 & \cdots & 0 \\
      0 & 1 & \cdots & 0 \\
      \vdots & \vdots & \ddots & \vdots \\
      0 & 0 & \cdots & 1 \\
        &   & \vdots &  \\
      0 & 0 & \cdots & 0 \\
    \end{pmatrix}
  \]
  Let $L = R^\top$, ie the $n\times m$ matrix
  \[
    \begin{pmatrix}
      1 & 0 & \cdots & 0 & \cdots & 0 \\
      0 & 1 & \cdots & 0 & \cdots & 0 \\
      \vdots & \vdots & \ddots & & \vdots & \\
      0 & 0 & \cdots & 1 & \cdots & 0 \\
    \end{pmatrix}
  \]
  Then $LR = I_n$.  Since $R = EA$ for some matrix $E$, we get $(LE)A = I_n$, and so $A$ is left-invertible.

  Now suppose $A$ is left-invertible, say with left inverse $B$.  If $\lambda_1,\ldots,\lambda_n\in\RR$ are such that
  \[
    \lambda_1 a_1 + \cdots + \lambda_n a_n = 0
  \]
  then
  \[
    \begin{pmatrix}
      \lambda_1 \\ \vdots \\ \lambda_n \\
    \end{pmatrix} = 
    I\begin{pmatrix}
      \lambda_1 \\ \vdots \\ \lambda_n \\
    \end{pmatrix} = 
    BA\begin{pmatrix}
      \lambda_1 \\ \vdots \\ \lambda_n \\
    \end{pmatrix} = 
    B(\lambda_1 a_1 + \cdots + \lambda_n a_n) = B0 = 0
  \]
  and hence $\lambda_1 = \cdots = \lambda_n = 0$.
\end{proof}
\begin{cor}
  Let $A$ be an $m\times n$ matrix.  Then $A$ is invertible if and only if its columns make up a basis for $\RR^m$.
\end{cor}

\begin{example*}
  Is the following set a basis for $\RR^4$?
  \[
    \left\{
      \begin{pmatrix}
        1 \\ 3 \\ 0 \\ 0 \\
      \end{pmatrix},
      \begin{pmatrix}
        2 \\ 4 \\ 0 \\ 0 \\
      \end{pmatrix},
      \begin{pmatrix}
        0 \\ 0 \\ 1 \\ 4\\
      \end{pmatrix},
      \begin{pmatrix}
        0 \\ 0 \\ 1 \\ 6\\
      \end{pmatrix}
    \right\}
  \]
\end{example*}

\begin{thm}
  \label{dimension}
  Let $k\ge 1$ and let $S$ be any subspace of $\RR^k$.  Then any two bases for $S$ have the same size.
\end{thm}
\begin{proof}
  Let $\SA = \{a_1,\ldots,a_n\}$ and $\SB = \{b_1,\ldots,b_m\}$ be two bases for $S$.  Let $A$ and $B$ be the $k\times n$ and $k\times m$ matrices whose columns are $a_1,\ldots,a_n$ and $b_1,\ldots,b_m$ respectively. By Theorem~\ref{unique-lc}, we can write $b_i$ uniquely as a linear combination of $a_1,\ldots,a_n$;
  \[
    b_i = \lambda_{i1}a_1 + \cdots + \lambda_{in} a_n
  \]
  Let $L$ be the $m\times n$ matrix with entries $\lambda_{ij}$.  Then the above proves that $B = AL$.  Since $B$ is left-invertible, so is $L$; for if $C$ is a left inverse for $B$, then $(CA)L = C(AL) = CB = I$.  So $\nul(L) = \{0\}$.  Then by Corollary~\ref{non-null}, $L$ can't have more columns than rows, ie, $n\le m$.

  By symmetry (swapping $A$ with $B$ and performing the same argument) we see that $m\le n$.  Then $m = n$.
\end{proof}

Now we can make the following definition.
\begin{defn*}
  If $S$ is a subspace of $\RR^n$, then $\dim(S)$, the dimension of $S$, is the unique size of any basis for $S$.
\end{defn*}

And now we can finally prove that all invertible matrices are square!
\begin{cor}
  If $A$ is an invertible matrix then $A$ must be square.
\end{cor}
\begin{proof}
  Suppose $A$ is $m\times n$ and invertible.  Then its columns form a basis for $\RR^m$, by Theorem~\ref{basis-invertibility}.  There are $n$ of them; there are also $m$ many standard basis vectors for $\RR^m$.  Therefore $m = n$ by Theorem~\ref{dimension}.
\end{proof}

\end{document}
