\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{needspace}
\usepackage{tabls}
\usepackage{tikz}
\usepackage{ytableau}
\usepackage{skak}
\usepackage{rotating}
\usepackage[framemethod=tikz]{mdframed}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, December 09, 2019 17:28:44}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\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{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[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}}
\allowdisplaybreaks
\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}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\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{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\ihead{Math 201-003 Fall 2019 (Darij Grinberg): final exam training}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 201-003 Fall 2019 (Darij Grinberg): final exam training}
\end{center}

This is only about the material of the last few weeks. Don't forget the rest
of the course; go over the
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/mt1t.pdf}{midterm training
problems 1} and
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/mt2t.pdf}{midterm training
problems 2}, as well as the actual midterms.

\section{Subspaces}

\begin{exercise}
\label{exe.subspaces-or-not.R2.3}Which of the following sets are subspaces of
$\mathbb{R}^{2}$ ?%
\begin{align*}
A  &  =\left\{  \left(  x_{1},x_{2}\right)  ^{T}\in\mathbb{R}^{2}\ \mid
\ x_{1}+x_{2}=1\right\}  ;\\
B  &  =\left\{  \left(  x_{1},x_{2}\right)  ^{T}\in\mathbb{R}^{2}\ \mid
\ x_{1}+x_{2}=0\right\}  ;\\
C  &  =\left\{  \left(  x_{1},x_{2}\right)  ^{T}\in\mathbb{R}^{2}\ \mid
\ x_{1}-x_{2}=1\right\}  ;\\
D  &  =\left\{  \left(  x_{1},x_{2}\right)  ^{T}\in\mathbb{R}^{2}\ \mid
\ x_{1}-x_{2}=0\right\}  ;\\
E  &  =\left\{  \left(  x_{1},x_{2}\right)  ^{T}\in\mathbb{R}^{2}\ \mid
\ x_{1}x_{2}=1\right\}  ;\\
F  &  =\left\{  \left(  x_{1},x_{2}\right)  ^{T}\in\mathbb{R}^{2}\ \mid
\ x_{1}x_{2}=0\right\}  ;\\
G  &  =\left\{  \left(  x_{1},x_{2}\right)  ^{T}\in\mathbb{R}^{2}\ \mid
\ x_{1}^{2}+x_{2}^{2}=1\right\}  ;\\
H  &  =\left\{  \left(  x_{1},x_{2}\right)  ^{T}\in\mathbb{R}^{2}\ \mid
\ x_{1}^{2}+x_{2}^{2}=0\right\}  ;\\
I  &  =\left\{  \left(  a,a+b\right)  ^{T}\ \mid\ a,b\in\mathbb{R}\right\}
;\\
J  &  =\left\{  \left(  a-b,b-a\right)  ^{T}\ \mid\ a,b\in\mathbb{R}\right\}
.
\end{align*}

\end{exercise}

\section{Independence, spanning and bases}

