\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 01:04:22}
%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}$
%$\psi=\dfrac{1-\sqrt{5}}{2}$
%$U=\left(
%\begin{array}
%[c]{ccc}%
%1 & 1 & 3\\
%0 & 1 & 4\\
%0 & 0 & 2
%\end{array}
%\right)  $
%$D=\left(
%\begin{array}
%[c]{ccc}%
%1 & 0 & 0\\
%0 & 2 & 0\\
%0 & 0 & 3
%\end{array}
%\right)  $
%}
%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-11}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

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

\subsection{Definition and examples (recall)}

Recall some material from last time and from the lecture before:

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

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

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

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

\subsection{Diagonalization}

\subsubsection{Motivation (recall)}

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.
\]


We have showed that%
\begin{equation}
\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\geq
0,\label{eq.fibonacci.by-mat}%
\end{equation}
where $A=\left(
\begin{array}
[c]{cc}%
0 & 1\\
1 & 1
\end{array}
\right)  $. Thus, in order to compute $f_{m}$, it suffices to compute $A^{m}$.

\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
\begin{equation}
\left(  UDU^{-1}\right)  ^{m}=U\operatorname*{diag}\left(  d_{1}^{m},d_{2}%
^{m},\ldots,d_{n}^{m}\right)  U^{-1}.\label{eq.prop.diagonalization.power.2}%
\end{equation}

\end{proposition}

\subsubsection{The method}

Recall the following definition:

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

We stated (but did not prove) the following proposition:

\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 still need to prove this. First, let us apply this to the Fibonacci sequence:

\begin{example}
Let $A=\left(
\begin{array}
[c]{cc}%
0 & 1\\
1 & 1
\end{array}
\right)  $ be the matrix that occurred in the computation of the Fibonacci
numbers. We want to obtain a diagonalization of $A$ (because this will help us
compute $A^{m}$ and thus $f_{m}$ for all $m\geq0$). Following Proposition
\ref{prop.diagonalization.evals} \textbf{(a)}, we try to achieve this by
finding a basis of $\mathbb{R}^{2}$ consisting of eigenvectors of $A$. So let
us find eigenvectors of $A$.

The characteristic polynomial of $A$ is $\chi_{A}\left(  t\right)
=\det\left(  A-tI_{n}\right)  =\det\left(
\begin{array}
[c]{cc}%
0-t & 1\\
1 & 1-t
\end{array}
\right)  =t^{2}-t-1$. So the eigenvalues of $A$ are the roots of $t^{2}-t-1$,
which are
\[
\dfrac{1+\sqrt{5}}{2}\approx1.\,618\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \dfrac{1-\sqrt{5}}{2}\approx-0.618\,.
\]
The first of these two roots is called the \textbf{golden ratio}. It is often
denoted $\phi$; it has the property that $\phi^{2}=\phi+1$, that is,
$\phi-1=1/\phi$. Let me denote the second root by $\psi$.

So
\[
\phi=\dfrac{1+\sqrt{5}}{2}\approx1.\,618\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \psi=\dfrac{1-\sqrt{5}}{2}\approx-0.618
\]
are the two eigenvalues of $A$. Now, let's look for eigenvectors:

\begin{itemize}
\item The $\phi$-eigenvectors of $A$ are the nonzero $\left(
\begin{array}
[c]{c}%
x\\
y
\end{array}
\right)  \in\mathbb{R}^{2}$ such that $A\left(
\begin{array}
[c]{c}%
x\\
y
\end{array}
\right)  =\phi\left(
\begin{array}
[c]{c}%
x\\
y
\end{array}
\right)  $. They are the nonzero multiples of $\left(
\begin{array}
[c]{c}%
-\psi\\
1
\end{array}
\right)  $. (You can find this by Gaussian elimination.)

\item The $\psi$-eigenvectors of $A$ are the nonzero $\left(
\begin{array}
[c]{c}%
x\\
y
\end{array}
\right)  \in\mathbb{R}^{2}$ such that $A\left(
\begin{array}
[c]{c}%
x\\
y
\end{array}
\right)  =\psi\left(
\begin{array}
[c]{c}%
x\\
y
\end{array}
\right)  $. They are the nonzero multiples of $\left(
\begin{array}
[c]{c}%
-\phi\\
1
\end{array}
\right)  $. (You can find this by Gaussian elimination.)
\end{itemize}

So we have found two linearly independent eigenvectors of $A$, namely $\left(
%
\begin{array}
[c]{c}%
-\psi\\
1
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{c}%
-\phi\\
1
\end{array}
\right)  $. Thus, they form a basis of $\mathbb{R}^{2}$ consisting of
eigenvectors of $A$.

