\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{wasysym}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Thursday, December 05, 2019 22:44:34}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows}
\newcounter{exer}
\newcounter{exera}
\numberwithin{exer}{subsection}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[subsection]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{teachingnote}[1][Teaching note]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\newenvironment{teachingnote}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\excludecomment{teachingnote}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\lf}[2]{#1^{\underline{#2}}}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\nnn}{\nonumber\\}
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}}
\allowdisplaybreaks
\iffalse
\UNEXPAND{\today}{\today}
\fi
\ihead{Fall 2019 Math 201-003 at Drexel: blackboard notes of 2019-10-07}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{Fall 2019 Math 201-003 at Drexel: blackboard notes of 2019-10-07}
\author{Darij Grinberg}
\date{\today}
\maketitle

\section{Gaussian elimination (continued)}

\subsection{Linear dependence (continued)}

\begin{proposition}
Let $v_{1},v_{2},\ldots,v_{k}$ be $k$ vectors in $\mathbb{R}^{n}$. Then,
$v_{1},v_{2},\ldots,v_{k}$ are dependent \textbf{if and only if} one of them
is a combination of the others.
\end{proposition}

(Remember: \textquotedblleft dependent\textquotedblright\ = \textquotedblleft
linearly dependent\textquotedblright, and \textquotedblleft
combination\textquotedblright\ = \textquotedblleft linear
combination\textquotedblright.)

\begin{proof}
$\Longrightarrow:$ Assume that $v_{1},v_{2},\ldots,v_{k}$ are dependent. We
must show that one of them is a combination of the others.

We have assumed that $v_{1},v_{2},\ldots,v_{k}$ are dependent. Hence, there
exists a nontrivial relation%
\[
\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k}v_{k}=0.
\]
Since this relation is nontrivial, there is some $i$ such that $\lambda
_{i}\neq0$. Now, we can rewrite this relation as follows:%
\[
\lambda_{i}v_{i}=-\lambda_{1}v_{1}-\lambda_{2}v_{2}-\cdots-\lambda
_{i-1}v_{i-1}-\lambda_{i+1}v_{i+1}-\cdots-\lambda_{k}v_{k}.
\]
But since $\lambda_{i}\neq0$, we can multiply this equality by $\dfrac
{1}{\lambda_{i}}$. We get%
\begin{align*}
v_{i}  &  =\dfrac{1}{\lambda_{i}}\left(  -\lambda_{1}v_{1}-\lambda_{2}%
v_{2}-\cdots-\lambda_{i-1}v_{i-1}-\lambda_{i+1}v_{i+1}-\cdots-\lambda_{k}%
v_{k}\right) \\
&  =\dfrac{-\lambda_{1}}{\lambda_{i}}v_{1}+\dfrac{-\lambda_{2}}{\lambda_{i}%
}v_{2}+\cdots+\dfrac{-\lambda_{i-1}}{\lambda_{i}}v_{i-1}+\dfrac{-\lambda
_{i+1}}{\lambda_{i}}v_{i+1}+\cdots+\dfrac{-\lambda_{k}}{\lambda_{i}}v_{k}.
\end{align*}
Thus, $v_{i}$ is a linear combination of all the remaining $v$'s (that is, of
$v_{1},v_{2},\ldots,v_{i-1},v_{i+1},\ldots,v_{k}$).

$\Longleftarrow:$ Assume that one of $v_{1},v_{2},\ldots,v_{k}$ is a
combination of the others. We must show that $v_{1},v_{2},\ldots,v_{k}$ are dependent.

We have assumed that one of $v_{1},v_{2},\ldots,v_{k}$ -- say, $v_{i}$ -- is a
combination of the others. Thus,%
\[
v_{i}=\alpha_{1}v_{1}+\alpha_{2}v_{2}+\cdots+\alpha_{i-1}v_{i-1}+\alpha
_{i+1}v_{i+1}+\cdots+\alpha_{k}v_{k}%
\]
for some numbers $\alpha_{1},\alpha_{2},\ldots,\alpha_{i-1},\alpha
_{i+1},\ldots,\alpha_{k}$. Subtracting $v_{i}$ from both sides, we get%
\begin{align*}
0  &  =\left(  \alpha_{1}v_{1}+\alpha_{2}v_{2}+\cdots+\alpha_{i-1}%
v_{i-1}+\alpha_{i+1}v_{i+1}+\cdots+\alpha_{k}v_{k}\right)  -v_{i}\\
&  =\alpha_{1}v_{1}+\alpha_{2}v_{2}+\cdots+\alpha_{i-1}v_{i-1}+\left(
-1\right)  v_{i}+\alpha_{i+1}v_{i+1}+\cdots+\alpha_{k}v_{k}.
\end{align*}
This is a linear relation between $v_{1},v_{2},\ldots,v_{k}$, and it is
nontrivial since $-1\neq0$. So $v_{1},v_{2},\ldots,v_{k}$ are dependent.
\end{proof}

\textbf{Warning:} \textquotedblleft One of $v_{1},v_{2},\ldots,v_{k}$ is a
combination of others\textquotedblright\ is not the same as saying
\textquotedblleft any of $v_{1},v_{2},\ldots,v_{k}$ is a combination of
others\textquotedblright.

\begin{example}
Let $k=3$ and $v_{1}=\left(
\begin{array}
[c]{c}%
1\\
0
\end{array}
\right)  $ and $v_{2}=\left(
\begin{array}
[c]{c}%
2\\
0
\end{array}
\right)  $ and $v_{3}=\left(
\begin{array}
[c]{c}%
0\\
1
\end{array}
\right)  $.

Then, $v_{1},v_{2},v_{3}$ are dependent. Thus, the proposition shows that one
of them is a combination of the others. And indeed,%
\begin{align*}
v_{1}\text{ is a combination of }v_{2}\text{ and }v_{3}\text{, since }v_{1}
&  =\dfrac{1}{2}v_{2}+0v_{3};\\
v_{2}\text{ is a combination of }v_{1}\text{ and }v_{3}\text{, since }v_{2}
&  =2v_{1}+0v_{3}.
\end{align*}
But $v_{3}$ is not a combination of $v_{1}$ and $v_{2}$.
\end{example}

\begin{corollary}
Let $v$ and $w$ be two vectors in $\mathbb{R}^{n}$.

