\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=Tuesday, November 19, 2019 20:05:59}
%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): midterm training 2}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

\section{Determinants}

\begin{exercise}
\label{exe.19fla-mt2t.det1}Here is a $4\times4$-matrix filled with the numbers
$1,2,3,...,4^{2}$ by going from left to right along the first row, then
backwards along the second row, then forward again along the third, etc.:%
\[
\left(
\begin{array}
[c]{cccc}%
1 & 2 & 3 & 4\\
8 & 7 & 6 & 5\\
9 & 10 & 11 & 12\\
16 & 15 & 14 & 13
\end{array}
\right)  .
\]
Explain why the determinant of this matrix, but also the determinant of the
similarly constructed $n\times n$-matrix for every $n\geq3$, is $0$.
\end{exercise}

\begin{exercise}
\label{exe.19fla-mt2t.detP}Let $n$ be a positive integer. Let $x_{1}%
,x_{2},\ldots,x_{n}$ be $n$ reals, and let $y_{1},y_{2},\ldots,y_{n}$ be $n$
further reals. Let $P_{n}$ denote the $n\times n$-matrix%
\[
\left(  x_{i}y_{j}\right)  _{1\leq i\leq n,\ 1\leq j\leq n}=\left(
\begin{array}
[c]{cccc}%
x_{1}y_{1} & x_{1}y_{2} & \cdots & x_{1}y_{n}\\
x_{2}y_{1} & x_{2}y_{2} & \cdots & x_{2}y_{n}\\
\vdots & \vdots & \ddots & \vdots\\
x_{n}y_{1} & x_{n}y_{2} & \cdots & x_{n}y_{n}%
\end{array}
\right)  .
\]


\textbf{(a)} Find $\det\left(  P_{n}\right)  $ if $n=2$. (In this case,
$P_{n}=P_{2}=\left(
\begin{array}
[c]{cc}%
x_{1}y_{1} & x_{1}y_{2}\\
x_{2}y_{1} & x_{2}y_{2}%
\end{array}
\right)  $.)

\textbf{(b)} Find $\det\left(  P_{n}\right)  $ if $n=3$.

\textbf{(c)} Find $\det\left(  P_{n}\right)  $ if $n=4$.

[\textbf{Hint:} The answers are very simple, and can be obtained in a simple
way for all $n\geq2$ simultaneously.

Feel free to use simpler notations, such as renaming $x_{1},x_{2},x_{3}$ as
$x,y,z$ and renaming $y_{1},y_{2},y_{3}$ as $a,b,c$.]
\end{exercise}

\begin{noncompile}
This is from detnotes.
\end{noncompile}

\begin{exercise}
\label{exe.19fla-mt2t.detS}Let $n$ be a positive integer. Let $x_{1}%
,x_{2},\ldots,x_{n}$ be $n$ reals, and let $y_{1},y_{2},\ldots,y_{n}$ be $n$
further reals. Let $S_{n}$ denote the $n\times n$-matrix%
\[
\left(  x_{i}+y_{j}\right)  _{1\leq i\leq n,\ 1\leq j\leq n}=\left(
\begin{array}
[c]{cccc}%
x_{1}+y_{1} & x_{1}+y_{2} & \cdots & x_{1}+y_{n}\\
x_{2}+y_{1} & x_{2}+y_{2} & \cdots & x_{2}+y_{n}\\
\vdots & \vdots & \ddots & \vdots\\
x_{n}+y_{1} & x_{n}+y_{2} & \cdots & x_{n}+y_{n}%
\end{array}
\right)  .
\]


\textbf{(a)} Find $\det\left(  S_{n}\right)  $ if $n=3$.

\textbf{(b)} Find $\det\left(  S_{n}\right)  $ if $n=4$.

[\textbf{Hint:} There are very simple answers for all $n\geq3$. If you are
getting complicated expressions, you should expand them or use a different approach.]
\end{exercise}

\begin{noncompile}
This is from detnotes.
\end{noncompile}

\begin{exercise}
\label{exe.19fla-mt2t.detA}For each $n\in\mathbb{N}$, let $A_{n}$ be the
$n\times n$-matrix%
\[
\left(
\begin{array}
[c]{ccccccc}%
1 & 1 & 0 & \cdots & 0 & 0 & 0\\
-1 & 1 & 1 & \cdots & 0 & 0 & 0\\
0 & -1 & 1 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & 0 & \cdots & 1 & 1 & 0\\
0 & 0 & 0 & \cdots & -1 & 1 & 1\\
0 & 0 & 0 & \cdots & 0 & -1 & 1
\end{array}
\right)  .
\]
(This is the $n\times n$-matrix whose entries on the diagonal and just above
it are $1$, while its entries just below the diagonal are $-1$, and all
remaining entries are $0$. No exceptional entries hiding in the corners this time!)

\textbf{(a)} Find $\det\left(  A_{1}\right)  $. (Note that $A_{1}=\left(
\begin{array}
[c]{c}%
1
\end{array}
\right)  $.)

\textbf{(b)} Find $\det\left(  A_{2}\right)  $. (Note that $A_{2}=\left(
\begin{array}
[c]{cc}%
1 & 1\\
-1 & 1
\end{array}
\right)  $.)

\textbf{(c)} Find $\det\left(  A_{3}\right)  $. (Note that $A_{3}=\left(
\begin{array}
[c]{ccc}%
1 & 1 & 0\\
-1 & 1 & 1\\
0 & -1 & 1
\end{array}
\right)  $.)

\textbf{(d)} For a general integer $n\geq2$, find an expression for
$\det\left(  A_{n}\right)  $ in terms of $\det\left(  A_{n-1}\right)  $ and
$\det\left(  A_{n-2}\right)  $.

\textbf{(e)} Find a formula for $\det\left(  A_{n}\right)  $ in terms of
things we have seen in class.

[\textbf{Hint:} In \textbf{(d)}, use Laplace expansion.]
\end{exercise}

\begin{noncompile}
This is from detnotes.
\end{noncompile}

\section{Eigenvalues and eigenvectors}

\begin{exercise}
\label{exe.19fla-mt2t.ev1}\textbf{(a)} Find the eigenvalues of the matrix
$A:=\left(
\begin{array}
[c]{ccc}%
0 & 0 & 3\\
0 & 2 & -2\\
1 & -1 & 0
\end{array}
\right)  $.

\textbf{(b)} Diagonalize this matrix (i.e., find a diagonalization of $A$).

[\textbf{Hint:} This is one of those rare cases where the roots of $\chi
_{A}\left(  t\right)  $ can be described nicely. Actually, they are rational
numbers. See \href{https://brilliant.org/wiki/rational-root-theorem/}{the
rational root theorem} for how to find the rational roots of a polynomial with
rational coefficients.]
\end{exercise}

\begin{noncompile}
The EVs are $1,-2,3$ and this is a particular case of
\texttt{\href{http://mathoverflow.net/questions/185530}{http://mathoverflow.net/questions/185530}%
} .

$\left(
\begin{array}
[c]{ccc}%
0 & 0 & 3\\
0 & 2 & -2\\
1 & -1 & 0
\end{array}
\right)  =\allowbreak\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
-\dfrac{1}{3} & \dfrac{2}{3} & -2\\
-\dfrac{2}{3} & \dfrac{1}{3} & 1
\end{array}
\right)  \left(
\begin{array}
[c]{ccc}%
-2 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 3
\end{array}
\right)  \left(
\begin{array}
[c]{ccc}%
\dfrac{2}{5} & -\dfrac{1}{5} & -\dfrac{4}{5}\\
\dfrac{1}{2} & \dfrac{1}{2} & \dfrac{1}{2}\\
\dfrac{1}{10} & -\dfrac{3}{10} & \dfrac{3}{10}%
\end{array}
\right)  $
\end{noncompile}

\begin{exercise}
\label{exe.19fla-mt2t.ev2}\textbf{(a)} Find the eigenvalues and at least two
linearly independent eigenvectors of the matrix $\left(
\begin{array}
[c]{ccc}%
1 & 1 & 0\\
-1 & 2 & 1\\
0 & 1 & 1
\end{array}
\right)  $.

\textbf{(b)} Does this matrix have a diagonalization?
\end{exercise}

\begin{noncompile}
The eigenvalues are $1,1,2$, but there is only one eigenvector for eigenvalue
$1$. Thus, no diagonalization.
\end{noncompile}

\begin{exercise}
\label{exe.19fla-mt2t.ev3}Let $\left(  h_{0},h_{1},h_{2},\ldots\right)  $ be
the sequence of integers defined by%
\[
h_{0}=0,\ \ \ \ \ \ \ \ \ \ h_{1}=1,\ \ \ \ \ \ \ \ \ \ h_{n}=h_{n-1}%
+6h_{n-2}\ \ \ \ \ \ \ \ \ \ \text{for all }n\geq2.
\]


(Thus, $h_{2}=h_{1}+6h_{0}=1$ and $h_{3}=h_{2}+6h_{1}=7$.)

Find an explicit formula for $h_{m}$ for all $m\geq0$.
\end{exercise}

\begin{noncompile}
$h_{m}=\dfrac{3^{m}-\left(  -2\right)  ^{m}}{5}$.
\end{noncompile}