Now, Proposition \ref{prop.diagonalization.evals} \textbf{(a)} tells us that
we can find a diagonalization $\left(  U,D\right)  $ of $A$ by setting%
\[
U=\left[  u_{1}\mid u_{2}\mid\cdots\mid u_{n}\right]  \text{ and
}D=\operatorname*{diag}\left(  \lambda_{1},\lambda_{2},\ldots,\lambda
_{n}\right)  ,
\]
where the $u_{1},u_{2},\ldots,u_{n}$ are the eigenvectors of $A$ (so
$u_{1}=\left(
\begin{array}
[c]{c}%
-\psi\\
1
\end{array}
\right)  $ and $u_{2}=\left(
\begin{array}
[c]{c}%
-\phi\\
1
\end{array}
\right)  $) and where the $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$ are the
corresponding eigenvalues (so $\lambda_{1}=\phi$ and $\lambda_{2}=\psi$).
Thus,%
\[
U=\left(
\begin{array}
[c]{cc}%
-\psi & -\phi\\
1 & 1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ D=\operatorname*{diag}\left(  \phi,\psi\right)  =\left(
\begin{array}
[c]{cc}%
\phi & 0\\
0 & \psi
\end{array}
\right)  .
\]
(You can easily double-check that these indeed satisfy $A=UDU^{-1}$.)

Now, let $m\geq0$. Then, (\ref{eq.prop.diagonalization.power.2}) (applied to
$n=2$, $d_{1}=\phi$ and $d_{2}=\psi$) yields%
\[
\left(  UDU^{-1}\right)  ^{m}=U\operatorname*{diag}\left(  \phi^{m},\psi
^{m}\right)  U^{-1}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }%
\ D=\operatorname*{diag}\left(  \phi,\psi\right)  \right)  .
\]
In view of $UDU^{-1}=A$, this rewrites as
\begin{align*}
A^{m} &  =U\operatorname*{diag}\left(  \phi^{m},\psi^{m}\right)
U^{-1}=\left(
\begin{array}
[c]{cc}%
-\psi & -\phi\\
1 & 1
\end{array}
\right)  \operatorname*{diag}\left(  \phi^{m},\psi^{m}\right)  \left(
\begin{array}
[c]{cc}%
-\psi & -\phi\\
1 & 1
\end{array}
\right)  ^{-1}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }U=\left(
\begin{array}
[c]{cc}%
-\psi & -\phi\\
1 & 1
\end{array}
\right)  \text{ and }n=2\text{ and }d_{1}=\phi\text{ and }d_{2}=\psi\right)
\\
&  =\left(
\begin{array}
[c]{cc}%
-\psi & -\phi\\
1 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
\phi^{m} & 0\\
0 & \psi^{m}%
\end{array}
\right)  \underbrace{\left(
\begin{array}
[c]{cc}%
-\psi & -\phi\\
1 & 1
\end{array}
\right)  ^{-1}}_{\substack{=\dfrac{1}{\left(  -\psi\right)  -\left(
-\phi\right)  }\left(
\begin{array}
[c]{cc}%
1 & \phi\\
-1 & -\psi
\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}{\left(  -\psi\right)  -\left(  -\phi\right)  }%
}_{\substack{=\dfrac{1}{\sqrt{5}}\\\text{(since a quick computation}%
\\\text{shows that }\left(  -\psi\right)  -\left(  -\phi\right)  =\sqrt
{5}\text{)}}}\left(
\begin{array}
[c]{cc}%
-\psi & -\phi\\
1 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
\phi^{m} & 0\\
0 & \psi^{m}%
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
1 & \phi\\
-1 & -\psi
\end{array}
\right)  \\
&  =\dfrac{1}{\sqrt{5}}\left(
\begin{array}
[c]{cc}%
-\psi & -\phi\\
1 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
\phi^{m} & 0\\
0 & \psi^{m}%
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
1 & \phi\\
-1 & -\psi
\end{array}
\right)  .
\end{align*}
We could multiply this out. But we want $f_{m}$, not $A^{m}$. There is a
faster way to get $f_{m}$: From (\ref{eq.fibonacci.by-mat}), we obtain%
\begin{align*}
\left(
\begin{array}
[c]{c}%
f_{m}\\
f_{m+1}%
\end{array}
\right)   &  =\underbrace{A^{m}}_{=\dfrac{1}{\sqrt{5}}\left(
\begin{array}
[c]{cc}%
-\psi & -\phi\\
1 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
\phi^{m} & 0\\
0 & \psi^{m}%
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
1 & \phi\\
-1 & -\psi
\end{array}
\right)  }\underbrace{\left(
\begin{array}
[c]{c}%
f_{0}\\
f_{1}%
\end{array}
\right)  }_{\substack{=\left(
\begin{array}
[c]{c}%
0\\
1
\end{array}
\right)  \\\text{(since }f_{0}=0\text{ and }f_{1}=1\text{)}}}\\
&  =\dfrac{1}{\sqrt{5}}\left(
\begin{array}
[c]{cc}%
-\psi & -\phi\\
1 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{cc}%
\phi^{m} & 0\\
0 & \psi^{m}%
\end{array}
\right)  \underbrace{\left(
\begin{array}
[c]{cc}%
1 & \phi\\
-1 & -\psi
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
0\\
1
\end{array}
\right)  }_{=\left(
\begin{array}
[c]{c}%
\phi\\
-\psi
\end{array}
\right)  }\\
&  =\dfrac{1}{\sqrt{5}}\left(
\begin{array}
[c]{cc}%
-\psi & -\phi\\
1 & 1
\end{array}
\right)  \underbrace{\left(
\begin{array}
[c]{cc}%
\phi^{m} & 0\\
0 & \psi^{m}%
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
\phi\\
-\psi
\end{array}
\right)  }_{=\left(
\begin{array}
[c]{c}%
\phi^{m}\phi\\
\psi^{m}\left(  -\psi\right)
\end{array}
\right)  }\\
&  =\dfrac{1}{\sqrt{5}}\underbrace{\left(
\begin{array}
[c]{cc}%
-\psi & -\phi\\
1 & 1
\end{array}
\right)  \left(
\begin{array}
[c]{c}%
\phi^{m}\phi\\
\psi^{m}\left(  -\psi\right)
\end{array}
\right)  }_{\substack{=\left(
\begin{array}
[c]{c}%
\left(  -\psi\right)  \phi^{m}\phi+\left(  -\phi\right)  \psi^{m}\left(
-\psi\right)  \\
\ast
\end{array}
\right)  \\\text{(where the asterisk \textquotedblleft}\ast
\text{\textquotedblright\ stands for}\\\text{an entry that we are not
interested in)}}}\\
&  =\dfrac{1}{\sqrt{5}}\left(
\begin{array}
[c]{c}%
\left(  -\psi\right)  \phi^{m}\phi+\left(  -\phi\right)  \psi^{m}\left(
-\psi\right)  \\
\ast
\end{array}
\right)  \\
&  =\left(
\begin{array}
[c]{c}%
\dfrac{1}{\sqrt{5}}\left(  \left(  -\psi\right)  \phi^{m}\phi+\left(
-\phi\right)  \psi^{m}\left(  -\psi\right)  \right)  \\
\ast
\end{array}
\right)  .
\end{align*}
$\allowbreak$Thus, by comparing the $\left(  1,1\right)  $-entries on both
sides, we obtain%
\begin{align*}
f_{m} &  =\dfrac{1}{\sqrt{5}}\left(  \left(  -\psi\right)  \phi^{m}%
\phi+\left(  -\phi\right)  \psi^{m}\left(  -\psi\right)  \right)  =\dfrac
{-1}{\sqrt{5}}\left(  \underbrace{\phi\psi}_{=-1}\phi^{m}-\underbrace{\phi
\psi}_{=-1}\psi^{m}\right)  \\
&  =\dfrac{1}{\sqrt{5}}\left(  \phi^{m}-\psi^{m}\right)  =\dfrac{1}{\sqrt{5}%
}\left(  \left(  \dfrac{1+\sqrt{5}}{2}\right)  ^{m}-\left(  \dfrac{1-\sqrt{5}%
}{2}\right)  ^{m}\right)  .
\end{align*}
This is an \textbf{explicit} formula for the Fibonacci number $f_{m}$. It is
known as the \textbf{Binet formula}. It shows that $f_{m}$ grows exponentially
with $m$, with growth rate $\phi\approx1.618\ldots$.
\end{example}

In order to prove Proposition \ref{prop.diagonalization.evals}, we will need a
lemma that follows quickly from the definition of matrix multiplication:

\begin{lemma}
\label{lem.diagonalization.AU-UD}Let $n\in\mathbb{N}$. Let $u_{1},u_{2}%
,\ldots,u_{n}$ be $n$ vectors in $\mathbb{R}^{n}$. Let $U=\left[  u_{1}\mid
u_{2}\mid\cdots\mid u_{n}\right]  $ (this is an $n\times n$-matrix).

\textbf{(a)} If $A$ is any $n\times n$-matrix, then%
\[
AU=\left[  Au_{1}\mid Au_{2}\mid\cdots\mid Au_{n}\right]  .
\]


\textbf{(b)} If $D=\operatorname*{diag}\left(  \lambda_{1},\lambda_{2}%
,\ldots,\lambda_{n}\right)  $ is a diagonal $n\times n$-matrix, then%
\[
UD=\left[  \lambda_{1}u_{1}\mid\lambda_{2}u_{2}\mid\cdots\mid\lambda_{n}%
u_{n}\right]  .
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.diagonalization.AU-UD}.] \textbf{(a)} Recall that any
two $n\times n$-matrices $A$ and $B$ and any $j\in\left\{  1,2,\ldots
,n\right\}  $ satisfy%
\begin{equation}
\operatorname{col}_{j}\left(  AB\right)  =A\cdot\operatorname{col}%
_{j}B.\label{pf.lem.diagonalization.AU-UD.a.col}%
\end{equation}
(This is a particular case of Proposition 2.6.2 \textbf{(d)} in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-09-23.pdf}{the notes
from 2019-09-23}.)

