\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, December 10, 2019 21:56:38}
%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 2}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

\section{Reminders}

\begin{definition}
Let $A$ be an $n\times n$-matrix. Then, the \textbf{determinant} $\det A$ of
$A$ is defined to be the sum%
\[
\sum_{\sigma\text{ is a permutation of }\left[  n\right]  }%
\operatorname*{sign}\left(  \sigma\right)  \cdot A_{1,\sigma\left(  1\right)
}A_{2,\sigma\left(  2\right)  }\cdots A_{n,\sigma\left(  n\right)  }.
\]

\end{definition}

Here, $\left[  n\right]  $ means $\left\{  1,2,\ldots,n\right\}  $.

\begin{theorem}
[Laplace expansion]Let $A$ be an $n\times n$-matrix. For each $p,q\in\left[
n\right]  $, we let $M_{p,q}$ be the $\left(  n-1\right)  \times\left(
n-1\right)  $-matrix obtained from $A$ by removing row $p$ and column $q$. Then:

\textbf{(a)} For each $p\in\left[  n\right]  $, we have%
\[
\det A=\sum_{q=1}^{n}\left(  -1\right)  ^{p+q}A_{p,q}\det\left(
M_{p,q}\right)  .
\]
(This is called \textbf{Laplace expansion along the }$p$\textbf{-th row}.)

\textbf{(b)} For each $q\in\left[  n\right]  $, we have%
\[
\det A=\sum_{p=1}^{n}\left(  -1\right)  ^{p+q}A_{p,q}\det\left(
M_{p,q}\right)  .
\]
(This is called \textbf{Laplace expansion along the }$q$\textbf{-th column}.)
\end{theorem}

\begin{definition}
Let $A$ be an $n\times n$-matrix. Let $\lambda$ be a scalar (i.e., a real number).

\textbf{(a)} A $\lambda$\textbf{-eigenvector of }$A$ means a nonzero vector
$v\in\mathbb{R}^{n}$ such that $Av=\lambda v$.

\textbf{(b)} We say that $\lambda$ is an \textbf{eigenvalue} of $A$ if and
only if there exists a $\lambda$-eigenvector of $A$.

\textbf{(c)} The \textbf{characteristic polynomial} of $A$ is the polynomial%
\[
\chi_{A}\left(  t\right)  =\det\left(  A-tI_{n}\right)  .
\]

\end{definition}

\cleardoublepage


\section{Determinants}

\begin{exercise}
\label{exe.19fla-mt2.det1}Let $a,b,c,x,y,z$ be six reals.

\textbf{(a)} Find%
\[
\det\left(
\begin{array}
[c]{ccc}%
a-x & a-y & a-z\\
b-x & b-y & b-z\\
c-x & c-y & c-z
\end{array}
\right)  .
\]


\textbf{(b)} Find%
\[
\det\left(
\begin{array}
[c]{ccc}%
1+ax & 1+ay & 1+az\\
1+bx & 1+by & 1+bz\\
1+cx & 1+cy & 1+cz
\end{array}
\right)  .
\]


\textbf{(c)} Find
\[
\det\left(
\begin{array}
[c]{ccc}%
a & b & c\\
x & y & 0\\
z & 0 & 0
\end{array}
\right)  .
\]

\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt2.det1}.]Let us recall some 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}

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

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

\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. (This 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$.)
\end{statement}

\begin{statement}
\textit{Property 7:} If an $n\times n$-matrix $A$ is triangular (i.e.,
upper-triangular or lower-triangular), then its determinant is the product of
its diagonal elements:
\[
\det A=A_{1,1}A_{2,2}\cdots A_{n,n}.
\]
(This is Theorem 1.1.2 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 8:} If we swap two rows of an $n\times n$-matrix, then its
determinant gets multiplied by $-1$ (that is, it flips its sign but preserves
its magnitude). (This is Theorem 1.2.6 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{the class
notes from 2019-10-30}.)
\end{statement}

\bigskip

\textbf{(a)} Part \textbf{(a)} of the exercise is similar to Exercise 3 on
\href{https://www.cip.ifi.lmu.de/~grinberg/t/19fla/mt2t.pdf}{midterm training
\#2} (but we have minus signs instead of plus signs now, and we have
restricted ourselves to a $3\times3$-matrix to make the solution more
intuitive). Let us give two solutions.

\bigskip

\textit{First solution to part \textbf{(a)}:} We have%
\begin{align*}
&  \det\left(
\begin{array}
[c]{ccc}%
a-x & a-y & a-z\\
b-x & b-y & b-z\\
c-x & c-y & c-z
\end{array}
\right) \\
&  =\det\left(
\begin{array}
[c]{ccc}%
a-x & a-y & a-z\\
b-a & b-a & b-a\\
c-x & c-y & c-z
\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]{ccc}%
a-x & a-y & a-z\\
b-a & b-a & b-a\\
c-a & c-a & c-a
\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(  b-a\right)  \det\left(
\begin{array}
[c]{ccc}%
a-x & a-y & a-z\\
1 & 1 & 1\\
c-a & c-a & c-a
\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 }b-a
\end{array}
\right) \\
&  =\left(  b-a\right)  \left(  c-a\right)  \underbrace{\det\left(
\begin{array}
[c]{ccc}%
a-x & a-y & a-z\\
1 & 1 & 1\\
1 & 1 & 1
\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))}%
}}\\
&  =0.
\end{align*}


\bigskip

\textit{Second solution to part \textbf{(a)}:} Define two $n\times n$-matrices
$X$ and $Y$ by%
\[
X=\left(
\begin{array}
[c]{ccc}%
a & -1 & 0\\
b & -1 & 0\\
c & -1 & 0
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ Y=\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
x & y & z\\
0 & 0 & 0
\end{array}
\right)  .
\]
The matrix $Y$ has a zero row (namely, its third row). Thus, Property 4 yields
$\det Y=0$.

