\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{tikz}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{wasysym}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Tuesday, November 12, 2019 00:58:19}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{ComputeDefs=
%$A=\left(
%\begin{array}
%[c]{cc}%
%0 & 1\\
%1 & 1
%\end{array}
%\right)  $
%$\phi=\dfrac{1+\sqrt{5}}{2}$
%}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows}
\newcounter{exer}
\newcounter{exera}
\numberwithin{exer}{subsection}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[subsection]
\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{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{teachingnote}[1][Teaching note]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\newenvironment{teachingnote}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\excludecomment{teachingnote}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\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{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\lf}[2]{#1^{\underline{#2}}}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\nnn}{\nonumber\\}
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}}
\allowdisplaybreaks
\iffalse
\UNEXPAND{\today}{\today}
\fi
\ihead{Fall 2019 Math 201-003 at Drexel: blackboard notes of 2019-11-06}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{Fall 2019 Math 201-003 at Drexel: blackboard notes of 2019-11-06}
\author{Darij Grinberg}
\date{\today}
\maketitle

\section{Eigenvalues and eigenvectors (\textquotedblleft
eigenstuff\textquotedblright)}

\subsection{Definition and examples (recall)}

Recall some material from last time:

\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$.
\end{definition}

\begin{definition}
Let $A$ be an $n\times n$-matrix. We define%
\[
\chi_{A}\left(  t\right)  =\det\left(  A-tI_{n}\right)  .
\]
This is a polynomial in $t$, and is called the \textbf{characteristic
polynomial} of $A$.
\end{definition}

\begin{proposition}
Let $A$ be an $n\times n$-matrix. Then, the eigenvalues of $A$ are the roots
of the characteristic polynomial $\chi_{A}\left(  t\right)  $.
\end{proposition}

\begin{proposition}
\label{prop.eigen.triang}If a matrix $A$ is triangular, then its eigenvalues
are its diagonal entries.
\end{proposition}

\textbf{Method for finding eigenvalues and eigenvectors of a matrix:}

Given an $n\times n$-matrix $A$, find all eigenvalues and eigenvectors of $A$
as follows:

\begin{itemize}
\item Calculate the characteristic polynomial $\chi_{A}\left(  t\right)
=\det\left(  A-tI_{n}\right)  $ of $A$.

\item Find all roots $\lambda_{1},\lambda_{2},\ldots,\lambda_{k}$ of $\chi
_{A}\left(  t\right)  $. These are the eigenvalues of $A$.

\item For each eigenvalue $\lambda_{i}$, compute the nonzero solutions to
$\left(  A-\lambda_{i}I_{n}\right)  v=0$ (for example, using Gaussian
elimination). These are the $\lambda_{i}$-eigenvectors of $A$.
\end{itemize}

\subsection{The characteristic polynomial, explicitly}

The following theorem gives a more-or-less explicit formula for the
coefficients of the characteristic polynomial of a matrix. It is \textbf{not}
a great way of computing them (too much work), but it can help double-check them.

\begin{theorem}
\label{thm.charpoly.coeffs}Let $A$ be an $n\times n$-matrix. Then, its
characteristic polynomial $\chi_{A}\left(  t\right)  $ is a polynomial of
degree $n$, and equals%
\[
\chi_{A}\left(  t\right)  =c_{0}+c_{1}t+c_{2}t^{2}+\cdots+c_{n}t^{n},
\]
where

\begin{itemize}
\item $c_{0}=\det A$.

\item $c_{n}=\left(  -1\right)  ^{n}$.

