\documentclass[12pt]{amsart}

\usepackage{241}

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


\begin{document}

\maketitle

If I were to tell you
\[
  \mbox{``Let }S = \lspan\left\{
    \begin{pmatrix}
      1 \\ 2 \\ 3 \\
    \end{pmatrix},
    \begin{pmatrix}
      3 \\ 0 \\ 1 \\
    \end{pmatrix},
    \begin{pmatrix}
      4 \\ 2 \\ 4 \\
    \end{pmatrix}
  \right\}\mbox{...''}
\]
you might stop me and tell me I've been inefficient; for I didn't have to go through the tedious process of typing $\smat{4 \\ 2 \\ 4}$, since
\[
  \lspan\left\{
    \begin{pmatrix}
      1 \\ 2 \\ 3 \\
    \end{pmatrix},
    \begin{pmatrix}
      3 \\ 0 \\ 1 \\
    \end{pmatrix},
    \begin{pmatrix}
      4 \\ 2 \\ 4 \\
    \end{pmatrix}
  \right\} = 
  \lspan\left\{
    \begin{pmatrix}
      1 \\ 2 \\ 3 \\
    \end{pmatrix},
    \begin{pmatrix}
      3 \\ 0 \\ 1 \\
    \end{pmatrix}
  \right\}
\]
Now that I'm tired from all that typing, and embarrassed to boot for missing the above, I'd like to find a consistent way of avoiding this situation.  Indeed, since the third vector above is the sum of the first two, it's not too hard to see that I don't need it when taking the span; but what's to say I can't drop one of the first two as well?  The following definition will help in solving this problem.

\begin{defn*}
  A set $X\subseteq\RR^n$ of vectors is called \emph{linearly independent} if for all \emph{distinct} $x_1,\ldots,x_k\in X$ and $\lambda_1,\ldots,\lambda_k\in\RR$, if
  \[
    \lambda_1 x_1 + \cdots + \lambda_k x_k = 0
  \]
  then $\lambda_1 = \cdots = \lambda_k = 0$.
\end{defn*}

\begin{example*}
  Let's check that
  \[
    X = \left\{
      \begin{pmatrix}
        1 \\ 2 \\ 3 \\
      \end{pmatrix},
      \begin{pmatrix}
        3 \\ 0 \\ 1 \\
      \end{pmatrix}
    \right\}
  \]
  is linearly independent.  Call the two vectors above $x$ and $y$.  Then if $\lambda,\mu\in\RR$ satisfy
  \[
    \lambda x + \mu y = 0
  \]
  we must have
  \begin{LinearSystems}{4}
    \lambda + 3\mu = 0 \\
   2\lambda     &  = 0 \\
   3\lambda +  \mu = 0 \\
  \end{LinearSystems}
  This easily shows $\lambda = \mu = 0$.
\end{example*}
In general we have
\begin{lemma}
  Let $a_1,\ldots,a_n\in\RR^m$ be \emph{distinct} vectors.  Then the set $\{a_1,\ldots,a_n\}$ is linearly independent if and only if the only solution to $Ax = 0$ is the zero vector, where $A$ is the $m\times n$ matrix with columns $a_1,\ldots,a_n$.
\end{lemma}

\begin{proof}
  Both directions follow from the fact that
  \[
    A\begin{pmatrix} \lambda_1 \\ \vdots \\ \lambda_n \\ \end{pmatrix} = \lambda_1 a_1 + \cdots + \lambda_n a_n
  \]
\end{proof}

\begin{thm}
  \label{independence}
  Let $X\subseteq\RR^n$.  Then the following are equivalent;
  \begin{enumerate}
    \item  $X$ is linearly independent.
    \item  For all $x\in X$, $\lspan(X\sm\{x\}) \neq \lspan(X)$.
  \end{enumerate}
\end{thm}
[If $A$ and $B$ are sets, then $A\sm B = \set{a}{a\in A\land a\not\in B}$.  So $X\sm \{x\}$ is just $X$ with $x$ removed.]  The second condition says exactly what I wanted above; that I can't get away with writing down less vectors when describing the span.  The first condition, linear independence, will be easier to check (and have uses in other situations, as well).  Before we prove this theorem we need to prove a lemma about spans.