\begin{exercise}
\label{exe.span.lincomb.mt1p}Define four vectors $a,b,c,d$ in $\mathbb{R}^{3}$
as follows:%
\[
a=\left(
\begin{array}
[c]{c}%
4\\
3\\
2
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ b=\left(
\begin{array}
[c]{c}%
1\\
2\\
3
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ c=\left(
\begin{array}
[c]{c}%
2\\
1\\
0
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ d=\left(
\begin{array}
[c]{c}%
-1\\
0\\
1
\end{array}
\right)  .
\]
Show that $\operatorname{span}\left(  a,b\right)  =\operatorname{span}\left(
c,d\right)  $ as follows:

\textbf{(a)} Write each of $a$ and $b$ as a linear combination of $c$ and $d$.

\textbf{(b)} Write $\lambda a+\mu b$ (for any fixed reals $\lambda$ and $\mu$)
as a linear combination of $c$ and $d$. Conclude that $\lambda a+\mu
b\in\operatorname{span}\left(  c,d\right)  $ for each $\lambda,\mu
\in\mathbb{R}$, and therefore $\operatorname{span}\left(  a,b\right)
\subseteq\operatorname{span}\left(  c,d\right)  $.

\textbf{(c)} Write each of $c$ and $d$ as a linear combination of $a$ and $b$.

\textbf{(d)} Write $\lambda c+\mu d$ (for any fixed reals $\lambda$ and $\mu$)
as a linear combination of $a$ and $b$. Conclude that $\lambda c+\mu
d\in\operatorname{span}\left(  a,b\right)  $ for each $\lambda,\mu
\in\mathbb{R}$, and therefore $\operatorname{span}\left(  c,d\right)
\subseteq\operatorname{span}\left(  a,b\right)  $.

The results of \textbf{(b)} and \textbf{(d)} combined yield
$\operatorname{span}\left(  a,b\right)  =\operatorname{span}\left(
c,d\right)  $.
\end{exercise}

\begin{noncompile}
16f/mt1ps/Exe6 with last coord kicked
\end{noncompile}

\begin{exercise}
\label{exe.subspace.find-spanners}\textbf{(a)} Find a list of $3$ vectors that
spans the subspace%
\[
K=\left\{  \left(  a,b,c,d\right)  ^{T}\in\mathbb{R}^{4}\ \mid
\ a+b=c+d\right\}
\]
of $\mathbb{R}^{4}$.

\textbf{(b)} Find a list of $4$ vectors that spans the subspace%
\[
L=\left\{  \left(  a_{1}+a_{2},a_{2}+a_{3},a_{3}+a_{4},a_{4}+a_{1}\right)
^{T}\ \mid\ a_{1},a_{2},a_{3},a_{4}\in\mathbb{R}\right\}
\]
of $\mathbb{R}^{4}$.

\textbf{(c)} Find a list of $3$ vectors that spans $L$.
\end{exercise}

\begin{noncompile}
16f/mt1ps/Exe7
\end{noncompile}

\begin{exercise}
\label{exe.mt2p.shrink-and-extend}Consider the vector space $\mathbb{R}^{3}$.

\textbf{(a)} The list $\mathbf{a}=\left(  \left(
\begin{array}
[c]{c}%
1\\
2\\
-1
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
1\\
1\\
0
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
0\\
1\\
-1
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
1\\
1\\
1
\end{array}
\right)  \right)  $ spans $\mathbb{R}^{3}$. Shrink this list to a basis of
$\mathbb{R}^{3}$ by removing some redundant elements.

\textbf{(b)} The list $\mathbf{b}=\left(  \left(
\begin{array}
[c]{c}%
-1\\
0\\
1
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
2\\
3\\
4
\end{array}
\right)  \right)  $ is linearly independent. Extend this list to a basis of
$\mathbb{R}^{3}$ by appending to it some elements from the list $\mathbf{a}$.
\end{exercise}

\begin{noncompile}
16f/mt2ps/Exe1
\end{noncompile}

\section{Rank and rank normal form}

\begin{exercise}
\label{exe.rank.find-16712}Let $A=\left(
\begin{array}
[c]{cccc}%
1 & 6 & 7 & 12\\
2 & 5 & 8 & 11\\
3 & 4 & 9 & 10
\end{array}
\right)  $.

Find the rank of $A$ and a sequence of row and column operations that
transform $A$ into its rank normal form.
\end{exercise}

(See \S 1.3 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-12-04.pdf}{the class
notes from 2019-12-04} for the meaning of column operations and of rank. But
you don't need to proceed in the exact same way as in the example given there;
you may find it easier to start applying some convenient column operations
before bringing the matrix into RREF.)

\newpage

\section{Solution outlines}

\begin{noncompile}
The following solutions are a bit rough at some places, but they have enough
detail to get full scores.
\end{noncompile}

\begin{noncompile}
Some of these solutions use tricks instead of systematic methods. You are free
to use the methods -- but the tricks are often faster and reveal some ideas
that you would have missed if you just followed the methods.
\end{noncompile}

\begin{proof}
[Solution to Exercise \ref{exe.subspaces-or-not.R2.3}.]\textbf{(a)} The set
$A$ is not a subspace of $\mathbb{R}^{2}$. Indeed, it fails to contain
$\overrightarrow{0}=\left(  0,0\right)  ^{T}$.

\bigskip

\textbf{(b)} The set $B$ is a subspace of $\mathbb{R}^{2}$.

\begin{fineprint}
[\textit{Proof.} We need to check that $B$ contains the zero vector, is closed
under addition, and is closed under scaling.

\begin{itemize}
\item Let us show that $B$ contains the zero vector: We have
$\overrightarrow{0}=\left(  0,0\right)  ^{T}\in B$, since $0+0=0$.

\item Let us show that $B$ is closed under addition: Let $v\in B$ and $w\in
B$. We must prove that $v+w\in B$.

We have $v\in B=\left\{  \left(  x_{1},x_{2}\right)  ^{T}\in\mathbb{R}%
^{2}\ \mid\ x_{1}+x_{2}=0\right\}  $; thus, we can write $v$ as $v=\left(
v_{1},v_{2}\right)  ^{T}\in\mathbb{R}^{2}$ for some reals $v_{1},v_{2}$ that
satisfy $v_{1}+v_{2}=0$. Consider these $v_{1},v_{2}$.

We have $w\in B=\left\{  \left(  x_{1},x_{2}\right)  ^{T}\in\mathbb{R}%
^{2}\ \mid\ x_{1}+x_{2}=0\right\}  $; thus, we can write $w$ as $w=\left(
w_{1},w_{2}\right)  ^{T}\in\mathbb{R}^{2}$ for some reals $w_{1},w_{2}$ that
satisfy $w_{1}+w_{2}=0$. Consider these $w_{1},w_{2}$.

Now,%
\[
\underbrace{v}_{=\left(  v_{1},v_{2}\right)  ^{T}}+\underbrace{w}_{=\left(
w_{1},w_{2}\right)  ^{T}}=\left(  v_{1},v_{2}\right)  ^{T}+\left(  w_{1}%
,w_{2}\right)  ^{T}=\left(  v_{1}+w_{1},v_{2}+w_{2}\right)  ^{T}.
\]
Thus, in order to prove that $v+w\in B$, we need to show that $\left(
v_{1}+w_{1}\right)  +\left(  v_{2}+w_{2}\right)  =0$ (by the definition of
$B$). But this is easy to show:%
\[
\left(  v_{1}+w_{1}\right)  +\left(  v_{2}+w_{2}\right)  =\underbrace{\left(
v_{1}+v_{2}\right)  }_{=0}+\underbrace{\left(  w_{1}+w_{2}\right)  }_{=0}=0.
\]
Thus, we have proved that $v+w\in B$. This completes the proof that $B$ is
closed under addition.

\item Let us show that $B$ is closed under scaling: Let $\lambda\in\mathbb{R}$
and $v\in B$. We must prove that $\lambda v\in B$.

We have $v\in B=\left\{  \left(  x_{1},x_{2}\right)  ^{T}\in\mathbb{R}%
^{2}\ \mid\ x_{1}+x_{2}=0\right\}  $; thus, we can write $v$ as $v=\left(
v_{1},v_{2}\right)  ^{T}\in\mathbb{R}^{2}$ for some reals $v_{1},v_{2}$ that
satisfy $v_{1}+v_{2}=0$. Consider these $v_{1},v_{2}$.

Now,%
\[
\lambda\underbrace{v}_{=\left(  v_{1},v_{2}\right)  ^{T}}=\lambda\left(
v_{1},v_{2}\right)  ^{T}=\left(  \lambda v_{1},\lambda v_{2}\right)  ^{T}.
\]
Thus, in order to prove that $\lambda v\in B$, we need to show that $\lambda
v_{1}+\lambda v_{2}=0$ (by the definition of $B$). But this is easy to show:%
\[
\lambda v_{1}+\lambda v_{2}=\lambda\underbrace{\left(  v_{1}+v_{2}\right)
}_{=0}=0.
\]
Thus, we have proved that $\lambda v\in B$. This completes the proof that $B$
is closed under scaling.
\end{itemize}

\noindent Combining these three facts, we conclude that $B$ is a subspace of
$\mathbb{R}^{2}$.]
\end{fineprint}

\bigskip

\textbf{(c)} The set $C$ is not a subspace of $\mathbb{R}^{2}$. Indeed, it
fails to contain $\overrightarrow{0}=\left(  0,0\right)  ^{T}$.

\bigskip

\textbf{(d)} The set $D$ is a subspace of $\mathbb{R}^{2}$.

[\textit{Proof.} The proof of this is analogous to the proof of the fact that
$B$ is a subspace of $\mathbb{R}^{2}$. (The only difference is that some
\textquotedblleft$+$\textquotedblright\ signs have to be replaced by
\textquotedblleft$-$\textquotedblright\ signs now.)]

\bigskip

\textbf{(e)} The set $E$ is not a subspace of $\mathbb{R}^{2}$. Indeed, it
fails to contain $\overrightarrow{0}=\left(  0,0\right)  ^{T}$.

\bigskip

\textbf{(f)} The set $F$ is not a subspace of $\mathbb{R}^{2}$. Indeed, it is
not closed under addition, since the two elements $\left(  0,1\right)  ^{T}\in
F$ and $\left(  1,0\right)  ^{T}\in F$ have sum $\left(  0,1\right)
^{T}+\left(  1,0\right)  ^{T}=\left(  1,1\right)  ^{T}\notin F$.

\bigskip

\textbf{(g)} The set $G$ is not a subspace of $\mathbb{R}^{2}$. Indeed, it is
not closed under addition, since the two elements $\left(  0,1\right)  ^{T}\in
G$ and $\left(  1,0\right)  ^{T}\in G$ have sum $\left(  0,1\right)
^{T}+\left(  1,0\right)  ^{T}=\left(  1,1\right)  ^{T}\notin G$.

\bigskip

\textbf{(h)} The set $H$ is a subspace of $\mathbb{R}^{2}$. Indeed, it is the
one-element set $\left\{  \overrightarrow{0}\right\}  =\left\{  \left(
0,0\right)  ^{T}\right\}  $, since the only two reals $x_{1}$ and $x_{2}$
satisfying $x_{1}^{2}+x_{2}^{2}=0$ are $0$ and $0$.

\bigskip

\textbf{(i)} The set $I$ is a subspace of $\mathbb{R}^{2}$. Indeed, it is the
full $\mathbb{R}^{2}$, since each $\left(  x_{1},x_{2}\right)  ^{T}%
\in\mathbb{R}^{2}$ can be written as $\left(  a,a+b\right)  ^{T}$ for some
$a,b\in\mathbb{R}$ (namely, for $a=x_{1}$ and $b=x_{2}-x_{1}$).

\bigskip

\textbf{(j)} The set $J$ is a subspace of $\mathbb{R}^{2}$. Indeed, it is the
same set as $B$.

[\textit{Proof.} Each element of $J$ has the form $\left(  a-b,b-a\right)
^{T}$ for some $a,b\in\mathbb{R}$ (by the definition of $J$), and thus is a
vector in $\mathbb{R}^{2}$ whose two entries sum to $0$ (because its two
entries $a-b$ and $b-a$ sum to $\left(  a-b\right)  +\left(  b-a\right)  =0$).

The definition of $B$ can be restated as follows: The set $B$ consists of all
vectors in $\mathbb{R}^{2}$ whose two entries sum to $0$. Thus, $J\subseteq B$
(since each element of $J$ is a vector in $\mathbb{R}^{2}$ whose two entries
sum to $0$). Conversely, it is easy to see that $B\subseteq J$. (Indeed, any
element of $B$ has the form $\left(  x_{1},x_{2}\right)  ^{T}\in\mathbb{R}%
^{2}$ for some reals $x_{1},x_{2}$ satisfying $x_{1}+x_{2}=0$ (by the
definition of $B$); thus, it has the form $\left(  x_{1},-x_{1}\right)  $
(since $x_{1}+x_{2}=0$ entails $x_{2}=-x_{1}$), and this shows that it has the
form $\left(  a-b,b-a\right)  ^{T}$ for some $a,b\in\mathbb{R}$ (namely, for
$a=x_{1}$ and $b=0$). But the latter says precisely that it belongs to $J$. So
we have shown that every element of $B$ belongs to $J$. In other words,
$B\subseteq J$.)

Combining $J\subseteq B$ with $B\subseteq J$, we obtain $J=B$. Thus, $J$ is a
subspace of $\mathbb{R}^{2}$ (since we already know that $B$ is a subspace of
$\mathbb{R}^{2}$.]
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.span.lincomb.mt1p}.]\textbf{(a)} Let us first
write $a$ as a linear combination of $c$ and $d$. In other words, we are
seeking two real numbers $\gamma$ and $\delta$ such that $a=\gamma c+\delta
d$. In other words, we are solving the equation $a=\gamma c+\delta d$ in two
real unknowns $\gamma$ and $\delta$. Since $a=\left(
\begin{array}
[c]{c}%
4\\
3\\
2
\end{array}
\right)  $, $c=\left(
\begin{array}
[c]{c}%
2\\
1\\
0
\end{array}
\right)  $ and $d=\left(
\begin{array}
[c]{c}%
-1\\
0\\
1
\end{array}
\right)  $, this equation rewrites as $\left(
\begin{array}
[c]{c}%
4\\
3\\
2
\end{array}
\right)  =\gamma\left(
\begin{array}
[c]{c}%
2\\
1\\
0
\end{array}
\right)  +\delta\left(
\begin{array}
[c]{c}%
-1\\
0\\
1
\end{array}
\right)  $. This is equivalent to the system $\left\{
\begin{array}
[c]{l}%
2\gamma+\left(  -1\right)  \delta=4\\
1\gamma+0\delta=3\\
0\gamma+1\delta=2
\end{array}
\right.  $ of linear equations. Solving this system in any way, we find
$\gamma=3$ and $\delta=2$. Thus, $a=\gamma c+\delta d$ becomes $a=3c+2d$.

So we have written $a$ as a linear combination of $c$ and $d$. Similarly, we
can do the same for $b$, obtaining $b=2c+3d$.

\bigskip

\textbf{(b)} For any two reals $\lambda$ and $\mu$, we have
\begin{align*}
\lambda\underbrace{a}_{=3c+2d}+\mu\underbrace{b}_{=2c+3d}  &  =\lambda\left(
3c+2d\right)  +\mu\left(  2c+3d\right) \\
&  =3\lambda c+2\lambda d+2\mu c+3\mu d\\
&  =\left(  3\lambda+2\mu\right)  c+\left(  2\lambda+3\mu\right)  d.
\end{align*}
This is a representation of $\lambda a+\mu b$ as a linear combination of $c$
and $d$. Thus, $\lambda a+\mu b\in\operatorname{span}\left(  c,d\right)  $ for
each $\lambda,\mu\in\mathbb{R}$. In other words,%
\[
\left\{  \lambda a+\mu b\ \mid\ \lambda,\mu\in\mathbb{R}\right\}
\subseteq\operatorname{span}\left(  c,d\right)  .
\]
But the definition of $\operatorname{span}\left(  a,b\right)  $ yields
$\operatorname{span}\left(  a,b\right)  =\left\{  \lambda a+\mu b\ \mid
\ \lambda,\mu\in\mathbb{R}\right\}  $. Hence,%
\[
\operatorname{span}\left(  a,b\right)  =\left\{  \lambda a+\mu b\ \mid
\ \lambda,\mu\in\mathbb{R}\right\}  \subseteq\operatorname{span}\left(
c,d\right)  .
\]
This solves part \textbf{(b)}.

\bigskip

\textbf{(c)} Similarly to part \textbf{(a)}, we find $c=\dfrac{3}{5}%
a+\dfrac{-2}{5}b$ and $d=\dfrac{-2}{5}a+\dfrac{3}{5}b$.

\bigskip

\textbf{(d)} Similarly to part \textbf{(b)}, we can represent $\lambda c+\mu
d$ as a linear combination of $a$ and $b$ as follows:%
\[
\lambda c+\mu d=\left(  \dfrac{3}{5}\lambda+\dfrac{-2}{5}\mu\right)  a+\left(
\dfrac{-2}{5}\lambda+\dfrac{3}{5}\mu\right)  b.
\]

\end{proof}

In order to solve Exercise \ref{exe.subspace.find-spanners}, we shall use the
following simple fact:

\begin{proposition}
\label{prop.span.redundant-inside}Let $\mathbb{K}$ be a field. Let $V$ be a
$\mathbb{K}$-vector space. Let $v_{1},v_{2},\ldots,v_{k}$ be some vectors in
$V$. Let $W=\operatorname{span}\left(  v_{1},v_{2},\ldots,v_{k}\right)  $
(this is a subspace of $V$). Let $w\in W$. Then, $\operatorname{span}\left(
v_{1},v_{2},\ldots,v_{k},w\right)  =W$.
\end{proposition}

(Roughly speaking, Proposition \ref{prop.span.redundant-inside} says that the
span of a list of vectors does not change if we append a new vector to the
list, as long as this new vector already lies in the span of the old vectors.)

\begin{proof}
[Proof of Proposition \ref{prop.span.redundant-inside}.]We have $w\in
W=\operatorname{span}\left(  v_{1},v_{2},\ldots,v_{k}\right)  $. In other
words, $w$ is a linear combination of $v_{1},v_{2},\ldots,v_{k}$ (since
$\operatorname*{span}\left(  v_{1},v_{2},\ldots,v_{k}\right)  $ is the set of
all such combinations). In other words, there exist scalars $\alpha_{1}%
,\alpha_{2},\ldots,\alpha_{k}\in\mathbb{K}$ such that $w=\alpha_{1}%
v_{1}+\alpha_{2}v_{2}+\cdots+\alpha_{k}v_{k}$. Consider these $\alpha
_{1},\alpha_{2},\ldots,\alpha_{k}$.

Now, we shall prove that $\operatorname{span}\left(  v_{1},v_{2},\ldots
,v_{k},w\right)  \subseteq W$ and $W\subseteq\operatorname{span}\left(
v_{1},v_{2},\ldots,v_{k},w\right)  $ separately:

\begin{itemize}
\item \textit{Proof of }$\operatorname{span}\left(  v_{1},v_{2},\ldots
,v_{k},w\right)  \subseteq W$\textit{:}

Let $p\in\operatorname{span}\left(  v_{1},v_{2},\ldots,v_{k},w\right)  $.
Thus, $p$ is a linear combination of $v_{1},v_{2},\ldots,v_{k},w$. In other
words, there exist scalars $\beta_{1},\beta_{2},\ldots,\beta_{k},\gamma
\in\mathbb{K}$ such that $p=\beta_{1}v_{1}+\beta_{2}v_{2}+\cdots+\beta
_{k}v_{k}+\gamma w$. Consider these $\beta_{1},\beta_{2},\ldots,\beta
_{k},\gamma$. We have%
\begin{align*}
p  &  =\beta_{1}v_{1}+\beta_{2}v_{2}+\cdots+\beta_{k}v_{k}+\gamma
\underbrace{w}_{=\alpha_{1}v_{1}+\alpha_{2}v_{2}+\cdots+\alpha_{k}v_{k}}\\
&  =\beta_{1}v_{1}+\beta_{2}v_{2}+\cdots+\beta_{k}v_{k}+\gamma\left(
\alpha_{1}v_{1}+\alpha_{2}v_{2}+\cdots+\alpha_{k}v_{k}\right) \\
&  =\beta_{1}v_{1}+\beta_{2}v_{2}+\cdots+\beta_{k}v_{k}+\gamma\alpha_{1}%
v_{1}+\gamma\alpha_{2}v_{2}+\cdots+\gamma\alpha_{k}v_{k}\\
&  =\left(  \beta_{1}v_{1}+\gamma\alpha_{1}v_{1}\right)  +\left(  \beta
_{2}v_{2}+\gamma\alpha_{2}v_{2}\right)  +\cdots+\left(  \beta_{k}v_{k}%
+\gamma\alpha_{k}v_{k}\right) \\
&  =\left(  \beta_{1}+\gamma\alpha_{1}\right)  v_{1}+\left(  \beta_{2}%
+\gamma\alpha_{2}\right)  v_{2}+\cdots+\left(  \beta_{k}+\gamma\alpha
_{k}\right)  v_{k}.
\end{align*}
Hence, $p$ is a linear combination of $v_{1},v_{2},\ldots,v_{k}$. In other
words, \newline$p\in\operatorname{span}\left(  v_{1},v_{2},\ldots
,v_{k}\right)  $. In other words, $p\in W$ (since $W=\operatorname{span}%
\left(  v_{1},v_{2},\ldots,v_{k}\right)  $).

We thus have showed that every $p\in\operatorname{span}\left(  v_{1}%
,v_{2},\ldots,v_{k},w\right)  $ satisfies $p\in W$. In other words,
$\operatorname{span}\left(  v_{1},v_{2},\ldots,v_{k},w\right)  \subseteq W$.

\item \textit{Proof of }$W\subseteq\operatorname{span}\left(  v_{1}%
,v_{2},\ldots,v_{k},w\right)  $\textit{:}

Let $p\in W$. Thus, $p\in W=\operatorname*{span}\left(  v_{1},v_{2}%
,\ldots,v_{k}\right)  $. In other words, $p$ is a linear combination of
$v_{1},v_{2},\ldots,v_{k}$. In other words, there exist scalars $\delta
_{1},\delta_{2},\ldots,\delta_{k}\in\mathbb{K}$ such that $p=\delta_{1}%
v_{1}+\delta_{2}v_{2}+\cdots+\delta_{k}v_{k}$. Consider these $\delta
_{1},\delta_{2},\ldots,\delta_{k}$. We have%
\begin{align*}
p  &  =\delta_{1}v_{1}+\delta_{2}v_{2}+\cdots+\delta_{k}v_{k}\\
&  =\delta_{1}v_{1}+\delta_{2}v_{2}+\cdots+\delta_{k}v_{k}%
+\underbrace{\overrightarrow{0}}_{=0w}\\
&  =\delta_{1}v_{1}+\delta_{2}v_{2}+\cdots+\delta_{k}v_{k}+0w.
\end{align*}
Hence, $p$ is a linear combination of $v_{1},v_{2},\ldots,v_{k},w$. In other
words, $p\in\operatorname{span}\left(  v_{1},v_{2},\ldots,v_{k},w\right)  $.

We thus have showed that every $p\in W$ satisfies $p\in\operatorname{span}%
\left(  v_{1},v_{2},\ldots,v_{k},w\right)  $. In other words, $W\subseteq
\operatorname{span}\left(  v_{1},v_{2},\ldots,v_{k},w\right)  $.
\end{itemize}

We have now proved the two relations $\operatorname{span}\left(  v_{1}%
,v_{2},\ldots,v_{k},w\right)  \subseteq W$ and $W\subseteq\operatorname{span}%
\left(  v_{1},v_{2},\ldots,v_{k},w\right)  $. Combining them, we obtain
$\operatorname{span}\left(  v_{1},v_{2},\ldots,v_{k},w\right)  =W$. This
proves Proposition \ref{prop.span.redundant-inside}.

(You have seen some very similar arguments in class.)
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.subspace.find-spanners}.][\textbf{Note:}
Throughout the solution of this problem, you have a lot of freedom to make
choices. Thus, your answers may be completely different from mine and still correct.]