\item $c_{n-1}=\left(  -1\right)  ^{n-1}\operatorname*{Tr}A$. (Recall:
$\operatorname*{Tr}A$ is the trace of $A$, as defined on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/hw1s.pdf}{homework set \#1}.)

\item For each $k\in\left\{  0,1,\ldots,n\right\}  $, we have
\[
c_{k}=\left(  -1\right)  ^{k}\cdot\left(
\begin{array}
[c]{c}%
\text{the sum of the determinants of all submatrices}\\
\text{of }A\text{ obtained from }A\text{ by removing }k\text{ rows}\\
\text{and the corresponding }k\text{ columns}%
\end{array}
\right)  .
\]
(Here, \textquotedblleft corresponding $k$ columns\textquotedblright\ means
\textquotedblleft the $k$ columns with the same indices as the removed $k$
rows\textquotedblright. So, for example, if we remove rows $2$ and $5$, then
we must remove columns $2$ and $5$.)
\end{itemize}
\end{theorem}

Instead of a formal proof, let us confirm this theorem on an example:

\begin{proof}
[Proof of Theorem \ref{thm.charpoly.coeffs} for $n=3$.]Assume that $n=3$.
Write $A$ as $A=\left(
\begin{array}
[c]{ccc}%
a & b & c\\
d & e & f\\
g & h & i
\end{array}
\right)  $. Then, the definition of $\chi_{A}\left(  t\right)  $ yields%
\begin{align*}
\chi_{A}\left(  t\right)   &  =\det\left(  A-tI_{n}\right)  =\det\left(
\begin{array}
[c]{ccc}%
a-t & b & c\\
d & e-t & f\\
g & h & i-t
\end{array}
\right) \\
&  =\left(  a-t\right)  \left(  e-t\right)  \left(  i-t\right)
+bfg+cdh-\left(  a-t\right)  fh-c\left(  e-t\right)  g-bd\left(  i-t\right) \\
&  =\left(  aei-\left(  ae+ai+ei\right)  t+\left(  a+e+i\right)  t^{2}%
-t^{3}\right) \\
&  \ \ \ \ \ \ \ \ \ \ +bfg+cdh+\left(  afh-fht\right)  -\left(
ceg-cgt\right)  -\left(  bdi-bdt\right) \\
&  =\underbrace{\left(  aei+bfg+cdh-afh-ceg-bdi\right)  }_{\substack{=\det
\left(
\begin{array}
[c]{ccc}%
a & b & c\\
d & e & f\\
g & h & i
\end{array}
\right)  \\=\det A}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  ae+ai+ei-fh-cg-bd\right)
}_{\substack{=\left(  ae-bd\right)  +\left(  ai-cg\right)  +\left(
ei-fh\right)  \\=\left(
\begin{array}
[c]{c}%
\text{the sum of the determinants of all}\\
\text{submatrices obtained from }A\text{ by removing}\\
\text{one row and the corresponding column}%
\end{array}
\right)  }}t\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  a+e+i\right)  }%
_{=\operatorname*{Tr}A}t^{2}-t^{3}.
\end{align*}
This confirms the theorem for $n=3$.
\end{proof}

\begin{remark}
Many authors define $\chi_{A}\left(  t\right)  $ not as $\det\left(
A-tI_{n}\right)  $ (as we did), but instead as $\det\left(  tI_{n}-A\right)
$. This does not change much (in particular, this does not change the roots of
$\chi_{A}\left(  t\right)  $), because%
\[
\det\left(  tI_{n}-A\right)  =\left(  -1\right)  ^{n}\cdot\det\left(
A-tI_{n}\right)  .
\]

\end{remark}

\begin{proof}
Recall the fact (Corollary 1.5.3 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-30.pdf}{classwork
from 2019-10-30}) that says that if $B$ is an $n\times n$-matrix, and if
$\lambda$ is a scalar, then $\det\left(  \lambda B\right)  =\lambda^{n}\det
B$. Applying this to $\lambda=-1$ and $B=A-tI_{n}$, we obtain $\det\left(
\left(  -1\right)  \left(  A-tI_{n}\right)  \right)  =\left(  -1\right)
^{n}\cdot\det\left(  A-tI_{n}\right)  $. Since $\left(  -1\right)  \left(
A-tI_{n}\right)  =tI_{n}-A$, this rewrites as $\det\left(  tI_{n}-A\right)
=\left(  -1\right)  ^{n}\cdot\det\left(  A-tI_{n}\right)  $.
\end{proof}

\subsection{Linear independence of eigenvectors}

Eigenvectors become particularly useful when we have many of them and they are
linearly independent. Let us take this for a given for now (we will later see
how they are useful), and see some ways to quickly get lots of linearly
independent eigenvectors.

We begin with the following fact (\cite[Proposition 13.19]{Strickland}):

\begin{proposition}
\label{prop.eigenvecs.indep1}Let $A$ be a $n\times n$-matrix. Let $\lambda
_{1},\lambda_{2},\ldots,\lambda_{k}$ be $k$ distinct eigenvalues of $A$. For
each $i\in\left\{  1,2,\ldots,k\right\}  $, let $v_{i}$ be a $\lambda_{i}%
$-eigenvector of $A$. Then, $v_{1},v_{2},\ldots,v_{k}$ are linearly independent.
\end{proposition}