\section{Complex numbers}

As usual, we let $i$ denote the imaginary unit in this section. Thus,
$i^{2}=-1$.

To \textquotedblleft find\textquotedblright\ a complex number always means to
write it as $a+bi$ with $a$ and $b$ being real. You don't have to write out
$a$ and $b$ in decimal (e.g., you don't have to expand $2^{10}$ as $1024$).

\begin{exercise}
\label{exe.19fla-mt2t.CC1}\textbf{(a)} Find $\left(  1+i\right)  ^{2}$.

\textbf{(b)} Find $\left(  1+i\right)  ^{3}$.

\textbf{(c)} Find $\left(  1+i\right)  ^{4}$.

\textbf{(d)} Find $\left(  1+i\right)  ^{8}$.

\textbf{(e)} Find $\left(  1+i\right)  ^{1000}$.
\end{exercise}

\begin{exercise}
\label{exe.19fla-mt2t.CC2}Let $\omega=\dfrac{1+\sqrt{3}i}{2}$.

\textbf{(a)} Find $\omega^{2}$.

\textbf{(b)} Find $\omega^{3}$.

\textbf{(c)} Find $\omega^{6}$.

\textbf{(d)} Draw the first $6$ powers of $\omega$ on the Argand diagram.

\textbf{(e)} Find $\omega^{1000}$.
\end{exercise}

\begin{exercise}
\label{exe.19fla-mt2t.CCabsmul}Prove that $\left\vert zw\right\vert
=\left\vert z\right\vert \cdot\left\vert w\right\vert $ for any two complex
numbers $z$ and $w$.
\end{exercise}

\newpage

\section{Solutions}

The following solutions are a bit rough at some places, but they have enough
detail to get full scores.

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.

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt2t.det1}.]Let $A$ be the $4\times
4$-matrix shown in the exercise. Our first goal is to show that $\det A=0$.
Indeed, as direct consequences of the construction of $A$, we have%
\[
\operatorname{col}_{2}A-\operatorname{col}_{1}A=\left(
\begin{array}
[c]{c}%
1\\
-1\\
1\\
-1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ \operatorname{col}%
_{3}A-\operatorname{col}_{2}A=\left(
\begin{array}
[c]{c}%
1\\
-1\\
1\\
-1
\end{array}
\right)  .
\]
Comparing these two equalities, we obtain $\operatorname{col}_{2}%
A-\operatorname{col}_{1}A=\operatorname{col}_{3}A-\operatorname{col}_{2}A$.
This can be rewritten as
\[
\left(  -1\right)  \operatorname{col}_{1}A+2\operatorname{col}_{2}A+\left(
-1\right)  \operatorname{col}_{3}A=0.
\]
This is a nontrivial relation between the columns of $A$. Thus, the columns of
$A$ are linearly dependent. By the Non-Inverse Matrix Theorem\footnote{more
precisely: by the implication \textbf{(b')} $\Longrightarrow$ \textbf{(l')} in
Theorem 2.1.4 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-04.pdf}{the class
notes from 2019-11-04}}, this entails that $\det A=0$.

Thus, we have shown that the determinant of the $4\times4$-matrix shown in the
exercise is $0$. The same argument yields the same statement for the similarly
constructed $n\times n$-matrix for every $n\geq3$.
\end{proof}

\begin{proof}
[First solution to Exercise \ref{exe.19fla-mt2t.detP}.]We claim that
$\det\left(  P_{n}\right)  =0$ for each $n\geq2$.

Before we prove this claim, let us notice that it does not hold for $n=1$
(because $\det\left(  P_{1}\right)  =\det\left(
\begin{array}
[c]{c}%
x_{1}y_{1}%
\end{array}
\right)  =x_{1}y_{1}$); nor does it hold for $n=0$ (since the $0\times
0$-matrix has determinant $1$, by definition). Thus, the proof of this claim
must necessarily use the condition $n\geq2$.

So let us prove our claim. Let $n$ be an integer such that $n\geq2$. We must
show that $\det\left(  P_{n}\right)  =0$. We shall use the following two
properties of determinants:

\begin{statement}
\textit{Property 1:} If an $n\times n$-matrix $A$ has two equal rows, then
$\det A=0$. (This is Theorem 1.3.3 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-23.pdf}{the class
notes from 2019-10-23}.)
\end{statement}

\begin{statement}
\textit{Property 2:} If we scale a row of an $n\times n$-matrix by a number
$\lambda$, then $\det A$ gets multiplied by $\lambda$. (This is Theorem 1.3.5
in \href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-23.pdf}{the class
notes from 2019-10-23}.)
\end{statement}

Now, let $Q_{n}$ be the $n\times n$-matrix%
\[
\left(
\begin{array}
[c]{cccc}%
y_{1} & y_{2} & \cdots & y_{n}\\
y_{1} & y_{2} & \cdots & y_{n}\\
x_{3}y_{1} & x_{3}y_{2} & \cdots & x_{3}y_{n}\\
x_{4}y_{1} & x_{4}y_{2} & \cdots & x_{4}y_{n}\\
\vdots & \vdots & \ddots & \vdots\\
x_{n}y_{1} & x_{n}y_{2} & \cdots & x_{n}y_{n}%
\end{array}
\right)  .
\]
(This is the matrix $P_{n}$, except that its first two rows have been replaced
by $\left(  y_{1},y_{2},\ldots,y_{n}\right)  $.)

The matrix $Q_{n}$ has two equal rows (namely, its first two rows are
equal)\footnote{Here we are using $n\geq2$.}. Thus, Property 1 shows that
$\det\left(  Q_{n}\right)  =0$. But the matrix $P_{n}$ is obtained from
$Q_{n}$ by scaling the first row by $x_{1}$ and scaling the second row by
$x_{2}$. Thus, Property 2 (applied twice) yields that
\[
\det\left(  P_{n}\right)  =x_{1}\cdot x_{2}\cdot\underbrace{\det\left(
Q_{n}\right)  }_{=0}=0.
\]
Thus, our claim is proved. This solves the exercise.
\end{proof}

\begin{proof}
[Second solution to Exercise \ref{exe.19fla-mt2t.detP}.]We claim that
$\det\left(  P_{n}\right)  =0$ for each $n\geq2$.

This time, we shall derive it from the following two properties of determinants:

\begin{statement}
\textit{Property 3:} We have $\det\left(  XY\right)  =\det X\cdot\det Y$ for
any two $n\times n$-matrices $X$ and $Y$. (This is Theorem 1.5.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{the class
notes from 2019-10-30}.)
\end{statement}

\begin{statement}
\textit{Property 4:} If an $n\times n$-matrix $A$ has a zero row (i.e., a row
full of zeroes), then $\det A=0$. (This is Corollary 1.2.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{the class
notes from 2019-10-30}.)
\end{statement}

Now, let $n$ be an integer such that $n\geq2$. Let $X$ be the $n\times
n$-matrix%
\[
\left(
\begin{array}
[c]{cccc}%
x_{1} & 0 & \cdots & 0\\
x_{2} & 0 & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
x_{n} & 0 & \cdots & 0
\end{array}
\right)  .
\]
(The first column of this matrix is $\left(  x_{1},x_{2},\ldots,x_{n}\right)
^{T}$, while all remaining columns are zero.)

Also, let $Y$ be the $n\times n$-matrix
\[
\left(
\begin{array}
[c]{cccc}%
y_{1} & y_{2} & \cdots & y_{n}\\
0 & 0 & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & 0
\end{array}
\right)  .
\]
(The first row of this matrix is $\left(  y_{1},y_{2},\ldots,y_{n}\right)  $,
while all remaining rows are zero.)

The matrix $Y$ has a zero row (for example, its second row)\footnote{Here we
are using $n\geq2$.}. Thus, Property 4 yields $\det Y=0$.

But it is easy to see (just compute $XY$) that $P_{n}=XY$. Thus,%
\begin{align*}
\det\left(  P_{n}\right)   &  =\det\left(  XY\right)  =\det X\cdot
\underbrace{\det Y}_{=0}\ \ \ \ \ \ \ \ \ \ \left(  \text{by Property
3}\right) \\
&  =0.
\end{align*}
Thus, our exercise is solved again.
\end{proof}

\begin{proof}
[First solution to Exercise \ref{exe.19fla-mt2t.detS}.]We claim that
$\det\left(  S_{n}\right)  =0$ for each $n\geq3$.

Before we prove this claim, let us notice that it does not hold for $n=2$
(because $\det\left(  S_{2}\right)  =\det\left(
\begin{array}
[c]{cc}%
x_{1}+y_{1} & x_{1}+y_{2}\\
x_{2}+y_{1} & x_{2}+y_{2}%
\end{array}
\right)  =-\left(  x_{1}-x_{2}\right)  \left(  y_{1}-y_{2}\right)  $); nor
does it hold for $n=1$ (because $\det\left(  S_{1}\right)  =\det\left(
\begin{array}
[c]{c}%
x_{1}+y_{1}%
\end{array}
\right)  =x_{1}+y_{1}$); nor does it hold for $n=0$ (since the $0\times
0$-matrix has determinant $1$, by definition). Thus, the proof of this claim
must necessarily use the condition $n\geq3$.