\textbf{(a)} The set $K$ is the set of all solutions of the system of (one)
linear equation $\left\{  a+b=c+d\right.  $ in the four unknowns $a,b,c,d$.
Solving this system, we find that its solutions have the form%
\[
\left(
\begin{array}
[c]{c}%
a\\
b\\
c\\
d
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
s+t-u\\
u\\
t\\
s
\end{array}
\right)
\]
with three free variables $s,t,u$. Thus,%
\begin{align*}
K  &  =\left\{  \left(
\begin{array}
[c]{c}%
s+t-u\\
u\\
t\\
s
\end{array}
\right)  \ \mid\ s,t,u\in\mathbb{R}\right\} \\
&  =\left\{  s\left(
\begin{array}
[c]{c}%
1\\
0\\
0\\
1
\end{array}
\right)  +t\left(
\begin{array}
[c]{c}%
1\\
0\\
1\\
0
\end{array}
\right)  +u\left(
\begin{array}
[c]{c}%
-1\\
1\\
0\\
0
\end{array}
\right)  \ \mid\ s,t,u\in\mathbb{R}\right\} \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left(
\begin{array}
[c]{c}%
s+t-u\\
u\\
t\\
s
\end{array}
\right)  =s\left(
\begin{array}
[c]{c}%
1\\
0\\
0\\
1
\end{array}
\right)  +t\left(
\begin{array}
[c]{c}%
1\\
0\\
1\\
0
\end{array}
\right)  +u\left(
\begin{array}
[c]{c}%
-1\\
1\\
0\\
0
\end{array}
\right)  \right) \\
&  =\operatorname{span}\left(  \left(
\begin{array}
[c]{c}%
1\\
0\\
0\\
1
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
1\\
0\\
1\\
0
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
-1\\
1\\
0\\
0
\end{array}
\right)  \right)  .
\end{align*}
Thus, we have written $K$ as a span of three vectors.