But it is easy to see that $\left(
\begin{array}
[c]{ccc}%
a-x & a-y & a-z\\
b-x & b-y & b-z\\
c-x & c-y & c-z
\end{array}
\right)  =XY$. Hence,%
\begin{align*}
\det\left(
\begin{array}
[c]{ccc}%
a-x & a-y & a-z\\
b-x & b-y & b-z\\
c-x & c-y & c-z
\end{array}
\right)   &  =\det\left(  XY\right)  =\det X\cdot\underbrace{\det Y}%
_{=0}\ \ \ \ \ \ \ \ \ \ \left(  \text{by Property 3}\right) \\
&  =0.
\end{align*}


\bigskip

\textbf{(b)} This is similar to part \textbf{(a)}. Again, we will give two solutions:

\bigskip

\textit{First solution to part \textbf{(b)}:} We have%
\begin{align*}
&  \det\left(
\begin{array}
[c]{ccc}%
1+ax & 1+ay & 1+az\\
1+bx & 1+by & 1+bz\\
1+cx & 1+cy & 1+cz
\end{array}
\right) \\
&  =\det\left(
\begin{array}
[c]{ccc}%
1+ax & 1+ay & 1+az\\
\left(  b-a\right)  x & \left(  b-a\right)  y & \left(  b-a\right)  z\\
1+cx & 1+cy & 1+cz
\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]{ccc}%
1+ax & 1+ay & 1+az\\
\left(  b-a\right)  x & \left(  b-a\right)  y & \left(  b-a\right)  z\\
\left(  c-a\right)  x & \left(  c-a\right)  y & \left(  c-a\right)  z
\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(  b-a\right)  \det\left(
\begin{array}
[c]{ccc}%
1+ax & 1+ay & 1+az\\
x & y & z\\
\left(  c-a\right)  x & \left(  c-a\right)  y & \left(  c-a\right)  z
\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 }b-a
\end{array}
\right) \\
&  =\left(  b-a\right)  \left(  c-a\right)  \underbrace{\det\left(
\begin{array}
[c]{ccc}%
1+ax & 1+ay & 1+az\\
x & y & z\\
x & y & z
\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))}%
}}\\
&  =0.
\end{align*}


\bigskip

\textit{Second solution to part \textbf{(b)}:} Define two $n\times n$-matrices
$X$ and $Y$ by%
\[
X=\left(
\begin{array}
[c]{ccc}%
1 & a & 0\\
1 & b & 0\\
1 & c & 0
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ Y=\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
x & y & z\\
0 & 0 & 0
\end{array}
\right)  .
\]
The matrix $Y$ has a zero row (namely, its third row). Thus, Property 4 yields
$\det Y=0$.

But it is easy to see that $\left(
\begin{array}
[c]{ccc}%
1+ax & 1+ay & 1+az\\
1+bx & 1+by & 1+bz\\
1+cx & 1+cy & 1+cz
\end{array}
\right)  =XY$. Hence,%
\begin{align*}
\det\left(
\begin{array}
[c]{ccc}%
1+ax & 1+ay & 1+az\\
1+bx & 1+by & 1+bz\\
1+cx & 1+cy & 1+cz
\end{array}
\right)   &  =\det\left(  XY\right)  =\det X\cdot\underbrace{\det Y}%
_{=0}\ \ \ \ \ \ \ \ \ \ \left(  \text{by Property 3}\right) \\
&  =0.
\end{align*}


\bigskip

\textbf{(c)} Again, let us give two solutions:

\bigskip

\textit{First solution to part \textbf{(c)}:} Recall the explicit formula%
\begin{align*}
\det A  &  =A_{1,1}A_{2,2}A_{3,3}+A_{1,2}A_{2,3}A_{3,1}+A_{1,3}A_{2,1}%
A_{3,2}\\
&  \ \ \ \ \ \ \ \ \ \ -A_{1,1}A_{2,3}A_{3,2}-A_{1,2}A_{2,1}A_{3,3}%
-A_{1,3}A_{2,2}A_{3,1}%
\end{align*}
for the determinant of an arbitrary $3\times3$-matrix. Applying this formula
to $A=\left(
\begin{array}
[c]{ccc}%
a & b & c\\
x & y & 0\\
z & 0 & 0
\end{array}
\right)  $, we obtain%
\[
\det\left(
\begin{array}
[c]{ccc}%
a & b & c\\
x & y & 0\\
z & 0 & 0
\end{array}
\right)  =ay\cdot0+b\cdot0z+cx\cdot0-a0\cdot0-bx\cdot0-cyz=-cyz.
\]


\bigskip

\textit{Second solution to part \textbf{(c)}:} We have%
\begin{align*}
&  \det\left(
\begin{array}
[c]{ccc}%
a & b & c\\
x & y & 0\\
z & 0 & 0
\end{array}
\right) \\
&  =-\underbrace{\det\left(
\begin{array}
[c]{ccc}%
z & 0 & 0\\
x & y & 0\\
a & b & c
\end{array}
\right)  }_{\substack{=zyc\\\text{(by Property 7, since this matrix}\\\text{is
lower-triangular)}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have swapped the }1\text{-st and }3\text{-rd rows of the
matrix;}\\
\text{this caused the determinant to get multiplied by }-1\\
\text{(by Property 8)}%
\end{array}
\right) \\
&  =-zyc=-cyz.
\end{align*}

\end{proof}

Let us remark that all three parts of Exercise \ref{exe.19fla-mt2.det1} can be
generalized to $n\times n$-matrices. Indeed, Exercise \ref{exe.19fla-mt2.det1}
\textbf{(a)} is a particular case of the following fact:

\begin{proposition}
\label{prop.19fla-mt2.det1a.gen}Let $n\geq3$ be an 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 $D_{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)  .
\]
Then, $\det\left(  D_{n}\right)  =0$.
\end{proposition}