So let us prove our claim. Let $n$ be an integer such that $n\geq3$. We must
show that $\det\left(  S_{n}\right)  =0$. We shall use the following two
properties of determinants:

\begin{statement}
\textit{Property 1:} If an $n\times n$-matrix $A$ has two equal rows, then
$\det A=0$. (This is Theorem 1.3.3 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-23.pdf}{the class
notes from 2019-10-23}.)
\end{statement}

\begin{statement}
\textit{Property 2:} If we scale a row of an $n\times n$-matrix by a number
$\lambda$, then $\det A$ gets multiplied by $\lambda$. (This is Theorem 1.3.5
in \href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-23.pdf}{the class
notes from 2019-10-23}.)
\end{statement}

We shall also use the following property of determinants:

\begin{statement}
\textit{Property 5:} Let $A$ be an $n\times n$-matrix, and let $p$ and $q$ be
two distinct elements of $\left[  n\right]  $. If we add $\lambda
\cdot\operatorname{row}_{p}A$ to the $q$-th row of $A$, then $\det A$ does not
change. (This is Corollary 1.2.5 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{the class
notes from 2019-10-30}.)
\end{statement}

More precisely, we shall use the following particular case of Property 5:

\begin{statement}
\textit{Property 6:} Let $A$ be an $n\times n$-matrix, and let $p$ and $q$ be
two distinct elements of $\left[  n\right]  $. If we subtract
$\operatorname{row}_{p}A$ from the $q$-th row of $A$, then $\det A$ does not change.
\end{statement}

Property 6 follows from Property 5 (applied to $\lambda=-1$), because adding
$\left(  -1\right)  \cdot\operatorname{row}_{p}A$ to the $q$-th row of $A$ is
the same as subtracting $\operatorname{row}_{p}A$ from the $q$-th row of $A$.

Now, the definition of $S_{n}$ shows that%
\begin{align*}
\det\left(  S_{n}\right)   &  =\det\left(
\begin{array}
[c]{cccc}%
x_{1}+y_{1} & x_{1}+y_{2} & \cdots & x_{1}+y_{n}\\
x_{2}+y_{1} & x_{2}+y_{2} & \cdots & x_{2}+y_{n}\\
\vdots & \vdots & \ddots & \vdots\\
x_{n}+y_{1} & x_{n}+y_{2} & \cdots & x_{n}+y_{n}%
\end{array}
\right) \\
&  =\det\left(
\begin{array}
[c]{cccc}%
x_{1}+y_{1} & x_{1}+y_{2} & \cdots & x_{1}+y_{n}\\
x_{2}+y_{1} & x_{2}+y_{2} & \cdots & x_{2}+y_{n}\\
x_{3}+y_{1} & x_{3}+y_{2} & \cdots & x_{3}+y_{n}\\
x_{4}+y_{1} & x_{4}+y_{2} & \cdots & x_{4}+y_{n}\\
\vdots & \vdots & \ddots & \vdots\\
x_{n}+y_{1} & x_{n}+y_{2} & \cdots & x_{n}+y_{n}%
\end{array}
\right) \\
&  =\det\left(
\begin{array}
[c]{cccc}%
x_{1}+y_{1} & x_{1}+y_{2} & \cdots & x_{1}+y_{n}\\
x_{2}-x_{1} & x_{2}-x_{1} & \cdots & x_{2}-x_{1}\\
x_{3}+y_{1} & x_{3}+y_{2} & \cdots & x_{3}+y_{n}\\
x_{4}+y_{1} & x_{4}+y_{2} & \cdots & x_{4}+y_{n}\\
\vdots & \vdots & \ddots & \vdots\\
x_{n}+y_{1} & x_{n}+y_{2} & \cdots & x_{n}+y_{n}%
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have subtracted the }1\text{-st row of our matrix}\\
\text{from the }2\text{-nd row; this did not change the determinant}\\
\text{(by Property 6)}%
\end{array}
\right) \\
&  =\det\left(
\begin{array}
[c]{cccc}%
x_{1}+y_{1} & x_{1}+y_{2} & \cdots & x_{1}+y_{n}\\
x_{2}-x_{1} & x_{2}-x_{1} & \cdots & x_{2}-x_{1}\\
x_{3}-x_{1} & x_{3}-x_{1} & \cdots & x_{3}-x_{1}\\
x_{4}+y_{1} & x_{4}+y_{2} & \cdots & x_{4}+y_{n}\\
\vdots & \vdots & \ddots & \vdots\\
x_{n}+y_{1} & x_{n}+y_{2} & \cdots & x_{n}+y_{n}%
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have subtracted the }1\text{-st row of our matrix}\\
\text{from the }3\text{-rd row; this did not change the determinant}\\
\text{(by Property 6)}%
\end{array}
\right) \\
&  =\left(  x_{2}-x_{1}\right)  \det\left(
\begin{array}
[c]{cccc}%
x_{1}+y_{1} & x_{1}+y_{2} & \cdots & x_{1}+y_{n}\\
1 & 1 & \cdots & 1\\
x_{3}-x_{1} & x_{3}-x_{1} & \cdots & x_{3}-x_{1}\\
x_{4}+y_{1} & x_{4}+y_{2} & \cdots & x_{4}+y_{n}\\
\vdots & \vdots & \ddots & \vdots\\
x_{n}+y_{1} & x_{n}+y_{2} & \cdots & x_{n}+y_{n}%
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Property 2, because the matrix before the}\\
\text{equality sign can be obtained from the matrix after}\\
\text{the equality sign by scaling the }2\text{-nd row by }x_{2}-x_{1}%
\end{array}
\right) \\
&  =\left(  x_{2}-x_{1}\right)  \left(  x_{3}-x_{1}\right)  \underbrace{\det
\left(
\begin{array}
[c]{cccc}%
x_{1}+y_{1} & x_{1}+y_{2} & \cdots & x_{1}+y_{n}\\
1 & 1 & \cdots & 1\\
1 & 1 & \cdots & 1\\
x_{4}+y_{1} & x_{4}+y_{2} & \cdots & x_{4}+y_{n}\\
\vdots & \vdots & \ddots & \vdots\\
x_{n}+y_{1} & x_{n}+y_{2} & \cdots & x_{n}+y_{n}%
\end{array}
\right)  }_{\substack{=0\\\text{(by Property 1, because this matrix has two
equal rows}\\\text{(namely, its }2\text{-nd and }3\text{-rd rows are equal))}%
}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Property 2, because the matrix before the}\\
\text{equality sign can be obtained from the matrix after}\\
\text{the equality sign by scaling the }3\text{-rd row by }x_{3}-x_{1}%
\end{array}
\right) \\
&  =0.
\end{align*}
This proves our claim, thus solving the exercise.
\end{proof}

\begin{proof}
[Second solution to Exercise \ref{exe.19fla-mt2t.detS}.]We claim that
$\det\left(  S_{n}\right)  =0$ for each $n\geq3$.

This time, we shall derive it from the following two properties of determinants:

\begin{statement}
\textit{Property 3:} We have $\det\left(  XY\right)  =\det X\cdot\det Y$ for
any two $n\times n$-matrices $X$ and $Y$. (This is Theorem 1.5.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{the class
notes from 2019-10-30}.)
\end{statement}

\begin{statement}
\textit{Property 4:} If an $n\times n$-matrix $A$ has a zero row (i.e., a row
full of zeroes), then $\det A=0$. (This is Corollary 1.2.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{the class
notes from 2019-10-30}.)
\end{statement}

Now, let $n$ be an integer such that $n\geq3$. Let $X$ be the $n\times
n$-matrix%
\[
\left(
\begin{array}
[c]{ccccc}%
x_{1} & 1 & 0 & \cdots & 0\\
x_{2} & 1 & 0 & \cdots & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
x_{n} & 1 & 0 & \cdots & 0
\end{array}
\right)  .
\]
(The first column of this matrix is $\left(  x_{1},x_{2},\ldots,x_{n}\right)
^{T}$; the second column is $\left(  1,1,\ldots,1\right)  ^{T}$; all remaining
columns are zero.)

Also, let $Y$ be the $n\times n$-matrix
\[
\left(
\begin{array}
[c]{cccc}%
1 & 1 & \cdots & 1\\
y_{1} & y_{2} & \cdots & y_{n}\\
0 & 0 & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & 0
\end{array}
\right)  .
\]
(The first row of this matrix is $\left(  y_{1},y_{2},\ldots,y_{n}\right)  $;
the second row is $\left(  1,1,\ldots,1\right)  $; all remaining rows are zero.)

The matrix $Y$ has a zero row (for example, its third row)\footnote{Here we
are using $n\geq3$.}. Thus, Property 4 yields $\det Y=0$.

But it is easy to see that $S_{n}=XY$ (indeed, just compute $XY$ and notice
that $x_{i}\cdot1+1\cdot y_{j}=x_{i}+y_{j}$). Thus,%
\begin{align*}
\det\left(  S_{n}\right)   &  =\det\left(  XY\right)  =\det X\cdot
\underbrace{\det Y}_{=0}\ \ \ \ \ \ \ \ \ \ \left(  \text{by Property
3}\right) \\
&  =0.
\end{align*}
Thus, our exercise is solved again.
\end{proof}

