\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=Wednesday, October 30, 2019 22:11:57}
%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}}
\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): homework set 2}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 201-003 Fall 2019 (Darij Grinberg): homework set 2 with
solutions}
\end{center}

\begin{exercise}
\label{exe.Adiag}Let $n\in\mathbb{N}$. For any $n$ numbers $d_{1},d_{2}%
,\ldots,d_{n}\in\mathbb{R}$, we let $\operatorname*{diag}\left(  d_{1}%
,d_{2},\ldots,d_{n}\right)  $ denote the $n\times n$-matrix whose diagonal
entries are $d_{1},d_{2},\ldots,d_{n}$ (in this order from top to bottom),
while its off-diagonal entries are all $0$. In other words,%
\[
\operatorname*{diag}\left(  d_{1},d_{2},\ldots,d_{n}\right)  =\left(
\begin{array}
[c]{cccc}%
d_{1} & 0 & \cdots & 0\\
0 & d_{2} & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & d_{n}%
\end{array}
\right)  .
\]
This is called the \textit{diagonal matrix with diagonal entries }$d_{1}%
,d_{2},\ldots,d_{n}$.

\textbf{(a)} Given any $d_{1},d_{2},d_{3}\in\mathbb{R}$ and any $3\times
3$-matrix $A=\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}\\
a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime}%
\end{array}
\right)  $, compute $\operatorname*{diag}\left(  d_{1},d_{2},d_{3}\right)
\cdot A$.

\textbf{(b)} State a rule for computing $\operatorname*{diag}\left(
d_{1},d_{2},\ldots,d_{n}\right)  \cdot A$, where $d_{1},d_{2},\ldots,d_{n}%
\in\mathbb{R}$ and where $A$ is any $n\times m$-matrix (with $m$ being any
nonnegative integer).

\textbf{(c)} State a rule for computing $A\cdot\operatorname*{diag}\left(
d_{1},d_{2},\ldots,d_{n}\right)  $, where $d_{1},d_{2},\ldots,d_{n}%
\in\mathbb{R}$ and where $A$ is any $m\times n$-matrix (with $m$ being any
nonnegative integer).

[You don't have to prove these rules.]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.Adiag}.]\textbf{(a)} We have%
\[
\operatorname*{diag}\left(  d_{1},d_{2},d_{3}\right)  =\left(
\begin{array}
[c]{ccc}%
d_{1} & 0 & 0\\
0 & d_{2} & 0\\
0 & 0 & d_{3}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }%
\operatorname*{diag}\left(  d_{1},d_{2},d_{3}\right)  \right)
\]
and%
\[
A=\left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}\\
a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime}%
\end{array}
\right)  .
\]
Multiplying these equalities, we obtain%
\begin{align*}
\operatorname*{diag}\left(  d_{1},d_{2},d_{3}\right)  \cdot A  &  =\left(
\begin{array}
[c]{ccc}%
d_{1} & 0 & 0\\
0 & d_{2} & 0\\
0 & 0 & d_{3}%
\end{array}
\right)  \left(
\begin{array}
[c]{ccc}%
a & b & c\\
a^{\prime} & b^{\prime} & c^{\prime}\\
a^{\prime\prime} & b^{\prime\prime} & c^{\prime\prime}%
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{ccc}%
d_{1}a+0a^{\prime}+0a^{\prime\prime} & d_{1}b+0b^{\prime}+0b^{\prime\prime} &
d_{1}c+0c^{\prime}+0c^{\prime\prime}\\
0a+d_{2}a^{\prime}+0a^{\prime\prime} & 0b+d_{2}b^{\prime}+0b^{\prime\prime} &
0c+d_{2}c^{\prime}+0c^{\prime\prime}\\
0a+0a^{\prime}+d_{3}a^{\prime\prime} & 0b+0b^{\prime}+d_{3}b^{\prime\prime} &
0c+0c^{\prime}+d_{3}c^{\prime\prime}%
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{ccc}%
d_{1}a & d_{1}b & d_{1}c\\
d_{2}a^{\prime} & d_{2}b^{\prime} & d_{2}c^{\prime}\\
d_{3}a^{\prime\prime} & d_{3}b^{\prime\prime} & d_{3}c^{\prime\prime}%
\end{array}
\right)  .
\end{align*}


\textbf{(b)} Let $d_{1},d_{2},\ldots,d_{n}\in\mathbb{R}$. Let $m\in\mathbb{N}%
$. Let $A$ be any $n\times m$-matrix. Then, the matrix $\operatorname*{diag}%
\left(  d_{1},d_{2},\ldots,d_{n}\right)  \cdot A$ is obtained from $A$ by
scaling the $i$-th row by $d_{i}$ for each $i\in\left\{  1,2,\ldots,n\right\}
$. In other words,%
\begin{equation}
\left(  \operatorname*{diag}\left(  d_{1},d_{2},\ldots,d_{n}\right)  \cdot
A\right)  _{i,j}=d_{i}A_{i,j} \label{sol.Adiag.b.claim}%
\end{equation}
for each $i\in\left\{  1,2,\ldots,n\right\}  $ and $j\in\left\{
1,2,\ldots,m\right\}  $.