\begin{proof}
See \cite[Proposition 13.19]{Strickland}.
\end{proof}

Proposition \ref{prop.eigenvecs.indep1} says that a list of eigenvectors of
the same matrix is automatically linearly independent if they belong to
distinct eigenvalues. There is an even stronger result (\cite[Remark
13.21]{Strickland}, proved in his exercises), which shows linear independence
even if some of the eigenvectors belong to the same eigenvalue, as long as the
eigenvectors to each eigenvalue are linearly independent among themselves.
Here is the precise statement:

\begin{proposition}
\label{prop.eigenvecs.indep2}Let $A$ be a $n\times n$-matrix. Let $\lambda
_{1},\lambda_{2},\ldots,\lambda_{k}$ be $k$ distinct eigenvalues of $A$. For
each $i\in\left\{  1,2,\ldots,k\right\}  $, let $v_{i,1},v_{i,2}%
,\ldots,v_{i,h_{i}}$ be some linearly independent $\lambda_{i}$-eigenvectors
of $A$. Then, the list
\begin{align*}
&  \underbrace{v_{1,1},v_{1,2},\ldots,v_{1,h_{1}}}_{\text{eigenvectors for
}\lambda_{1}},\\
&  \underbrace{v_{2,1},v_{2,2},\ldots,v_{2,h_{2}}}_{\text{eigenvectors for
}\lambda_{2}},\\
&  \ldots,\\
&  \underbrace{v_{k,1},v_{k,2},\ldots,v_{k,h_{k}}}_{\text{eigenvectors for
}\lambda_{k}}%
\end{align*}
(obtained by throwing all our eigenvectors for different eigenvalues together)
is a list of linearly independent vectors.
\end{proposition}

The next fact is \cite[Proposition 13.22]{Strickland}:

\begin{proposition}
\label{prop.eigenvecs.basis}Let $A$ be an $n\times n$-matrix that has $n$
distinct eigenvalues $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$. For each
$i\in\left\{  1,2,\ldots,n\right\}  $, let $v_{i}$ be a $\lambda_{i}%
$-eigenvector of $A$. Then, $v_{1},v_{2},\ldots,v_{n}$ form a basis of
$\mathbb{R}^{n}$.
\end{proposition}

\begin{proof}
Proposition \ref{prop.eigenvecs.indep1} yields that $v_{1},v_{2},\ldots,v_{n}$
are linearly independent. But they are $n$ vectors in $\mathbb{R}^{n}$, so as
we have learned, this means that they form a basis of $\mathbb{R}^{n}$.
\end{proof}

How often is the assumption of the proposition satisfied? In other words, how
likely is it for an $n\times n$-matrix $A$ to have $n$ distinct eigenvalues?
Here are some informal answers:

\begin{itemize}
\item If we content ourselves with \textbf{complex} eigenvalues, then
\textquotedblleft almost every\textquotedblright\ $n\times n$-matrix $A$ has
$n$ distinct eigenvalues. In other words, a \textquotedblleft randomly
chosen\textquotedblright\ $n\times n$-matrix $A$ has $n$ distinct eigenvalues.
This is not a rigorous statement at this point.

\item For a matrix $A$ that comes from a mathematical problem (a matrix with
\textquotedblleft meaning\textquotedblright), it may very well happen that $A$
does not have $n$ distinct eigenvalues. Some of the most \textquotedblleft
interesting\textquotedblright\ matrices do not have $n$ distinct eigenvalues.

\item If we want real eigenvalues, it happens fairly often that an $n\times
n$-matrix has less than $n$ of them. It may even happen that it has none.
\end{itemize}

For example, here is a \href{https://xkcd.com/221/}{\textquotedblleft randomly
chosen\textquotedblright} $3\times3$-matrix: $\left(
\begin{array}
[c]{ccc}%
5 & 1 & 3\\
9 & 7 & 6\\
2 & -3 & 0
\end{array}
\right)  $. Its characteristic polynomial: $-t^{3}+12t^{2}-38t-21$. Its roots
(i.e., the eigenvalues of the matrix) are (approximately) $6.\,\allowbreak
238\,9-2.\,\allowbreak244\,4i,\ 6.\,\allowbreak238\,9+2.\,\allowbreak
244\,4i,\ -0.477\,7\allowbreak$. The first two are non-real complex numbers;
only the third is a real number. There are no good exact formulas for these
roots, because $-t^{3}+12t^{2}-38t-21$ is an unremarkable degree-$3$
polynomial. (There is \href{http://web.mst.edu/~lmhall/3-Cardano.pdf}{a very
messy formula that involves both square and cube roots}, but you really don't
want to use that one.)