\begin{lemma}
  Let $X\subseteq\RR^n$ and let $x\in X$ be given.  Then $\lspan(X\sm\{x\}) = \lspan(X)$ if and only if $x\in\lspan(X\sm\{x\})$.
\end{lemma}
\begin{proof}
  Suppose $\lspan(X\sm\{x\}) = \lspan(X)$.  Since $x\in X$, and $X\subseteq\lspan(X)$, it follows that $x\in\lspan(X\sm\{x\})$.

  Now suppose $x\in\lspan(X\sm\{x\})$.  Then there are $y_1,\ldots,y_k\in X\sm\{x\}$ and $\lambda_1,\ldots,\lambda_k\in\RR$ such that
  \[
    x = \lambda_1 y_1 + \cdots + \lambda_k y_k
  \]
  We'd like to show $\lspan(X)\subseteq\lspan(X\sm\{x\})$ (the other inclusion is obvious).  So let $v\in\lspan(X)$ be given.  Then there are $z_1\ldots,z_\ell\in X$ and $\mu_1,\ldots,\mu_\ell\in\RR$ such that $v = \mu_1 z_1 + \cdots + \mu_\ell z_\ell$.  By relabeling things, we may assume that $z_1,\ldots,z_\ell\neq x$ and
  \[
    v = \alpha x + \mu_1 z_1 + \cdots + \mu_\ell z_\ell
  \]
  Then
  \[
    v = \alpha\lambda_1 y_1 + \cdots + \alpha \lambda_k y_k + \mu_1 z_1 + \cdots + \mu_\ell z_\ell
  \]
  and hence $v\in\lspan(X\sm\{x\})$ since none of the $y$'s or the $z$'s is equal to $x$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{independence}]
  Suppose $X$ is linearly independent.  Let $x\in X$ be given and assume for sake of contradiction that $\lspan(X\sm\{x\}) = \lspan(X)$.  By the Lemma above, $x\in\lspan(X\sm\{x\})$.  Hence there are $y_1\ldots,y_k\in X\sm\{x\}$ and $\lambda_1,\ldots,\lambda_k\in \RR$ such that
  \[
    x = \lambda_1 y_1 + \cdots + \lambda_k y_k
  \]
  But then
  \[
    \lambda_1 y_1 + \cdots + \lambda_k y_k + (-1)x = 0
  \]
  and this contradicts linear independence since $-1 \neq 0$.

  Now suppose that for all $x\in X$, $\lspan(X\sm\{x\}) \neq \lspan(X)$.  Let $x_1,\ldots,x_k$ be distinct members of $X$ and $\lambda_1,\ldots,\lambda_k\in\RR$ coefficients such that
  \[
    \lambda_1 x_1 + \cdots + \lambda_k x_k = 0
  \]
  Suppose for sake of contradiction that for some $i$, $\lambda_i\neq 0$.  Then we have
  \[
    x_i = \frac{1}{\lambda_i}(\lambda_1 x_1 + \cdots + \lambda_{i-1} x_{i-1} + \lambda_{i+1} x_{i+1} + \cdots + \lambda_k x_k)
  \]
  showing $x_i\in \lspan(X\sm\{x_i\})$ (since the $x_j$'s are distinct).  Again by the above lemma, $\lspan(X) = \lspan(X\sm\{x_i\})$, and we have a contradiction.
\end{proof}

We can go in another direction to prove another theorem.
\begin{thm}
  Let $X\subseteq\RR^n$ be a linearly independent set and let $x\in\RR^n$ be given.  Then $X\cup\{x\}$ is linearly independent if and only if $x\not\in\lspan(X)$.
\end{thm}
%\begin{proof}
%  Suppose $X\cup\{x\}$ is linearly independent.  Then for all $y\in X\cup\{x\}$, $\lspan((X\cup\{x\})\sm\{y\}) \neq \lspan(X\cup\{x\})$.  In particular, with $y = x$, we have $\lspan(X) \neq \lspan(X\cup\{x\})$.  Then $x\not\in\lspan(X)$.
%
%  Now suppose $x\not\in\lspan(X)$.  Then $\lspan(X)\neq \lspan(X\cup\{x\})$ since the set on the right has $x$ while the set on the left doesn't.  Since $X$ was also assumed to be linearly independent, we also have
%  \[
%    \forall y\in X\quad \lspan(X\sm\{y\}) \neq \lspan(X)
%  \]
%\end{proof}

\end{document}