Now, let $A$ be any $n\times n$-matrix. Then, for each $j\in\left\{
1,2,\ldots,n\right\}  $, we have
\begin{align*}
\operatorname{col}_{j}\left(  AU\right)    & =A\cdot
\underbrace{\operatorname{col}_{j}U}_{\substack{=u_{j}\\\text{(since
}U=\left[  u_{1}\mid u_{2}\mid\cdots\mid u_{n}\right]  \text{)}}%
}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{pf.lem.diagonalization.AU-UD.a.col}), applied to }B=U\right)  \\
& =Au_{j}.
\end{align*}
Thus, the $n$ columns of the matrix $AU$ are $Au_{1},Au_{2},\ldots,Au_{n}$. In
other words, $AU=\left[  Au_{1}\mid Au_{2}\mid\cdots\mid Au_{n}\right]  $.
This proves Lemma \ref{lem.diagonalization.AU-UD} \textbf{(a)}.

\textbf{(b)} Let $D=\operatorname*{diag}\left(  \lambda_{1},\lambda_{2}%
,\ldots,\lambda_{n}\right)  $ be a diagonal $n\times n$-matrix.

We already know what happens to a matrix when we multiply it on the right by a
diagonal matrix: Namely, in the solution of Exercise 1 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/hw2s.pdf}{homework set \#2}
(applied to $A=U$ and $d_{i}=\lambda_{i}$), we have observed that the matrix
$U\cdot\operatorname*{diag}\left(  \lambda_{1},\lambda_{2},\ldots,\lambda
_{n}\right)  $ is obtained from $U$ by scaling the $j$-th column by
$\lambda_{j}$ for each $j\in\left\{  1,2,\ldots,n\right\}  $. Thus, the
columns of the matrix $U\cdot\operatorname*{diag}\left(  \lambda_{1}%
,\lambda_{2},\ldots,\lambda_{n}\right)  $ are the columns of $U$, scaled by
$\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$, respectively. In other words,
the columns of the matrix $U\cdot\operatorname*{diag}\left(  \lambda
_{1},\lambda_{2},\ldots,\lambda_{n}\right)  $ are $\lambda_{1}u_{1}%
,\lambda_{2}u_{2},\ldots,\lambda_{n}u_{n}$ (since the columns of $U$ are
$u_{1},u_{2},\ldots,u_{n}$). In other words,%
\[
U\cdot\operatorname*{diag}\left(  \lambda_{1},\lambda_{2},\ldots,\lambda
_{n}\right)  =\left[  \lambda_{1}u_{1}\mid\lambda_{2}u_{2}\mid\cdots
\mid\lambda_{n}u_{n}\right]  .
\]
In view of $D=\operatorname*{diag}\left(  \lambda_{1},\lambda_{2}%
,\ldots,\lambda_{n}\right)  $, this rewrites as $UD=\left[  \lambda_{1}%
u_{1}\mid\lambda_{2}u_{2}\mid\cdots\mid\lambda_{n}u_{n}\right]  $. This proves
Lemma \ref{lem.diagonalization.AU-UD} \textbf{(b)}.
\end{proof}

Let us now prove Proposition \ref{prop.diagonalization.evals}:

\begin{proof}
[Proof of Proposition \ref{prop.diagonalization.evals}.]\textbf{(a)} The
Inverse Matrix Theorem (more precisely, the implication \textbf{(d)}
$\Longrightarrow$ \textbf{(k)} from Theorem 1.2.1 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-10-16.pdf}{the notes
from 2019-10-16})  shows that the matrix $U$ is invertible (since its $n$
columns $u_{1},u_{2},\ldots,u_{n}$ form a basis of $\mathbb{R}^{n}$). The
matrix $D$ is diagonal. It remains to prove that $A=UDU^{-1}$. Equivalently,
we need to prove that $AU=UD$.