Let us do a few examples where we compute the eigenvalues and eigenvectors of
a matrix $A$ and attempt to form a basis out of the eigenvectors.

\begin{example}
Let $A=\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
0 & 2 & 2\\
0 & 0 & 3
\end{array}
\right)  $. Then, the eigenvalues of $A$ are $1,2,3$ (by Proposition
\ref{prop.eigen.triang}). Thus, Proposition \ref{prop.eigenvecs.basis} says
that if we pick one eigenvector for each eigenvalue, we obtain a basis of
$\mathbb{R}^{3}$. Let us do this:

\begin{itemize}
\item Let us find the $1$-eigenvectors. These 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)  =1\left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  $. Solving this, we find the eigenvector $\left(
\begin{array}
[c]{c}%
1\\
0\\
0
\end{array}
\right)  $.

\item Let us find the $2$-eigenvectors. These 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)  =2\left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  $. Solving this, we find the eigenvector $\left(
\begin{array}
[c]{c}%
1\\
1\\
0
\end{array}
\right)  $.

\item Let us find the $3$-eigenvectors. These 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)  =3\left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  $. Solving this, we find the eigenvector $\left(
\begin{array}
[c]{c}%
3\\
4\\
2
\end{array}
\right)  $.
\end{itemize}

Now, we have found three eigenvectors:%
\[
\left(
\begin{array}
[c]{c}%
1\\
0\\
0
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
1\\
1\\
0
\end{array}
\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
3\\
4\\
2
\end{array}
\right)  .
\]
Since these are eigenvectors for distinct eigenvalues, Proposition
\ref{prop.eigenvecs.basis} says that they form a basis of $\mathbb{R}^{3}$.
\end{example}

\begin{example}
Let $A=\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
0 & 1 & 1\\
0 & 0 & 1
\end{array}
\right)  $. Then, $\chi_{A}\left(  t\right)  =\left(  1-t\right)  ^{3}$. Thus,
the only eigenvalue is $1$. Thus, we cannot apply Proposition
\ref{prop.eigenvecs.basis}. But if we can find $3$ linearly independent
$1$-eigenvectors, then we can apply Proposition \ref{prop.eigenvecs.indep2}
(or simply recall that $3$ linearly independent vectors in $\mathbb{R}^{3}$
must always form a basis of $\mathbb{R}^{3}$). But can we find them?

The $1$-eigenvectors of $A$ are the nonzero vectors $\left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  $ such that $A\left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  =1\left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  $. These are the nonzero scalar multiples of $\left(
\begin{array}
[c]{c}%
1\\
0\\
0
\end{array}
\right)  $. Thus, any two of them are proportional. Hence, there are no $3$
linearly independent $1$-eigenvectors of $A$ (or even $2$ such). Thus, there
is no basis of $\mathbb{R}^{3}$ consisting of eigenvectors of $A$.
\end{example}

\begin{example}
Let $A=\left(
\begin{array}
[c]{ccc}%
0 & 0 & 1\\
0 & 1 & 0\\
1 & 0 & 0
\end{array}
\right)  $. Then,
\begin{align*}
\chi_{A}\left(  t\right)   &  =\det\left(  A-tI_{n}\right)  =\det\left(
\begin{array}
[c]{ccc}%
0-t & 0 & 1\\
0 & 1-t & 0\\
1 & 0 & 0-t
\end{array}
\right)  =\left(  1-t\right)  \underbrace{\det\left(
\begin{array}
[c]{cc}%
0-t & 1\\
1 & 0-t
\end{array}
\right)  }_{\substack{=\left(  0-t\right)  ^{2}-1^{2}\\=\left(  t+1\right)
\left(  t-1\right)  }}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Laplace expansion along the
}2\text{-nd row}\right) \\
&  =\left(  1-t\right)  \left(  t+1\right)  \left(  t-1\right)  =-\left(
t-1\right)  ^{2}\left(  t+1\right)  .
\end{align*}
So the eigenvalues of $A$ are $1$ and $-1$. So Proposition
\ref{prop.eigenvecs.basis} does not give us a basis of eigenvectors (since $1$
and $-1$ are only $2$ eigenvalues, not $3$). However, we still have a chance
of finding such a basis, if we find enough linearly independent eigenvectors.