\begin{fineprint}
[\textit{Proof of (\ref{sol.Adiag.b.claim}):} Set $D=\operatorname*{diag}%
\left(  d_{1},d_{2},\ldots,d_{n}\right)  $. Thus,%
\begin{equation}
D_{i,k}=0\ \ \ \ \ \ \ \ \ \ \text{for any two distinct elements }i\text{ and
}k\text{ of }\left\{  1,2,\ldots,n\right\}  , \label{sol.Adiag.b.claim.pf.1}%
\end{equation}
and%
\begin{equation}
D_{i,i}=d_{i}\ \ \ \ \ \ \ \ \ \ \text{for each }i\in\left\{  1,2,\ldots
,n\right\}  . \label{sol.Adiag.b.claim.pf.2}%
\end{equation}
But the definition of the product of two matrices yields%
\begin{equation}
DA=\left(  D_{i,1}A_{1,j}+D_{i,2}A_{2,j}+\cdots+D_{i,n}A_{n,j}\right)  _{1\leq
i\leq n,\ 1\leq j\leq m}. \label{sol.Adiag.b.claim.pf.3}%
\end{equation}
Hence,
\begin{equation}
\left(  DA\right)  _{i,j}=D_{i,1}A_{1,j}+D_{i,2}A_{2,j}+\cdots+D_{i,n}A_{n,j}
\label{sol.Adiag.b.claim.pf.5}%
\end{equation}
for each $i\in\left\{  1,2,\ldots,n\right\}  $ and $j\in\left\{
1,2,\ldots,m\right\}  $.

Fix $i\in\left\{  1,2,\ldots,n\right\}  $ and $j\in\left\{  1,2,\ldots
,m\right\}  $. The sum $D_{i,1}A_{1,j}+D_{i,2}A_{2,j}+\cdots+D_{i,n}A_{n,j}$
has $n$ addends. One of these $n$ addends (to be specific: the $i$-th one) is%
\[
\underbrace{D_{i,i}}_{\substack{=d_{i}\\\text{(by
(\ref{sol.Adiag.b.claim.pf.2}))}}}A_{i,j}=d_{i}A_{i,j},
\]
whereas all the other addends are $0$ (because each of them has the form
$D_{i,k}A_{k,j}$ for some $k\in\left\{  1,2,\ldots,n\right\}  $ distinct from
$i$, and thus rewrites as $\underbrace{D_{i,k}}_{\substack{=0\\\text{(by
(\ref{sol.Adiag.b.claim.pf.1}))}}}A_{k,j}=0$). Hence, this sum equals
$d_{i}A_{i,j}$. In other words,%
\[
D_{i,1}A_{1,j}+D_{i,2}A_{2,j}+\cdots+D_{i,n}A_{n,j}=d_{i}A_{i,j}.
\]
Hence, (\ref{sol.Adiag.b.claim.pf.5}) rewrites as $\left(  DA\right)
_{i,j}=d_{i}A_{i,j}$. In view of $D=\operatorname*{diag}\left(  d_{1}%
,d_{2},\ldots,d_{n}\right)  $, this further rewrites as
\[
\left(  \operatorname*{diag}\left(  d_{1},d_{2},\ldots,d_{n}\right)  \cdot
A\right)  _{i,j}=d_{i}A_{i,j}.
\]
This proves (\ref{sol.Adiag.b.claim}).]
\end{fineprint}

\textbf{(c)} Let $d_{1},d_{2},\ldots,d_{n}\in\mathbb{R}$. Let $m\in\mathbb{N}%
$. Let $A$ be any $m\times n$-matrix. Then, the matrix $A\cdot
\operatorname*{diag}\left(  d_{1},d_{2},\ldots,d_{n}\right)  $ is obtained
from $A$ by scaling the $j$-th column by $d_{j}$ for each $j\in\left\{
1,2,\ldots,n\right\}  $. In other words,%
\[
\left(  A\cdot\operatorname*{diag}\left(  d_{1},d_{2},\ldots,d_{n}\right)
\right)  _{i,j}=d_{j}A_{i,j}%
\]
for each $i\in\left\{  1,2,\ldots,m\right\}  $ and $j\in\left\{
1,2,\ldots,n\right\}  $.

\begin{fineprint}
[The proof of this is similar to the proof of (\ref{sol.Adiag.b.claim}); we
omit it.]
\end{fineprint}
\end{proof}

We recall the definition of linear combinations (\cite[Definition
7.1]{Strickland}):

\begin{definition}
\label{def.linc}Let $v_{1},v_{2},\ldots,v_{k}$ be some vectors in
$\mathbb{R}^{n}$. Then, a \textit{linear combination} of $v_{1},v_{2}%
,\ldots,v_{k}$ means a vector that can be written in the form%
\[
\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k}v_{k}%
\ \ \ \ \ \ \ \ \ \ \text{for some }\lambda_{1},\lambda_{2},\ldots,\lambda
_{k}\in\mathbb{R}.
\]

\end{definition}