\textbf{(a)} The one-element list $\left(  v\right)  $ is linearly dependent
if and only if $v=0$.

\textbf{(b)} The two-element list $\left(  v,w\right)  $ is linearly dependent
if and only if one of $v$ and $w$ is a scalar multiple of the other (i.e.,
there is $\lambda\in\mathbb{R}$ such that either $v=\lambda w$ or $w=\lambda
v$).
\end{corollary}

\begin{proof}
\textbf{(a)} Left to the reader.

\textbf{(b)} According to the proposition, the two-element list $\left(
v,w\right)  $ is linearly dependent if and only if one of $v$ and $w$ is a
combination of the other. But a linear combination of a single vector $u$ is
the same as a scalar multiple of $u$.
\end{proof}

Slogan:

\begin{itemize}
\item Linear dependence is a sort of redundancy -- if a list of vectors is
linearly dependent, then all its combinations can be obtained even if one of
the vectors is removed (but we have to remove the right one, not just any one).

\item Linear dependence is a generalization of proportionality between two
lists of numbers.
\end{itemize}

Note that in the plane $\mathbb{R}^{2}$, linearly dependent vectors are said
to be \textbf{parallel}.

\begin{proposition}
If a list of vectors contains the $0$ vector, then it is automatically dependent.
\end{proposition}

\begin{proof}
If $v_{i}=0$, then $0\cdot v_{1}+0\cdot v_{2}+\cdots+0\cdot v_{i-1}+1\cdot
v_{i}+0\cdot v_{i+1}+\cdots+0\cdot v_{k}=0$ is a nontrivial relation.
\end{proof}

\subsubsection{Linear combinations as matrix-by-vector products}

\begin{definition}
Let $v_{1},v_{2},\ldots,v_{m}$ be $m$ column vectors in $\mathbb{R}^{n}$.
Then,%
\[
\left[  v_{1}\mid v_{2}\mid\cdots\mid v_{m}\right]
\]
shall denote the $n\times m$-matrix whose columns are $v_{1},v_{2}%
,\ldots,v_{m}$.
\end{definition}

This notation just lets us paste together some column vectors into a matrix.
For example,%
\[
\left[  \left(
\begin{array}
[c]{c}%
a\\
b
\end{array}
\right)  \mid\left(
\begin{array}
[c]{c}%
c\\
d
\end{array}
\right)  \mid\left(
\begin{array}
[c]{c}%
e\\
f
\end{array}
\right)  \right]  =\left(
\begin{array}
[c]{ccc}%
a & c & e\\
b & d & f
\end{array}
\right)  .
\]


In what follows, we will need a lemma:

\begin{lemma}
\label{lem.vlam}Let $v_{1},v_{2},\ldots,v_{m}$ be $m$ column vectors in
$\mathbb{R}^{n}$. Let $\lambda_{1},\lambda_{2},\ldots,\lambda_{m}$ be $m$ real
numbers. Then,%
\[
\left[  v_{1}\mid v_{2}\mid\cdots\mid v_{m}\right]  \left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{m}%
\end{array}
\right)  =\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}.
\]

\end{lemma}

This lemma shows that the linear combination $\lambda_{1}v_{1}+\lambda
_{2}v_{2}+\cdots+\lambda_{m}v_{m}$ can be written as a \textquotedblleft
matrix $\cdot$ column vector\textquotedblright\ product.

\begin{proof}
[Proof of Lemma \ref{lem.vlam}.]Just multiply things out! Write each vector
$v_{i}$ as $\left(
\begin{array}
[c]{c}%
v_{i,1}\\
v_{i,2}\\
\vdots\\
v_{i,n}%
\end{array}
\right)  $. Thus,%
\[
\left[  v_{1}\mid v_{2}\mid\cdots\mid v_{m}\right]  =\left(
\begin{array}
[c]{cccc}%
v_{1,1} & v_{2,1} & \cdots & v_{m,1}\\
v_{1,2} & v_{2,2} & \cdots & v_{m,2}\\
\vdots & \vdots & \ddots & \vdots\\
v_{1,n} & v_{2,n} & \cdots & v_{m,n}%
\end{array}
\right)  .
\]
Hence,%
\begin{align*}
&  \left[  v_{1}\mid v_{2}\mid\cdots\mid v_{m}\right]  \left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{m}%
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{cccc}%
v_{1,1} & v_{2,1} & \cdots & v_{m,1}\\
v_{1,2} & v_{2,2} & \cdots & v_{m,2}\\
\vdots & \vdots & \ddots & \vdots\\
v_{1,n} & v_{2,n} & \cdots & v_{m,n}%
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{m}%
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{c}%
v_{1,1}\lambda_{1}+v_{2,1}\lambda_{2}+\cdots+v_{m,1}\lambda_{m}\\
v_{1,2}\lambda_{1}+v_{2,2}\lambda_{2}+\cdots+v_{m,2}\lambda_{m}\\
\vdots\\
v_{1,n}\lambda_{1}+v_{2,n}\lambda_{2}+\cdots+v_{m,n}\lambda_{m}%
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{c}%
v_{1,1}\lambda_{1}\\
v_{1,2}\lambda_{1}\\
\vdots\\
v_{1,n}\lambda_{1}%
\end{array}
\right)  +\left(
\begin{array}
[c]{c}%
v_{2,1}\lambda_{2}\\
v_{2,2}\lambda_{2}\\
\vdots\\
v_{2,n}\lambda_{2}%
\end{array}
\right)  +\cdots+\left(
\begin{array}
[c]{c}%
v_{m,1}\lambda_{m}\\
v_{m,2}\lambda_{m}\\
\vdots\\
v_{m,n}\lambda_{m}%
\end{array}
\right) \\
&  =\lambda_{1}\underbrace{\left(
\begin{array}
[c]{c}%
v_{1,1}\\
v_{1,2}\\
\vdots\\
v_{1,n}%
\end{array}
\right)  }_{=v_{1}}+\lambda_{2}\underbrace{\left(
\begin{array}
[c]{c}%
v_{2,1}\\
v_{2,2}\\
\vdots\\
v_{2,n}%
\end{array}
\right)  }_{=v_{2}}+\cdots+\lambda_{m}\underbrace{\left(
\begin{array}
[c]{c}%
v_{m,1}\\
v_{m,2}\\
\vdots\\
v_{m,n}%
\end{array}
\right)  }_{=v_{m}}\\
&  =\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}.
\end{align*}