\begin{itemize}
\item The $1$-eigenvectors of $A$ are the nonzero $\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)  =1\left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  $. These are all nonzero vectors of the form $\left(
\begin{array}
[c]{c}%
z\\
y\\
z
\end{array}
\right)  $. We can thus find two linearly independent $1$-eigenvectors:
namely, $\left(
\begin{array}
[c]{c}%
0\\
1\\
0
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{c}%
1\\
0\\
1
\end{array}
\right)  $.

\item The $\left(  -1\right)  $-eigenvectors of $A$ are the nonzero $\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(  -1\right)  \left(
\begin{array}
[c]{c}%
x\\
y\\
z
\end{array}
\right)  $. These are all nonzero vectors of the form $\left(
\begin{array}
[c]{c}%
-z\\
0\\
z
\end{array}
\right)  $. Thus, we can pick $\left(
\begin{array}
[c]{c}%
-1\\
0\\
1
\end{array}
\right)  $ as one of them.
\end{itemize}

Altogether, we can now conclude from Proposition \ref{prop.eigenvecs.indep2}
that%
\[
\underbrace{\left(
\begin{array}
[c]{c}%
0\\
1\\
0
\end{array}
\right)  ,\ \ \left(
\begin{array}
[c]{c}%
1\\
0\\
1
\end{array}
\right)  }_{\text{independent }1\text{-eigenvectors}},\ \ \underbrace{\left(
\begin{array}
[c]{c}%
-1\\
0\\
1
\end{array}
\right)  }_{\left(  -1\right)  \text{-eigenvector}}%
\]
form a basis of $\mathbb{R}^{3}$ consisting of eigenvectors. (Of course, you
can easily check this without invoking Proposition \ref{prop.eigenvecs.indep2}.)
\end{example}

\begin{example}
Let $A=\left(
\begin{array}
[c]{cc}%
0 & -1\\
1 & 0
\end{array}
\right)  $. The eigenvalues of $A$ in $\mathbb{R}$ don't exist at all (as we
have seen in Example 2.1.13 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-04.pdf}{classwork
from 2019-11-04}). Thus, there is no basis of $\mathbb{R}^{2}$ that consists
of eigenvectors of $A$. (But we can fix this by extending our number system to
the so-called \textbf{complex numbers}, which we will see next time.)
\end{example}

\begin{remark}
Let $n$ be odd. Then, every $n\times n$-matrix with real entries has
\textbf{at least one} real eigenvalue.
\end{remark}

\begin{proof}
Let $A$ be an $n\times n$-matrix. Then, its characteristic polynomial
$\chi_{A}\left(  t\right)  $ has odd degree (since it has degree $n$, which is
odd). But any real polynomial of odd degree has at least one real root. Thus,
$A$ has at least one real eigenvalue.
\end{proof}

\subsection{Diagonalization}

\subsubsection{Motivation}

\begin{example}
The \textbf{Fibonacci numbers} are a sequence $\left(  f_{0},f_{1}%
,f_{2},\ldots\right)  $ of nonnegative integers. They are defined recursively
by%
\[
f_{0}=0,\ \ \ \ \ \ \ \ \ \ f_{1}=1,\ \ \ \ \ \ \ \ \ \ f_{n}=f_{n-1}%
+f_{n-2}\ \ \ \ \ \ \ \ \ \ \text{for all }n\geq2.
\]


Here is a table of the first $9$ Fibonacci numbers:%
\[%
\begin{tabular}
[c]{|l||l|l|l|l|l|l|l|l|l|}\hline
$m$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$\\\hline
$f_{m}$ & $0$ & $1$ & $1$ & $2$ & $3$ & $5$ & $8$ & $13$ & $21$\\\hline
\end{tabular}
\ \ \ .
\]
You might wonder: Is there an explicit formula for $f_{m}$ ? Is there a faster
way to compute $f_{m}$ than working one's way up recursively? How fast does
$f_{m}$ grow?

