\documentclass[12pt]{amsart}

\usepackage{241}

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


\begin{document}

\maketitle

\begin{defn*}
  A subset $S$ of $\RR^n$ is called a \emph{subspace} (of $\RR^n$) if:
  \begin{enumerate}
    \item  $0\in S$.
    \item  For all $x\in S$, and $\lambda\in \RR$, $\lambda x$ is also in $S$.
    \item  For all $x,y\in S$, $x + y$ is also in $S$.
  \end{enumerate}
\end{defn*}

Note that the second condition implies the first, \emph{so long as $S$ is nonempty}.  Thus the first condition is just there to ensure that a subspace is nonempty.

\begin{fact}
  If $S$ is a subspace of $\RR^n$ and $x_1,\ldots,x_k\in S$ and $\lambda_1,\ldots,\lambda_k\in\RR$, then
  \[
    \lambda_1 x_1 + \cdots + \lambda_k x_k \in S
  \]
\end{fact}

\begin{example*}
  Let $A$ be an $m\times n$ matrix.  Then
  \[
    \set{x\in\RR^n}{Ax = 0}
  \]
  is a subspace of $\RR^n$.  This is called the \emph{null space of $A$} and is denoted by $\nul(A)$.  On the other hand,
  \[
    \set{Ax}{x\in\RR^n}
  \]
  is a subspace of $\RR^m$, and is called the \emph{range space of $A$}, written $\ran(A)$.
\end{example*}

\begin{defn*}
  Let $S$ be a subspace of $\RR^n$.  A subset $X\subseteq S$ of $S$ is said to \emph{span $S$} if for every $s\in S$, there are some $x_1,\ldots,x_k\in X$ and $\lambda_1,\ldots,\lambda_k\in \RR$ such that
  \[
    s = \lambda_1 x_1 + \cdots + \lambda_k x_k
  \]
  If $X\subseteq\RR^n$, then the \emph{span of $X$} is the set
  \[
    \lspan(X) = \set{\lambda_1 x_1 + \cdots + \lambda_k x_k}{k\in\NN\land x_1,\ldots,x_k\in X\land \lambda_1,\ldots,\lambda_k\in\RR}
  \]
\end{defn*}

This last definition provides us with a wealth of examples of subspaces of $\RR^n$.
\begin{fact}
  If $X$ is any subset of $\RR^n$ then $\lspan(X)$ is a subspace of $\RR^n$.
\end{fact}

It's easy to see that if $X\subseteq Y\subseteq\RR^n$, then $\lspan(X)\subseteq\lspan(Y)$.  However, the converse doesn't hold.  In fact, we have the following example where $X\not\subseteq Y$ and $Y\not\subseteq X$, but $\lspan(X) = \lspan(Y)$.

\begin{example*}
  Consider the following two finite subsets of $\RR^3$.
  \[
    X = 
    \left\{
    \begin{pmatrix}
      1 \\ 3 \\ -2 \\
    \end{pmatrix},
    \begin{pmatrix}
      1 \\ 1 \\ -1 \\
    \end{pmatrix},
    \begin{pmatrix}
      0 \\ 2 \\ -1 \\
    \end{pmatrix}
    \right\}
    \qquad
    Y = 
    \left\{
    \begin{pmatrix}
      1 \\ 3 \\ -2 \\
    \end{pmatrix},
    \begin{pmatrix}
      1 \\ 1 \\ -1 \\
    \end{pmatrix},
    \begin{pmatrix}
      2 \\ 4 \\ -3 \\
    \end{pmatrix}
    \right\}
  \]
  Then we have $\lspan(X) = \lspan(Y)$.
\end{example*}

The proof of the above is made much easier using the following, which we call the ``linear combination lemma.''
\begin{lemma}
  Let $x_1,\ldots,x_k\in\RR^n$ be vectors in $\RR^n$.  If each of $y_1,\ldots,y_\ell$ is a linear combination of $x_1,\ldots,x_k$ then so is any linear combination of $y_1,\ldots,y_\ell$.