This Proposition \ref{prop.19fla-mt2.det1a.gen} follows from our answer to
Exercise 3 on
\href{https://www.cip.ifi.lmu.de/~grinberg/t/19fla/mt2t.pdf}{midterm training
\#2} (applied to $-y_{j}$ instead of $y_{j}$).

Exercise \ref{exe.19fla-mt2.det1} \textbf{(b)} is a particular case of the
following fact:

\begin{proposition}
\label{prop.19fla-mt2.det1b.gen}Let $n\geq3$ be an 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 $T_{n}$ denote the $n\times n$-matrix%
\[
\left(  1+x_{i}y_{j}\right)  _{1\leq i\leq n,\ 1\leq j\leq n}=\left(
\begin{array}
[c]{cccc}%
1+x_{1}y_{1} & 1+x_{1}y_{2} & \cdots & 1+x_{1}y_{n}\\
1+x_{2}y_{1} & 1+x_{2}y_{2} & \cdots & 1+x_{2}y_{n}\\
\vdots & \vdots & \ddots & \vdots\\
1+x_{n}y_{1} & 1+x_{n}y_{2} & \cdots & 1+x_{n}y_{n}%
\end{array}
\right)  .
\]
Then, $\det\left(  T_{n}\right)  =0$.
\end{proposition}

This Proposition \ref{prop.19fla-mt2.det1b.gen} can be proved by adapating any
of our above two solutions to Exercise \ref{exe.19fla-mt2.det1} \textbf{(b)}
in a straightforward manner.

Finally, Exercise \ref{exe.19fla-mt2.det1} \textbf{(c)} is a particular case
of the following fact:

\begin{proposition}
\label{prop.19fla-mt2.det1c.gen}Let $n\in\mathbb{N}$. Let $A$ be an $n\times
n$-matrix. The straight line connecting the upper-right corner of $A$ with the
bottom-left corner of $A$ will be called the \textit{anti-diagonal} of $A$.

Assume that all entries of $A$ below the anti-diagonal are $0$. (In other
words, assume that $A_{i,j}=0$ for all $\left(  i,j\right)  $ satisfying
$i+j>n+1$.)

Then,
\[
\det A=\left(  -1\right)  ^{n\left(  n-1\right)  /2}A_{1,n}A_{2,n-1}\cdots
A_{n-1,2}A_{n,1}.
\]

\end{proposition}

Applying Proposition \ref{prop.19fla-mt2.det1c.gen} to $n=3$, we recover
Exercise \ref{exe.19fla-mt2.det1} \textbf{(c)}.

Proposition \ref{prop.19fla-mt2.det1c.gen} can be proven in the same two ways
in which we solved Exercise \ref{exe.19fla-mt2.det1} \textbf{(c)}, although
each of them requires some more thinking in the general case:

\begin{itemize}
\item Imitating the second solution to Exercise \ref{exe.19fla-mt2.det1}
\textbf{(c)}, we can prove Proposition \ref{prop.19fla-mt2.det1c.gen} by
turning the matrix $A$ into a lower-triangular matrix by a sequence of row
swaps. (There are several ways to do so; the conceptually simplest way is
probably to swap every row with every row.)

\item Imitating the first solution to Exercise \ref{exe.19fla-mt2.det1}
\textbf{(c)}, we can prove Proposition \ref{prop.19fla-mt2.det1c.gen} by
showing that only $1$ of the $n!$ many addends in the definition of $\det A$
has any chance to be nonzero, and that this addend is precisely%
\[
\left(  -1\right)  ^{n\left(  n-1\right)  /2}A_{1,n}A_{2,n-1}\cdots
A_{n-1,2}A_{n,1}.
\]
(This addend corresponds to the permutation $\sigma$ of $\left[  n\right]  $
that sends $1,2,\ldots,n-1,n$ to $n,n-1,\ldots,2,1$ respectively; the sign of
this permutation is $\operatorname*{sign}\left(  \sigma\right)  =\left(
-1\right)  ^{n\left(  n-1\right)  /2}$, since $\sigma$ has $n\left(
n-1\right)  /2$ inversions.)
\end{itemize}

We leave the details to the interested reader.

\cleardoublepage


\begin{exercise}
\label{exe.19fla-mt2.det2}For each $n\in\mathbb{N}$, let $B_{n}$ be the
$n\times n$-matrix%
\[
\left(
\begin{array}
[c]{ccccccc}%
2 & 1 & 0 & \cdots & 0 & 0 & 0\\
1 & 2 & 1 & \cdots & 0 & 0 & 0\\
0 & 1 & 2 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & 0 & \cdots & 2 & 1 & 0\\
0 & 0 & 0 & \cdots & 1 & 2 & 1\\
0 & 0 & 0 & \cdots & 0 & 1 & 2
\end{array}
\right)  .
\]
(This is the $n\times n$-matrix whose entries on the diagonal are $2$, while
all entries just above and just below the diagonal are $1$, and all remaining
entries are $0$.)

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

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

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

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

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

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

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt2.det2}.]This exercise is analogous to
Exercise 4 on
\href{https://www.cip.ifi.lmu.de/~grinberg/t/19fla/mt2t.pdf}{midterm training
\#2}. Parts \textbf{(a)}, \textbf{(b)}, \textbf{(c)} and \textbf{(d)} are
solved in the exact same way (with some obvious changes) as the corresponding
parts of the latter exercise. Part \textbf{(e)}, however, involves a new twist.

\textbf{(a)} We have $B_{1}=\left(
\begin{array}
[c]{c}%
2
\end{array}
\right)  $ and thus $\det\left(  B_{1}\right)  =\det\left(
\begin{array}
[c]{c}%
2
\end{array}
\right)  =2$.

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

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

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

We have%
\[
B_{n}=\left(
\begin{array}
[c]{ccccccc}%
2 & 1 & 0 & \cdots & 0 & 0 & 0\\
1 & 2 & 1 & \cdots & 0 & 0 & 0\\
0 & 1 & 2 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & 0 & \cdots & 2 & 1 & 0\\
0 & 0 & 0 & \cdots & 1 & 2 & 1\\
0 & 0 & 0 & \cdots & 0 & 1 & 2
\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 $B_{n}$ has only two nonzero entries: the $2$ 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(  B_{n}\right)   &  =2\cdot\det\underbrace{\left(
\begin{array}
[c]{cccccc}%
2 & 1 & \cdots & 0 & 0 & 0\\
1 & 2 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & \cdots & 2 & 1 & 0\\
0 & 0 & \cdots & 1 & 2 & 1\\
0 & 0 & \cdots & 0 & 1 & 2
\end{array}
\right)  _{\left(  n-1\right)  \times\left(  n-1\right)  }}_{=B_{n-1}}\\
&  \ \ \ \ \ \ \ \ \ \ -1\cdot\det\left(
\begin{array}
[c]{cccccc}%
1 & 1 & \cdots & 0 & 0 & 0\\
0 & 2 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & \cdots & 2 & 1 & 0\\
0 & 0 & \cdots & 1 & 2 & 1\\
0 & 0 & \cdots & 0 & 1 & 2
\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) \\
&  =2\cdot\det\left(  B_{n-1}\right)  -\det\left(
\begin{array}
[c]{cccccc}%
1 & 1 & \cdots & 0 & 0 & 0\\
0 & 2 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & \cdots & 2 & 1 & 0\\
0 & 0 & \cdots & 1 & 2 & 1\\
0 & 0 & \cdots & 0 & 1 & 2
\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 & 2 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
0 & 0 & \cdots & 2 & 1 & 0\\
0 & 0 & \cdots & 1 & 2 & 1\\
0 & 0 & \cdots & 0 & 1 & 2
\end{array}
\right)  _{\left(  n-1\right)  \times\left(  n-1\right)  }$} by $C_{n-1}$. The
$1$-st column of this matrix $C_{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(  C_{n-1}\right)   &  =1\cdot\det\underbrace{\left(
\begin{array}
[c]{ccccc}%
2 & \cdots & 0 & 0 & 0\\
\vdots & \ddots & \vdots & \vdots & \vdots\\
0 & \cdots & 2 & 1 & 0\\
0 & \cdots & 1 & 2 & 1\\
0 & \cdots & 0 & 1 & 2
\end{array}
\right)  _{\left(  n-2\right)  \times\left(  n-2\right)  }}_{=B_{n-2}}%
=1\cdot\det\left(  B_{n-2}\right) \\
&  =\det\left(  B_{n-2}\right)  .
\end{align*}
Thus, our above computation becomes%
\begin{align*}
\det\left(  B_{n}\right)   &  =2\cdot\det\left(  B_{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)  }}_{=C_{n-1}}\\
&  =2\cdot\det\left(  B_{n-1}\right)  -\underbrace{\det\left(  C_{n-1}\right)
}_{=\det\left(  B_{n-2}\right)  }=2\cdot\det\left(  B_{n-1}\right)
-\det\left(  B_{n-2}\right)  .
\end{align*}
This solves part \textbf{(d)} of the exercise.

\textbf{(e)} We claim that%
\begin{equation}
\det\left(  B_{n}\right)  =n+1\ \ \ \ \ \ \ \ \ \ \text{for each }n\geq1.
\label{sol.19fla-mt2.det2.claim}%
\end{equation}


[\textit{Proof of (\ref{sol.19fla-mt2.det2.claim}):} We shall prove
(\ref{sol.19fla-mt2.det2.claim}) by strong induction on $n$:

\textit{Induction step:} Let $m\geq1$ be an integer. Assume (as induction
hypothesis) that (\ref{sol.19fla-mt2.det2.claim}) holds for all $n<m$. We must
then show that (\ref{sol.19fla-mt2.det2.claim}) holds for $n=m$. In other
words, we must show that $\det\left(  B_{m}\right)  =m+1$.

This is clearly true when $m=1$ (because in part \textbf{(a)} of this
exercise, we showed that $\det\left(  B_{1}\right)  =2=1+1$). It is also true
when $m=2$ (because in part \textbf{(b)} of this exercise, we showed that
$\det\left(  B_{2}\right)  =3=2+1$). Thus, for the rest of this induction
step, we can WLOG assume that $m\neq1$ and $m\neq2$. Assume this; hence,
$m\geq3$.

The integer $m-1$ satisfies $m-1\geq1$ (since $m\geq3\geq2$) and $m-1<m$.
Thus, our induction hypothesis shows that (\ref{sol.19fla-mt2.det2.claim})
holds for $n=m-1$. In other words, we have $\det\left(  B_{m-1}\right)
=\left(  m-1\right)  +1$.

The integer $m-2$ satisfies $m-2\geq1$ (since $m\geq3$) and $m-2<m$. Thus, our
induction hypothesis shows that (\ref{sol.19fla-mt2.det2.claim}) holds for
$n=m-2$. In other words, we have $\det\left(  B_{m-2}\right)  =\left(
m-2\right)  +1$.

But in part \textbf{(d)} of the exercise, we have seen that $\det\left(
B_{n}\right)  =2\cdot\det\left(  B_{n-1}\right)  -\det\left(  B_{n-2}\right)
$ for each $n\geq2$. Applying this to $n=m$, we find%
\[
\det\left(  B_{m}\right)  =2\cdot\underbrace{\det\left(  B_{m-1}\right)
}_{=\left(  m-1\right)  +1}-\underbrace{\det\left(  B_{m-2}\right)
}_{=\left(  m-2\right)  +1}=2\cdot\left(  \left(  m-1\right)  +1\right)
-\left(  \left(  m-2\right)  +1\right)  =m+1.
\]
In other words, (\ref{sol.19fla-mt2.det2.claim}) holds for $n=m$. This
completes the induction step. Thus, (\ref{sol.19fla-mt2.det2.claim}) is proved
by strong induction.]

Now that (\ref{sol.19fla-mt2.det2.claim}) is proved, part \textbf{(e)} of the
exercise is solved.

[\textit{Remark:} The above proof of (\ref{sol.19fla-mt2.det2.claim}) by
strong induction is rigorous and completely straightforward (once you know
what you are proving!), but it is somewhat bland and unmotivated (in the sense
that you need to know the formula (\ref{sol.19fla-mt2.det2.claim}) in order to
find this proof). Of course, this is not a serious issue here, since the
formula (\ref{sol.19fla-mt2.det2.claim}) is easy to guess (just look at the
values of $\det\left(  B_{n}\right)  $ for $n=0,1,2,3,4$, and extend the
obvious pattern). Nevertheless, there is value in having a more motivated
proof. Here is an outline of such a proof: In part \textbf{(d)} of the
exercise, we have seen that $\det\left(  B_{n}\right)  =2\cdot\det\left(
B_{n-1}\right)  -\det\left(  B_{n-2}\right)  $ for each $n\geq2$. We can
rewrite this equality as%
\[
\det\left(  B_{n}\right)  -\det\left(  B_{n-1}\right)  =\det\left(
B_{n-1}\right)  -\det\left(  B_{n-2}\right)  .
\]
But this equality is just saying that the differences between consecutive
elements of the sequence%
\[
\left(  \det\left(  B_{0}\right)  ,\det\left(  B_{1}\right)  ,\det\left(
B_{2}\right)  ,\det\left(  B_{3}\right)  ,\ldots\right)
\]
don't change from one pair of consecutive elements to the next. In other
words, these differences are all the same. In other words, the sequence%
\[
\left(  \det\left(  B_{0}\right)  ,\det\left(  B_{1}\right)  ,\det\left(
B_{2}\right)  ,\det\left(  B_{3}\right)  ,\ldots\right)
\]
is an arithmetic sequence. Which arithmetic sequence? Since an arithmetic
sequence is uniquely determined by any two of its values, we can answer this
question by finding $\det\left(  B_{1}\right)  $ and $\det\left(
B_{2}\right)  $ and extending the pattern. Since $\det\left(  B_{1}\right)
=2$ and $\det\left(  B_{2}\right)  =3$, we see that the pattern is
$\det\left(  B_{n}\right)  =n+1$ for all $n\geq0$. This proves
(\ref{sol.19fla-mt2.det2.claim}) again.]
\end{proof}

\cleardoublepage


\section{Eigenvalues and eigenvectors}

\begin{exercise}
\label{exe.19fla-mt2.ev1}Find the eigenvalues and the eigenvectors of the
$3\times3$-matrix $\left(
\begin{array}
[c]{ccc}%
0 & 1 & 0\\
1 & 0 & 1\\
0 & 1 & 0
\end{array}
\right)  $.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt2.ev1}.]Let $A$ denote this $3\times
3$-matrix. Then, the characteristic polynomial of $A$ is%
\begin{align*}
\chi_{A}\left(  t\right)   &  =\det\left(  A-tI_{3}\right)  =\det\left(
\begin{array}
[c]{ccc}%
-t & 1 & 0\\
1 & -t & 1\\
0 & 1 & -t
\end{array}
\right)  \\
&  =2t-t^{3}\ \ \ \ \ \ \ \ \ \ \left(  \text{this is easy to check by
expanding the determinant}\right)  \\
&  =t\underbrace{\left(  2-t^{2}\right)  }_{=\left(  \sqrt{2}-t\right)
\left(  \sqrt{2}+t\right)  }=t\left(  \sqrt{2}-t\right)  \left(  \sqrt
{2}+t\right)  .
\end{align*}
Hence, the roots of $\chi_{A}\left(  t\right)  $ are $0,\sqrt{2},-\sqrt{2}$.

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
$0,\sqrt{2},-\sqrt{2}$. Hence, the eigenvalues of $A$ are $0,\sqrt{2}%
,-\sqrt{2}$.