\begin{proof}
[Solution to Exercises \ref{exe.19fla-mt2t.detA}.]\textbf{(a)} We have
$A_{1}=\left(
\begin{array}
[c]{c}%
1
\end{array}
\right)  $ and thus $\det\left(  A_{1}\right)  =\det\left(
\begin{array}
[c]{c}%
1
\end{array}
\right)  =1$.

\textbf{(b)} We have $A_{2}=\left(
\begin{array}
[c]{cc}%
1 & 1\\
-1 & 1
\end{array}
\right)  $ and thus $\det\left(  A_{2}\right)  =\det\left(
\begin{array}
[c]{cc}%
1 & 1\\
-1 & 1
\end{array}
\right)  =2$.

\textbf{(c)} We have $A_{3}=\left(
\begin{array}
[c]{ccc}%
1 & 1 & 0\\
-1 & 1 & 1\\
0 & -1 & 1
\end{array}
\right)  $ and thus $\det\left(  A_{3}\right)  =\det\left(
\begin{array}
[c]{ccc}%
1 & 1 & 0\\
-1 & 1 & 1\\
0 & -1 & 1
\end{array}
\right)  =3$.

\textbf{(d)} Let $n$ be an integer such that $n\geq2$.

We have%
\[
A_{n}=\left(
\begin{array}
[c]{ccccccc}%
1 & 1 & 0 & \cdots & 0 & 0 & 0\\
-1 & 1 & 1 & \cdots & 0 & 0 & 0\\
0 & -1 & 1 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & 0 & \cdots & 1 & 1 & 0\\
0 & 0 & 0 & \cdots & -1 & 1 & 1\\
0 & 0 & 0 & \cdots & 0 & -1 & 1
\end{array}
\right)  _{n\times n}.
\]
Here, the subscript \textquotedblleft$n\times n$\textquotedblright\ tells us
that the matrix you are seeing is understood to be an $n\times n$-matrix.
(Similar notations will be used further below.)

The $1$-st row of the matrix $A_{n}$ has only two nonzero entries: the $1$ in
position $1$, and the $1$ in position $2$. Hence, Laplace expansion along the
$1$-st row (see Theorem 1.7.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{the class
notes from 2019-10-30}) yields%
\begin{align*}
\det\left(  A_{n}\right)   &  =1\cdot\det\underbrace{\left(
\begin{array}
[c]{cccccc}%
1 & 1 & \cdots & 0 & 0 & 0\\
-1 & 1 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & \cdots & 1 & 1 & 0\\
0 & 0 & \cdots & -1 & 1 & 1\\
0 & 0 & \cdots & 0 & -1 & 1
\end{array}
\right)  _{\left(  n-1\right)  \times\left(  n-1\right)  }}_{=A_{n-1}}\\
&  \ \ \ \ \ \ \ \ \ \ -1\cdot\det\left(
\begin{array}
[c]{cccccc}%
-1 & 1 & \cdots & 0 & 0 & 0\\
0 & 1 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & \cdots & 1 & 1 & 0\\
0 & 0 & \cdots & -1 & 1 & 1\\
0 & 0 & \cdots & 0 & -1 & 1
\end{array}
\right)  _{\left(  n-1\right)  \times\left(  n-1\right)  }\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \text{several addends that equal }0\text{ and
thus can be ignored}\right) \\
&  =\det\left(  A_{n-1}\right)  -\det\left(
\begin{array}
[c]{cccccc}%
-1 & 1 & \cdots & 0 & 0 & 0\\
0 & 1 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & \cdots & 1 & 1 & 0\\
0 & 0 & \cdots & -1 & 1 & 1\\
0 & 0 & \cdots & 0 & -1 & 1
\end{array}
\right)  _{\left(  n-1\right)  \times\left(  n-1\right)  }.
\end{align*}
Let us denote the second matrix on the right hand side of this
equality\footnote{i.e., the matrix $\left(
\begin{array}
[c]{cccccc}%
-1 & 1 & \cdots & 0 & 0 & 0\\
0 & 1 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & \cdots & 1 & 1 & 0\\
0 & 0 & \cdots & -1 & 1 & 1\\
0 & 0 & \cdots & 0 & -1 & 1
\end{array}
\right)  _{\left(  n-1\right)  \times\left(  n-1\right)  }$} by $B_{n-1}$. The
$1$-st column of this matrix $B_{n-1}$ has only one nonzero entry, namely the
$-1$ in position $1$. Hence, Laplace expansion along the $1$-st column (see
Theorem 1.2.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-04.pdf}{the class
notes from 2019-11-04}) yields%
\begin{align*}
\det\left(  B_{n-1}\right)   &  =\left(  -1\right)  \cdot\det
\underbrace{\left(
\begin{array}
[c]{ccccc}%
1 & \cdots & 0 & 0 & 0\\
\vdots & \ddots & \vdots & \vdots & \vdots\\
0 & \cdots & 1 & 1 & 0\\
0 & \cdots & -1 & 1 & 1\\
0 & \cdots & 0 & -1 & 1
\end{array}
\right)  _{\left(  n-2\right)  \times\left(  n-2\right)  }}_{=A_{n-2}}=\left(
-1\right)  \cdot\det\left(  A_{n-2}\right) \\
&  =-\det\left(  A_{n-2}\right)  .
\end{align*}
Thus, our above computation becomes%
\begin{align*}
\det\left(  A_{n}\right)   &  =\det\left(  A_{n-1}\right)  -\det
\underbrace{\left(
\begin{array}
[c]{cccccc}%
-1 & 1 & \cdots & 0 & 0 & 0\\
0 & 1 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & \cdots & 1 & 1 & 0\\
0 & 0 & \cdots & -1 & 1 & 1\\
0 & 0 & \cdots & 0 & -1 & 1
\end{array}
\right)  _{\left(  n-1\right)  \times\left(  n-1\right)  }}_{=B_{n-1}}\\
&  =\det\left(  A_{n-1}\right)  -\underbrace{\det\left(  B_{n-1}\right)
}_{=-\det\left(  A_{n-2}\right)  }=\det\left(  A_{n-1}\right)  -\left(
-\det\left(  A_{n-2}\right)  \right) \\
&  =\det\left(  A_{n-1}\right)  +\det\left(  A_{n-2}\right)  .
\end{align*}
This solves part \textbf{(d)} of the exercise.

\textbf{(e)} Recall \href{https://en.wikipedia.org/wiki/Fibonacci_number}{the
Fibonacci numbers} $f_{0},f_{1},f_{2},\ldots$ defined in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-06.pdf}{the class
notes from 2019-11-06}. We claim that%
\[
\det\left(  A_{n}\right)  =f_{n+1}\ \ \ \ \ \ \ \ \ \ \text{for each }n\geq0.
\]
In other words, we claim that the sequence $\left(  \det\left(  A_{0}\right)
,\det\left(  A_{1}\right)  ,\det\left(  A_{2}\right)  ,\ldots\right)  $ is
identical to the sequence $\left(  f_{1},f_{2},f_{3},\ldots\right)  $.

To see why this is true, all we need to show is that

\begin{itemize}
\item both of these sequences begin with the entries $1$ and $1$ (that is, we
have $\det\left(  A_{0}\right)  =1$ and $\det\left(  A_{1}\right)  =1$ and
$f_{1}=1$ and $f_{2}=1$), and

\item both of these sequences are constructed by the same rule (that is, we
have $\det\left(  A_{n}\right)  =\det\left(  A_{n-1}\right)  +\det\left(
A_{n-2}\right)  $ and $f_{n+1}=f_{n}+f_{n-1}$ for each $n\geq2$).
\end{itemize}

\noindent But this is clear: The equalities $\det\left(  A_{0}\right)  =1$ and
$\det\left(  A_{1}\right)  =1$ and $f_{1}=1$ and $f_{2}=1$ can be verified
directly\footnote{Keep in mind that the $0\times0$-matrix has determinant $1$
(by definition); this is why $\det\left(  A_{0}\right)  =1$.}. The equality
$\det\left(  A_{n}\right)  =\det\left(  A_{n-1}\right)  +\det\left(
A_{n-2}\right)  $ is our answer to part \textbf{(d)} of this exercise. The
equality $f_{n+1}=f_{n}+f_{n-1}$ follows from the definition of the Fibonacci numbers.

Thus, our claim is proved, and part \textbf{(e)} of the exercise is solved.