The numbers $\lambda_{1},\lambda_{2},\ldots,\lambda_{k}$ in this definition
are called \textit{coefficients} of this linear combination; but they are not
necessarily unique (in fact, they are unique if $v_{1},v_{2},\ldots,v_{k}$ are
linearly independent; we shall see this later in class). For example, if
$v_{1}=\left(
\begin{array}
[c]{c}%
1\\
1
\end{array}
\right)  $ and $v_{2}=\left(
\begin{array}
[c]{c}%
2\\
2
\end{array}
\right)  $, then the vector $\left(
\begin{array}
[c]{c}%
3\\
3
\end{array}
\right)  $ is a linear combination of $v_{1}$ and $v_{2}$, and can be written
as $\lambda_{1}v_{1}+\lambda_{2}v_{2}$ in many ways:%
\[
\left(
\begin{array}
[c]{c}%
3\\
3
\end{array}
\right)  =1v_{1}+1v_{2}=3v_{1}+0v_{2}=0v_{1}+\dfrac{3}{2}v_{2}=2v_{1}%
+\dfrac{1}{2}v_{2}=\cdots.
\]


We recall the definition of linear independence (\cite[\S 8]{Strickland}):

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

\textbf{(a)} A \textit{relation} (more precisely: \textit{linear relation})
between $v_{1},v_{2},\ldots,v_{k}$ means a choice of reals $\lambda
_{1},\lambda_{2},\ldots,\lambda_{k}$ satisfying%
\[
\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k}v_{k}=0.
\]
(Here, $0$ denotes the zero vector $0_{n\times1}\in\mathbb{R}^{n}$.)

\textbf{(b)} The \textit{trivial relation} between $v_{1},v_{2},\ldots,v_{k}$
is the relation obtained by choosing $\lambda_{1}=\lambda_{2}=\cdots
=\lambda_{k}=0$. Clearly, $v_{1},v_{2},\ldots,v_{k}$ always have this trivial relation.

\textbf{(c)} 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)  $ of these
vectors) are\textit{ independent} (more precisely: \textit{linearly
independent}) if the only relation between $v_{1},v_{2},\ldots,v_{k}$ is the
trivial relation. Otherwise, we say that these vectors are \textit{dependent}.
\end{definition}

