\documentclass[12pt]{amsart}

\usepackage{241}

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


\begin{document}

\maketitle

\section{Basic material}

The proof of the following theorem is exactly the same as the proof of the theorem we saw last time, that all bases for the same subspace have the same size.  I've really just changed the assumptions and conclusions to match what I did in that proof.  In this one I'm using but not referencing the lemmas I proved last time; you should recognize where and how they're being used.
\begin{thm}
  Suppose $S$ is a subspace of $\RR^k$, and $X$ and $Y$ are finite subsets of $S$ such that $X$ is linearly independent and $Y$ spans $S$.  Then $|X| \le |Y|$.
\end{thm}
\begin{proof}
  Say $X = \{a_1,\ldots,a_n\}$ and $Y = \{b_1,\ldots,b_m\}$.  Since $Y$ spans $S$, and $X\subseteq S$, there are coefficients $\lambda_{ij}$ such that 
  \[
    a_j = \lambda_{1j}b_1 + \cdots + \lambda_{mj} b_m
  \]
  Let $A$ be the matrix with columns $a_1,\ldots,a_n$, $B$ the matrix with columns $b_1,\ldots,b_m$, and $L$ the matrix with entries $\lambda_{ij}$.  Then $A = BL$.  Since $X$ is linearly independent, $A$ is left-invertible.  Hence $L$ is too, and it follows that $L$ can't have more columns than rows.  Then $n\le m$.
\end{proof}

\begin{cor}
  Let $X$ be a linearly independent subset of $\RR^n$.  Then $|X| \le n$.
\end{cor}

\begin{lemma}
  Suppose $X\subseteq\RR^n$ is linearly independent, and $s\in\RR^n$ but $s\not\in\lspan(X)$.  Then $X\cup\{s\}$ is linearly independent.
\end{lemma}
\begin{proof}
  I'll prove the contrapositive; that if $X\cup\{s\}$ is linearly dependent, but $X$ is linearly independent, then $s\in\lspan(X)$.  So suppose $X\cup\{s\}$ is linearly dependent.  Then there are distinct $x_1,\ldots,x_k\in X$, and coefficients $\lambda_1,\ldots,\lambda_k,\mu\in\RR$ such that
  \[
    \mu s + \lambda_1 x_1 + \cdots + \lambda_k x_k = 0
  \]
  but not all of $\mu,\lambda_1,\ldots,\lambda_k$ are zero.  Now if $\mu = 0$, then we have
  \[
    \lambda_1 x_1 + \cdots + \lambda_k x_k = 0
  \]
  and so $\lambda_1 = \cdots = \lambda_k = 0$, since $X$ is linearly independent; but then all of them are zero, which we know isn't right.  So it must be that $\mu \neq 0$.  But then
  \[
    s = \frac{1}{\mu}(\lambda_1 x_1 + \cdots + \lambda_k x_k)
  \]
  and so $s\in\lspan(X)$.
\end{proof}

\begin{thm}
  \label{basis.extension}
  Suppose $S$ is a subspace of $\RR^n$, $X\subseteq S$, and $X$ is linearly independent.  Then there is a basis $Y$ for $S$ such that $X\subseteq Y$.
\end{thm}
\begin{proof}
  If $X$ isn't already a basis, then there is some $s\in S$ which is not in the span of $X$.  It follows that $X\cup\{s\}$ is linearly independent.  Now repeat with $X\cup\{s\}$.  This process can only go finitely many steps, since a linearly independent subset of $\RR^n$ can have size at most $n$.  
\end{proof}

\begin{cor}
  Every subspace of $\RR^n$ has a basis.
\end{cor}

\begin{cor}
  Let $S$ be a subspace (of some $\RR^n$) and let $X$ and $Y$ be finite subsets of $S$, such that $X$ is linearly independent and $Y$ spans $S$.  Then $|X| \le \dim(S) \le |Y|$.
\end{cor}

\begin{thm}
  Suppose $S$ and $T$ are subspaces of $\RR^n$, and $S\subseteq T$.  Then $\dim(S)\le \dim(T)$.  Moreover, if $\dim(S) = \dim(T)$, then $S = T$.