\end{proof}

\subsubsection{Checking linear dependence via RREF}

\textbf{Question:} How do we check whether $m$ vectors $v_{1},v_{2}%
,\ldots,v_{m}$ are dependent?

We already know a way: We want to know whether there is a nontrivial relation
$\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}=0$. We translate
this relation into a system in the unknowns $\lambda_{1},\lambda_{2}%
,\ldots,\lambda_{m}$. If this system has any nontrivial solution (i.e., if it
has any free variables), then the vectors $v_{1},v_{2},\ldots,v_{m}$ are
dependent. If this system has only the trivial solution, then the vectors
$v_{1},v_{2},\ldots,v_{m}$ are independent.

But there is a better method (\cite[Method 8.8]{Strickland}):

\begin{theorem}
Let $v_{1},v_{2},\ldots,v_{m}$ be $m$ vectors in $\mathbb{R}^{n}$. To see
whether they are dependent, the following algorithm works:

\textbf{(a)} Form the $n\times m$-matrix $A$ whose columns are $v_{1}%
,v_{2},\ldots,v_{m}$. This is usually written as follows:%
\[
A=\left[  v_{1}\mid v_{2}\mid\cdots\mid v_{m}\right]  .
\]


\textbf{(b)} Row-reduce $A$ to get an $n\times m$-matrix $B$ in RREF.

\textbf{(c)} If every column of $B$ has a pivot, then $v_{1},v_{2}%
,\ldots,v_{m}$ are independent.

\textbf{(d)} If some column of $B$ has no pivot, then $v_{1},v_{2}%
,\ldots,v_{m}$ are dependent. Moreover, solutions to the system $B\lambda=0$
(where $\lambda=\left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{m}%
\end{array}
\right)  $) correspond precisely to the relations between $v_{1},v_{2}%
,\ldots,v_{m}$.
\end{theorem}

\begin{proof}
We are trying to see whether the vectors $v_{1},v_{2},\ldots,v_{m}$ are
dependent. In other words, we are trying to see whether there exist numbers
$\lambda_{1},\lambda_{2},\ldots,\lambda_{m}\in\mathbb{R}$ that are not all $0$
but satisfy $\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}=0$. In
other words, we are trying to see whether there exists a column vector
$\lambda=\left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{m}%
\end{array}
\right)  $ satisfying $A\lambda=0$ (because if $\lambda=\left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{m}%
\end{array}
\right)  $ is any vector, then
\[
A\lambda=\left[  v_{1}\mid v_{2}\mid\cdots\mid v_{m}\right]  \left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{m}%
\end{array}
\right)  =\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}%
\]
(by Lemma \ref{lem.vlam}), and therefore the equation $\lambda_{1}%
v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{m}v_{m}=0$ can be rewritten as
$A\lambda=0$). In other words, we are trying to see whether the system
$A\lambda=0$ of linear equations has a nonzero solution $\lambda$. Since this
system always has the zero solution $\lambda=0$ (because $A0=0$), this is the
same as checking whether this system has a \textbf{unique} solution. (Indeed,
if it has a unique solution, then it must be the zero solution, and thus our
vectors $v_{1},v_{2},\ldots,v_{m}$ are independent; but if its solution is not
unique, then it must have a nonzero solution, and thus our vectors
$v_{1},v_{2},\ldots,v_{m}$ are dependent.)

How do we tell whether the system $A\lambda=0$ has a unique solution? We can
solve the system using the (systematic) Gaussian elimination method that we
learned last time. This method starts by constructing the augmented matrix of
the system, which we shall denote by $A^{\prime}$ this time because the letter
$A$ is already taken. Clearly,%
\[
A^{\prime}=\left[  v_{1}\mid v_{2}\mid\cdots\mid v_{m}\mid0\right]  .
\]
That is, the augmented matrix $A^{\prime}$ is $A$ with an extra column full of
zeroes attached to it on the right end.

The next step in Gaussian elimination is to bring the augmented matrix
$A^{\prime}$ into RREF. But note that the last column of $A^{\prime}$ is full
of zeroes. This fact does not change as we perform the row operations of
Gaussian elimination; indeed, adding, scaling or switching zeroes only
produces zeroes.\footnote{Example:%
\[
\left(
\begin{array}
[c]{ccc}%
a & b & 0\\
c & d & 0\\
e & f & 0
\end{array}
\right)  \longrightarrow\left(
\begin{array}
[c]{ccc}%
a & b & 0\\
a+c & b+d & 0\\
e & f & 0
\end{array}
\right)  .
\]
Thus, the last column of $A^{\prime}$, being initially a zero vector, will
remain a zero vector throughout the row-reduction process, and will not impact
the life of the other columns. Hence, row-reducing the augmented matrix
$A^{\prime}$ is the same as row-reducing the matrix $A$, except that the last
column is just \textquotedblleft hanging around\textquotedblright.} Thus, the
row operations that we apply to $A^{\prime}$ only change the first $m$ columns
of $A^{\prime}$ while the last column remains filled with zeroes. This means
that these row operations are tantamount to the row operations that bring the
matrix $A=\left[  v_{1}\mid v_{2}\mid\cdots\mid v_{m}\right]  $ into RREF; the
only difference is that now we have a useless column full of zeroes dangling
around at the right end, which never changes.

Thus, the RREF of $A^{\prime}$ will be the matrix $B$ with a column full of
zeroes attached at the right end (since the RREF of $A$ was $B$). Let me call
this matrix $B^{\prime}$. So $B^{\prime}$ is obtained from $B$ by adding an
extra column full of zeroes at the right end. Here is a (symbolic) picture of
our situation:%
\[
\xymatrix{
A \ar[rrrr]^{\text{bring to RREF}} \ar[dd]_{\text{attach column full of zeroes}} & & & & B \ar[dd]^{\text{attach column full of zeroes}} \\
& \\
A^{\prime} \ar[rrrr]_{\text{bring to RREF}} & & & & B^{\prime}
}
\]


But $B^{\prime}$ is the RREF of $A^{\prime}$; thus the Gaussian elimination
method tells us the following about solutions to $A\lambda=0$:

\begin{itemize}
\item A solution to $A\lambda=0$ exists if and only if the matrix $B^{\prime}$
has no pivot in the last column.

\item If $B^{\prime}$ has no pivot in the last column but a pivot in each of
the other columns, then there is only one solution to $A\lambda=0$ (since
there are no free variables).

\item If $B^{\prime}$ has no pivot in at least one column other than the last
one, then there are multiple solutions to $A\lambda=0$ (since there are free variables).
\end{itemize}

We can restate this in terms of $B$, since $B$ is simply $B^{\prime}$ without
the last column (and since the last column of $B^{\prime}$ is full of zeroes
and thus has no pivot). We thus obtain the following:

\begin{itemize}
\item A solution to $A\lambda=0$ always exists. (Not surprising -- it's just
$\lambda=0$.)

\item If $B$ has a pivot in each of its columns, then there is only one
solution to $A\lambda=0$ (since there are no free variables).

\item If $B$ has no pivot in at least one column, then there are multiple
solutions to $A\lambda=0$ (since there are free variables).
\end{itemize}

Now, recall that \textquotedblleft there is only one solution to $A\lambda
=0$\textquotedblright\ means \textquotedblleft$v_{1},v_{2},\ldots,v_{m}$ are
independent\textquotedblright, whereas \textquotedblleft there are multiple
solutions to $A\lambda=0$\textquotedblright\ means \textquotedblleft%
$v_{1},v_{2},\ldots,v_{m}$ are dependent\textquotedblright. Thus, what we just
proved is precisely the theorem.
\end{proof}

\begin{example}
Consider the three vectors%
\[
v_{1}=\left(
\begin{array}
[c]{c}%
1\\
2\\
3
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{2}=\left(
\begin{array}
[c]{c}%
2\\
2\\
3
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{3}=\left(
\begin{array}
[c]{c}%
3\\
3\\
3
\end{array}
\right)  .
\]
Are they dependent?

The algorithm described in the previous theorem tells us to construct the
matrix
\[
A=\left[  v_{1}\mid v_{2}\mid v_{3}\right]  =\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
2 & 2 & 3\\
3 & 3 & 3
\end{array}
\right)
\]
and to row-reduce it:%
\begin{align*}
\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
2 & 2 & 3\\
3 & 3 & 3
\end{array}
\right)   &  \longrightarrow\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
0 & -2 & -3\\
3 & 3 & 3
\end{array}
\right)  \longrightarrow\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
0 & -2 & -3\\
0 & -3 & -6
\end{array}
\right) \\
&  \longrightarrow\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
0 & 1 & 3/2\\
0 & -3 & -6
\end{array}
\right)  \longrightarrow\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
0 & 1 & 3/2\\
0 & 0 & -3/2
\end{array}
\right) \\
&  \longrightarrow\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
0 & 1 & 3/2\\
0 & 0 & 1
\end{array}
\right)  .
\end{align*}
We are not done row-reducing the matrix yet, but we already see that it will
have a pivot in each column. Thus, the vectors $v_{1},v_{2},v_{3}$ are independent.
\end{example}

\begin{example}
Are the vectors%
\[
v_{1}=\left(
\begin{array}
[c]{c}%
1\\
2
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{2}=\left(
\begin{array}
[c]{c}%
2\\
3
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{3}=\left(
\begin{array}
[c]{c}%
3\\
4
\end{array}
\right)
\]
dependent?

We can proceed by the same method:%
\[
A=\left[  v_{1}\mid v_{2}\mid v_{3}\right]  =\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
2 & 3 & 4
\end{array}
\right)  \longrightarrow\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
0 & -1 & -2
\end{array}
\right)  \longrightarrow\left(
\begin{array}
[c]{ccc}%
1 & 2 & 3\\
0 & 1 & 2
\end{array}
\right)  .
\]
Again, we have not row-reduced the matrix yet, but we already see the pivots,
and in particular we see that there won't be a pivot in the last column. Thus,
the vectors $v_{1},v_{2},v_{3}$ are dependent.

I claim that this was clear even earlier. We didn't have to do any row
operations! Why not? Because $A$ was a $2\times3$-matrix. It has more columns
than rows. Of course, this will still hold after row-reduction. Hence, if each
column had a pivot, then the matrix would have $3$ pivots, which would thus
lie in $3$ different rows (since each pivot has to lie in a different row).
But $A$ does not have $3$ different rows to begin with. So there is at least
one column without pivot. Thus, $v_{1},v_{2},v_{3}$ are dependent.
\end{example}

This generalizes:

\begin{definition}
An $m\times n$-matrix is said to be

\begin{itemize}
\item \textbf{wide} if $n>m$;

\item \textbf{square} if $n=m$;

\item \textbf{tall} if $n<m$.
\end{itemize}
\end{definition}

These words refer to how the matrix looks like:%
\[
\underbrace{\ \
\begin{tabular}
[c]{|llll|}\hline
&  &  & \\
&  &  & \\\hline
\end{tabular}
\ \ }_{\text{wide}}\ \ ,\ \ \ \ \ \ \ \ \ \ \underbrace{\ \
\begin{tabular}
[c]{|ll|}\hline
\phantom{w} & \\
& \\\hline
\end{tabular}
\ \ \ }_{\text{square}}\ \ ,\ \ \ \ \ \ \ \ \ \ \underbrace{\ \
\begin{tabular}
[c]{|ll|}\hline
& \\
& \\
& \\
& \\\hline
\end{tabular}
\ \ }_{\text{tall}}\ \ .
\]


Let us now generalize what we have observed in the last example:

\begin{proposition}
The RREF of a wide matrix cannot have a pivot in each column.
\end{proposition}

\begin{proof}
The RREF of a wide matrix is still a wide matrix. If it had a pivot in each
column, then it would have as many pivots as it has columns, and thus it would
have at least as many rows as it has columns (since each pivot must lie in a
different row). But this is not true for a wide matrix.
\end{proof}

\begin{corollary}
Any $m$ vectors in $\mathbb{R}^{n}$ are dependent if $m>n$.
\end{corollary}

\begin{proof}
Apply the method above to check whether these $m$ vectors are dependent. The
matrix $B$ will be wide, so by the previous proposition it cannot have a pivot
in each column. According to the method, this means that the $m$ vectors are dependent.
\end{proof}