\textbf{(b)} For every $a_{1},a_{2},a_{3},a_{4}\in\mathbb{R}$, we have%
\begin{align*}
&  \left(  a_{1}+a_{2},a_{2}+a_{3},a_{3}+a_{4},a_{4}+a_{1}\right)  ^{T}\\
&  =\left(
\begin{array}
[c]{c}%
a_{1}+a_{2}\\
a_{2}+a_{3}\\
a_{3}+a_{4}\\
a_{4}+a_{1}%
\end{array}
\right)  =a_{1}\left(
\begin{array}
[c]{c}%
1\\
0\\
0\\
1
\end{array}
\right)  +a_{2}\left(
\begin{array}
[c]{c}%
1\\
1\\
0\\
0
\end{array}
\right)  +a_{3}\left(
\begin{array}
[c]{c}%
0\\
1\\
1\\
0
\end{array}
\right)  +a_{4}\left(
\begin{array}
[c]{c}%
0\\
0\\
1\\
1
\end{array}
\right)  .
\end{align*}
Thus, the definition of $L$ rewrites as follows:%
\begin{align}
L  &  =\left\{  a_{1}\left(
\begin{array}
[c]{c}%
1\\
0\\
0\\
1
\end{array}
\right)  +a_{2}\left(
\begin{array}
[c]{c}%
1\\
1\\
0\\
0
\end{array}
\right)  +a_{3}\left(
\begin{array}
[c]{c}%
0\\
1\\
1\\
0
\end{array}
\right)  +a_{4}\left(
\begin{array}
[c]{c}%
0\\
0\\
1\\
1
\end{array}
\right)  \ \mid\ a_{1},a_{2},a_{3},a_{4}\in\mathbb{R}\right\} \nonumber\\
&  =\operatorname{span}\left(  \left(
\begin{array}
[c]{c}%
1\\
0\\
0\\
1
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
1\\
1\\
0\\
0
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
0\\
1\\
1\\
0
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
0\\
0\\
1\\
1
\end{array}
\right)  \right)  . \label{exe.subspace.find-spanners.sol.2}%
\end{align}
Hence, we have written $L$ as a span of four vectors.