\end{thm}
\begin{proof}
  Let $k = \dim(S)$ and $\ell = \dim(T)$.  Choose a basis $X$ for $S$.  Then $X$ is a linearly independent subset of $S$, and hence a linearly independent subset of $T$, since $S\subseteq T$.  By Theorem~\ref{basis.extension}, there is some basis $Y$ for $T$ such that $X\subseteq Y$.  $Y$ has $\ell$ elements, $X$ has $k$ elements, and $X\subseteq Y$; therefore $k\le \ell$.

  Now assume $k = \ell$.  Then since $X\subseteq Y$ and $|X| = k = \ell = |Y|$, it must be that $X = Y$.  Hence
  \[
    S = \lspan(X) = \lspan(Y) = T
  \]
\end{proof}

\section{Basic computation}

So how do we find a basis for a given subspace?  Let's first recall the following definitions.
\begin{defn*}
  Let $A$ be an $m\times n$ matrix.  Say $c_1,\ldots,c_n$ are the columns of $A$, and $r_1,\ldots,r_m$ are the rows of $A$.  Then
  \begin{enumerate}
    \item  $\row(A) = \lspan\{r_1,\ldots,r_m\}$.
    \item  $\col(A) = \lspan\{c_1,\ldots,c_n\}$.
    \item  $\nul(A) = \set{x}{Ax = 0}$.
  \end{enumerate}
\end{defn*}

Now I'll state the \emph{Rank-Nullity Theorem}, which essentially outlines an algorithm for finding bases for each of the above subspaces.  I'll prove it tomorrow.
\begin{thm}(Rank-Nullity)
  Let $A$ be an $m\times n$ matrix, and let $R$ be any row-echelon form of $A$.  Say $R$ has $k$ nonzero rows, $r_1,\ldots,r_k$, and the leading entry of $r_i$ appears in column $\ell_i$.  (Since $R$ is in row-echelon form, this means $\ell_1 < \ell_2 < \cdots < \ell_k$.)  Let $a_1,\ldots,a_n$ be the columns of $A$, in that order.  Then;
  \begin{enumerate}
    \item  $\{r_1,\ldots,r_k\}$ is a basis for $\row(A)$.
    \item  $\{a_{\ell_1},\ldots,a_{\ell_k}\}$ is a basis for $\col(A)$.
    \item  $\{s_1,\ldots,s_{n-k}\}$ is a basis for $\nul(A)$, where $s_i$ is the vector with a $1$ in the entry corresponding to the $i$th free variable, and a $0$ in every entry corresponding to the other free variables.  (Note that since $s_i$ must be in $\nul(A)$, this determines the rest of the entries in $s_i$.)
  \end{enumerate}
\end{thm}

\begin{example*}
  Let
  \[
    A = 
    \begin{pmatrix}
      1 & 4 & 7 & 9 \\
      2 & 6 & 11 & 15 \\
      3 & 10 & 18 & 24 \\
    \end{pmatrix}
  \]
  Find bases for $\row(A)$, $\col(A)$, and $\nul(A)$.
\end{example*}

\begin{proof}[Solution]
  After row-reducing $A$ we get
  \[
    R =
    \begin{pmatrix}
      1 & 4 & 7 & 9 \\
      0 & 2 & 3 & 3 \\
      0 & 0 & 0 & 0 \\
    \end{pmatrix}
  \]
  Hence a basis for $\row(A)$ is
  \[
    \left\{
    \begin{pmatrix}
      1 & 4 & 7 & 9 \\
    \end{pmatrix},
    \begin{pmatrix}
      0 & 2 & 3 & 3 \\
    \end{pmatrix}
    \right\}
  \]
  For $\col(A)$,
  \[
    \left\{
    \begin{pmatrix}
      1 \\ 2 \\ 3 \\
    \end{pmatrix},
    \begin{pmatrix}
      4 \\ 6 \\ 10 \\
    \end{pmatrix}
    \right\}
  \]
  For $\nul(A)$ we need to do some back-substitution.  The homogeneous system corresponding to $R$ is
  \begin{LinearSystems}{5}
    x + 4y + 7z + 9w = 0 \\
    &   2y + 3w + 3w = 0 \\
    &    &    &    0 = 0 \\
  \end{LinearSystems}
  Plugging in $w = 1$ and $z = 0$, we get $y = -3/2$ and $x = -4y - 9 = 6 - 9 = -3$.  Plugging in $w = 0$ and $z = 1$, we get $y = -3/2$ and $x = -1$.  Hence a basis for $\nul(A)$ is
  \[
    \left\{
    \begin{pmatrix}
      -3 \\ -3/2 \\ 0 \\ 1 \\
    \end{pmatrix},
    \begin{pmatrix}
      -1 \\ -3/2 \\ 1 \\ 0 \\
    \end{pmatrix}
    \right\}
  \]
\end{proof}


\end{document}