\end{lemma}
\begin{proof}
  The hardest part of this proof is figuring out what the statement of the lemma is, in formal terms.  We have our vectors $x_1,\ldots,x_k\in\RR^n$; suppose $y_1,\ldots,y_\ell$ are vectors in $\RR^n$, each of which is a linear combination of $x_1,\ldots,x_k$;
  \[
    y_i = \lambda_{i1} x_1 + \cdots + \lambda_{ik} x_k\qquad 1\le i \le \ell
  \]
	Now suppose $z = \mu_1 y_1 + \cdots + \mu_\ell y_\ell$ is a linear combination of $y_1,\ldots,y_\ell$.  Then,
  \begin{align*}
    z & = \sum_{i=1}^\ell \mu_i y_i \\
      & = \sum_{i=1}^\ell \mu_i \sum_{j=1}^k \lambda_{ij} x_j \\
      & = \sum_{j=1}^k \sum_{i=1}^\ell \mu_i \lambda_{ij} x_j \\
      & = \sum_{j=1}^k \left(\sum_{i=1}^\ell \mu_i \lambda_{ij}\right) x_j \\
  \end{align*}
  So $z$ is also a linear combination of $x_1,\ldots,x_k$, namely the one whose coefficient for $x_j$ is
  \[
    \sum_{i=1}^\ell \mu_i \lambda_{ij}
  \]
\end{proof}

\begin{lemma}
  Suppose $S$ is a subspace of $\RR^n$, and $X\subseteq S$.  Then $\lspan(X)\subseteq S$.
\end{lemma}
\begin{proof}
  Suppose $y\in\lspan(X)$; then there are $x_1,\ldots,x_k\in X$ and $\lambda_1,\ldots,\lambda_k\in\RR$ such that $y = \lambda_1 x_1 + \cdots + \lambda_k x_k$.  But $x_1,\ldots,x_k\in S$, and so
  \[
    y = \lambda_1 x_1 + \cdots + \lambda_k x_k \in S
  \]
\end{proof}

\begin{defn*}
  If $A$ is an $m\times n$ matrix with columns $c_1,\ldots,c_n\in\RR^m$, and rows $r_1,\ldots,r_m\in\RR^n$, then we write
  \[
    \col(A) = \lspan\{c_1,\ldots,c_n\}\qquad \row(A) = \lspan\{r_1,\ldots,r_m\}
  \]
  We call $\col(A)$ and $\row(A)$ the \emph{column space} and \emph{row space} of $A$, respectively.
\end{defn*}

\begin{fact}
  If $A$ is any matrix, then $\ran(A) = \col(A)$.
\end{fact}
\begin{proof}
  Suppose $A$ is $m\times n$ and $c_1\ldots,c_n\in\RR^m$ are the column vectors of $A$.  We've seen before that if $x\in\RR^n$, then
  \[
    Ax = x_1 c_1 + \cdots + x_n c_n
  \]
  The right-hand side of the above equation is a member of $\col(A)$, since it's a linear combination of the columns of $A$.  Since $x\in\RR^n$ was arbitrary, this shows $\ran(A)\subseteq\col(A)$.  Now if $y\in\col(A)$, then $y$ is a linear combination of the columns of $A$, and hence for some $\lambda_1,\ldots,\lambda_n\in\RR$,
  \[
    y = \lambda_1 c_1 + \cdots + \lambda_n c_n
  \]
  But then by the same fact,
  \[
    y = \lambda_1 c_1 + \cdots + \lambda_n c_n = A\begin{pmatrix} \lambda_1 \\ \vdots \\ \lambda_n \\ \end{pmatrix}
  \]
  and the right-hand side of this equation is in $\ran(A)$.  This shows $\col(A)\subseteq\ran(A)$.
\end{proof}

You might guess now, since $\row(A)$ and $\nul(A)$ are both subspaces of $\RR^n$, that they are equal; but you'd be wrong! They \emph{are} related, but we won't see how for a while yet.  For now, let's see how we can phrase a problem related to spanning sets in terms of Gaussian elimination.