For example, if we set%
\[
v_{1}=\left(
\begin{array}
[c]{c}%
1\\
1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ v_{2}=\left(
\begin{array}
[c]{c}%
1\\
2
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ v_{3}=\left(
\begin{array}
[c]{c}%
1\\
3
\end{array}
\right)  ,
\]
then the vectors $v_{1},v_{2},v_{3}$ are linearly dependent, since they have
the nontrivial relation $1v_{1}+\left(  -2\right)  v_{2}+1v_{3}=0$.

\begin{exercise}
\label{exe.linc.1}Let
\[
v_{1}=\left(
\begin{array}
[c]{c}%
0\\
1\\
-1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ v_{2}=\left(
\begin{array}
[c]{c}%
-1\\
0\\
1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ v_{3}=\left(
\begin{array}
[c]{c}%
1\\
-1\\
0
\end{array}
\right)  .
\]


\textbf{(a)} Are $v_{1},v_{2},v_{3}$ dependent? (If yes, show a nontrivial
relation between them.)

\textbf{(b)} Is $\left(
\begin{array}
[c]{c}%
1\\
2\\
3
\end{array}
\right)  $ a linear combination of $v_{1},v_{2},v_{3}$ ? (If yes, provide a
choice of coefficients $\lambda_{1},\lambda_{2},\lambda_{3}$ that demonstrate it.)

\textbf{(c)} Is $\left(
\begin{array}
[c]{c}%
1\\
2\\
-3
\end{array}
\right)  $ a linear combination of $v_{1},v_{2},v_{3}$ ? (If yes, provide a
choice of coefficients $\lambda_{1},\lambda_{2},\lambda_{3}$ that demonstrate it.)
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.linc.1}.]\textbf{(a)} The vectors $v_{1}%
,v_{2},v_{3}$ are dependent.

\textit{Proof.} It is easy to see that $1v_{1}+1v_{2}+1v_{3}=0$, which is a
nontrivial relation.

\textbf{(b)} No.

\textit{Proof.} Each of the three vectors $v_{1},v_{2},v_{3}$ has the property
that the sum of its coordinates is $0$. Thus, every combination of
$v_{1},v_{2},v_{3}$ has this property as well\footnote{Make sure you
understand why! (Also make sure you understand why a property like
\textquotedblleft one of the coordinates is $0$\textquotedblright\ would
\textbf{not} be transferred from $v_{1},v_{2},v_{3}$ to all their
combinations.}. But the vector $\left(
\begin{array}
[c]{c}%
1\\
2\\
3
\end{array}
\right)  $ does not have this property. Thus, the latter vector is not a
combination of $v_{1},v_{2},v_{3}$.

\textbf{(c)} Yes.

\textit{Proof.} We have $\left(
\begin{array}
[c]{c}%
1\\
2\\
-3
\end{array}
\right)  =v_{3}+3v_{1}=3v_{1}+0v_{2}+1v_{3}$.

[\textit{Remark: }The above proofs rely on pattern-spotting and educated
guesses, which require a bit of ingenuity or experience to find. But you can
just as well solve the exercise by following algorithms. Indeed, \cite[Method
8.8]{Strickland} is a surefire way to answer questions like part \textbf{(a)}
of this exercise, whereas \cite[Method 7.6]{Strickland} can be used to solve
parts \textbf{(b)} and \textbf{(c)}.]
\end{proof}

Clearly, rearranging a list of vectors does not change the set of its linear
combinations: In fact, the rearranged vectors will have the same linear
combinations as the original vectors; only the coefficients will change their
order. For example, the linear combinations of $v_{1},v_{2},v_{3}$ are the
same as the linear combinations of $v_{3},v_{1},v_{2}$, since $\lambda
_{1}v_{1}+\lambda_{2}v_{2}+\lambda_{3}v_{3}=\lambda_{3}v_{3}+\lambda_{1}%
v_{1}+\lambda_{2}v_{2}$.

Rearranging a list of vectors also does not change its linear dependence or
independence: In fact, any linear relation between the rearranged vectors is a
rearranged linear relation between the original vectors, and vice versa. Thus,
$v_{1},v_{2},v_{3}$ are dependent if and only if $v_{3},v_{1},v_{2}$ are dependent.

What happens to lists of vectors when we duplicate a vector? The following
exercise answers this question (at least when it's the last vector that is duplicated):

\begin{exercise}
\label{exe.lincd.vk-1=vk}Let $v_{1},v_{2},\ldots,v_{k}$ be some vectors in
$\mathbb{R}^{n}$. Assume that $v_{k-1}=v_{k}$. Justify the following (i.e.,
sketch the proofs):

\textbf{(a)} The vectors $v_{1},v_{2},\ldots,v_{k}$ are linearly dependent.

\textbf{(b)} The linear combinations of $v_{1},v_{2},\ldots,v_{k}$ are the
same vectors as the linear combinations of $v_{1},v_{2},\ldots,v_{k-1}$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.lincd.vk-1=vk}.]\textbf{(a)} We have
\[
0v_{1}+0v_{2}+\cdots+0v_{k-2}+1v_{k-1}+\left(  -1\right)  v_{k}=v_{k-1}%
-v_{k}=0
\]
(since $v_{k-1}=v_{k}$). Thus, the relation%
\[
0v_{1}+0v_{2}+\cdots+0v_{k-2}+1v_{k-1}+\left(  -1\right)  v_{k}=0
\]
between $v_{1},v_{2},\ldots,v_{k}$ holds. This relation is clearly nontrivial,
since $1\neq0$. Hence, the vectors $v_{1},v_{2},\ldots,v_{k}$ are linearly
dependent. This solves part \textbf{(a)} of the exercise.

\textbf{(b)} We need to show the following two claims:

\begin{statement}
\textit{Claim 1:} Every linear combination of $v_{1},v_{2},\ldots,v_{k}$ is a
linear combination of $v_{1},v_{2},\ldots,v_{k-1}$.
\end{statement}

\begin{statement}
\textit{Claim 2:} Every linear combination of $v_{1},v_{2},\ldots,v_{k-1}$ is
a linear combination of $v_{1},v_{2},\ldots,v_{k}$.
\end{statement}

[\textit{Proof of Claim 1:} Let $w$ be a linear combination of $v_{1}%
,v_{2},\ldots,v_{k}$. We must show that $w$ is a linear combination of
$v_{1},v_{2},\ldots,v_{k-1}$.

We know that $w$ is a linear combination of $v_{1},v_{2},\ldots,v_{k}$. In
other words, there exist numbers $\lambda_{1},\lambda_{2},\ldots,\lambda_{k}$
such that $w=\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k}v_{k}$. Thus,%
\begin{align*}
w  &  =\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k}v_{k}\\
&  =\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k-2}v_{k-2}%
+\lambda_{k-1}v_{k-1}+\lambda_{k}\underbrace{v_{k}}_{=v_{k-1}}\\
&  =\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k-2}v_{k-2}%
+\underbrace{\lambda_{k-1}v_{k-1}+\lambda_{k}v_{k-1}}_{=\left(  \lambda
_{k-1}+\lambda_{k}\right)  v_{k-1}}\\
&  =\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k-2}v_{k-2}+\left(
\lambda_{k-1}+\lambda_{k}\right)  v_{k-1}.
\end{align*}
This shows that $w$ is a linear combination of $v_{1},v_{2},\ldots,v_{k-1}$.
This proves Claim 1.]

[\textit{Proof of Claim 2:} Let $w$ be a linear combination of $v_{1}%
,v_{2},\ldots,v_{k-1}$. We must show that $w$ is a linear combination of
$v_{1},v_{2},\ldots,v_{k}$.

We know that $w$ is a linear combination of $v_{1},v_{2},\ldots,v_{k-1}$. In
other words, there exist numbers $\lambda_{1},\lambda_{2},\ldots,\lambda
_{k-1}$ such that $w=\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda
_{k-1}v_{k-1}$. Thus,%
\begin{align*}
w  &  =\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k-1}v_{k-1}\\
&  =\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k-1}v_{k-1}+0\\
&  =\lambda_{1}v_{1}+\lambda_{2}v_{2}+\cdots+\lambda_{k-1}v_{k-1}+0v_{k}.
\end{align*}
This shows that $w$ is a linear combination of $v_{1},v_{2},\ldots,v_{k}$.
This proves Claim 2.]