So we can answer certain dependence questions without even computing the RREF.

\begin{example}
Any $16$ vectors in $\mathbb{R}^{15}$ are dependent.
\end{example}

Let us extend the last proposition a little bit (\cite[Lemma 8.7]{Strickland}):

\begin{lemma}
\label{lem.rref.piv-in-each-col}Let $B$ be a $p\times q$-matrix in RREF.

\textbf{(a)} If $B$ is wide, then $B$ cannot have a pivot in each column.

\textbf{(b)} If $B$ is square, then the only way for $B$ to have a pivot in
each column is when $B=I_{p}$.

\textbf{(c)} The only way for $B$ to have a pivot in each column is when
$p\geq q$ and%
\[
B=\left[
\begin{array}
[c]{c}%
I_{q}\\
0_{\left(  p-q\right)  \times q}%
\end{array}
\right]  .
\]
(The right hand side of this equality is to be understood as the $p\times
q$-matrix obtained by piling the $q\times q$ identity matrix $I_{q}$ on top of
the $\left(  p-q\right)  \times q$ zero matrix $0_{\left(  p-q\right)  \times
q}$. For example, if $q=2$ and $p=5$, then it means $\left(
\begin{array}
[c]{cc}%
1 & 0\\
0 & 1\\
0 & 0\\
0 & 0\\
0 & 0
\end{array}
\right)  $. If $p=q$, then it simply means $I_{q}$.)
\end{lemma}