[\textit{Remark:} An $n\times n$-matrix whose nonzero entries are limited to
the diagonal and the cells just above and just below it is called a
\textit{\href{https://en.wikipedia.org/wiki/Tridiagonal_matrix}{\textit{tridiagonal
matrix}}}. There is
\href{https://en.wikipedia.org/wiki/Tridiagonal_matrix#Determinant}{a
recursive formula} -- similarly to the answer we obtained in part \textbf{(d)}
of this exercise -- for the determinant of an arbitrary tridiagonal matrix.
See \cite[\S 6.13]{detnotes} for a detailed proof of this formula. (Note that
our claim that $\det\left(  A_{n}\right)  =f_{n+1}$ for each $n\geq0$ appears
in \cite[Exercise 6.27]{detnotes}.)]
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt2t.ev1}.]\textbf{(a)} The
characteristic polynomial $\chi_{A}\left(  t\right)  $ of $A$ is%
\[
\chi_{A}\left(  t\right)  =\det\left(  A-tI_{3}\right)  =\det\left(
\begin{array}
[c]{ccc}%
0-t & 0 & 3\\
0 & 2-t & -2\\
1 & -1 & 0-t
\end{array}
\right)  =-\left(  t+2\right)  \left(  t-1\right)  \left(  t-3\right)  .
\]


\begin{fineprint}
(Obviously, checking the equality $\det\left(
\begin{array}
[c]{ccc}%
0-t & 0 & 3\\
0 & 2-t & -2\\
1 & -1 & 0-t
\end{array}
\right)  =-\left(  t+2\right)  \left(  t-1\right)  \left(  t-3\right)  $ is
straightforward, but how would you find it? I'm afraid there is no better way
than to expand $\det\left(
\begin{array}
[c]{ccc}%
0-t & 0 & 3\\
0 & 2-t & -2\\
1 & -1 & 0-t
\end{array}
\right)  $ as $-t^{3}+2t^{2}+5t-6$, and then to search for rational roots
using \href{https://en.wikipedia.org/wiki/Rational_root_theorem}{the rational
root theorem}.)
\end{fineprint}

Recall that the eigenvalues of $A$ are the roots of $\chi_{A}\left(  t\right)
$ (by Proposition 2.1.7 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-04.pdf}{the class
notes from 2019-11-04}). But the roots of $\chi_{A}\left(  t\right)  $ are
$-2,1,3$ (since $\chi_{A}\left(  t\right)  =-\left(  t+2\right)  \left(
t-1\right)  \left(  t-3\right)  $). Hence, the eigenvalues of $A$ are $-2,1,3$.

\textbf{(b)} We have just seen that the eigenvalues of $A$ are $-2,1,3$.
Denote these eigenvalues by $\lambda_{1},\lambda_{2},\lambda_{3}$,
respectively. Let us find eigenvectors for them:

\begin{itemize}
\item The $\lambda_{1}$-eigenvectors (i.e., the $\left(  -2\right)
$-eigenvectors) of $A$ are the nonzero vectors $v\in\mathbb{R}^{3}$ satisfying
$Av=\left(  -2\right)  v$. In other words, they are the nonzero vectors
$\left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  \in\mathbb{R}^{3}$ such that $A\left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  =\left(  -2\right)  \left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  $. This is a system of $3$ linear equations in the unknowns $x,y,z$;
solving it by Gaussian elimination, we obtain $\left\{
\begin{array}
[c]{c}%
x=-\dfrac{3}{2}z\\
y=\dfrac{1}{2}z
\end{array}
\right.  $ (where $z$ is a free variable). Thus, they are the nonzero scalar
multiples of the vector $\left(
\begin{array}
[c]{c}%
-\dfrac{3}{2}\\
\dfrac{1}{2}\\
1
\end{array}
\right)  $. For convenience, let us scale this vector by $2$, so it becomes
$\left(
\begin{array}
[c]{c}%
-3\\
1\\
2
\end{array}
\right)  $.

\item Likewise, the $\lambda_{2}$-eigenvectors (i.e., the $1$-eigenvectors) of
$A$ are the nonzero scalar multiples of the vector $\left(
\begin{array}
[c]{c}%
3\\
2\\
1
\end{array}
\right)  $.

\item Likewise, the $\lambda_{3}$-eigenvectors (i.e., the $3$-eigenvectors) of
$A$ are the nonzero scalar multiples of the vector $\left(
\begin{array}
[c]{c}%
1\\
-2\\
1
\end{array}
\right)  $.
\end{itemize}

\noindent We have now found three eigenvectors for $A$: namely,%
\begin{align*}
u_{1}  &  =\left(
\begin{array}
[c]{c}%
-3\\
1\\
2
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{a }\lambda_{1}\text{-eigenvector}%
\right)  ;\\
u_{2}  &  =\left(
\begin{array}
[c]{c}%
3\\
2\\
1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{a }\lambda_{2}\text{-eigenvector}%
\right)  ;\\
u_{3}  &  =\left(
\begin{array}
[c]{c}%
1\\
-2\\
1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{a }\lambda_{3}\text{-eigenvector}%
\right)  .
\end{align*}
These $3$ vectors $u_{1},u_{2},u_{3}$ form a basis of $\mathbb{R}^{3}$
(indeed, this can either be derived from Proposition 1.3.3 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-06.pdf}{the class
notes from 2019-11-06}, or just checked by hand).

Thus, $\left(  u_{1},u_{2},u_{3}\right)  $ is a basis of $\mathbb{R}^{3}$ that
consists of eigenvectors of $A$, and $\lambda_{1},\lambda_{2},\lambda_{3}$ are
the corresponding eigenvalues. Hence, we can find a diagonalization of $A$
using Proposition 1.2.3 \textbf{(a)} in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-11.pdf}{the class
notes from 2019-11-11}: We set
\begin{align*}
U  &  =\left[  u_{1}\mid u_{2}\mid u_{3}\right]  =\left(
\begin{array}
[c]{ccc}%
-3 & 3 & 1\\
1 & 2 & -2\\
2 & 1 & 1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\\
D  &  =\operatorname*{diag}\left(  \lambda_{1},\lambda_{2},\lambda_{3}\right)
=\operatorname*{diag}\left(  -2,1,3\right)  =\left(
\begin{array}
[c]{ccc}%
-2 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 3
\end{array}
\right)  .
\end{align*}
The pair $U,D$ is a diagonalization of $A$ (that is, $U$ is invertible, and
$D$ is diagonal, and we have $A=UDU^{-1}$).

[\textit{Remark:} There are many diagonalizations of $A$. For example, you can
obtain a different diagonalization of $A$ by listing the eigenvalues of $A$ in
a different order, or by scaling the eigenvectors $u_{1},u_{2},u_{3}$ differently.]
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt2t.ev2}.]Let us denote the matrix shown
in this exercise by $A$.

\textbf{(a)} The characteristic polynomial $\chi_{A}\left(  t\right)  $ of $A$
is%
\[
\chi_{A}\left(  t\right)  =\det\left(  A-tI_{3}\right)  =\det\left(
\begin{array}
[c]{ccc}%
1-t & 1 & 0\\
-1 & 2-t & 1\\
0 & 1 & 1-t
\end{array}
\right)  =-\left(  t-1\right)  ^{2}\left(  t-2\right)  .
\]


Recall that the eigenvalues of $A$ are the roots of $\chi_{A}\left(  t\right)
$ (by Proposition 2.1.7 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-04.pdf}{the class
notes from 2019-11-04}). But the roots of $\chi_{A}\left(  t\right)  $ are $1$
and $2$ (since $\chi_{A}\left(  t\right)  =-\left(  t-1\right)  ^{2}\left(
t-2\right)  $). Hence, the eigenvalues of $A$ are $1$ and $2$.

\textbf{(b)} No.

\textit{Proof.} We have just found the eigenvalues of $A$: they are $1$ and
$2$. Let us find eigenvectors for them:

\begin{itemize}
\item The $1$-eigenvectors of $A$ are the nonzero scalar multiples of the
vector $\left(
\begin{array}
[c]{c}%
1\\
0\\
1
\end{array}
\right)  $. (This can be found by Gaussian elimination, just as in the above
solution to Exercise \ref{exe.19fla-mt2t.ev1}.)

\item The $2$-eigenvectors of $A$ are the nonzero scalar multiples of the
vector $\left(
\begin{array}
[c]{c}%
1\\
1\\
1
\end{array}
\right)  $.
\end{itemize}

\noindent This shows that we cannot find $3$ linearly independent eigenvectors
for $A$. Thus, there is no basis of $\mathbb{R}^{3}$ consisting of
eigenvectors of $A$. But Proposition 1.2.3 \textbf{(b)} in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-11.pdf}{the class
notes from 2019-11-11} shows that every diagonalization of $A$ can be obtained
from such a basis. Thus, there is no diagonalization of $A$.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt2t.ev3}.]We proceed in the same way as
we analyzed the Fibonacci numbers (in Example 1.4.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-06.pdf}{the class
notes from 2019-11-06}).