Lemma \ref{lem.diagonalization.AU-UD} \textbf{(a)} yields%
\begin{align*}
AU &  =\left[  Au_{1}\mid Au_{2}\mid\cdots\mid Au_{n}\right]  =\left[
\lambda_{1}u_{1}\mid\lambda_{2}u_{2}\mid\cdots\mid\lambda_{n}u_{n}\right]  \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }Au_{i}=\lambda_{i}u_{i}\text{ for
each }i\text{ (because each }u_{i}\text{ is a }\lambda_{i}\text{-eigenvector)}%
\right)  .
\end{align*}
On the other hand, Lemma \ref{lem.diagonalization.AU-UD} \textbf{(b)} yields%
\[
UD=\left[  \lambda_{1}u_{1}\mid\lambda_{2}u_{2}\mid\cdots\mid\lambda_{n}%
u_{n}\right]  .
\]
So we got the same expression for $AU$ as for $UD$. Thus, $AU=UD$. Multiplying
both sides of this equality by $U^{-1}$ on the right, we obtain $A=UDU^{-1}$.
This proves Proposition \ref{prop.diagonalization.evals} \textbf{(a)}.

\textbf{(b)} The same argument, done in reverse, proves part \textbf{(b)}.
(See \cite[proof of Proposition 14.4]{Strickland} for details.)
\end{proof}

Some more examples of diagonalization of matrices:

\begin{example}
Let $A=\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
0 & 2 & 2\\
0 & 0 & 3
\end{array}
\right)  $. In Example 1.3.4 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-06.pdf}{the notes
from 2019-11-06}, we showed that the 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)
\]
of $A$ (for eigenvalues $1,2,3$) form a basis of $\mathbb{R}^{3}$. We can now
use this basis to diagonalize $A$: Namely, Proposition
\ref{prop.diagonalization.evals} \textbf{(a)} yields that%
\[
U=\left(
\begin{array}
[c]{ccc}%
1 & 1 & 3\\
0 & 1 & 4\\
0 & 0 & 2
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ D=\operatorname*{diag}\left(  1,2,3\right)  =\left(
\begin{array}
[c]{ccc}%
1 & 0 & 0\\
0 & 2 & 0\\
0 & 0 & 3
\end{array}
\right)
\]
form a diagonalization of $A$.

Thus, (\ref{eq.prop.diagonalization.power.2}) yields that%
\[
A^{m}=U\operatorname*{diag}\left(  1^{m},2^{m},3^{m}\right)  U^{-1}%
\ \ \ \ \ \ \ \ \ \ \text{for each }m\geq0.
\]

\end{example}

\begin{example}
Let $A=\left(
\begin{array}
[c]{ccc}%
1 & 1 & 1\\
0 & 1 & 1\\
0 & 0 & 1
\end{array}
\right)  $. Does this $A$ have a diagonalization?

In Example 1.3.5 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/19fla/2019-11-06.pdf}{the notes
from 2019-11-06}, we found that there is no basis of $\mathbb{R}^{3}$
consisting of eigenvectors of $A$. Hence, Proposition
\ref{prop.diagonalization.evals} \textbf{(b)} shows that there is no
diagonalization of $A$.
\end{example}

So some matrices have a diagonalization (and usually many), while others don't.

In the case of the matrix $A=\left(
\begin{array}
[c]{cc}%
0 & 1\\
1 & 1
\end{array}
\right)  $ (which was used to compute the Fibonacci numbers), we were in luck,
since our matrix $A$ had a diagonalization. What would have happened if it
didn't? Let's see:

\begin{example}
Define a sequence $\left(  g_{0},g_{1},g_{2},\ldots\right)  $ of integers by%
\[
g_{0}=0,\ \ \ \ \ \ \ \ \ \ g_{1}=1,\ \ \ \ \ \ \ \ \ \ g_{n}=2g_{n-1}%
-g_{n-2}.
\]


This time, we get $\left(
\begin{array}
[c]{c}%
g_{m}\\
g_{m+1}%
\end{array}
\right)  =A\left(
\begin{array}
[c]{c}%
g_{0}\\
g_{1}%
\end{array}
\right)  $ for $A=\left(
\begin{array}
[c]{cc}%
0 & 1\\
-1 & 2
\end{array}
\right)  $.

The matrix $A=\left(
\begin{array}
[c]{cc}%
0 & 1\\
-1 & 2
\end{array}
\right)  $ has characteristic polynomial $t^{2}-2t+1=\allowbreak\left(
t-1\right)  ^{2}$. Thus, its only eigenvalue is $1$. The corresponding
eigenvectors are nonzero multiples of $\left(
\begin{array}
[c]{c}%
1\\
1
\end{array}
\right)  $. Thus, there is no basis of $\mathbb{R}^{2}$ consisting of
eigenvectors of $A$. Hence, there is no diagonalization of $A$. So we cannot
compute $g_{m}$ by the same method that we used to find $f_{m}$.

However, there is a very simple formula for $g_{m}$: namely,%
\[
g_{m}=m\ \ \ \ \ \ \ \ \ \ \text{for each }m\geq0.
\]
You can prove this by induction on $m$.
\end{example}

There is a more general concept than diagonalization -- the so-called
\textbf{Jordan normal form} -- that exists for \textbf{any} $n\times
n$-matrix. (See \cite[\S Five.IV]{Hefferon} or a typical course on Linear
Algebra 2 or Abstract Algebra 1 or 2.)

\subsection{Complex numbers}

\subsubsection{Motivation}

Now, let us return to an example of a matrix that we have not managed to find
any eigenvectors of:

\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}), since the characteristic polynomial $\chi_{A}\left(
t\right)  =t^{2}+1$ has no real roots (its plot stays strictly above the
x-axis). But let us \textbf{pretend} that there is a new \textquotedblleft
mythical number\textquotedblright\ $i$, which is a square root of $-1$, in the
sense that $i^{2}=-1$. Then, of course, $\left(  -i\right)  ^{2}=-1$ as well,
since $\left(  -i\right)  ^{2}=i^{2}$. (Here we are assuming that this
\textquotedblleft mythical number\textquotedblright\ $i$ and its whole retinue
of numbers derived from it satisfy the same rules as the familiar real
numbers, such as the identity $\left(  -x\right)  ^{2}=x^{2}$.) Thus, $-i$ and
$i$ are roots of the polynomial $t^{2}+1$. Since a degree-$2$ polynomial
should have only $2$ roots (at least if these \textquotedblleft mythical
numbers\textquotedblright\ behave as nicely as our familiar real numbers),
we thus have found all the roots of this polynomial.

Thus, the eigenvalues of $A$ are the \textquotedblleft mythical
numbers\textquotedblright\ $i$ and $-i$. We can find the corresponding
eigenvectors using Gaussian elimination:

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

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

Of course, these vectors $\left(
\begin{array}
[c]{c}%
i\\
1
\end{array}
\right)  ,\left(
\begin{array}
[c]{c}%
-i\\
1
\end{array}
\right)  $ don't belong to $\mathbb{R}^{2}$, and thus cannot form a basis of
$\mathbb{R}^{2}$. But if we redo all the linear algebra that we did using our
new \textquotedblleft mythical numbers\textquotedblright\ instead of real
numbers as scalars, then they form a basis of the analogue of $\mathbb{R}^{2}$.