\textbf{(c)} Set $\alpha=\left(
\begin{array}
[c]{c}%
1\\
0\\
0\\
1
\end{array}
\right)  $, $\beta=\left(
\begin{array}
[c]{c}%
1\\
1\\
0\\
0
\end{array}
\right)  $, $\gamma=\left(
\begin{array}
[c]{c}%
0\\
1\\
1\\
0
\end{array}
\right)  $, and $\delta=\left(
\begin{array}
[c]{c}%
0\\
0\\
1\\
1
\end{array}
\right)  $. Then, (\ref{exe.subspace.find-spanners.sol.2}) rewrites as%
\begin{equation}
L=\operatorname{span}\left(  \alpha,\beta,\gamma,\delta\right)  .
\label{exe.subspace.find-spanners.sol.4}%
\end{equation}


However, it is easy to observe that $\alpha+\gamma=\beta+\delta$. Hence,
$\delta=\alpha+\gamma-\beta$. In particular, $\delta$ is a linear combination
of $\alpha,\beta,\gamma$. Hence, $\delta\in\operatorname{span}\left(
\alpha,\beta,\gamma\right)  $.

Now, set $V=\mathbb{R}^{4}$; let $v_{1},v_{2},\ldots,v_{k}$ be the vectors
$\alpha,\beta,\gamma$ (so $k=3$); let $W=\operatorname{span}\left(
\alpha,\beta,\gamma\right)  $; and let $w=\delta$. Then, the condition of
Proposition \ref{prop.span.redundant-inside} is satisfied (because we have
$\delta\in\operatorname{span}\left(  \alpha,\beta,\gamma\right)  $). Thus,
Proposition \ref{prop.span.redundant-inside} (applied to $\mathbb{K}%
=\mathbb{R}$) yields $\operatorname{span}\left(  \alpha,\beta,\gamma
,\delta\right)  =\operatorname{span}\left(  \alpha,\beta,\gamma\right)  $.
Hence, (\ref{exe.subspace.find-spanners.sol.4}) becomes $L=\operatorname{span}%
\left(  \alpha,\beta,\gamma,\delta\right)  =\operatorname{span}\left(
\alpha,\beta,\gamma\right)  $. Thus, we have represented $L$ as a span of
three vectors.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.mt2p.shrink-and-extend}.](I am going to be very
detailed here. You don't need to write half as much when solving this kind of problem!)

\textbf{(a)} We proceed using the standard algorithm\footnote{In this
algorithm, we treat $\mathbf{a}$ as a mutable variable.}: We scan the list
$\mathbf{a}$ from left to right. Each time we read an entry of $\mathbf{a}$,
we check if this entry is a linear combination of the entries before it. If it
is, then we remove this entry from $\mathbf{a}$ and start from scratch with
the new (shorter) $\mathbf{a}$. If it is not, then we proceed to the next
entry. If we have arrived at the end of the list, then our list has no
redundant entries, and thus is a basis of $\mathbb{R}^{3}$.

Let us execute this algorithm step by step:

\begin{itemize}
\item We scan the list $\mathbf{a}$ from left to right. Thus, we begin at its
first entry, which is $\left(  1,2,-1\right)  ^{T}$.

\item Is this first entry $\left(  1,2,-1\right)  ^{T}$ a linear combination
of the entries before it? There are no entries before it, and thus the only
linear combination of the entries before it is $\overrightarrow{0}$ (because
the only linear combination of no vectors is $\overrightarrow{0}$). But our
entry $\left(  1,2,-1\right)  ^{T}$ is not $\overrightarrow{0}$; thus,
$\left(  1,2,-1\right)  ^{T}$ is not a linear combination of the entries
before it. Hence, we proceed to the second entry.

\item Is this second entry $\left(  1,1,0\right)  ^{T}$ a linear combination
of the entries before it? There is only one entry before it, namely $\left(
1,2,-1\right)  ^{T}$. Hence, we are asking whether $\left(  1,1,0\right)
^{T}$ is a linear combination of the vector $\left(  1,2,-1\right)  ^{T}$. In
other words, we are asking whether $\left(  1,1,0\right)  ^{T}=\lambda
_{1}\left(  1,2,-1\right)  ^{T}$ for some $\lambda_{1}\in\mathbb{R}$.
Equivalently, we want to know whether $\left\{
\begin{array}
[c]{c}%
1=1\lambda_{1}\\
1=2\lambda_{1}\\
0=-1\lambda_{1}%
\end{array}
\right.  $ for some $\lambda_{1}\in\mathbb{R}$ (because the equation $\left(
1,1,0\right)  ^{T}=\lambda_{1}\left(  1,2,-1\right)  ^{T}$ is equivalent to
the system of equations $\left\{
\begin{array}
[c]{c}%
1=1\lambda_{1}\\
1=2\lambda_{1}\\
0=-1\lambda_{1}%
\end{array}
\right.  $). In other words, we want to know whether the system $\left\{
\begin{array}
[c]{c}%
1=1\lambda_{1}\\
1=2\lambda_{1}\\
0=-1\lambda_{1}%
\end{array}
\right.  $ of linear equations (in the unknown $\lambda_{1}$) has a solution.
But this question is easy to answer (e.g., by Gaussian elimination), and the
answer is \textquotedblleft no\textquotedblright. Thus, our entry $\left(
1,1,0\right)  ^{T}$ is not a linear combination of the entries before it.
Hence, we proceed to the third entry.

\item Is this third entry $\left(  0,1,-1\right)  ^{T}$ a linear combination
of the entries before it? The entries before it are $\left(  1,2,-1\right)
^{T}$ and $\left(  1,1,0\right)  ^{T}$. Hence, we are asking whether $\left(
0,1,-1\right)  ^{T}$ is a linear combination of the vectors $\left(
1,2,-1\right)  ^{T}$ and $\left(  1,1,0\right)  ^{T}$. In other words, we are
asking whether $\left(  0,1,-1\right)  ^{T}=\lambda_{1}\left(  1,2,-1\right)
^{T}+\lambda_{2}\left(  1,1,0\right)  ^{T}$ for some $\lambda_{1}\in
\mathbb{R}$. Equivalently, we want to know whether $\left\{
\begin{array}
[c]{c}%
0=1\lambda_{1}+1\lambda_{2}\\
1=2\lambda_{1}+1\lambda_{2}\\
-1=-1\lambda_{1}+0\lambda_{2}%
\end{array}
\right.  $ for some $\lambda_{1},\lambda_{2}\in\mathbb{R}$ (because the
equation $\left(  0,1,-1\right)  ^{T}=\lambda_{1}\left(  1,2,-1\right)
^{T}+\lambda_{2}\left(  1,1,0\right)  ^{T}$ is equivalent to the system of
equations $\left\{
\begin{array}
[c]{c}%
0=1\lambda_{1}+1\lambda_{2}\\
1=2\lambda_{1}+1\lambda_{2}\\
-1=-1\lambda_{1}+0\lambda_{2}%
\end{array}
\right.  $). In other words, we want to know whether the system $\left\{
\begin{array}
[c]{c}%
0=1\lambda_{1}+1\lambda_{2}\\
1=2\lambda_{1}+1\lambda_{2}\\
-1=-1\lambda_{1}+0\lambda_{2}%
\end{array}
\right.  $ of linear equations (in the unknowns $\lambda_{1},\lambda_{2}$) has
a solution. But this question is easy to answer (e.g., by Gaussian
elimination), and the answer is \textquotedblleft yes\textquotedblright. Thus,
our entry $\left(  0,1,-1\right)  ^{T}$ is a linear combination of the entries
before it\footnote{Namely, $\left(  0,1,-1\right)  ^{T}=1\left(
1,2,-1\right)  ^{T}+\left(  -1\right)  \left(  1,1,0\right)  ^{T}$. But we
don't need to know these specifics.}. Thus, we remove the entry from
$\mathbf{a}$, and start from scratch with the new (shorter) $\mathbf{a}$.

\item We scan the new list $\mathbf{a}=\left(  \left(  1,2,-1\right)
^{T},\left(  1,1,0\right)  ^{T},\left(  1,1,1\right)  ^{T}\right)  $ (the
result of removing $\left(  0,1,-1\right)  ^{T}$ from the old list
$\mathbf{a}$) from left to right. Thus, we begin at its first entry, which is
$\left(  1,2,-1\right)  ^{T}$.

\item Is this first entry $\left(  1,2,-1\right)  ^{T}$ a linear combination
of the entries before it? We have already answered this question during our
previous scan of the list (since the segment of our list $\mathbf{a}$ up to
its first entry has not changed when we removed $\left(  0,1,-1\right)  ^{T}%
$), and thus we already know that the answer is \textquotedblleft
no\textquotedblright. Hence, we proceed to the second entry.

\item Is this second entry $\left(  1,1,0\right)  ^{T}$ a linear combination
of the entries before it? Again, this is a question we have already answered
during our previous scan of the list (since the segment of our list
$\mathbf{a}$ up to its second entry has not changed when we removed $\left(
0,1,-1\right)  ^{T}$), and thus we already know that the answer is
\textquotedblleft no\textquotedblright. Hence, we proceed to the third entry.

\item Is this third entry $\left(  1,1,1\right)  ^{T}$ a linear combination of
entries before it? The entries before it are $\left(  1,2,-1\right)  ^{T}$ and
$\left(  1,1,0\right)  ^{T}$. Hence, we are asking whether $\left(
1,1,1\right)  ^{T}$ is a linear combination of the vectors $\left(
1,2,-1\right)  ^{T}$ and $\left(  1,1,0\right)  ^{T}$. In other words, we are
asking whether $\left(  1,1,1\right)  ^{T}=\lambda_{1}\left(  1,2,-1\right)
^{T}+\lambda_{2}\left(  1,1,0\right)  ^{T}$ for some $\lambda_{1}\in
\mathbb{R}$. Equivalently, we want to know whether $\left\{
\begin{array}
[c]{c}%
1=1\lambda_{1}+1\lambda_{2}\\
1=2\lambda_{1}+1\lambda_{2}\\
1=-1\lambda_{1}+0\lambda_{2}%
\end{array}
\right.  $ for some $\lambda_{1},\lambda_{2}\in\mathbb{R}$ (because the
equation $\left(  1,1,1\right)  ^{T}=\lambda_{1}\left(  1,2,-1\right)
^{T}+\lambda_{2}\left(  1,1,0\right)  ^{T}$ is equivalent to the system of
equations $\left\{
\begin{array}
[c]{c}%
1=1\lambda_{1}+1\lambda_{2}\\
1=2\lambda_{1}+1\lambda_{2}\\
1=-1\lambda_{1}+0\lambda_{2}%
\end{array}
\right.  $). In other words, we want to know whether the system $\left\{
\begin{array}
[c]{c}%
1=1\lambda_{1}+1\lambda_{2}\\
1=2\lambda_{1}+1\lambda_{2}\\
1=-1\lambda_{1}+0\lambda_{2}%
\end{array}
\right.  $ of linear equations (in the unknowns $\lambda_{1},\lambda_{2}$) has
a solution. But this question is easy to answer (e.g., by Gaussian
elimination), and the answer is \textquotedblleft no\textquotedblright. Thus,
our entry $\left(  1,1,1\right)  ^{T}$ is not a linear combination of the
entries before it. Thus, we have arrived at the end of the list.
\end{itemize}

We have thus ended up with the list $\left(  \left(  1,2,-1\right)
^{T},\left(  1,1,0\right)  ^{T},\left(  1,1,1\right)  ^{T}\right)  $. This
list is therefore a basis of $\mathbb{R}^{3}$ obtained by shrinking our (old)
list $\mathbf{a}$.

\textbf{(b)} There are various ways to do this. One particularly simple way is
the following\footnote{In this algorithm, we treat $\mathbf{b}$ as a mutable
variable.}: We scan the list $\mathbf{a}$ from left to right. Each time we
read an entry of $\mathbf{a}$, we check if this entry is a linear combination
of the (current) entries of $\mathbf{b}$. If it isn't, then we append this
entry to $\mathbf{b}$. In either case, we proceed to the next entry. By the
time we have scanned all entries of $\mathbf{a}$, the list $\mathbf{b}$ has
become a basis of $\mathbb{R}^{3}$. (This is easy to
prove\footnote{\textit{Proof.} Consider the following:
\par
\begin{itemize}
\item Every time we append an entry of $\mathbf{a}$ to the list $\mathbf{b}$,
the list $\mathbf{b}$ remains linearly independent (because we append an entry
to $\mathbf{b}$ only if this entry is not a linear combination of the existing
entries of $\mathbf{b}$; but this guarantees that the linear independence of
the list $\mathbf{b}$ is preserved).
\par
\item By the time we have scanned all entries of $\mathbf{a}$, the list
$\mathbf{b}$ has the property that each entry of $\mathbf{a}$ is a linear
combination of the entries of $\mathbf{b}$ (because when we scanned this
entry, we have ensured that it became such a linear combination by appending
it to $\mathbf{b}$, if it wasn't already one). In other words, every entry of
$\mathbf{a}$ belongs to $\operatorname*{span}\left(  \mathbf{b}\right)  $.
Thus, $\operatorname*{span}\left(  \mathbf{a}\right)  \subseteq
\operatorname*{span}\left(  \mathbf{b}\right)  $. But since $\mathbf{a}$ spans
$\mathbb{R}^{3}$, we have $\operatorname*{span}\left(  \mathbf{a}\right)
=\mathbb{R}^{3}$, so that $\mathbb{R}^{3}=\operatorname*{span}\left(
\mathbf{a}\right)  \subseteq\operatorname*{span}\left(  \mathbf{b}\right)  $
and thus $\operatorname*{span}\left(  \mathbf{b}\right)  =\mathbb{R}^{3}$.
\end{itemize}
\par
Hence, by the time we have scanned all entries of $\mathbf{a}$, the list
$\mathbf{b}$ is linearly independent and satisfies $\operatorname*{span}%
\left(  \mathbf{b}\right)  =\mathbb{R}^{3}$. In other words, this list
$\mathbf{b}$ has become a basis of $\mathbb{R}^{3}$.}.)

In order to simplify our life, we use not the original list
\[
\mathbf{a}=\left(  \left(  1,2,-1\right)  ^{T},\left(  1,1,0\right)
^{T},\left(  0,1,-1\right)  ^{T},\left(  1,1,1\right)  ^{T}\right)  ,
\]
but the shorter list
\[
\mathbf{a}=\left(  \left(  1,2,-1\right)  ^{T},\left(  1,1,0\right)
^{T},\left(  1,1,1\right)  ^{T}\right)
\]
obtained at the end of the shrinking process in part \textbf{(a)} of the
problem. Indeed, this shorter list works just as well (it is a basis of
$\mathbb{R}^{3}$ and thus spans $\mathbb{R}^{3}$), and clearly its elements
are elements of the original list $\mathbf{a}$ as well.

Let us now execute our algorithm step by step:

\begin{itemize}
\item We scan the list $\mathbf{a}$ from left to right. Thus, we begin at its
first entry, which is $\left(  1,2,-1\right)  ^{T}$.

\item Is this first entry $\left(  1,2,-1\right)  ^{T}$ a linear combination
of the entries of $\mathbf{b}$? The entries of $\mathbf{b}$ are $\left(
-1,0,1\right)  ^{T}$ and $\left(  2,3,4\right)  ^{T}$. Hence, we are asking
whether $\left(  1,2,-1\right)  ^{T}$ is a linear combination of the vectors
$\left(  -1,0,1\right)  ^{T}$ and $\left(  2,3,4\right)  ^{T}$. In other
words, we are asking whether $\left(  1,2,-1\right)  ^{T}=\lambda_{1}\left(
-1,0,1\right)  ^{T}+\lambda_{2}\left(  2,3,4\right)  ^{T}$ for some
$\lambda_{1},\lambda_{2}\in\mathbb{R}$. Equivalently, we want to know whether
$\left\{
\begin{array}
[c]{c}%
1=\left(  -1\right)  \lambda_{1}+2\lambda_{2}\\
2=0\lambda_{1}+3\lambda_{2}\\
-1=1\lambda_{1}+4\lambda_{2}%
\end{array}
\right.  $ for some $\lambda_{1},\lambda_{2}\in\mathbb{R}$ (because the
equation $\left(  1,2,-1\right)  ^{T}=\lambda_{1}\left(  -1,0,1\right)
^{T}+\lambda_{2}\left(  2,3,4\right)  ^{T}$ is equivalent to the system of
equations $\left\{
\begin{array}
[c]{c}%
1=\left(  -1\right)  \lambda_{1}+2\lambda_{2}\\
2=0\lambda_{1}+3\lambda_{2}\\
-1=1\lambda_{1}+4\lambda_{2}%
\end{array}
\right.  $). In other words, we want to know whether the system $\left\{
\begin{array}
[c]{c}%
1=\left(  -1\right)  \lambda_{1}+2\lambda_{2}\\
2=0\lambda_{1}+3\lambda_{2}\\
-1=1\lambda_{1}+4\lambda_{2}%
\end{array}
\right.  $ of linear equations (in the unknowns $\lambda_{1},\lambda_{2}$) has
a solution. But this question is easy to answer (e.g., by Gaussian
elimination), and the answer is \textquotedblleft no\textquotedblright. Thus,
our entry $\left(  1,2,-1\right)  ^{T}$ is not a linear combination of the
entries of $\mathbf{b}$. Thus, we append this entry to $\mathbf{b}$, so that
$\mathbf{b}$ becomes $\left(  \left(  -1,0,1\right)  ^{T},\left(
2,3,4\right)  ^{T},\left(  1,2,-1\right)  ^{T}\right)  $. We now proceed to
the second entry of $\mathbf{a}$.

\item Is this second entry $\left(  1,1,0\right)  ^{T}$ a linear combination
of the entries of $\mathbf{b}$? The entries of $\mathbf{b}$ are $\left(
-1,0,1\right)  ^{T}$, $\left(  2,3,4\right)  ^{T}$ and $\left(  1,2,-1\right)
^{T}$ (keep in mind that $\mathbf{b}$ has changed in the previous step!).
Hence, we are asking whether $\left(  1,1,0\right)  ^{T}$ is a linear
combination of the vectors $\left(  -1,0,1\right)  ^{T}$, $\left(
2,3,4\right)  ^{T}$ and $\left(  1,2,-1\right)  ^{T}$. By now, we have seen
often enough how to answer such questions (of course, we now have to solve a
system of equations in three unknowns $\lambda_{1},\lambda_{2},\lambda_{3}$).
The answer is \textquotedblleft yes\textquotedblright. Thus, our entry
$\left(  1,1,0\right)  ^{T}$ is a linear combination of the entries of
$\mathbf{b}$. Hence, we proceed to the third entry of $\mathbf{a}$ (without
adding anything to $\mathbf{b}$). Recall that we have used the shorter list
$\mathbf{a}=\left(  \left(  1,2,-1\right)  ^{T},\left(  1,1,0\right)
^{T},\left(  1,1,1\right)  ^{T}\right)  $ as our $\mathbf{a}$, so this third
entry is $\left(  1,1,1\right)  ^{T}$.

\item Is this third entry $\left(  1,1,1\right)  ^{T}$ a linear combination of
the entries of $\mathbf{b}$? The answer is \textquotedblleft
yes\textquotedblright\ (found in the same way as many times before). Hence, we
arrive at the end of $\mathbf{a}$ (without adding anything to $\mathbf{b}$).
\end{itemize}

We have thus ended up with the list $\mathbf{b}=\left(  \left(  -1,0,1\right)
^{T},\left(  2,3,4\right)  ^{T},\left(  1,2,-1\right)  ^{T}\right)  $. This
list is therefore a basis of $\mathbb{R}^{3}$ obtained by appending some
elements from $\mathbf{a}$ to the (old) list $\mathbf{b}$.

[\textit{Remark:} We could have made our life much easier. In fact, we could
have stopped our algorithm immediately after adding $\left(  1,2,-1\right)
^{T}$ to the list $\mathbf{b}$, because the list $\mathbf{b}$ had become a
basis of $\mathbb{R}^{3}$ at that moment (being a linearly independent list of
$3$ vectors in $\mathbb{R}^{3}$).

There are other ways to solve this exercise, and some of them lead to
different results. For example, $\left(  \left(  -1,0,1\right)  ^{T},\left(
2,3,4\right)  ^{T},\left(  0,1,-1\right)  ^{T}\right)  $ is an equally valid
answer to part \textbf{(b)}.]
\end{proof}



\begin{proof}
[Solution to Exercise \ref{exe.rank.find-16712}.] There are many ways to solve
this. The most systematic one is to follow the algorithm sketched in Example
1.3.5 in \href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-12-04.pdf}{the
class notes from 2019-12-04}; this algorithm proceeds in three phases:

\begin{enumerate}
\item[\textbf{Phase 1:}] first, transform $A$ into RREF using row operations;

\item[\textbf{Phase 2:}] then, clear out the nonzero entries to the right of
the pivots using column operations of the ECO3 kind;

\item[\textbf{Phase 3:}] finally, move all pivots as far left as possible
using column operations of the ECO1 kind).
\end{enumerate}

\noindent I will not show this procedure in detail, but let me remark that the
RREF of $A$ is $\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & \dfrac{13}{7} & \dfrac{6}{7}\\
0 & \fbox{$1$} & \dfrac{6}{7} & \dfrac{13}{7}\\
0 & 0 & 0 & 0
\end{array}
\right)  $ (where the pivots are boxed, as usual), and thus Phase 2 results in
$\left(
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & 0 & 0\\
0 & \fbox{$1$} & 0 & 0\\
0 & 0 & 0 & 0
\end{array}
\right)  $. The pivots here are already in the first two columns, so Phase 3
is not necessary, and we conclude that the rank normal form of $A$ is $\left(
%
\begin{array}
[c]{cccc}%
\fbox{$1$} & 0 & 0 & 0\\
0 & \fbox{$1$} & 0 & 0\\
0 & 0 & 0 & 0
\end{array}
\right)  $. The rank of $A$ is the number of pivots; thus, it equals $2$.

\bigskip

\begin{fineprint}
[However, let me show one alternative way to find the rank normal form of $A$,
without going through the RREF. Recall that we can do any row operations and
any column operations, as long as the final result is in rank normal form. So
we can make our job easier by picking the easiest operations to do:%
\begin{align*}
& \left(
\begin{array}
[c]{cccc}%
1 & 6 & 7 & 12\\
2 & 5 & 8 & 11\\
3 & 4 & 9 & 10
\end{array}
\right)  \underset{\text{to column }3}{\overset{\text{add }-1\cdot\text{column
}1}{\longrightarrow}}\left(
\begin{array}
[c]{cccc}%
1 & 6 & 6 & 12\\
2 & 5 & 6 & 11\\
3 & 4 & 6 & 10
\end{array}
\right)  \underset{\text{to column }4}{\overset{\text{add }-1\cdot\text{column
}2}{\longrightarrow}}\left(
\begin{array}
[c]{cccc}%
1 & 6 & 6 & 6\\
2 & 5 & 6 & 6\\
3 & 4 & 6 & 6
\end{array}
\right)  \\
& \underset{\text{to column }4}{\overset{\text{add }-1\cdot\text{column
}3}{\longrightarrow}}\left(
\begin{array}
[c]{cccc}%
1 & 6 & 6 & 0\\
2 & 5 & 6 & 0\\
3 & 4 & 6 & 0
\end{array}
\right)  \underset{\text{by }1/6}{\overset{\text{scale column }%
3}{\longrightarrow}}\left(
\begin{array}
[c]{cccc}%
1 & 6 & 1 & 0\\
2 & 5 & 1 & 0\\
3 & 4 & 1 & 0
\end{array}
\right)  \underset{\text{to column }2}{\overset{\text{add }1\cdot\text{column
}1}{\longrightarrow}}\left(
\begin{array}
[c]{cccc}%
1 & 7 & 1 & 0\\
2 & 7 & 1 & 0\\
3 & 7 & 1 & 0
\end{array}
\right)  \\
& \underset{\text{by }1/7}{\overset{\text{scale column }2}{\longrightarrow}%
}\left(
\begin{array}
[c]{cccc}%
1 & 1 & 1 & 0\\
2 & 1 & 1 & 0\\
3 & 1 & 1 & 0
\end{array}
\right)  \underset{\text{to column }3}{\overset{\text{add }-1\cdot\text{column
}2}{\longrightarrow}}\left(
\begin{array}
[c]{cccc}%
1 & 1 & 0 & 0\\
2 & 1 & 0 & 0\\
3 & 1 & 0 & 0
\end{array}
\right)  \underset{\text{to row }2}{\overset{\text{add }-2\cdot\text{row
}1}{\longrightarrow}}\left(
\begin{array}
[c]{cccc}%
1 & 1 & 0 & 0\\
0 & -1 & 0 & 0\\
3 & 1 & 0 & 0
\end{array}
\right)  \\
& \underset{\text{to row }3}{\overset{\text{add }-3\cdot\text{row
}1}{\longrightarrow}}\left(
\begin{array}
[c]{cccc}%
1 & 1 & 0 & 0\\
0 & -1 & 0 & 0\\
0 & -2 & 0 & 0
\end{array}
\right)  \underset{\text{to row }3}{\overset{\text{add }-2\cdot\text{row
}2}{\longrightarrow}}\left(
\begin{array}
[c]{cccc}%
1 & 1 & 0 & 0\\
0 & -1 & 0 & 0\\
0 & 0 & 0 & 0
\end{array}
\right)  \underset{\text{to row }1}{\overset{\text{add }1\cdot\text{row
}2}{\longrightarrow}}\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & -1 & 0 & 0\\
0 & 0 & 0 & 0
\end{array}
\right)  \\
& \underset{\text{by }-1}{\overset{\text{scale row }1}{\longrightarrow}%
}\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 0
\end{array}
\right)  .
\end{align*}
The matrix we have obtained is clearly in rank normal form, so it must be the
rank normal form of $A$. Moreover, it has $2$ pivots, so the rank of $A$ must
be $2$.]
\end{fineprint}
\end{proof}


\end{document}