It remains to find the eigenvectors. This is an easy matter of solving systems
of linear equations:

\begin{itemize}
\item The $0$-eigenvectors of $A$ are the nonzero vectors $v\in\mathbb{R}^{3}$
satisfying $Av=0v$. 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)  =0\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=-z\\
y=0
\end{array}
\right.  $ (where $z$ is a free variable). Thus, they are the nonzero scalar
multiples of the vector $\left(
\begin{array}
[c]{c}%
-1\\
0\\
1
\end{array}
\right)  $.

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

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

\cleardoublepage


\begin{exercise}
\label{exe.19fla-mt2.ev2}Consider the matrix $A=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
1 & 2 & 0 & 0\\
0 & 2 & 3 & 0\\
0 & 0 & 3 & 4
\end{array}
\right)  $. Here are four eigenvectors of $A$:%
\[
\left(
\begin{array}
[c]{c}%
0\\
0\\
-1\\
3
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
0\\
1\\
-2\\
3
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
0\\
0\\
0\\
1
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
-1\\
1\\
-1\\
1
\end{array}
\right)  .
\]


\textbf{(a)} What are the eigenvalues corresponding to these four eigenvectors?

\textbf{(b)} Find a diagonalization of $A$ -- that is, a pair $\left(
U,D\right)  $ of an invertible matrix $U$ and a diagonal matrix $D$ such that
$A=UDU^{-1}$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt2.ev2}.]\textbf{(a)} Let us denote
these four eigenvectors by $u_{1},u_{2},u_{3},u_{4}$, in the order in which
they are given. Let $\lambda_{1},\lambda_{2},\lambda_{3},\lambda_{4}$ be the
corresponding eigenvalues of $A$.

