\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=Saturday, October 12, 2019 14:48:33}
%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{fns}{\begin{footnotesize}}{\end{footnotesize}}
\iffalse
\newenvironment{proof}[1][Proof]{\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}

due date: Wednesday 2019-10-16 at the beginning of class,

or before that by email or Blackboard

\textbf{Please solve 5 of the 6 exercises!}
\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}

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}

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}
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{exercise}
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}

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

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}
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{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[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}