Instead of computing $h_{m}$, let us look at the vectors $\left(
\begin{array}
[c]{c}%
h_{m}\\
h_{m+1}%
\end{array}
\right)  $ for $m\geq0$. Each of these vectors determines the next one:%
\begin{align*}
\left(
\begin{array}
[c]{c}%
h_{m+1}\\
h_{m+2}%
\end{array}
\right)   &  =\left(
\begin{array}
[c]{c}%
h_{m+1}\\
h_{m+1}+6h_{m}%
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since the definition of the }h_{n}\text{
yields }h_{m+2}=h_{m+1}+6h_{m}\right) \\
&  =\left(
\begin{array}
[c]{cc}%
0 & 1\\
6 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
h_{m}\\
h_{m+1}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }m\geq0.
\end{align*}
Let us define the $2\times2$-matrix $A=\left(
\begin{array}
[c]{cc}%
0 & 1\\
6 & 1
\end{array}
\right)  $. Thus, this becomes%
\[
\left(
\begin{array}
[c]{c}%
h_{m+1}\\
h_{m+2}%
\end{array}
\right)  =A\left(
\begin{array}
[c]{c}%
h_{m}\\
h_{m+1}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }m\geq0.
\]
Hence, by induction on $m$, we can show that%
\begin{equation}
\left(
\begin{array}
[c]{c}%
h_{m}\\
h_{m+1}%
\end{array}
\right)  =A^{m}\left(
\begin{array}
[c]{c}%
h_{0}\\
h_{1}%
\end{array}
\right)  \label{sol.19fla-mt2t.ev3.3}%
\end{equation}
for each $m\geq0$. Thus, in order to compute $h_{m}$, it suffices to compute
$A^{m}$.

From here on, we proceed as in Example 1.2.4 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-11.pdf}{the class
notes from 2019-11-11} (except that our matrix $A$ is a different one now). We
seek a diagonalization of $A$. Since we have already seen how to diagonalize a
matrix (see, e.g., the solution to Exercise \ref{exe.19fla-mt2t.ev1}
\textbf{(b)} above), let me be brief: The characteristic polynomial of $A$ is
$\chi_{A}\left(  t\right)  =\det\left(
\begin{array}
[c]{cc}%
0-t & 1\\
6 & 1-t
\end{array}
\right)  =\left(  t-3\right)  \left(  t+2\right)  $; thus, the eigenvalues of
$A$ are $3$ and $-2$; the corresponding eigenvectors are nonzero scalar
multiples of $\left(
\begin{array}
[c]{c}%
1\\
3
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{c}%
-1\\
2
\end{array}
\right)  $, respectively; thus, we obtain a diagonalization $U,D$ with%
\begin{align*}
U  &  =\left[  u_{1}\mid u_{2}\right]  =\left(
\begin{array}
[c]{cc}%
1 & -1\\
3 & 2
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\\
D  &  =\operatorname*{diag}\left(  3,-2\right)  =\left(
\begin{array}
[c]{cc}%
3 & 0\\
0 & -2
\end{array}
\right)  .
\end{align*}


Now, let $m\geq0$. Then, Proposition 1.2.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-11.pdf}{the class
notes from 2019-11-11} (applied to $n=2$, $d_{1}=3$ and $d_{2}=-2$) yields%
\[
\left(  UDU^{-1}\right)  ^{m}=U\operatorname*{diag}\left(  3^{m},\left(
-2\right)  ^{m}\right)  U^{-1}\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}\ D=\operatorname*{diag}\left(  3,-2\right)  \right)  .
\]
In view of $UDU^{-1}=A$, this rewrites as
\begin{align*}
A^{m}  &  =U\operatorname*{diag}\left(  3^{m},\left(  -2\right)  ^{m}\right)
U^{-1}=\left(
\begin{array}
[c]{cc}%
1 & -1\\
3 & 2
\end{array}
\right)  \operatorname*{diag}\left(  3^{m},\left(  -2\right)  ^{m}\right)
\left(
\begin{array}
[c]{cc}%
1 & -1\\
3 & 2
\end{array}
\right)  ^{-1}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }U=\left(
\begin{array}
[c]{cc}%
1 & -1\\
3 & 2
\end{array}
\right)  \text{ and }n=2\text{ and }d_{1}=3\text{ and }d_{2}=-2\right) \\
&  =\left(
\begin{array}
[c]{cc}%
1 & -1\\
3 & 2
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
3^{m} & 0\\
0 & \left(  -2\right)  ^{m}%
\end{array}
\right)  \underbrace{\left(
\begin{array}
[c]{cc}%
1 & -1\\
3 & 2
\end{array}
\right)  ^{-1}}_{\substack{=\dfrac{1}{2-\left(  -1\right)  3}\left(
\begin{array}
[c]{cc}%
2 & 1\\
-3 & 1
\end{array}
\right)  \\\text{(by the formula }\left(
\begin{array}
[c]{cc}%
a & b\\
c & d
\end{array}
\right)  ^{1}=\dfrac{1}{ad-bc}\left(
\begin{array}
[c]{cc}%
d & -b\\
-c & a
\end{array}
\right)  \\\text{for the inverse of a }2\times2\text{-matrix)}}}\\
&  =\underbrace{\dfrac{1}{2-\left(  -1\right)  3}}_{\substack{=\dfrac{1}{5}%
}}\left(
\begin{array}
[c]{cc}%
1 & -1\\
3 & 2
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
3^{m} & 0\\
0 & \left(  -2\right)  ^{m}%
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
2 & 1\\
-3 & 1
\end{array}
\right) \\
&  =\dfrac{1}{5}\left(
\begin{array}
[c]{cc}%
1 & -1\\
3 & 2
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
3^{m} & 0\\
0 & \left(  -2\right)  ^{m}%
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
2 & 1\\
-3 & 1
\end{array}
\right)  .
\end{align*}
We could multiply this out. But we want $h_{m}$, not $A^{m}$. There is a
faster way to get $h_{m}$: From (\ref{sol.19fla-mt2t.ev3.3}), we obtain%
\begin{align*}
\left(
\begin{array}
[c]{c}%
h_{m}\\
h_{m+1}%
\end{array}
\right)   &  =\underbrace{A^{m}}_{=\dfrac{1}{5}\left(
\begin{array}
[c]{cc}%
1 & -1\\
3 & 2
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
3^{m} & 0\\
0 & \left(  -2\right)  ^{m}%
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
2 & 1\\
-3 & 1
\end{array}
\right)  }\underbrace{\left(
\begin{array}
[c]{c}%
h_{0}\\
h_{1}%
\end{array}
\right)  }_{\substack{=\left(
\begin{array}
[c]{c}%
0\\
1
\end{array}
\right)  \\\text{(since }h_{0}=0\text{ and }h_{1}=1\text{)}}}\\
&  =\dfrac{1}{5}\left(
\begin{array}
[c]{cc}%
1 & -1\\
3 & 2
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
3^{m} & 0\\
0 & \left(  -2\right)  ^{m}%
\end{array}
\right)  \underbrace{\left(
\begin{array}
[c]{cc}%
2 & 1\\
-3 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
0\\
1
\end{array}
\right)  }_{=\left(
\begin{array}
[c]{c}%
1\\
1
\end{array}
\right)  }\\
&  =\dfrac{1}{5}\left(
\begin{array}
[c]{cc}%
1 & -1\\
3 & 2
\end{array}
\right)  \underbrace{\left(
\begin{array}
[c]{cc}%
3^{m} & 0\\
0 & \left(  -2\right)  ^{m}%
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
1\\
1
\end{array}
\right)  }_{=\left(
\begin{array}
[c]{c}%
3^{m}\\
\left(  -2\right)  ^{m}%
\end{array}
\right)  }=\dfrac{1}{5}\underbrace{\left(
\begin{array}
[c]{cc}%
1 & -1\\
3 & 2
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
3^{m}\\
\left(  -2\right)  ^{m}%
\end{array}
\right)  }_{\substack{=\left(
\begin{array}
[c]{c}%
3^{m}-\left(  -2\right)  ^{m}\\
\ast
\end{array}
\right)  \\\text{(where the asterisk \textquotedblleft}\ast
\text{\textquotedblright\ stands}\\\text{for an entry that we}\\\text{are not
interested in)}}}\\
&  =\dfrac{1}{5}\left(
\begin{array}
[c]{c}%
3^{m}-\left(  -2\right)  ^{m}\\
\ast
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
\dfrac{1}{5}\left(  3^{m}-\left(  -2\right)  ^{m}\right) \\
\ast
\end{array}
\right)  .
\end{align*}
$\allowbreak$Thus, by comparing the $\left(  1,1\right)  $-entries on both
sides, we obtain%
\[
h_{m}=\dfrac{1}{5}\left(  3^{m}-\left(  -2\right)  ^{m}\right)  .
\]
This solves the exercise.