[\textit{Remark:} In our proof of Claim 2, we did not use the assumption that
$v_{k-1}=v_{k}$. More generally, it is always true that a linear combination
of a subsequence of a given list of vectors must always be a linear
combination of the whole sequence. It is the other direction that is usually
not valid.]
\end{proof}

\begin{exercise}
\label{exe.linc.eks}Let $n\in\mathbb{N}$. For each $k\in\left\{
1,2,\ldots,n\right\}  $, we let $e_{k}$ denote the column vector of size $n$
whose $k$-th entry is $1$ and whose all other entries are $0$.

(For example: If $n=3$, then $e_{1}=\left(
\begin{array}
[c]{c}%
1\\
0\\
0
\end{array}
\right)  $ and $e_{2}=\left(
\begin{array}
[c]{c}%
0\\
1\\
0
\end{array}
\right)  $ and $e_{3}=\left(
\begin{array}
[c]{c}%
0\\
0\\
1
\end{array}
\right)  $.)

Explain why each vector in $\mathbb{R}^{n}$ is a linear combination of
$e_{1},e_{2},\ldots,e_{n}$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.linc.eks}.]Let $v$ be any vector in
$\mathbb{R}^{n}$. We must prove that $v$ is a linear combination of
$e_{1},e_{2},\ldots,e_{n}$.

Write $v$ in the form $v=\left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{n}%
\end{array}
\right)  $, where $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}\in\mathbb{R}$
are its coordinates. For each $i\in\left\{  1,2,\ldots,n\right\}  $, we have%
\[
e_{i}=\left(
\begin{array}
[c]{c}%
0\\
0\\
\vdots\\
0\\
1\\
0\\
\vdots\\
0
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{with the }1\text{ being in the
}i\text{-th position}\right)
\]
and thus%
\[
\lambda_{i}e_{i}=\left(
\begin{array}
[c]{c}%
\lambda_{i}0\\
\lambda_{i}0\\
\vdots\\
\lambda_{i}0\\
\lambda_{i}1\\
\lambda_{i}0\\
\vdots\\
\lambda_{i}0
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
0\\
0\\
\vdots\\
0\\
\lambda_{i}\\
0\\
\vdots\\
0
\end{array}
\right)
\]
(where the entry $\lambda_{i}$ is in the $i$-th position). Hence,%
\begin{align*}
&  \lambda_{1}e_{1}+\lambda_{2}e_{2}+\cdots+\lambda_{n}e_{n}\\
&  =\left(
\begin{array}
[c]{c}%
\lambda_{1}\\
0\\
\vdots\\
0
\end{array}
\right)  +\left(
\begin{array}
[c]{c}%
0\\
\lambda_{2}\\
\vdots\\
0
\end{array}
\right)  +\cdots+\left(
\begin{array}
[c]{c}%
0\\
0\\
\vdots\\
\lambda_{n}%
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{c}%
\lambda_{1}+0+0+\cdots+0\\
0+\lambda_{2}+0+\cdots+0\\
\vdots\\
0+0+0+\cdots+\lambda_{n}%
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
\lambda_{1}\\
\lambda_{2}\\
\vdots\\
\lambda_{n}%
\end{array}
\right)  =v.
\end{align*}
In other words, $v=\lambda_{1}e_{1}+\lambda_{2}e_{2}+\cdots+\lambda_{n}e_{n}$.
Hence, $v$ is a linear combination of $e_{1},e_{2},\ldots,e_{n}$.
\end{proof}

Definition \ref{def.linc} and Definition \ref{def.lind} make sense not only
for vectors in $\mathbb{R}^{n}$. For example, we can replace \textquotedblleft
vectors in $\mathbb{R}^{n}$\textquotedblright\ by \textquotedblleft
polynomials\textquotedblright\ in both definitions, and obtain definitions for
linear combinations and linear independence of polynomials (in one variable
$x$, with real coefficients).\footnote{Of course, we then have to interpret
$0$ as the zero polynomial rather than the zero vector $0_{n\times1}$.} Thus:

\begin{itemize}
\item The polynomial $x^{2}+2x-1$ is a linear combination of the polynomials
$x^{2}$ and $\left(  x-1\right)  ^{2}$, since%
\[
x^{2}+2x-1=2\cdot x^{2}+\left(  -1\right)  \cdot\left(  x-1\right)  ^{2}.
\]