What is the quickest way to find $\lambda_{1}$ ? We must have $Au_{1}%
=\lambda_{1}u_{1}$ (since $u_{1}$ is a $\lambda_{1}$-eigenvector of $A$). In
view of $A=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
1 & 2 & 0 & 0\\
0 & 2 & 3 & 0\\
0 & 0 & 3 & 4
\end{array}
\right)  $ and $u_{1}=\left(
\begin{array}
[c]{c}%
0\\
0\\
-1\\
3
\end{array}
\right)  $, this rewrites as%
\[
\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
1 & 2 & 0 & 0\\
0 & 2 & 3 & 0\\
0 & 0 & 3 & 4
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
0\\
0\\
-1\\
3
\end{array}
\right)  =\lambda_{1}\left(
\begin{array}
[c]{c}%
0\\
0\\
-1\\
3
\end{array}
\right)  .
\]
Multiplying the left hand side of this equation out, we rewrite it as
\[
\left(
\begin{array}
[c]{c}%
0\\
0\\
-3\\
9
\end{array}
\right)  =\lambda_{1}\left(
\begin{array}
[c]{c}%
0\\
0\\
-1\\
3
\end{array}
\right)  .
\]
By comparing the $4$-th entries on the vectors of both sides of this equality,
we obtain $9=\lambda_{1}\cdot3$. Solving this for $\lambda_{1}$, we find
$\lambda_{1}=3$.