[\textit{Remark:} In general, if a $2\times2$-matrix has rational entries,
then its eigenvalues will be quadratic irrationalities (i.e., numbers of the
form $a+\sqrt{b}$ with $a,b\in\mathbb{Q}$); they don't have to be rational
numbers (and they don't have to be real numbers either; $b$ can be negative).
The reason why the matrix $A$ above has integer eigenvalues is that I have
picked such a matrix deliberately.]
\end{proof}

Before we solve the next two exercises, let me mention some basic properties
of powers of complex numbers:

\begin{proposition}
\label{prop.CC.CC.power-rules}\textbf{(a)} We have $\alpha^{n+1}=\alpha
\alpha^{n}$ for all $\alpha\in\mathbb{C}$ and $n\in\mathbb{N}$.

\textbf{(b)} We have $\alpha^{n+m}=\alpha^{n}\alpha^{m}$ for all $\alpha
\in\mathbb{C}$ and $n,m\in\mathbb{N}$.

\textbf{(c)} We have $\left(  \alpha\beta\right)  ^{n}=\alpha^{n}\beta^{n}$
for all $\alpha,\beta\in\mathbb{C}$ and $n\in\mathbb{N}$.

\textbf{(d)} We have $\left(  \alpha^{n}\right)  ^{m}=\alpha^{nm}$ for all
$\alpha\in\mathbb{C}$ and $n,m\in\mathbb{N}$.

\textbf{(e)} We have $1^{n}=1$ for all $n\in\mathbb{N}$.

\textbf{(f)} We have $\alpha^{n+1}=\alpha\alpha^{n}$ for all nonzero
$\alpha\in\mathbb{C}$ and all $n\in\mathbb{Z}$.

\textbf{(g)} We have $\alpha^{-n}=\left(  \alpha^{-1}\right)  ^{n}$ for all
nonzero $\alpha\in\mathbb{C}$ and all $n\in\mathbb{Z}$.

\textbf{(h)} We have $\alpha^{n+m}=\alpha^{n}\alpha^{m}$ for all nonzero
$\alpha\in\mathbb{C}$ and all $n,m\in\mathbb{Z}$.

\textbf{(i)} We have $\left(  \alpha\beta\right)  ^{n}=\alpha^{n}\beta^{n}$
for all nonzero $\alpha,\beta\in\mathbb{C}$ and all $n\in\mathbb{Z}$.

\textbf{(j)} We have $1^{n}=1$ for all $n\in\mathbb{Z}$.

\textbf{(k)} We have $\left(  \alpha^{n}\right)  ^{-1}=\alpha^{-n}$ for all
nonzero $\alpha\in\mathbb{C}$ and all $n\in\mathbb{Z}$. (In particular,
$\alpha^{n}$ is nonzero, so that $\left(  \alpha^{n}\right)  ^{-1}$ is well-defined.)

\textbf{(l)} We have $\left(  \alpha^{n}\right)  ^{m}=\alpha^{nm}$ for all
nonzero $\alpha\in\mathbb{C}$ and all $n,m\in\mathbb{Z}$. (In particular,
$\alpha^{n}$ is nonzero, so that $\left(  \alpha^{n}\right)  ^{m}$ is
well-defined for all $m\in\mathbb{Z}$.)

\textbf{(m)} Complex numbers satisfy the binomial formula: That is, if
$\alpha,\beta\in\mathbb{C}$, then%
\[
\left(  \alpha+\beta\right)  ^{n}=\sum_{k=0}^{n}\dbinom{n}{k}\alpha^{k}%
\beta^{n-k}\ \ \ \ \ \ \ \ \ \ \text{for }n\in\mathbb{N}\text{.}%
\]

\end{proposition}

This proposition is \cite[Proposition 4.1.20]{19s}; see \cite[solution to
Exercise 4.1.1]{19s} for a detailed proof. As for us, we will only need its
parts \textbf{(a)}, \textbf{(b)}, \textbf{(c)} and \textbf{(d)}, which are
both easy to check directly using the definition of nonnegative integer powers
(i.e., by using the fact that $\alpha^{k}=\underbrace{\alpha\alpha\cdots
\alpha}_{k\text{ times}}$ for each $\alpha\in\mathbb{C}$ and each
$k\in\mathbb{N}$, where the empty product $\underbrace{\alpha\alpha
\cdots\alpha}_{0\text{ times}}$ is understood to be $1$).

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt2t.CC1}.]\textbf{(a)} We have%
\[
\left(  1+i\right)  ^{2}=\left(  1+i\right)  \left(  1+i\right)
=1+i+i+\underbrace{i^{2}}_{=-1}=1+i+i+\left(  -1\right)  =2i.
\]


\textbf{(b)} Part \textbf{(a)} of this exercise shows that $\left(
1+i\right)  ^{2}=2i$. But Proposition \ref{prop.CC.CC.power-rules}
\textbf{(a)} (applied to $\alpha=1+i$ and $n=2$) yields
\begin{align*}
\left(  1+i\right)  ^{3}  &  =\left(  1+i\right)  \underbrace{\left(
1+i\right)  ^{2}}_{=2i}=\left(  1+i\right)  \cdot\left(  2i\right)
=2i+\underbrace{i\cdot2i}_{=2i^{2}}=2i+2\underbrace{i^{2}}_{=-1}\\
&  =2i+2\left(  -1\right)  =2i-2.
\end{align*}


\textbf{(c)} Part \textbf{(a)} of this exercise shows that $\left(
1+i\right)  ^{2}=2i$. But Proposition \ref{prop.CC.CC.power-rules}
\textbf{(d)} (applied to $\alpha=1+i$, $n=2$ and $m=2$) yields $\left(
\left(  1+i\right)  ^{2}\right)  ^{2}=\left(  1+i\right)  ^{2\cdot2}=\left(
1+i\right)  ^{4}$. Thus,%
\begin{align*}
\left(  1+i\right)  ^{4}  &  =\left(  \underbrace{\left(  1+i\right)  ^{2}%
}_{=2i}\right)  ^{2}=\left(  2i\right)  ^{2}=2^{2}\underbrace{i^{2}}%
_{=-1}\ \ \ \ \ \ \ \ \ \ \left(  \text{by Proposition
\ref{prop.CC.CC.power-rules} \textbf{(c)}}\right) \\
&  =2^{2}\left(  -1\right)  =-4.
\end{align*}


\textbf{(d)} Part \textbf{(c)} of this exercise shows that $\left(
1+i\right)  ^{4}=-4$. But Proposition \ref{prop.CC.CC.power-rules}
\textbf{(d)} (applied to $\alpha=1+i$, $n=4$ and $m=2$) yields $\left(
\left(  1+i\right)  ^{4}\right)  ^{2}=\left(  1+i\right)  ^{4\cdot2}=\left(
1+i\right)  ^{8}$. Thus,
\[
\left(  1+i\right)  ^{8}=\left(  \underbrace{\left(  1+i\right)  ^{4}}%
_{=-4}\right)  ^{2}=\left(  -4\right)  ^{2}=4^{2}=16.
\]


\textbf{(e)} By dividing $1000$ by $4$ with remainder, we obtain
$1000=4\cdot250$.

Part \textbf{(c)} of this exercise shows that $\left(  1+i\right)  ^{4}=-4$.
Now, Proposition \ref{prop.CC.CC.power-rules} \textbf{(d)} (applied to
$\alpha=1+i$, $n=4$ and $m=250$) yields $\left(  \left(  1+i\right)
^{4}\right)  ^{250}=\left(  1+i\right)  ^{4\cdot250}=\left(  1+i\right)
^{1000}$. Thus,
\[
\left(  1+i\right)  ^{1000}=\left(  \underbrace{\left(  1+i\right)  ^{4}%
}_{=-4}\right)  ^{250}=\left(  -4\right)  ^{250}=4^{250}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }250\text{ is even}\right)  .
\]

\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt2t.CC2}.]\textbf{(a)} From
$\omega=\dfrac{1+\sqrt{3}i}{2}$, we obtain%
\begin{align*}
\omega^{2}  &  =\left(  \dfrac{1+\sqrt{3}i}{2}\right)  ^{2}=\dfrac{1+\sqrt
{3}i}{2}\cdot\dfrac{1+\sqrt{3}i}{2}=\dfrac{1}{4}\underbrace{\left(  1+\sqrt
{3}i\right)  \left(  1+\sqrt{3}i\right)  }_{=1+\sqrt{3}i+\sqrt{3}i+\left(
\sqrt{3}i\right)  ^{2}}\\
&  =\dfrac{1}{4}\left(  1+\underbrace{\sqrt{3}i+\sqrt{3}i}_{=2\sqrt{3}%
i}+\underbrace{\left(  \sqrt{3}i\right)  ^{2}}_{\substack{=\left(  \sqrt
{3}\right)  ^{2}i^{2}\\\text{(by Proposition \ref{prop.CC.CC.power-rules}
\textbf{(c)})}}}\right) \\
&  =\dfrac{1}{4}\left(  1+2\sqrt{3}i+\underbrace{\left(  \sqrt{3}\right)
^{2}}_{=3}\underbrace{i^{2}}_{=-1}\right)  =\dfrac{1}{4}\underbrace{\left(
1+2\sqrt{3}i+3\left(  -1\right)  \right)  }_{=-2+2\sqrt{3}i}\\
&  =\dfrac{1}{4}\left(  -2+2\sqrt{3}i\right)  =\dfrac{-1+\sqrt{3}i}{2}.
\end{align*}