One way to approach this is using matrices: Instead of computing $f_{m}$, let
us look at the vectors $\left(
\begin{array}
[c]{c}%
f_{m}\\
f_{m+1}%
\end{array}
\right)  $ for $m\geq0$. The nice thing about these vectors is that each of
them determines the next one:%
\[
\left(
\begin{array}
[c]{c}%
f_{m+1}\\
f_{m+2}%
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
f_{m+1}\\
f_{m+1}+f_{m}%
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
0 & 1\\
1 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
f_{m}\\
f_{m+1}%
\end{array}
\right)  =A\left(
\begin{array}
[c]{c}%
f_{m}\\
f_{m+1}%
\end{array}
\right)  ,
\]
where $A=\left(
\begin{array}
[c]{cc}%
0 & 1\\
1 & 1
\end{array}
\right)  $. Thus, for example,%
\begin{align*}
\left(
\begin{array}
[c]{c}%
f_{5}\\
f_{6}%
\end{array}
\right)   &  =A\left(
\begin{array}
[c]{c}%
f_{4}\\
f_{5}%
\end{array}
\right)  =AA\left(
\begin{array}
[c]{c}%
f_{3}\\
f_{4}%
\end{array}
\right)  =AAA\left(
\begin{array}
[c]{c}%
f_{2}\\
f_{3}%
\end{array}
\right)  =AAAA\left(
\begin{array}
[c]{c}%
f_{1}\\
f_{2}%
\end{array}
\right) \\
&  =AAAAA\left(
\begin{array}
[c]{c}%
f_{0}\\
f_{1}%
\end{array}
\right)  =A^{5}\left(
\begin{array}
[c]{c}%
f_{0}\\
f_{1}%
\end{array}
\right)  .
\end{align*}
More generally,%
\[
\left(
\begin{array}
[c]{c}%
f_{m}\\
f_{m+1}%
\end{array}
\right)  =A^{m}\left(
\begin{array}
[c]{c}%
f_{0}\\
f_{1}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }m\geq0.
\]
(Formally speaking, you can prove this by induction on $m$.) Thus, in order to
compute $f_{m}$, it suffices to compute $A^{m}$.
\end{example}

Now, how can we easily compute the $m$-th power of a matrix?

Let's look at diagonal matrices first. The product of two diagonal matrices is
given by simply multiplying their diagonal entries:%
\[
\left(
\begin{array}
[c]{cc}%
a & 0\\
0 & b
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
c & 0\\
0 & d
\end{array}
\right)  =\left(
\begin{array}
[c]{cc}%
ac & 0\\
0 & bd
\end{array}
\right)  .
\]
Thus, by induction, we see that a similar rule holds for taking a diagonal
matrix to a power:%
\[
\left(
\begin{array}
[c]{cc}%
a & 0\\
0 & b
\end{array}
\right)  ^{m}=\left(
\begin{array}
[c]{cc}%
a^{m} & 0\\
0 & b^{m}%
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }m\geq0.
\]
But our matrix $A$ is not diagonal! So this doesn't directly help us find
$A^{m}$.

But let's extend this trick to matrices that are not diagonal in themselves,
but have the form%
\[
UDU^{-1}\ \ \ \ \ \ \ \ \ \ \text{where }D\text{ is diagonal and }U\text{ is
invertible.}%
\]


For example:%
\begin{align*}
\left(  UDU^{-1}\right)  ^{2}  &  =UD\underbrace{U^{-1}U}_{=I}DU^{-1}%
=U\underbrace{DD}_{=D^{2}}U^{-1}=UD^{2}U^{-1};\\
\left(  UDU^{-1}\right)  ^{3}  &  =UD\underbrace{U^{-1}U}_{=I}%
D\underbrace{U^{-1}U}_{=I}DU^{-1}=U\underbrace{DDD}_{=D^{3}}U^{-1}%
=UD^{3}U^{-1};\\
\left(  UDU^{-1}\right)  ^{4}  &  =UD\underbrace{U^{-1}U}_{=I}%
D\underbrace{U^{-1}U}_{=I}D\underbrace{U^{-1}U}_{=I}DU^{-1}=U\underbrace{DDDD}%
_{=D^{4}}U^{-1}=UD^{4}U^{-1}.
\end{align*}
You can probably see how this sequence of equalities goes on; the result is
the following:\footnote{The notation $\operatorname*{diag}\left(  p_{1}%
,p_{2},\ldots,p_{n}\right)  $ stands for the diagonal $n\times n$-matrix whose
diagonal entries are $p_{1},p_{2},\ldots,p_{n}$ (from top-left to
bottom-right). For example, $\operatorname*{diag}\left(  2,9,4\right)
=\left(
\begin{array}
[c]{ccc}%
2 & 0 & 0\\
0 & 9 & 0\\
0 & 0 & 4
\end{array}
\right)  $.}