\item The polynomials $x^{2}$, $\left(  x-1\right)  ^{2}$, $\left(
x-2\right)  ^{2}$ and $\left(  x-3\right)  ^{2}$ are linearly dependent, since
there exists a nontrivial linear relation between them: If we take
$\lambda_{1}=1$, $\lambda_{2}=-3$, $\lambda_{3}=3$ and $\lambda_{4}=-1$, then%
\begin{align*}
&  \lambda_{1}x^{2}+\lambda_{2}\left(  x-1\right)  ^{2}+\lambda_{3}\left(
x-2\right)  ^{2}+\lambda_{4}\left(  x-3\right)  ^{2}\\
&  =1\cdot x^{2}+\left(  -3\right)  \cdot\left(  x-1\right)  ^{2}%
+3\cdot\left(  x-2\right)  ^{2}+\left(  -1\right)  \cdot\left(  x-3\right)
^{2}=0.
\end{align*}


\item The polynomials $x^{2}$, $\left(  x-1\right)  ^{2}$ and $\left(
x-2\right)  ^{2}$ are linearly independent, because the only relation
\begin{equation}
\lambda_{1}x^{2}+\lambda_{2}\left(  x-1\right)  ^{2}+\lambda_{3}\left(
x-2\right)  ^{2}=0 \label{eq.lind.pol.exa.3.eq1}%
\end{equation}
between them is the trivial one. How to be sure of this? One way is to assume
that (\ref{eq.lind.pol.exa.3.eq1}) holds, and try to derive $\lambda
_{1}=\lambda_{2}=\lambda_{3}=0$ from it. This can be done, for example, by
comparing coefficients: Straightforward expansion yields%
\begin{align*}
&  \lambda_{1}x^{2}+\lambda_{2}\left(  x-1\right)  ^{2}+\lambda_{3}\left(
x-2\right)  ^{2}\\
&  =\lambda_{1}x^{2}+\lambda_{2}\left(  x^{2}-2x+1\right)  +\lambda_{3}\left(
x^{2}-4x+4\right) \\
&  =\left(  \lambda_{1}+\lambda_{2}+\lambda_{3}\right)  x^{2}+\left(
-2\lambda_{2}-4\lambda_{3}\right)  x+\left(  \lambda_{2}+4\lambda_{3}\right)
,
\end{align*}
and thus (\ref{eq.lind.pol.exa.3.eq1}) rewrites as
\[
\left(  \lambda_{1}+\lambda_{2}+\lambda_{3}\right)  x^{2}+\left(
-2\lambda_{2}-4\lambda_{3}\right)  x+\left(  \lambda_{2}+4\lambda_{3}\right)
=0.
\]
Since equal polynomials have equal coefficients, this is equivalent to the
following system of linear equations:%
\[
\left\{
\begin{array}
[c]{c}%
\lambda_{1}+\lambda_{2}+\lambda_{3}=0\\
-2\lambda_{2}-4\lambda_{3}=0\\
\lambda_{2}+4\lambda_{3}=0
\end{array}
\right.  ,
\]
whose only solution is $\left(  \lambda_{1},\lambda_{2},\lambda_{3}\right)
=\left(  0,0,0\right)  $ (you know how to check this) -- and thus the relation
must be trivial. So the polynomials $x^{2}$, $\left(  x-1\right)  ^{2}$ and
$\left(  x-2\right)  ^{2}$ are linearly independent.
\end{itemize}

\begin{exercise}
\label{exe.lincd.polysdeg3}\textbf{(a)} Are the four polynomials
$x^{3},\left(  x-1\right)  ^{3},\left(  x-2\right)  ^{3},\left(  x-3\right)
^{3}$ linearly independent?

\textbf{(b)} Is $1$ a linear combination of these four polynomials?
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.lincd.polysdeg3}.]\textbf{(a)} Yes.

\textit{Proof.} Let $ax^{3}+b\left(  x-1\right)  ^{3}+c\left(  x-2\right)
^{3}+d\left(  x-3\right)  ^{3}=0$ be any relation between these four
polynomials. We must show that this relation is trivial, i.e., that
$a=b=c=d=0$.

We have%
\begin{align*}
&  ax^{3}+b\underbrace{\left(  x-1\right)  ^{3}}_{=x^{3}-3x^{2}+3x-1}%
+c\underbrace{\left(  x-2\right)  ^{3}}_{=x^{3}-6x^{2}+12x-8}%
+d\underbrace{\left(  x-3\right)  ^{3}}_{=x^{3}-9x^{2}+27x-27}\\
&  =ax^{3}+b\left(  x^{3}-3x^{2}+3x-1\right)  +c\left(  x^{3}-6x^{2}%
+12x-8\right)  +d\left(  x^{3}-9x^{2}+27x-27\right) \\
&  =ax^{3}+bx^{3}-3bx^{2}+3bx-b+cx^{3}-6cx^{2}+12cx-8c+dx^{3}-9dx^{2}%
+27dx-27d\\
&  =\left(  a+b+c+d\right)  x^{3}+\left(  -3b-6c-9d\right)  x^{2}+\left(
3b+12c+27d\right)  x+\left(  -b-8c-27d\right)  .
\end{align*}
Thus, our relation $ax^{3}+b\left(  x-1\right)  ^{3}+c\left(  x-2\right)
^{3}+d\left(  x-3\right)  ^{3}=0$ rewrites as the following equality:
\[
\left(  a+b+c+d\right)  x^{3}+\left(  -3b-6c-9d\right)  x^{2}+\left(
3b+12c+27d\right)  x+\left(  -b-8c-27d\right)  =0.
\]
But a polynomial can only be $0$ if all its coefficients are $0$ (since a
polynomial is defined as a sequence of coefficients). Thus, the equality that
we have just showed entails that%
\begin{align*}
a+b+c+d  &  =0;\\
-3b-6c-9d  &  =0;\\
3b+12c+27d  &  =0;\\
-b-8c-27d  &  =0.
\end{align*}
This is a system of $4$ linear equations in $a,b,c,d$. Solving it (e.g., by
Gaussian elimination), we find that the only solution is $a=b=c=d=0$. Thus, we
conclude that $a=b=c=d=0$, which is exactly what we needed to show.