[Note that you don't even need to fully multiply the left hand side out to see
this! Just find one nonzero entry of the product, and compare it with the
corresponding entry on the right hand side.]

Similarly, we can find $\lambda_{2}=2$ and $\lambda_{3}=4$ and $\lambda_{4}%
=1$. Thus, the eigenvalues corresponding to our four eigenvectors are
$3,2,4,1$ (in this order).

\textbf{(b)} The four eigenvectors $u_{1},u_{2},u_{3},u_{4}$ of $A$ correspond
to the four distinct eigenvalues $\lambda_{1},\lambda_{2},\lambda_{3}%
,\lambda_{4}$ (indeed, these four eigenvalues are distinct, because they equal
$3,2,4,1$, as we have just observed). Thus, 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} shows that $u_{1},u_{2},u_{3},u_{4}$ form a basis of
$\mathbb{R}^{4}$.

Hence, the $4$-tuple $\left(  u_{1},u_{2},u_{3},u_{4}\right)  $ is a basis of
$\mathbb{R}^{4}$ that consists of eigenvectors of $A$, and $\lambda
_{1},\lambda_{2},\lambda_{3},\lambda_{4}$ 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}\mid u_{4}\right]  =\left(
\begin{array}
[c]{cccc}%
0 & 0 & 0 & -1\\
0 & 1 & 0 & 1\\
-1 & -2 & 0 & -1\\
3 & 3 & 1 & 1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\\
D  &  =\operatorname*{diag}\left(  \lambda_{1},\lambda_{2},\lambda_{3}%
,\lambda_{4}\right)  =\operatorname*{diag}\left(  3,2,4,1\right)  =\left(
\begin{array}
[c]{cccc}%
3 & 0 & 0 & 0\\
0 & 2 & 0 & 0\\
0 & 0 & 4 & 0\\
0 & 0 & 0 & 1
\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}$).
\end{proof}

\begin{noncompile}
$A=\left(
\begin{array}
[c]{cccc}%
1 & 0 & 0 & 0\\
1 & 2 & 0 & 0\\
0 & 2 & 3 & 0\\
0 & 0 & 3 & 4
\end{array}
\right)  $

$U=\left(
\begin{array}
[c]{cccc}%
0 & 0 & 0 & -1\\
0 & 1 & 0 & 1\\
-1 & -2 & 0 & -1\\
3 & 3 & 1 & 1
\end{array}
\right)  $

$D=\left(
\begin{array}
[c]{cccc}%
3 & 0 & 0 & 0\\
0 & 2 & 0 & 0\\
0 & 0 & 4 & 0\\
0 & 0 & 0 & 1
\end{array}
\right)  $
\end{noncompile}

\cleardoublepage


\begin{exercise}
\label{exe.19fla-mt2.ev3}Let $a,b,c,x,y,z$ be six reals. Let $A$ be the
$3\times3$-matrix%
\[
\left(
\begin{array}
[c]{ccc}%
ax & ay & az\\
bx & by & bz\\
cx & cy & cz
\end{array}
\right)  .
\]


\textbf{(a)} Explain why $ax+by+cz$ is an eigenvalue of $A$, and find a
corresponding eigenvector.

\textbf{(b)} Assume that $a,b,c,x,y,z$ are nonzero. Find a $0$-eigenvector of
$A$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt2.ev3}.]\textbf{(a)} It clearly
suffices to find an $\left(  ax+by+cz\right)  $-eigenvector of $A$, because if
such an eigenvector exists, then $ax+by+cz$ will be an eigenvalue of $A$ (by
the definition of \textquotedblleft eigenvalue\textquotedblright).

If $a,b,c$ are all $0$, then an $\left(  ax+by+cz\right)  $-eigenvector of $A$
is easy to find, because \textbf{any} nonzero vector in $\mathbb{R}^{3}$ is an
$\left(  ax+by+cz\right)  $-eigenvector of $A$ in this
case\footnote{\textit{Proof.} Assume that $a,b,c$ are all $0$. Then, $A$ is
the zero matrix, and therefore $Av=0=0v$ for each $v\in\mathbb{R}^{3}$. Hence,
any nonzero vector in $\mathbb{R}^{3}$ is a $0$-eigenvector of $A$. In other
words, any nonzero vector is an $\left(  ax+by+cz\right)  $-eigenvector of $A$
(since $\underbrace{a}_{=0}x+\underbrace{b}_{=0}y+\underbrace{c}%
_{=0}z=0x+0y+0z=0$). Qed.}. Thus, for the rest of this proof, we WLOG assume
that $a,b,c$ are not all $0$. Hence, the vector $\left(
\begin{array}
[c]{c}%
a\\
b\\
c
\end{array}
\right)  \in\mathbb{R}^{3}$ is nonzero.

The vector $\left(
\begin{array}
[c]{c}%
a\\
b\\
c
\end{array}
\right)  $ is an $\left(  ax+by+cz\right)  $-eigenvector of $A$, since it is
nonzero and satisfies%
\begin{align*}
A\left(
\begin{array}
[c]{c}%
a\\
b\\
c
\end{array}
\right)   &  =\left(
\begin{array}
[c]{ccc}%
ax & ay & az\\
bx & by & bz\\
cx & cy & cz
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
a\\
b\\
c
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
a^{2}x+aby+acz\\
b^{2}y+abx+bcz\\
c^{2}z+acx+bcy
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{c}%
\left(  ax+by+cz\right)  a\\
\left(  ax+by+cz\right)  b\\
\left(  ax+by+cz\right)  c
\end{array}
\right)  =\left(  ax+by+cz\right)  \left(
\begin{array}
[c]{c}%
a\\
b\\
c
\end{array}
\right)  .
\end{align*}
Hence, we have found an $\left(  ax+by+cz\right)  $-eigenvector of $A$.