This should give a diagonalization $A=UDU^{-1}$ with%
\[
U=\left(
\begin{array}
[c]{cc}%
i & -i\\
1 & 1
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ D=\operatorname*{diag}\left(  i,-i\right)  =\left(
\begin{array}
[c]{cc}%
i & 0\\
0 & -i
\end{array}
\right)  .
\]
\end{example}

This looks neat, but you should have a lingering doubt:
Why can we just introduce a new \textquotedblleft
number\textquotedblright\ $i$ satisfying $i^{2}=-1$ ?

After all, this isn't much different from introducing a new \textquotedblleft
number\textquotedblright\ $\infty$ satisfying $0\cdot\infty=1$. But $\infty$
quickly leads to contradictions, at least if you pretend that it behaves like
a normal number (for example, $0\cdot\underbrace{\left(  0\cdot\infty\right)
}_{=1}=0\cdot1=0$, but $\underbrace{\left(  0\cdot0\right)  }_{=0}\cdot
\infty=0\cdot\infty=1$, so the associative law no longer holds). Why does
our mythical $i$ not lead to contradictions?

\subsubsection{Informal introduction}

Before we address this existential doubt, let us experiment a bit with
our new toy, leaving aside the question whether it has a rigorous meaning.

We have introduced a new ``number'' $i$ that satisfies $i^2 = -1$.
We call it the \textbf{imaginary unit}\footnote{The name is probably
referencing the fact that we just invented it. Arguably, all numbers
are just as imaginary to some extent...}.
Using familiar operations such as addition, subtraction and multiplication,
we can combine this new ``number'' $i$ with our familiar real numbers,
and obtain new ``numbers'' -- which are called \textbf{complex numbers}
(a formal definition will be given below).
For example, $2+3i-7i^3$ is a complex number; so is $i^5-\pi i+\dfrac{1}{3}$.
Let us calculate a bit with complex numbers (assuming that they satisfy
the same laws as real numbers, such as associativity, commutativity
and distributivity):
\[
\left(  1+i\right)  \left(  1-i\right)  =1+i-i+i\left(  -i\right)  =1+i\left(
-i\right)  =1-\underbrace{i^{2}}_{=-1}=1-\left(  -1\right)  =2;
\]%
\[
i^{4}=\left(  \underbrace{i^{2}}_{=-1}\right)  ^{2}=\left(  -1\right)
^{2}=1;
\]%
\[
i^{5}=\underbrace{i^{4}}_{=1}i=i;
\]%
\[
\left(-i\right)^2 = \left(-i\right) \left(-i\right)
= - \left(- ii\right) = ii = i^2 = -1 ;
\]
\[
\left(  1+i\right)  +\left(  1-i\right)  =2;
\]%
\[
\dfrac{1}{1+i}=\dfrac{1-i}{\left(  1+i\right)  \left(  1-i\right)  }%
=\dfrac{1-i}{2}=\dfrac{1}{2}-\dfrac{1}{2}i.
\]
The number $i$ is often called $\sqrt{-1}$ because its square is $-1$;
but it is only one of two complex numbers whose square is $-1$
(namely, $i$ and $-i$).

The above computations suggest that every complex number has the form $a+bi$
for some real numbers $a$ and $b$.
Let us see why: If we have two numbers of the form $a+bi$, then their sum,
difference, product and quotient is also of this form. Namely,%
\begin{align}
\left(  a+bi\right)  +\left(  c+di\right)   &  =\left(  a+c\right)  +\left(
b+d\right)  i;
\label{eq.CC.informal.sum}\\
\left(  a+bi\right)  -\left(  c+di\right)   &  =\left(  a-c\right)  +\left(
b-d\right)  i;
\label{eq.CC.informal.diff}\\
\left(  a+bi\right)  \left(  c+di\right)   &  =ac+bic+adi+bidi\nonumber\\
&  =ac+bci+adi+bd\underbrace{i^{2}}_{=-1}\nonumber\\
&  =ac+bci+adi-bd\nonumber\\
&  =\left(  ac-bd\right)  +\left(  ad+bc\right)  i;
\label{eq.CC.informal.prod}\\
\dfrac{a+bi}{c+di}  &  =\dfrac{\left(  a+bi\right)  \left(  c-di\right)
}{\left(  c+di\right)  \left(  c-di\right)  }=\dfrac{\left(  ac+bd\right)
+\left(  bc-ad\right)  i}{c^{2}+d^{2}},
\nonumber
\end{align}
where the last equation requires $\left(  c,d\right)  \neq\left(  0,0\right)
$.

These formulas show that if we start with real numbers and the new
\textquotedblleft number\textquotedblright\ $i$, then the standard operations
($+$, $-$, $\cdot$ and $/$) do not take us out of the set of numbers of the
form $a+bi$. Thus, all complex numbers have the form $a+bi$ for $a,b\in\mathbb{R}$.

We have assumed that all the standard rules for real numbers (associativity,
commutativity, distributivity) still hold for these new numbers. What about inequalities?

Here we are in for a disappointment.
If inequalities ($\geq$, $>$, $\leq$, $<$) would still make sense for complex
numbers (and behave anything like they do for real numbers),
then we would get the following contradiction:

\begin{itemize}
\item If $i\geq0$, then $i^{2}\geq0$, contradicting $i^{2}=-1$.

\item If $i<0$, then $-i > 0$ and thus
$i^{2}=\left(  -i\right)  ^{2}>0$ (since $-i>0$),
contradicting $i^{2}=-1$.
\end{itemize}

\noindent So $i$ is neither $\geq0$ nor $<0$. Thus, inequalities do not work for our
new numbers.

So how can we be sure that the other things (addition, subtraction,
multiplication) work and don't lead to contradictions?

\subsubsection{Rigorous definition of complex numbers}

The trick is to define complex numbers rigorously (using existing
objects such as real numbers), instead of obtaining
them by introducing a mythical ``number'' $i$ whose existence has
to be taken for granted.
How can we do this?
We forget about the mythical $i$, and instead define complex
numbers as pairs of real numbers.
Don't worry -- we will gain our $i$ back in a moment,
and it will be a rigorously defined $i$ rather than some mythical
object of unclear existence status.

Here is the promised rigorous definition of complex numbers and
the most basic operations (addition, subtraction and multiplication%
\footnote{We will define division and exponentiation (with integer
exponents) later.}) on them:\footnote{See \cite[Section 4.1]{19s}
for more details on this.}

\begin{definition}
\textbf{(a)} A \textbf{complex number} is defined as a pair $\left(
a,b\right)  $ of two real numbers.

\textbf{(b)} We let $\mathbb{C}$ be the set of all complex numbers.

\textbf{(c)} For each real number $r$, we denote the complex number $\left(
r,0\right)  $ as $r_{\mathbb{C}}$ (and we will later equate it with $r$).

\textbf{(d)} We let $i$ be the complex number $\left(  0,1\right)  $.

\textbf{(e)} We define three binary operations $+$, $-$ and $\cdot$ on
$\mathbb{C}$ by setting%
\begin{align}
\left(  a,b\right)  +\left(  c,d\right)   &  =\left(  a+c,b+d\right)  ,
\label{eq.CC.formal.sum}\\
\left(  a,b\right)  -\left(  c,d\right)   &  =\left(  a-c,b-d\right)  ,
\label{eq.CC.formal.diff}\\
\left(  a,b\right)  \cdot\left(  c,d\right)   &  =\left(  ac-bd,ad+bc\right)
.
\label{eq.CC.formal.prod}
\end{align}
(Thus, the operations $+$ and $-$ are just entrywise addition and
subtraction, just as for row vectors.
The operation $\cdot$ is more complicated, and we will soon see why
we have defined it in this particular way.)

\textbf{(f)}
As usual, we write $\alpha\beta$ for $\alpha\cdot\beta$
if $\alpha$ and $\beta$ are complex numbers.

As usual, we write $-\alpha$ for $0_{\mathbb{C}}-\alpha$
if $\alpha$ is a complex number.
\end{definition}

For example, this definition yields%
\[
\underbrace{i}_{=\left(  0,1\right)  }\underbrace{i}_{=\left(  0,1\right)
}=\left(  0,1\right)  \cdot\left(  0,1\right)  =\left(  0\cdot0-1\cdot
1,0\cdot1+1\cdot0\right)  =\left(  -1,0\right)  =\left(  -1\right)
_{\mathbb{C}}.
\]
So we get $i^{2}=-1$, at least if we abbreviate $ii$ as $i^{2}$.

If you compare this rigorous definition of complex numbers with
the informal introduction we gave before it,
you will now find that they lead to the same notion of complex
numbers: The pair $\left(a,b\right)$ from the rigorous definition
corresponds to the $a+bi$ from the informal introduction.
The operations $+$, $-$ and $\cdot$ on the former pairs correspond
precisely to the operations $+$, $-$ and $\cdot$ on the latter
``numbers'', because the equalities
\eqref{eq.CC.formal.sum}, \eqref{eq.CC.formal.diff} and
\eqref{eq.CC.formal.prod} are precisely the equalities
\eqref{eq.CC.informal.sum}, \eqref{eq.CC.informal.diff} and
\eqref{eq.CC.informal.prod} rewritten in terms of the rigorous
definition.
(This explains why we have chosen these exact definitions of
$+$, $-$ and $\cdot$ and no others -- we chose them in order
to recover the equalities
\eqref{eq.CC.informal.sum}, \eqref{eq.CC.informal.diff} and
\eqref{eq.CC.informal.prod}.)

So we know what complex numbers are and how to add, subtract
and multiply them. Do these operations behave well? Yes, as
the following theorem shows:

\begin{theorem}
All standard rules for addition, subtraction and multiplication (e.g.,
commutativity, associativity, distributivity) hold for complex numbers.
\end{theorem}

\begin{proof}
This is all straightforward.
See \cite[Theorem 4.1.2]{19s}.
\end{proof}

The complex numbers include copies of our old real numbers, because
of the following theorem:

\begin{theorem}
\label{thm.CC.rCsC}
The complex numbers $r_{\mathbb{C}}$ (for $r\in\mathbb{R}$) behave exactly as
the real numbers $r$: For example,%
\begin{align*}
\left(  r+s\right)  _{\mathbb{C}} &=r_{\mathbb{C}}+s_{\mathbb{C}};
\\
\left(  r-s\right)  _{\mathbb{C}} &=r_{\mathbb{C}}-s_{\mathbb{C}};
\\
\left(  rs\right) _{\mathbb{C}} &=r_{\mathbb{C}}s_{\mathbb{C}}
\end{align*}
for any two real numbers $r$ and $s$.
\end{theorem}

Thus, we can identify each real number $r$ with the corresponding complex
number $r_{\mathbb{C}}=\left(  r,0\right)  $. Let us do so; thus, the complex
numbers become an extension of the real numbers.
\footnote{Theorem \ref{thm.CC.rCsC} shows that this identification does not mess up
our algebraic operations! If this theorem was false, then equating $r$ with
$r_{\mathbb{C}}$ would make expressions like $r+s$, $r-s$ and $rs$ ambiguous,
as their meaning would depend on whether we are adding/subtracting/multiplying
the real numbers $r$ and $s$ or the corresponding complex numbers $r_{\mathbb{C}}$
and $s_{\mathbb{C}}$.}

Now that we have agreed to identify each $r\in\mathbb{R}$ with $r_{\mathbb{C}}$,
we have%
\[
\left(  a,b\right)  =a+bi\ \ \ \ \ \ \ \ \ \ \text{for every }\left(
a,b\right)  \in\mathbb{C}.
\]
This is because%
\begin{align*}
&  \underbrace{a}_{\substack{=a_{\mathbb{C}}\\=\left(  a,0\right)
}}+\underbrace{b}_{\substack{=b_{\mathbb{C}}\\=\left(  b,0\right)
}}\ \underbrace{i}_{=\left(  0,1\right)  }\\
&  =\left(  a,0\right)  +\left(  b,0\right)  \left(  0,1\right)  =\left(
a,0\right)  +\left(  b\cdot0-0\cdot1,b\cdot1+0\cdot0\right) \\
&  =\left(  a,0\right)  +\left(  0,b\right)  =\left(  a+0,0+b\right)  =\left(
a,b\right)  .
\end{align*}


We can define quotients of complex numbers (i.e., we can divide a complex
number by any other, as long as the latter is nonzero):
Given two complex numbers $\alpha$
and $\beta\neq0$, we can define $\dfrac{\alpha}{\beta}$ to be the unique
complex number $\gamma$ such that $\alpha=\beta\gamma$. This exists, because%
\[
\dfrac{a+bi}{c+di}=\dfrac{\left(  a+bi\right)  \left(  c-di\right)  }{\left(
c+di\right)  \left(  c-di\right)  }=\dfrac{\left(  ac+bd\right)  +\left(
bc-ad\right)  i}{c^{2}+d^{2}}.
\]


We can define integer powers of complex numbers: If $n\in\mathbb{Z}$ and
$\alpha\in\mathbb{C}$, then%
\begin{align*}
\alpha^{n}  &  =\underbrace{\alpha\alpha\cdots\alpha}_{n\text{ times}%
}\ \ \ \ \ \ \ \ \ \ \text{if }n>0;\\
\alpha^{0}  &  =1;\\
\alpha^{n}  &  =\left(  \dfrac{1}{\alpha}\right)  ^{-n}%
\ \ \ \ \ \ \ \ \ \ \text{if }n<0.
\end{align*}
The latter equality requires $\alpha$ to be nonzero. In particular,
$i^{2}=ii=-1$.

The main disadvantage of complex numbers compared to real numbers is the lack
of inequalities. There is no reasonable way to define what it means for a
complex number to be $\leq$ to another complex number.
(In fact, we have already seen how that would lead to contradictions.)

Also, there is no good way to define non-integer powers of complex
numbers (for example, $i^{\sqrt{2}}$ does not have a well-defined meaning).
(Some people would give you a definition, but it would depend on whom
you ask, and it would probably not satisfy standard rules like
$\alpha^{\beta\gamma} = \left(\alpha^\beta\right)^\gamma$.)

\subsubsection{The Argand diagram}

There is a visual way to represent complex numbers.
I will introduce it briefly; see \cite[Subsection 4.1.8 and further]{19s}
for more details (and pictures!).

As you know, the real numbers are typically viewed as points on a line. We
similarly represent complex numbers as points on the plane. Namely, the
complex number $\left(  a,b\right)  =a+bi$ (with $a, b \in \mathbb{R}$)
will be represented by the point $\left(  a,b\right)  $ (in Cartesian
coordinates). This way of representing complex numbers
called the \textbf{Argand diagram}.

Note that addition and subtraction of complex numbers $\left(  a,b\right)  $
are defined in the same way as for vectors: entrywise. Therefore, the sum of two
complex numbers can be found on the Argand diagram by the parallelogram rule,
just as the sum of two vectors. What about multiplication?

Multiplying a complex number by a real number is easy: If $a,b,c\in\mathbb{R}%
$, then%
\[
\underbrace{a}_{\substack{=a_{\mathbb{C}}\\=\left(  a,0\right)  }}\left(
b,c\right)  =\left(  a,0\right)  \left(  b,c\right)  =\left(
ab-0c,ac+0b\right)  =\left(  ab,ac\right)  .
\]
Thus, multiplying a complex number by a real number $a$ is simply multiplying
its both entries by $a$. On the Argand diagram, this corresponds to a
homothety with center at the origin (i.e., scaling).

How do we multiply two complex numbers?

To give a description, we introduce some notations:

\begin{definition}
Let $z$ be a complex number.
Write $z$ in the form
$z=\left(  a,b\right)  =a+bi$ for two real numbers $a,b$.

Let $P_z$ be the point corresponding to the complex number $z$
on the Argand diagram.
(As you remember, this is the point with coordinates $\left(a,b\right)$.)

\textbf{(a)} The real numbers
$a$ and $b$ are called the \textbf{real part} and the \textbf{imaginary part}
of $z$. They are the Cartesian coordinates of the point $P_z$.

\textbf{(b)} The \textbf{absolute value} of $z$ is defined to be the real
number $\sqrt{a^{2}+b^{2}}$. This is the distance between the origin and $P_z$.
This is the first (radial)
\textbf{polar coordinate} of $P_z$.
It is denoted by $\left\vert z\right\vert $.

\textbf{(c)} Assume that $z\neq0$. Then, consider the angle $\varphi$ (with
$-\pi<\varphi\leq\pi$) at which the ray from $0$ to $P_z$ stands to the
ray from $0$ to $1$ (i.e., the positive half-axis).
This is the second (angular) \textbf{polar coordinate} of $P_z$.
It is denoted by $\arg z$, and is
called the \textbf{argument} of $z$.
\end{definition}

\begin{example}
We have%
\[
\left\vert 1+i\right\vert =\left\vert \left(  1,1\right)  \right\vert
=\sqrt{1^{2}+1^{2}}=\sqrt{2}\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \arg\left(  1+i\right)  =\pi/4=45^{\circ}.
\]
Similarly,%
\[
\left\vert 1-i\right\vert =\left\vert \left(  1,-1\right)  \right\vert
=\sqrt{1^{2}+\left(  -1\right)  ^{2}}=\sqrt{2}\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \arg\left(  1-i\right)  =-\pi/4=-45^{\circ}.
\]

\end{example}

\bigskip

\begin{thebibliography}{9999999999}                                                                                       %
\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[AndAnd14]{AndAnd14}%
\href{https://doi.org/10.1007/978-0-8176-8415-0}{Titu Andreescu, Dorin
Andrica, \textit{Complex Numbers from A to\ldots Z}, 2nd edition, Springer
2014.}

\bibitem[Hefferon]{Hefferon}Jim Hefferon, \textit{Linear Algebra}, 3rd
edition, 1 January 2017,\newline\url{http://joshua.smcvt.edu/linearalgebra/} .

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

\bibitem[Swanso18]{Swanso18}Irena Swanson, \textit{Introduction to Analysis},
with construction of the number systems, 19 June 2019.\newline\url{https://people.reed.edu/~iswanson/analysisconstructR.pdf}

\end{thebibliography}


\end{document}