[\textit{Remark:} The claim generalizes: For any $n\in\mathbb{N}$ and any
$n+1$ distinct reals $a_{0},a_{1},\ldots,a_{n}$, the $n+1$ polynomials
$\left(  x-a_{0}\right)  ^{n},\left(  x-a_{1}\right)  ^{n},\ldots,\left(
x-a_{n}\right)  ^{n}$ are linearly independent. To prove this, we would need
some more advanced tools (such as the Vandermonde determinant), since the
system of linear equations would get larger and larger as $n$ grows.]

\textbf{(b)} Yes.

\textit{Proof.} We have%
\begin{equation}
\dfrac{1}{6}x^{3}+\dfrac{-1}{2}\left(  x-1\right)  ^{3}+\dfrac{1}{2}\left(
x-2\right)  ^{3}+\dfrac{-1}{6}\left(  x-3\right)  ^{3}=1.
\label{sol.lincd.polysdeg3.goal}%
\end{equation}


[\textit{Remark:} How did we find this relation? Well, we need to find four
numbers $a,b,c,d$ such that%
\[
ax^{3}+b\left(  x-1\right)  ^{3}+c\left(  x-2\right)  ^{3}+d\left(
x-3\right)  ^{3}=1.
\]
We can expand the left hand side of this equation (as we already did in the
proof of part \textbf{(a)}), thus rewriting the equation as%
\[
\left(  a+b+c+d\right)  x^{3}+\left(  -3b-6c-9d\right)  x^{2}+\left(
3b+12c+27d\right)  x+\left(  -b-8c-81d\right)  =1.
\]
But two polynomials are equal if and only if their respective coefficients are
equal (since a polynomial is defined as a sequence of coefficients). Thus, our
equation amounts to the following system of $4$ linear equations in $a,b,c,d$:%
\begin{align*}
a+b+c+d  &  =0;\\
-3b-6c-9d  &  =0;\\
3b+12c+27d  &  =0;\\
-b-8c-81d  &  =1.
\end{align*}
Now, Gaussian elimination shows that its solution is $a=\dfrac{1}{6}$,
$b=\dfrac{-1}{2}$, $c=\dfrac{1}{2}$ and $d=\dfrac{-1}{6}$. This leads exactly
to (\ref{sol.lincd.polysdeg3.goal}).]