\begin{proposition}
\label{prop.diagonalization.power}Let $U$ be an invertible $n\times n$-matrix,
and let $D$ be any $n\times n$-matrix. Then,%
\[
\left(  UDU^{-1}\right)  ^{m}=UD^{m}U^{-1}.
\]
Thus, in particular, when $D=\operatorname*{diag}\left(  d_{1},d_{2}%
,\ldots,d_{n}\right)  $, then $D^{m}=\operatorname*{diag}\left(  d_{1}%
^{m},d_{2}^{m},\ldots,d_{n}^{m}\right)  $, so this becomes
\[
\left(  UDU^{-1}\right)  ^{m}=U\operatorname*{diag}\left(  d_{1}^{m},d_{2}%
^{m},\ldots,d_{n}^{m}\right)  U^{-1}.
\]

\end{proposition}

\begin{proof}
The first equality is easily proved by induction on $m$.
\end{proof}

Therefore, if we can write our matrix $A$ in the form $A=UDU^{-1}$ for an
invertible $U$ and a diagonal $D$, then we can easily compute any power of
$A$. In particular, if we can do this for $A=\left(
\begin{array}
[c]{cc}%
0 & 1\\
1 & 1
\end{array}
\right)  $, then we can find an explicit formula for $A^{m}$ and thus for the
Fibonacci number $f_{m}$.

\subsubsection{The method}

So how do we write a square matrix $A$ as $UDU^{-1}$ ? Is it possible at all?

This is known as \textbf{diagonalization}:

\begin{definition}
Let $A$ be an $n\times n$-matrix. A \textbf{diagonalization} of $A$ means a
pair of an invertible $n\times n$-matrix $U$ and a diagonal $n\times n$-matrix
$D$ such that $A=UDU^{-1}$.
\end{definition}

Note that $A=UDU^{-1}$ can be rewritten equivalently as $U^{-1}AU=D$.

Later, we will see what diagonalizing a matrix \textquotedblleft really
means\textquotedblright: A diagonalization of $A$ is an \textquotedblleft
alternative coordinate system\textquotedblright\ in which $A$
\textquotedblleft becomes a diagonal matrix\textquotedblright. For now, think
of this as a vague idea.

How do we find a diagonalization of a matrix $A$ ? The following fact
(\cite[Proposition 14.4]{Strickland}) is crucial:

\begin{proposition}
\label{prop.diagonalization.evals}Let $A$ be an $n\times n$-matrix.

\textbf{(a)} Suppose that $u_{1},u_{2},\ldots,u_{n}$ is a basis of
$\mathbb{R}^{n}$ that consists of eigenvectors of $A$. Let $\lambda
_{1},\lambda_{2},\ldots,\lambda_{n}$ be the corresponding eigenvalues (so each
$u_{i}$ is a $\lambda_{i}$-eigenvector). Note that some $\lambda_{i}$ may be equal.

Set $U=\left[  u_{1}\mid u_{2}\mid\cdots\mid u_{n}\right]  $ and
$D=\operatorname*{diag}\left(  \lambda_{1},\lambda_{2},\ldots,\lambda
_{n}\right)  $. Then, $U,D$ is a diagonalization of $A$ (that is, $U$ is
invertible, $D$ is diagonal, and $A=UDU^{-1}$).

\textbf{(b)} Conversely, each diagonalization of $A$ has this form. (In other
words, if $U,D$ is a diagonalization of $A$, then the columns of $U$ form a
basis of $\mathbb{R}^{n}$ that consists of eigenvectors of $A$, and the
diagonal entries of $D$ are the corresponding eigenvalues.)
\end{proposition}

We will prove and apply this next time.

\begin{thebibliography}{9999999999}                                                                                       %


\bibitem[Strickland]{Strickland}Neil Strickland, \textit{MAS201 Linear
Mathematics for Applications}, lecture notes, 28 September 2013.\newline\url{http://neil-strickland.staff.shef.ac.uk/courses/MAS201/}
\end{thebibliography}


\end{document}