\begin{example*}
  Let
  \[
    X = \left\{
    \begin{pmatrix}
      0 \\ 1 \\ -2 \\ 3 \\
    \end{pmatrix},
    \begin{pmatrix}
      2 \\ 4 \\ 6 \\ 0 \\
    \end{pmatrix},
    \begin{pmatrix}
      3 \\ -5 \\ 7 \\ -1 \\
    \end{pmatrix}
    \right\}
  \]
  Is the vector $b = \smat{2 \\ 3 \\ 5 \\ 7 \\}$ in the span of $X$?

  To solve this, let
  \[
    A = \begin{pmatrix}
      0 & 2 & 3 \\
      1 & 4 & -5 \\
      -2 & 6 & 7 \\
      3 & 0 & -1 \\
    \end{pmatrix}
  \]
  Then $b$ is in the span of $X$ if and only if there is some $x\in\RR^3$ such that $Ax = b$.
\end{example*}

\begin{example*}
Let $X$ be the following set.
\[
   \left\{
    \begin{pmatrix}
      0 \\ 2 \\ 1 \\
    \end{pmatrix},
    \begin{pmatrix}
      1 \\ 1 \\ -1 \\
    \end{pmatrix},
    \begin{pmatrix}
      0 \\ 2 \\ -1 \\
    \end{pmatrix}
    \right\} 
\]
Prove that $\lspan(X) = \RR^3$.

To prove this it suffices to prove that the following matrix is right-invertible;
\[
  A = \begin{pmatrix}
    0 & 1 & 0 \\
    2 & 1 & 2 \\
    1 & -1 & -1 \\
  \end{pmatrix}
\]
for which it suffices to prove that $A$ is fully invertible;
\begin{alignat*}{2}
  & 
  \begin{pmatrix}
    0 & 1 & 0 \\
    2 & 1 & 2 \\
    1 & -1 & -1 \\
  \end{pmatrix} & 
  \begin{pmatrix}
    1 & 0 & 0 \\
    0 & 1 & 0 \\
    0 & 0 & 1 \\
  \end{pmatrix} \\
  \begin{matrix}
    \rho_2 \to \rho_2 - \rho_1 \\
    \rho_3 \to \rho_3 + \rho_1 \\
  \end{matrix} &
  \begin{pmatrix}
    0 & 1 & 0 \\
    2 & 0 & 2 \\
    1 & 0 & -1 \\
  \end{pmatrix} & 
  \begin{pmatrix}
    1 & 0 & 0 \\
    -1 & 1 & 0 \\
    1 & 0 & 1 \\
  \end{pmatrix} \\
  \rho_2 \to \rho_2 - 2\rho_3 &
  \begin{pmatrix}
    0 & 1 & 0 \\
    0 & 0 & 4 \\
    1 & 0 & -1 \\
  \end{pmatrix} & 
  \begin{pmatrix}
    1 & 0 & 0 \\
    -3 & 1 & -2 \\
    1 & 0 & 1 \\
  \end{pmatrix} \\
  \begin{matrix}
    \rho_1\swap \rho_2 \\
    \rho_1\swap \rho_3 \\
  \end{matrix} &
  \begin{pmatrix}
    1 & 0 & -1 \\
    0 & 1 & 0 \\
    0 & 0 & 4 \\
  \end{pmatrix} & 
  \begin{pmatrix}
    1 & 0 & 1 \\
    1 & 0 & 0 \\
    -3 & 1 & -2 \\
  \end{pmatrix} \\
  \begin{matrix}
    \rho_3\to \rho_3/4 \\
    \rho_1\to \rho_1 + \rho_3 \\
  \end{matrix} &
  \begin{pmatrix}
    1 & 0 & 0 \\
    0 & 1 & 0 \\
    0 & 0 & 1 \\
  \end{pmatrix} & 
  \begin{pmatrix}
    1/4 & 1/4 & 1/2 \\
    1 & 0 & 0 \\
    -3/4 & 1/4 & -1/2 \\
  \end{pmatrix} \\
\end{alignat*}
(I computed $A^{-1}$ above, but this is not necessary to prove that $A$ is invertible; it just suffices to show, since $A$ is square, that $A$ reduces to $I$.)
  

\end{example*}



\end{document}