\begin{fineprint}
[\textit{Another remark:} If you know the notion of factorials ($n!$), then
you can generalize (\ref{sol.lincd.polysdeg3.goal}): For any nonnegative
integer $n$, we have%
\[
\sum_{k=0}^{n}\dfrac{\left(  -1\right)  ^{k}}{k!\cdot\left(  n-k\right)
!}\left(  x-k\right)  ^{n}=1.
\]
Or, rewritten without the summation sign:%
\[
\dfrac{\left(  -1\right)  ^{0}}{0!\cdot\left(  n-0\right)  !}\left(
x-0\right)  ^{n}+\dfrac{\left(  -1\right)  ^{1}}{1!\cdot\left(  n-1\right)
!}\left(  x-1\right)  ^{n}+\dfrac{\left(  -1\right)  ^{2}}{2!\cdot\left(
n-2\right)  !}\left(  x-2\right)  ^{n}+\cdots+\dfrac{\left(  -1\right)  ^{n}%
}{n!\cdot\left(  n-n\right)  !}\left(  x-n\right)  ^{n}=1.
\]
Proving this for all $n$ is a different matter, however; this is often done in
courses on enumerative combinatorics\footnote{Combinatorialists usually
restate this equality in the form%
\[
\left(  -1\right)  ^{0}\dbinom{n}{0}\left(  x-0\right)  ^{n}+\left(
-1\right)  ^{1}\dbinom{n}{1}\left(  x-1\right)  ^{n}+\cdots+\left(  -1\right)
^{n}\dbinom{n}{n}\left(  x-n\right)  ^{n}=n!.
\]
It is not hard to derive it from the result in
\url{https://math.stackexchange.com/a/1943039/} .}.]
\end{fineprint}
\end{proof}

Similarly, we can define linear combinations and linear independence of
matrices: Just replace \textquotedblleft vectors in $\mathbb{R}^{n}%
$\textquotedblright\ by \textquotedblleft$n\times m$%
-matrices\textquotedblright\ in Definition \ref{def.linc} and Definition
\ref{def.lind}\footnote{Of course, we then have to interpret $0$ as the zero
matrix $0_{n\times m}$ rather than the zero vector $0_{n\times1}$.}. For
example, the matrix $\left(
\begin{array}
[c]{cc}%
1 & 1\\
1 & 1
\end{array}
\right)  $ is a linear combination of the matrices $\left(
\begin{array}
[c]{cc}%
1 & 1\\
1 & 0
\end{array}
\right)  $, $\left(
\begin{array}
[c]{cc}%
0 & 1\\
1 & 0
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{cc}%
0 & 1\\
1 & 1
\end{array}
\right)  $, since%
\[
\left(
\begin{array}
[c]{cc}%
1 & 1\\
1 & 1
\end{array}
\right)  =1\cdot\left(
\begin{array}
[c]{cc}%
1 & 1\\
1 & 0
\end{array}
\right)  +\left(  -1\right)  \cdot\left(
\begin{array}
[c]{cc}%
0 & 1\\
1 & 0
\end{array}
\right)  +1\cdot\left(
\begin{array}
[c]{cc}%
0 & 1\\
1 & 1
\end{array}
\right)  .
\]


\begin{exercise}
\label{exe.lincd.2x2matsNESW}Consider the four matrices%
\[
N=\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 0
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ E=\left(
\begin{array}
[c]{cc}%
0 & 1\\
0 & 1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ S=\left(
\begin{array}
[c]{cc}%
0 & 0\\
1 & 1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ W=\left(
\begin{array}
[c]{cc}%
1 & 0\\
1 & 0
\end{array}
\right)  .
\]
(The letter $E$ stands for \textquotedblleft east\textquotedblright, not for
the identity matrix, which some also call $E$.)

\textbf{(a)} Is the identity matrix $I_{2}$ a linear combination of $N,E,S,W$ ?

\textbf{(b)} Are $N,E,S,W$ linearly dependent?
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.lincd.2x2matsNESW}.]\textbf{(a)} No.

\textit{Proof.} Each of the four matrices $N,E,S,W$ has the property that the
sum of the two diagonal entries equals the sum of the two off-diagonal
entries\footnote{For example, for $E$, this holds because $0+1=1+0$.}. Thus,
every linear combination of $N,E,S,W$ has this property as well\footnote{Make
sure you understand why!}. But $I_{2}$ does not have this property.

\textbf{(b)} Yes. Indeed, $N+S=\left(
\begin{array}
[c]{cc}%
1 & 1\\
1 & 1
\end{array}
\right)  =E+W$; in other words, $1N+\left(  -1\right)  E+1S+\left(  -1\right)
W=0_{2\times2}$. This is a nontrivial relation between $N,E,S,W$.

[\textit{Remark:} These answers can be found without lucky inspiration: For
part \textbf{(a)}, you want to write $I_{2}$ in the form%
\[
I_{2}=aN+bE+cS+dW\ \ \ \ \ \ \ \ \ \ \text{for some }a,b,c,d\in\mathbb{R};
\]
this would entail%
\begin{align*}
\left(
\begin{array}
[c]{cc}%
1 & 0\\
0 & 1
\end{array}
\right)   &  =I_{2}=aN+bE+cS+dW\\
&  =a\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 0
\end{array}
\right)  +b\left(
\begin{array}
[c]{cc}%
0 & 1\\
0 & 1
\end{array}
\right)  +c\left(
\begin{array}
[c]{cc}%
0 & 0\\
1 & 1
\end{array}
\right)  +d\left(
\begin{array}
[c]{cc}%
1 & 0\\
1 & 0
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{cc}%
a\cdot1+b\cdot0+c\cdot0+d\cdot1 & a\cdot1+b\cdot1+c\cdot0+d\cdot0\\
a\cdot0+b\cdot0+c\cdot1+d\cdot1 & a\cdot0+b\cdot1+c\cdot1+d\cdot0
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
a+d & a+b\\
c+d & b+c
\end{array}
\right)  ;
\end{align*}
this would mean that the equations%
\[
1=a+d,\ \ \ \ \ \ \ \ \ \ 0=a+b,\ \ \ \ \ \ \ \ \ \ 0=c+d,\ \ \ \ \ \ \ \ \ \ 1=b+c
\]
hold (because two matrices are equal if and only if their respective entries
are equal); but this is a system of linear equations that has no solutions.
For part \textbf{(b)}, you are similarly trying to solve the equation
$0_{2\times2}=aN+bE+cS+dW$, but this time you are looking for a nontrivial solution.]
\end{proof}

\begin{thebibliography}{9999999999}                                                                                       %
\begin{comment}
\bibitem[lina]{lina}Darij Grinberg, \textit{Notes on linear algebra}, version
of 13 December 2016.\newline\url{https://github.com/darijgr/lina}
\end{comment}


\bibitem[lina]{lina}Darij Grinberg, \textit{Notes on linear algebra}, version
of 13 December 2016.\newline\url{https://github.com/darijgr/lina}

\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}