\textbf{(b)} The vector $\left(
\begin{array}
[c]{c}%
0\\
z\\
-y
\end{array}
\right)  $ is nonzero (since $y$ is nonzero) and satisfies%
\[
A\left(
\begin{array}
[c]{c}%
a\\
b\\
c
\end{array}
\right)  =\left(
\begin{array}
[c]{ccc}%
ax & ay & az\\
bx & by & bz\\
cx & cy & cz
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
0\\
z\\
-y
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
0\\
0\\
0
\end{array}
\right)  =0\left(
\begin{array}
[c]{c}%
0\\
z\\
-y
\end{array}
\right)  .
\]
In other words, this vector is a $0$-eigenvector of $A$.

[\textit{Remark:} Many answers are possible in part \textbf{(b)}. In
particular, all three vectors $\left(
\begin{array}
[c]{c}%
0\\
z\\
-y
\end{array}
\right)  $, $\left(
\begin{array}
[c]{c}%
-z\\
0\\
x
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{c}%
y\\
-x\\
0
\end{array}
\right)  $ as well as all their nonzero linear combinations are $0$%
-eigenvectors of $A$.

Note that our above argument only used the assumption that $y$ is nonzero (not
that the rest of $a,b,c,x,z$ are nonzero). Likewise, we can solve the problem
if $x$ is nonzero or if $z$ is nonzero. On the other hand, if all of $x,y,z$
are zero, then $A=0_{3\times3}$, and thus every nonzero vector in
$\mathbb{R}^{3}$ is a $0$-eigenvector of $A$.]
\end{proof}

\cleardoublepage


\begin{exercise}
\label{exe.19fla-mt2.evTF}True or false? \textbf{No justifications are
required in this exercise. Just write Y or N into the respective box!}

\bigskip

\textbf{(a)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} An $n\times n$-matrix $A$ is invertible if and only if $0$ is an
eigenvalue of $A$.

\bigskip

\textbf{(b)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} An $n\times n$-matrix $A$ is invertible if and only if $0$ is not an
eigenvalue of $A$.

\bigskip

\textbf{(c)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} The column vector $e_{1}=\left(
\begin{array}
[c]{c}%
1\\
0\\
0\\
\vdots\\
0
\end{array}
\right)  \in\mathbb{R}^{n}$ is an eigenvector of every upper-triangular
$n\times n$-matrix.

\bigskip

\textbf{(d)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} The column vector $e_{n}=\left(
\begin{array}
[c]{c}%
0\\
0\\
\vdots\\
0\\
1
\end{array}
\right)  \in\mathbb{R}^{n}$ is an eigenvector of every upper-triangular
$n\times n$-matrix.

\bigskip

\textbf{(e)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} If $\lambda$ is an eigenvalue of two $n\times n$-matrices $A$ and $B$,
then $\lambda$ is an eigenvalue of $A+B$ as well.

\bigskip

\textbf{(f)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} If $v$ is an eigenvector of two $n\times n$-matrices $A$ and $B$, then $v$
is an eigenvector of $A+B$ as well.

\bigskip

\textbf{(g)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} If an $n\times n$-matrix $A$ has $n$ distinct eigenvalues, then it is diagonalizable.

\bigskip

\textbf{(h)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} If two $n\times n$-matrices $A$ and $B$ have the same characteristic
polynomial (that is, $\chi_{A}\left(  t\right)  =\chi_{B}\left(  t\right)  $),
then $\det A=\det B$.

\bigskip

\textbf{(i)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} If all diagonal entries of an $n\times n$-matrix $A$ are $0$, then $\det
A=0$.

\bigskip

\textbf{(j)} \fbox{$\phantom{\left(
ww\dfrac{w}{w}www
\right)  .
}$} If all off-diagonal entries of an $n\times n$-matrix $A$ are $0$, then
$\det A=0$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.19fla-mt2.evTF}.]\textbf{(a)} \textbf{NO.}

\textit{Proof.} The identity matrix $I_{n}$ is invertible, but $0$ is not
among its eigenvalues (indeed, the only eigenvalue of $I_{n}$ is $1$, since
$I_{n}v=v=1v$ for each $v\in\mathbb{R}^{n}$).

\bigskip

\textbf{(b)} \textbf{YES}.

\textit{Proof.} Let $A$ be an $n\times n$-matrix. 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}).

We have $\chi_{A}\left(  t\right)  =\det\left(  A-tI_{n}\right)  $ (by the
definition of $\chi_{A}$). Substituting $0$ for $t$ in this equality, we find
$\chi_{A}\left(  0\right)  =\det\underbrace{\left(  A-0I_{n}\right)  }%
_{=A}=\det A$.

Theorem 1.4.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{the class
notes from 2019-10-30} shows that $A$ is invertible if and only if $\det
A\neq0$. Thus, we have the following chain of equivalences:%
\begin{align*}
\left(  A\text{ is invertible}\right)  \  &  \Longleftrightarrow\ \left(  \det
A\neq0\right) \\
&  \Longleftrightarrow\ \left(  \chi_{A}\left(  0\right)  \neq0\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\det A=\chi_{A}\left(  0\right)
\right) \\
&  \Longleftrightarrow\ \left(  0\text{ is not a root of the polynomial }%
\chi_{A}\left(  t\right)  \right) \\
&  \Longleftrightarrow\ \left(  0\text{ is not an eigenvalue of }A\right)
\end{align*}
(since the eigenvalues of $A$ are the roots of $\chi_{A}\left(  t\right)  $).
Thus, $A$ is invertible if and only if $0$ is not an eigenvalue of $A$. This
proves the claim of part \textbf{(b)}.

\bigskip

\textbf{(c)} \textbf{YES}.