\textbf{(b)} Part \textbf{(a)} of this exercise shows that $\omega^{2}%
=\dfrac{-1+\sqrt{3}i}{2}$. But Proposition \ref{prop.CC.CC.power-rules}
\textbf{(a)} (applied to $\alpha=\omega$ and $n=2$) yields
\begin{align*}
\omega^{3}  &  =\underbrace{\omega}_{=\dfrac{1+\sqrt{3}i}{2}}%
\ \ \underbrace{\omega^{2}}_{=\dfrac{-1+\sqrt{3}i}{2}}=\dfrac{1+\sqrt{3}i}%
{2}\cdot\dfrac{-1+\sqrt{3}i}{2}\\
&  =\dfrac{1}{4}\underbrace{\left(  1+\sqrt{3}i\right)  \left(  -1+\sqrt
{3}i\right)  }_{=-1+\sqrt{3}i-\sqrt{3}i+\left(  \sqrt{3}i\right)  ^{2}}%
=\dfrac{1}{4}\left(  -1+\underbrace{\sqrt{3}i-\sqrt{3}i}_{=0}%
+\underbrace{\left(  \sqrt{3}i\right)  ^{2}}_{\substack{=\left(  \sqrt
{3}\right)  ^{2}i^{2}\\\text{(by Proposition \ref{prop.CC.CC.power-rules}
\textbf{(c)})}}}\right) \\
&  =\dfrac{1}{4}\left(  -1+\underbrace{\left(  \sqrt{3}\right)  ^{2}}%
_{=3}\underbrace{i^{2}}_{=-1}\right)  =\dfrac{1}{4}\left(  -1+3\left(
-1\right)  \right)  =-1.
\end{align*}


\textbf{(c)} Part \textbf{(b)} of this exercise shows that $\omega^{3}=-1$.
But Proposition \ref{prop.CC.CC.power-rules} \textbf{(d)} (applied to
$\alpha=\omega$, $n=3$ and $m=2$) yields $\left(  \omega^{3}\right)
^{2}=\omega^{3\cdot2}=\omega^{6}$. Thus,%
\[
\omega^{6}=\left(  \underbrace{\omega^{3}}_{=-1}\right)  ^{2}=\left(
-1\right)  ^{2}=1.
\]


\textbf{(d)} Here is how they look:
\[
\begin{tikzpicture}[scale=2.5]
\draw[step=1cm,gray,very thin] (-1.2, -1.2) grid (1.2, 1.2);
\draw[->] (-1.3,0) -- (1.3,0);
\draw[->] (0,-1.3) -- (0,1.3);
\node (w1) at (0.5 cm, 0.866 cm) {};
\node (w2) at (-0.5 cm, 0.866 cm) {};
\node (w3) at (-1 cm, 0 cm) {};
\node (w4) at (-0.5 cm, -0.866 cm) {};
\node (w5) at (0.5 cm, -0.866 cm) {};
\node (w0) at (1 cm, 0 cm) {};
\fill (w1) circle (1pt) node[above right] {$\omega^1$};
\fill (w2) circle (1pt) node[above left] {$\omega^2$};
\fill (w3) circle (1pt) node[above left] {$\omega^3$};
\fill (w4) circle (1pt) node[below left] {$\omega^4$};
\fill (w5) circle (1pt) node[below right] {$\omega^5$};
\fill (w0) circle (1pt) node[above right] {$\omega^0$};
\end{tikzpicture}.
\]
As we can see, they are the vertices of a regular hexagon inscribed in the
unit circle, centered at the origin:
\[
\begin{tikzpicture}[scale=2.5]
\draw[step=1cm,gray,very thin] (-1.2, -1.2) grid (1.2, 1.2);
\draw[->] (-1.3,0) -- (1.3,0);
\draw[->] (0,-1.3) -- (0,1.3);
\node (w1) at (0.5 cm, 0.866 cm) {};
\node (w2) at (-0.5 cm, 0.866 cm) {};
\node (w3) at (-1 cm, 0 cm) {};
\node (w4) at (-0.5 cm, -0.866 cm) {};
\node (w5) at (0.5 cm, -0.866 cm) {};
\node (w0) at (1 cm, 0 cm) {};
\fill (w1) circle (1pt) node[above right] {$\omega^1$};
\fill (w2) circle (1pt) node[above left] {$\omega^2$};
\fill (w3) circle (1pt) node[above left] {$\omega^3$};
\fill (w4) circle (1pt) node[below left] {$\omega^4$};
\fill (w5) circle (1pt) node[below right] {$\omega^5$};
\fill (w0) circle (1pt) node[above right] {$\omega^0$};
\draw[very thick, red] (w0) -- (w1);
\draw[very thick, red] (w1) -- (w2);
\draw[very thick, red] (w2) -- (w3);
\draw[very thick, red] (w3) -- (w4);
\draw[very thick, red] (w4) -- (w5);
\draw[very thick, red] (w5) -- (w0);
\draw[very thick, green] (0,0) circle (1 cm);
\end{tikzpicture}.
\]


\textbf{(e)} By dividing $1000$ by $3$ with remainder, we obtain
$1000=3\cdot333+1$.

Part \textbf{(b)} of this exercise shows that $\omega^{3}=-1$. Now,
Proposition \ref{prop.CC.CC.power-rules} \textbf{(d)} (applied to
$\alpha=\omega$, $n=3$ and $m=333$) yields $\left(  \omega^{3}\right)
^{333}=\omega^{3\cdot333}=\omega^{999}$. Thus,
\[
\omega^{999}=\left(  \underbrace{\omega^{3}}_{=-1}\right)  ^{333}=\left(
-1\right)  ^{333}=-1\ \ \ \ \ \ \ \ \ \ \left(  \text{since }333\text{ is
odd}\right)  .
\]
Now, Proposition \ref{prop.CC.CC.power-rules} \textbf{(a)} (applied to
$\alpha=\omega$ and $n=999$) yields%
\[
\omega^{1000}=\omega\underbrace{\omega^{999}}_{=-1}=\omega\left(  -1\right)
=-\omega=-\dfrac{1+\sqrt{3}i}{2}\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}\omega=\dfrac{1+\sqrt{3}i}{2}\right)  .
\]

\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt2t.CCabsmul}.]Recall that a complex
number has been defined as a pair of real numbers. Thus, we can write the
complex numbers $z$ and $w$ as $z=\left(  a,b\right)  $ and $w=\left(
c,d\right)  $, respectively, where $a,b,c,d$ are four reals. Consider these
$a,b,c,d$.

From $z=\left(  a,b\right)  $ and $w=\left(  c,d\right)  $, we obtain%
\[
zw=\left(  a,b\right)  \left(  c,d\right)  =\left(  ac-bd,ad+bc\right)
\]
(by the definition of multiplication of complex numbers).

But the definition of the absolute value of a complex number yields%
\begin{align*}
\left\vert z\right\vert  &  =\sqrt{a^{2}+b^{2}}\ \ \ \ \ \ \ \ \ \ \left(
\text{since }z=\left(  a,b\right)  \right)  \ \ \ \ \ \ \ \ \ \ \text{and}\\
\left\vert w\right\vert  &  =\sqrt{c^{2}+d^{2}}\ \ \ \ \ \ \ \ \ \ \left(
\text{since }w=\left(  c,d\right)  \right)  \ \ \ \ \ \ \ \ \ \ \text{and}\\
\left\vert zw\right\vert  &  =\sqrt{\left(  ac-bd\right)  ^{2}+\left(
ad+bc\right)  ^{2}}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }zw=\left(
ac-bd,ad+bc\right)  \right)  .
\end{align*}
Multiplying the first two of these three equalities, we find%
\[
\left\vert z\right\vert \cdot\left\vert w\right\vert =\sqrt{a^{2}+b^{2}}%
\cdot\sqrt{c^{2}+d^{2}}=\sqrt{\left(  a^{2}+b^{2}\right)  \left(  c^{2}%
+d^{2}\right)  }=\sqrt{a^{2}c^{2}+a^{2}d^{2}+b^{2}c^{2}+b^{2}d^{2}}.
\]
Comparing this with%
\begin{align*}
\left\vert zw\right\vert  &  =\sqrt{\left(  ac-bd\right)  ^{2}+\left(
ad+bc\right)  ^{2}}=\sqrt{a^{2}c^{2}+a^{2}d^{2}+b^{2}c^{2}+b^{2}d^{2}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{l}%
\text{since }\left(  ac-bd\right)  ^{2}+\left(  ad+bc\right)  ^{2}\\
=\left(  a^{2}c^{2}-2acbd+b^{2}d^{2}\right)  +\left(  a^{2}d^{2}%
+2adbc+b^{2}c^{2}\right) \\
=\left(  a^{2}c^{2}-2abcd+b^{2}d^{2}\right)  +\left(  a^{2}d^{2}%
+2abcd+b^{2}c^{2}\right) \\
=a^{2}c^{2}+a^{2}d^{2}+b^{2}c^{2}+b^{2}d^{2}%
\end{array}
\right)  ,
\end{align*}
we obtain $\left\vert zw\right\vert =\left\vert z\right\vert \cdot\left\vert
w\right\vert $. This solves the exercise.
\end{proof}

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[19s]{19s}Darij Grinberg, \textit{Introduction to Modern Algebra (UMN
Spring 2019 Math 4281 notes)}, 29 June 2019.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.pdf}

\bibitem[Grinbe15]{detnotes}Darij Grinberg, \textit{Notes on the combinatorial
fundamentals of algebra}, 10 January 2019.\newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf} \newline The
numbering of theorems and formulas in this link might shift when the project
gets updated; for a \textquotedblleft frozen\textquotedblright\ version whose
numbering is guaranteed to match that in the citations above, see
\url{https://github.com/darijgr/detnotes/releases/tag/2019-01-10} .
\end{thebibliography}


\end{document}