\begin{proof}
Assume that $B$ has a pivot in each column. Thus, $B$ has $q$ pivots in total
(since $B$ has $q$ columns, and there can only be $1$ pivot per column).
Property RREF3 requires each pivot of an RREF matrix to \textquotedblleft
clear out\textquotedblright\ its column (in the sense that all other entries
in its column are $0$'s). Thus, all non-pivot entries of $B$ are $0$'s (since
$B$ has a pivot in each column). Due to property RREF2, we furthermore know
that the pivots move right as we move down the matrix. Thus,

\begin{itemize}
\item the topmost pivot has to be in column $1$ (since otherwise, column $1$
would have no pivot);

\item the second-topmost pivot has to be in column $2$ (since otherwise,
column $2$ would have no pivot);

\item the third-topmost pivot has to be in column $3$ (since otherwise, column
$3$ would have no pivot);

\item $\ldots$.
\end{itemize}

Also, property RREF0 shows that these pivots must be in the first $q$ rows of
$B$, since all rows with no pivot are zero rows. Thus, the first $q$ rows of
$B$ have pivots: row $1$ has a pivot in column $1$; row $2$ has a pivot in
column $2$; row $3$ has a pivot in column $3$; and so on. The remaining rows
are zero rows. This shows that $p\geq q$ (because $B$ must have $q$ rows to
begin with) and $B=\left[
\begin{array}
[c]{c}%
I_{q}\\
0_{\left(  p-q\right)  \times q}%
\end{array}
\right]  $ (since all non-pivot entries of $B$ are $0$'s). This proves part
\textbf{(c)} of the lemma.

Part \textbf{(b)} is just the particular case of part \textbf{(c)} for $p=q$.

Part \textbf{(a)} follows from the $p\geq q$ part of part \textbf{(c)} (since
\textquotedblleft$B$ is wide\textquotedblright\ means the same as
\textquotedblleft$p<q$\textquotedblright).
\end{proof}

\subsection{Spans and spanning}

\begin{proposition}
Let $v_{1},v_{2},\ldots,v_{k}$ be some vectors in $\mathbb{R}^{n}$. Then, any
combination of combinations of $v_{1},v_{2},\ldots,v_{k}$ is a combination of
$v_{1},v_{2},\ldots,v_{k}$.
\end{proposition}

\begin{proof}
For example, any combination of \textbf{two} combinations of $v_{1}%
,v_{2},\ldots,v_{k}$ is a combination of $v_{1},v_{2},\ldots,v_{k}$, because%
\begin{align*}
&  \alpha\left(  \lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k}%
v_{k}\right)  +\beta\left(  \mu_{1}v_{1}+\mu_{2}v_{2}+\cdots+\mu_{k}%
v_{k}\right) \\
&  =\left(  \alpha\lambda_{1}+\beta\mu_{1}\right)  v_{1}+\left(  \alpha
\lambda_{2}+\beta\mu_{2}\right)  v_{2}+\cdots+\left(  \alpha\lambda_{k}%
+\beta\mu_{k}\right)  v_{k}.
\end{align*}
A similar argument works for more than two combinations.
\end{proof}

\begin{definition}
Let $v_{1},v_{2},\ldots,v_{k}$ be some vectors in $\mathbb{R}^{n}$.

\textbf{(a)} The \textbf{span} of $v_{1},v_{2},\ldots,v_{k}$ is the set of all
combinations of $v_{1},v_{2},\ldots,v_{k}$.

This is a subset of $\mathbb{R}^{n}$, and is closed under combination, as the
previous proposition shows: i.e., any combination of elements in this span
must also lie in this span.

The span of $v_{1},v_{2},\ldots,v_{k}$ is called $\operatorname*{span}\left(
v_{1},v_{2},\ldots,v_{k}\right)  $ (or sometimes $\left\langle v_{1}%
,v_{2},\ldots,v_{k}\right\rangle $).

\textbf{(b)} We say that the vectors $v_{1},v_{2},\ldots,v_{k}$ (or, more
precisely, the list $\left(  v_{1},v_{2},\ldots,v_{k}\right)  $) \textbf{span}
$\mathbb{R}^{n}$ if and only if $\operatorname*{span}\left(  v_{1}%
,v_{2},\ldots,v_{k}\right)  =\mathbb{R}^{n}$. In other words, they span
$\mathbb{R}^{n}$ if and only if each vector in $\mathbb{R}^{n}$ is a
combination of $v_{1},v_{2},\ldots,v_{k}$.
\end{definition}

(In part \textbf{(a)}, the word \textquotedblleft span\textquotedblright\ is a
noun; in part \textbf{(b)}, it is a verb.)

\begin{example}
Consider the list $\left(  v_{1},v_{2},v_{3},v_{4},v_{5}\right)  $ where%
\[
v_{1}=\left(
\begin{array}
[c]{c}%
1\\
1\\
1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ v_{2}=\left(
\begin{array}
[c]{c}%
1\\
2\\
1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ v_{3}=\left(
\begin{array}
[c]{c}%
1\\
3\\
1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ v_{4}=\left(
\begin{array}
[c]{c}%
1\\
4\\
1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ v_{5}=\left(
\begin{array}
[c]{c}%
1\\
5\\
1
\end{array}
\right)  .
\]
What is $\operatorname*{span}\left(  v_{1},v_{2},\ldots,v_{5}\right)  $ ?

An arbitrary combination of $v_{1},v_{2},\ldots,v_{5}$ is%
\[
\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{5}v_{5}=\left(
\begin{array}
[c]{c}%
\lambda_{1}+\lambda_{2}+\cdots+\lambda_{5}\\
\lambda_{1}+2\lambda_{2}+3\lambda_{3}+4\lambda_{4}+5\lambda_{5}\\
\lambda_{1}+\lambda_{2}+\cdots+\lambda_{5}%
\end{array}
\right)  .
\]
This is a vector whose first entry equals its third entry. Thus, not every
vector in $\mathbb{R}^{3}$ can be a combination of $v_{1},v_{2},\ldots,v_{5}$.
Hence, $v_{1},v_{2},\ldots,v_{5}$ do not span $\mathbb{R}^{3}$.

What is $\operatorname*{span}\left(  v_{1},v_{2},\ldots,v_{5}\right)  $ ? We
have just shown that%
\[
\operatorname*{span}\left(  v_{1},v_{2},\ldots,v_{5}\right)  \subseteq\left\{
w\in\mathbb{R}^{3}\ \mid\ \ \text{the first entry of }w\text{ equals its third
entry}\right\}  .
\]
Do we have%
\[
\operatorname*{span}\left(  v_{1},v_{2},\ldots,v_{5}\right)  =\left\{
w\in\mathbb{R}^{3}\ \mid\ \ \text{the first entry of }w\text{ equals its third
entry}\right\}
\]
as well? In other words, can \textbf{each} vector in $\mathbb{R}^{3}$ whose
first entry equals its third entry be written as a combination of $v_{1}%
,v_{2},\ldots,v_{5}$ ?

Let's try: Given such a vector $\left(
\begin{array}
[c]{c}%
a\\
b\\
a
\end{array}
\right)  $, we want to write it as $\left(
\begin{array}
[c]{c}%
a\\
b\\
a
\end{array}
\right)  =\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{5}v_{5}$. This
means solving the system%
\[
\left\{
\begin{array}
[c]{l}%
\lambda_{1}+\lambda_{2}+\cdots+\lambda_{5}=a\\
\lambda_{1}+2\lambda_{2}+3\lambda_{3}+4\lambda_{4}+5\lambda_{5}=b\\
\lambda_{1}+\lambda_{2}+\cdots+\lambda_{5}=a
\end{array}
\right.  .
\]
This system always has a solution -- for example $\lambda_{1}=2a-b$ and
$\lambda_{2}=b-a$ and $\lambda_{3}=\lambda_{4}=\lambda_{5}=0$. So we indeed
have%
\[
\operatorname*{span}\left(  v_{1},v_{2},\ldots,v_{5}\right)  =\left\{
w\in\mathbb{R}^{3}\ \mid\ \ \text{the first entry of }w\text{ equals its third
entry}\right\}  .
\]

\end{example}

\textbf{Question:} How do we find out whether a given list of vectors spans
$\mathbb{R}^{n}$ ?

\textbf{Simple but slow answer:} We can try to write each of the standard
basis vectors $e_{1},e_{2},\ldots,e_{n}$ (see HW2 Exercise 4) as a combination
of this list.

(Remember: The standard basis vectors $e_{1},e_{2},\ldots,e_{n}$ are defined
by $e_{i}=\left(
\begin{array}
[c]{c}%
0\\
0\\
\vdots\\
0\\
1\\
0\\
\vdots\\
0
\end{array}
\right)  $ with the $1$ being placed in position $i$.)

If any of $e_{1},e_{2},\ldots,e_{n}$ is not a combination of our list, then
our list does not span $\mathbb{R}^{n}$.

If all of $e_{1},e_{2},\ldots,e_{n}$ are combinations of our list, then we
conclude that each vector in $\mathbb{R}^{n}$ is a combination of our list as
well (because HW2 Exercise 4 shows that each vector in $\mathbb{R}^{n}$ is a
combination of $e_{1},e_{2},\ldots,e_{n}$), and therefore our list does span
$\mathbb{R}^{n}$.

\textbf{However,} this method is slow, since it requires solving $n$ systems
of equations.

Here is a faster method (\cite[Method 9.7]{Strickland}):

\begin{theorem}
Let $\mathcal{V}=\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ be a list of
vectors in $\mathbb{R}^{n}$. We can check whether this list spans
$\mathbb{R}^{n}$ as follows:

\textbf{(a)} Form the $m\times n$-matrix%
\[
C=\left[
\begin{array}
[c]{c}%
v_{1}^{T}\\
v_{2}^{T}\\
\vdots\\
v_{m}^{T}%
\end{array}
\right]  .
\]
This is the matrix whose rows are $v_{1}^{T},v_{2}^{T},\ldots,v_{m}^{T}$ (the
transposes of the vectors in $\mathcal{V}$).

\textbf{(b)} Row-reduce $C$ to get a matrix $D$ in RREF.

\textbf{(c)} If $D$ has a pivot in each column, then $\mathcal{V}$ spans
$\mathbb{R}^{n}$.

\textbf{(d)} If $D$ has no pivot in some column, then $\mathcal{V}$ does not
span $\mathbb{R}^{n}$.
\end{theorem}

The proof of this theorem relies on tracking down what happens to the span of
the rows of a matrix\footnote{We are being slightly indirect here: We have
defined the span for column vectors only, but the rows of a matrix are row
vectors. So, to be precise, we should speak not of the span of the rows, but
of the span of the \textbf{transposes} of the rows. (The transpose of a row
vector is a column vector.) This explains why you see so many
\textquotedblleft$^{T}$\textquotedblright\ signs in the following lemma.} when
we apply row operations to the matrix:

\begin{lemma}
Let $v_{1}^{T},v_{2}^{T},\ldots,v_{m}^{T}$ be the rows of a matrix $C$, and
let $w_{1}^{T},w_{2}^{T},\ldots,w_{m}^{T}$ be the rows of a matrix $C^{\prime
}$ that is obtained from $C$ by row operations. Then,%
\[
\operatorname*{span}\left(  v_{1},v_{2},\ldots,v_{m}\right)
=\operatorname*{span}\left(  w_{1},w_{2},\ldots,w_{m}\right)  .
\]


In other words, row operations do not change the span of the rows.
\end{lemma}

\begin{proof}
Clearly, it suffices to show that any \textbf{single} row operation does not
change the span of the rows.

In other words, we have to show that any column vectors $v_{1},v_{2}%
,\ldots,v_{m}$ satisfy:

\begin{enumerate}
\item $\operatorname*{span}\left(  \lambda v_{1},v_{2},v_{3},\ldots
,v_{m}\right)  =\operatorname*{span}\left(  v_{1},v_{2},v_{3},\ldots
,v_{m}\right)  $ for any $\lambda\neq0$.

\item $\operatorname*{span}\left(  v_{1}+\lambda v_{2},v_{2},v_{3}%
,\ldots,v_{m}\right)  =\operatorname*{span}\left(  v_{1},v_{2},v_{3}%
,\ldots,v_{m}\right)  $ for any $\lambda\in\mathbb{R}$.

\item $\operatorname*{span}\left(  v_{2},v_{1},v_{3},\ldots,v_{m}\right)
=\operatorname*{span}\left(  v_{1},v_{2},v_{3},\ldots,v_{m}\right)  $.
\end{enumerate}

(At least, this corresponds to the row operations \textquotedblleft scaling
the first row by $\lambda$\textquotedblright, \textquotedblleft adding
$\lambda$ times the second row to the first row\textquotedblright\ and
\textquotedblleft swapping the first two rows\textquotedblright. To be honest,
we would have to show this not just for the first two rows, but also for any
pair of rows; but the arguments are the same.)

\textit{Proof of 1:} Any linear combination%
\[
\mu_{1}v_{1}+\mu_{2}v_{2}+\cdots+\mu_{m}v_{m}\ \ \ \ \ \ \ \ \ \ \text{of
}v_{1},v_{2},\ldots,v_{m}%
\]
will still be a linear combination of $\lambda v_{1},v_{2},v_{3},\ldots,v_{m}%
$, since it can be rewritten as%
\[
\left(  \mu_{1}\lambda^{-1}\right)  \left(  \lambda v_{1}\right)  +\mu
_{2}v_{2}+\cdots+\mu_{m}v_{m}.
\]


Conversely, any linear combination%
\[
\mu_{1}\left(  \lambda v_{1}\right)  +\mu_{2}v_{2}+\cdots+\mu_{m}%
v_{m}\ \ \ \ \ \ \ \ \ \ \text{of }\lambda v_{1},v_{2},\ldots,v_{m}%
\]
will be a linear combination of $v_{1},v_{2},\ldots,v_{m}$, since it can be
rewritten as%
\[
\left(  \mu_{1}\lambda\right)  v_{1}+\mu_{2}v_{2}+\cdots+\mu_{m}v_{m}.
\]


Thus, the linear combinations of $v_{1},v_{2},\ldots,v_{m}$ are the same as
the linear combinations of $\lambda v_{1},v_{2},\ldots,v_{m}$. In other words,
$\operatorname*{span}\left(  v_{1},v_{2},\ldots,v_{m}\right)
=\operatorname*{span}\left(  \lambda v_{1},v_{2},\ldots,v_{m}\right)  $.

\textit{Proof of 2:} Any linear combination%
\[
\mu_{1}v_{1}+\mu_{2}v_{2}+\cdots+\mu_{m}v_{m}\ \ \ \ \ \ \ \ \ \ \text{of
}v_{1},v_{2},\ldots,v_{m}%
\]
will still be a linear combination of $v_{1}+\lambda v_{2},v_{2},v_{3}%
,\ldots,v_{m}$, since it can be rewritten as%
\[
\mu_{1}\left(  v_{1}+\lambda v_{2}\right)  +\left(  \mu_{2}-\lambda\mu
_{1}\right)  v_{2}+\mu_{3}v_{3}+\cdots+\mu_{m}v_{m}.
\]
Similarly, the converse direction can be shown. Thus, $\operatorname*{span}%
\left(  v_{1}+\lambda v_{2},v_{2},v_{3},\ldots,v_{m}\right)
=\operatorname*{span}\left(  v_{1},v_{2},v_{3},\ldots,v_{m}\right)  $.

\textit{Proof of 3:} Any linear combination
\[
\mu_{1}v_{1}+\mu_{2}v_{2}+\cdots+\mu_{m}v_{m}\ \ \ \ \ \ \ \ \ \ \text{of
}v_{1},v_{2},\ldots,v_{m}%
\]
will still be a linear combination of $v_{2},v_{1},v_{3},\ldots,v_{m}$, since
it can be rewritten as%
\[
\mu_{2}v_{2}+\mu_{1}v_{1}+\mu_{3}v_{3}+\cdots+\mu_{m}v_{m}.
\]
Similarly, the converse direction can be shown. Thus, $\operatorname*{span}%
\left(  v_{2},v_{1},v_{3},\ldots,v_{m}\right)  =\operatorname*{span}\left(
v_{1},v_{2},v_{3},\ldots,v_{m}\right)  $.
\end{proof}

We just showed that when we apply row operations to a matrix, the span of its
rows does not change. This means that the span of its rows is the span of the
rows of its RREF (since the RREF is obtained by row operations).

Next, we claim the following lemma (\cite[Lemma 9.17]{Strickland}):

\begin{lemma}
Let $D$ be an $m\times n$-matrix in RREF.

\textbf{(a)} If every column of $D$ contains a pivot, then the transposes of
the rows of $D$ span $\mathbb{R}^{n}$.

\textbf{(b)} If some column of $D$ does not contain a pivot, then the
transposes of the rows of $D$ do not span $\mathbb{R}^{n}$.
\end{lemma}

\begin{proof}
\textbf{(a)} Assume that every column of $D$ contains a pivot. Then, Lemma
\ref{lem.rref.piv-in-each-col} \textbf{(c)} shows that $D=\left[
\begin{array}
[c]{c}%
I_{n}\\
0_{\left(  m-n\right)  \times n}%
\end{array}
\right]  $ (and $m\geq n$). Hence, the transposes of the rows of $D$ are
$e_{1},e_{2},\ldots,e_{n},\underbrace{0,0,\ldots,0}_{m-n\text{ zero vectors}}%
$. These $m$ vectors do span $\mathbb{R}^{n}$, since the $e_{1},e_{2}%
,\ldots,e_{n}$ span $\mathbb{R}^{n}$ already (by
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/hw2s.pdf}{homework set \#2}
Exercise 4).

\textbf{(b)} Assume that column $i$ of $D$ does not contain a pivot. I claim
that the transposes of the rows of $D$ do not span $\mathbb{R}^{n}$. More
specifically, I am claiming that the standard basis vector $e_{i}\in
\mathbb{R}^{n}$ is not a combination of the transposes of the rows of $D$.

Indeed, assume that $e_{i}$ is a combination of the transposes of the rows of
$D$. That is,%
\[
e_{i}=\lambda_{1}\left(  \operatorname{row}_{1}D\right)  ^{T}+\lambda
_{2}\left(  \operatorname{row}_{2}D\right)  ^{T}+\cdots+\lambda_{m}\left(
\operatorname{row}_{m}D\right)  ^{T}%
\]
for some $\lambda_{1},\lambda_{2},\ldots,\lambda_{m}\in\mathbb{R}$. Clearly,
not all of $\lambda_{1},\lambda_{2},\ldots,\lambda_{m}$ are $0$, since then
this equality would say $e_{i}=0$ (which is absurd). Thus, some $\lambda_{j}$
is $\neq0$. Pick the \textbf{smallest} $j\in\left\{  1,2,\ldots,m\right\}  $
such that $\lambda_{j}\neq0$. Thus, $\lambda_{1}=\lambda_{2}=\cdots
=\lambda_{j-1}=0$. We furthermore assume that $D$ has no zero rows, since we
could otherwise simply remove them and nothing important would change (since
zero vectors do not contribute to a span: $\operatorname*{span}\left(
v_{1},v_{2},\ldots,v_{k},0,0,\ldots,0\right)  =\operatorname*{span}\left(
v_{1},v_{2},\ldots,v_{k}\right)  $). Hence, each row of $D$ has a pivot
somewhere, and each row's pivot is further right than the previous row's pivot
(by property RREF2). Now,\footnote{We put asterisks (\textquotedblleft$\ast
$\textquotedblright) to signify entries whose values we don't care about.}%
\begin{align*}
e_{i} &  =\lambda_{1}\left(  \operatorname{row}_{1}D\right)  ^{T}+\lambda
_{2}\left(  \operatorname{row}_{2}D\right)  ^{T}+\cdots+\lambda_{m}\left(
\operatorname{row}_{m}D\right)  ^{T}\\
&  =\lambda_{j}\left(  \operatorname{row}_{j}D\right)  ^{T}+\lambda
_{j+1}\left(  \operatorname{row}_{j+1}D\right)  ^{T}+\cdots+\lambda_{m}\left(
\operatorname{row}_{m}D\right)  ^{T}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have thrown the first }j-1\text{ addends away,}\\
\text{since they are all }0\text{ (because }\lambda_{1}=\lambda_{2}%
=\cdots=\lambda_{j-1}=0\text{)}%
\end{array}
\right)  \\
&  =\lambda_{j}\left(
\begin{array}
[c]{c}%
0\\
\vdots\\
0\\
1\\
\ast\\
\ast\\
\ast\\
\vdots\\
\ast
\end{array}
\right)  +\lambda_{j+1}\left(
\begin{array}
[c]{c}%
0\\
0\\
\vdots\\
0\\
1\\
\ast\\
\ast\\
\vdots\\
\ast
\end{array}
\right)  +\cdots+\lambda_{m}\left(
\begin{array}
[c]{c}%
0\\
0\\
0\\
0\\
\vdots\\
0\\
1\\
\ast\\
\vdots
\end{array}
\right)  \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{because }D\text{ is a RREF matrix with no zero rows,}\\
\text{so each row of }D\text{ has a pivot equal to }1\text{,}\\
\text{and each row's pivot is further right than the previous row's pivot}%
\end{array}
\right)  \\
&  =\left(
\begin{array}
[c]{c}%
0\\
\vdots\\
0\\
\lambda_{j}\\
\ast\\
\ast\\
\vdots\\
\ast
\end{array}
\right)  .
\end{align*}
Thus, the first nonzero entry of the vector $e_{i}$ is in the same position as
the first nonzero entry in $\left(  \operatorname{row}_{j}D\right)  ^{T}$
(because the $\lambda_{j}\left(  \operatorname{row}_{j}D\right)  ^{T}$ addend
is a vector whose first nonzero entry is in this position, whereas all the
other addends have their first nonzero entries further down). But this is of
course the position in which the $j$-th row of $D$ has its pivot. Thus, it
cannot be in position $i$ (since $D$ has no pivot in the $i$-th column). But
this contradicts the fact that the first nonzero entry in $e_{i}$ is in
position $i$.
\end{proof}

From the last two lemmas, our theorem follows: The second-to-last lemma shows
that row operations don't change the span of the transposes of the rows; the
last lemma explains how we can tell from the RREF whether this span is
$\mathbb{R}^{n}$ or not.

\begin{corollary}
A list of $m$ vectors can never span $\mathbb{R}^{n}$ if $m<n$.
\end{corollary}

\begin{proof}
Consider some $m$ vectors $v_{1},v_{2},\ldots,v_{m}$ in $\mathbb{R}^{n}$,
where $m<n$. Apply the method above to check whether these $m$ vectors span
$\mathbb{R}^{n}$. The matrix $D$ will be wide, so it cannot have a pivot in
each column. According to the method, this means that the $m$ vectors cannot
span $\mathbb{R}^{n}$.
\end{proof}

\begin{thebibliography}{9999999999}                                                                                       %


\bibitem[Strickland]{Strickland}Neil Strickland, \textit{MAS201 Linear
Mathematics for Applications}, lecture notes, 28 September 2013.\newline\url{http://neil-strickland.staff.shef.ac.uk/courses/MAS201/}
\end{thebibliography}


\end{document}