\textit{Proof.} Let us just prove this in the case when $n=3$: Let $A$ be any
upper-triangular $3\times3$-matrix. Then, we can write $A$ in the form
$A=\left(
\begin{array}
[c]{ccc}%
a & b & c\\
0 & b^{\prime} & c^{\prime}\\
0 & 0 & c^{\prime\prime}%
\end{array}
\right)  $ for some reals $a,b,c,b^{\prime},c^{\prime},c^{\prime\prime}$.
Thus, we have%
\begin{align*}
Ae_{1}  &  =\left(
\begin{array}
[c]{ccc}%
a & b & c\\
0 & b^{\prime} & c^{\prime}\\
0 & 0 & c^{\prime\prime}%
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
1\\
0\\
0
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }e_{1}=\left(
\begin{array}
[c]{c}%
1\\
0\\
0
\end{array}
\right)  \right) \\
&  =\left(
\begin{array}
[c]{c}%
a\cdot1+b\cdot0+c\cdot0\\
0\cdot1+b^{\prime}\cdot0+c^{\prime}\cdot0\\
0\cdot1+0\cdot0+0\cdot c^{\prime\prime}%
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
a\\
0\\
0
\end{array}
\right)  =a\underbrace{\left(
\begin{array}
[c]{c}%
1\\
0\\
0
\end{array}
\right)  }_{=e_{1}}=ae_{1}.
\end{align*}
This shows that $e_{1}$ is an $a$-eigenvector of $A$ (since $e_{1}$ is
nonzero). Thus, $e_{1}$ is an eigenvector of $A$.

The same argument works for all $n$ (except that the matrices become larger).
Alternative, you may recall that $Ae_{1}=\operatorname{col}_{1}A$ (as a
consequence of Exercise 4 \textbf{(b)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/hw1s.pdf}{homework set
\#1}), and use this to show that $Ae_{1}=A_{1,1}e_{1}$ whenever $A$ is
upper-triangular. Either way, the claim of part \textbf{(c)} is proved.

\bigskip

\textbf{(d)} \textbf{NO}.

\textit{Proof.} Just check that this fails for the upper-triangular matrix
$\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 1
\end{array}
\right)  $ when $n=2$. (Indeed, $\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 1
\end{array}
\right)  e_{n}=\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
0\\
1
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
1\\
1
\end{array}
\right)  $ is not a scalar multiple of $e_{n}$.)

\bigskip

\textbf{(e)} \textbf{NO}.

\textit{Proof.} The number $1$ is an eigenvalue of the $1\times1$-matrices
$\left(
\begin{array}
[c]{c}%
1
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{c}%
1
\end{array}
\right)  $, but is not an eigenvalue of their sum $\left(
\begin{array}
[c]{c}%
1
\end{array}
\right)  +\left(
\begin{array}
[c]{c}%
1
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
2
\end{array}
\right)  $.

\bigskip

\textbf{(f)} \textbf{YES}.

\textit{Proof.} Let $A$ and $B$ be two $n\times n$-matrices. Let
$v\in\mathbb{R}$ be an eigenvector of both matrices $A$ and $B$. Let $\lambda$
and $\mu$ be the corresponding eigenvalues (so that $v$ is a $\lambda
$-eigenvector of $A$ and a $\mu$-eigenvector of $B$). Thus, $Av=\lambda v$ and
$Bv=\mu v$. Adding these two equalities together, we obtain $Av+Bv=\lambda
v+\mu v=\left(  \lambda+\mu\right)  v$. Hence, $\left(  A+B\right)
v=Av+Bv=\left(  \lambda+\mu\right)  v$. Since $v$ is nonzero (because $v$ is
an eigenvector of $A$), this shows that $v$ is a $\left(  \lambda+\mu\right)
$-eigenvector of $A+B$. Hence, $v$ is an eigenvector of $A+B$. This proves the
claim of part \textbf{(f)} of the exercise.

\bigskip

\textbf{(g)} \textbf{YES}.

\textit{Proof.} Let $A$ be an $n\times n$-matrix that has $n$ distinct
eigenvalues. Let $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$ be these
eigenvalues. For each $i\in\left\{  1,2,\ldots,n\right\}  $, there exists a
$\lambda_{i}$-eigenvector $u_{i}$ (by the definition of an eigenvalue);
consider this $u_{i}$. Thus, 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} shows that $u_{1},u_{2},\ldots,u_{n}$ form a basis of
$\mathbb{R}^{n}$. Thus, $\left(  u_{1},u_{2},\ldots,u_{n}\right)  $ is a basis
of $\mathbb{R}^{n}$ that consists of eigenvectors of $A$. 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}. Thus, $A$ has a diagonalization, i.e., is
diagonalizable. This proves the claim of part \textbf{(g)}.

\bigskip

\textbf{(h)} \textbf{YES}.

\textit{Proof.} Let $A$ and $B$ be two matrices that have the same
characteristic polynomial (that is, $\chi_{A}\left(  t\right)  =\chi
_{B}\left(  t\right)  $).

We have $\chi_{A}\left(  t\right)  =\det\left(  A-tI_{n}\right)  $ (by the
definition of $\chi_{A}$). Substituting $0$ for $t$ in this equality, we find
$\chi_{A}\left(  0\right)  =\det\underbrace{\left(  A-0I_{n}\right)  }%
_{=A}=\det A$. Likewise, $\chi_{B}\left(  0\right)  =\det B$. But substituting
$0$ for $t$ in the equality $\chi_{A}\left(  t\right)  =\chi_{B}\left(
t\right)  $, we obtain $\chi_{A}\left(  0\right)  =\chi_{B}\left(  0\right)
$. In view of $\chi_{A}\left(  0\right)  =\det A$ and $\chi_{B}\left(
0\right)  =\det B$, this rewrites as $\det A=\det B$. This proves the claim of
part \textbf{(h)}.

\bigskip

\textbf{(i)} \textbf{NO}.

\textit{Proof.} All diagonal entries of the $2\times2$-matrix $\left(
\begin{array}
[c]{cc}%
0 & 1\\
1 & 0
\end{array}
\right)  $ are $0$, yet the determinant of this matrix is $-1\neq0$.

\bigskip

\textbf{(j)} \textbf{NO}.

\textit{Proof.} All off-diagonal entries of the $2\times2$-matrix $\left(
\begin{array}
[c]{cc}%
1 & 0\\
0 & 1
\end{array}
\right)  $ are $0$, yet the determinant of this matrix is $1\neq0$.
\end{proof}

\cleardoublepage



\end{document}