% DEFINE some information that will be populated throughout the course notes.
\def \coursename {Linear Algebra}
\def \coursecode {MATH 2221}
\def \courseterm {Winter 2021}
\def \instructorname {Nathan Johnston}
% END DEFINITIONS


% IMPORT the course note formatting and templates
\input{course_notes_template}
% END IMPORT


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{chapter}{9} % Set to one less than the week number
\chapter{Eigenvalues and Eigenvectors}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\large This week we will learn about:

\begin{itemize}
	\item Complex numbers,
	\item Eigenvalues, eigenvectors, and eigenspaces,
	\item The characteristic polynomial of a matrix, and
	\item Algebraic and geometric multiplicity.
\end{itemize}\bigskip\bigskip

\noindent Extra reading:
\begin{itemize}
	\item Section 3.3 in the textbook
	\item Lecture videos \href{https://www.youtube.com/watch?v=unJjCemfYis&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=37}{37}, \href{https://www.youtube.com/watch?v=6YE8L1-tJx8&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=38}{38}, and \href{https://www.youtube.com/watch?v=WRunN_X7lMs&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=39}{39} on YouTube
	\item \href{https://en.wikipedia.org/wiki/Complex_number}{Complex number} at Wikipedia
	\item \href{http://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors}{Eigenvalues and eigenvectors} at Wikipedia
\end{itemize}\bigskip\bigskip

\noindent Extra textbook problems:
\begin{itemize}
	\item[$\star$] 3.3.1, 3.3.2
	\item[$\star \, \star$] 3.3.3, 3.3.5(a-e,g-l,n), 3.3.7, 3.3.9, 3.3.16, 3.3.20
	\item[$\star\star\star$] 3.3.6, 3.3.11--3.3.14
	\item[$\skull$] 3.3.19, 3.3.23, 3.3.24
\end{itemize}}


\newpage

\section*{Eigenvalues and Eigenvectors}

Some linear transformations behave very well when they act on certain specific vectors. For example, diagonal matrices behave very well on the standard basis vectors:

\horlines{4}
% example with random diagonal matrix and standard basis vectors, say 3x3
% diagonal matrix just scales those standard basis vectors, doesn't change their direction
% maybe draw 2D picture

In the above example, we saw that there are vectors such that matrix multiplication behaved just like scalar multiplication: $A\v = \lambda\v$. This is extremely desirable in many situations: we often want matrix multiplication to behave like scalar multiplication, and we often want general matrices to behave like diagonal matrices. This leads to the following definition.

\begin{definition}[Eigenvalues and Eigenvectors]
	Let $A$ be a square matrix. A scalar $\lambda$ is called an \textbf{eigenvalue} of $A$ if there is a non-zero vector $\v$ such that $A\v = \lambda\v$. Such a vector $\v$ is called an \textbf{eigenvector} of $A$ corresponding to $\lambda$.
\end{definition}

\exx[6]{Show that $\v = (1,1)$ is an eigenvector of $A = \begin{bmatrix}2 & 1 \\ 1 & 2\end{bmatrix}$, and find the corresponding eigenvalue.}
% Just multiply. The eigenvalue is 3.
% Then show annimated GIF week10/eigenvectors.gif. That is this same matrix.
% Insert week10/eigenvectors_static.png
% Also show (1,-1) is eigenvector with eigenvalue 1


\newpage


OK, how do we go about actually \emph{finding} eigenvalues and eigenvectors? It's easy enough when the eigenvector is given to us, but the real world isn't that nice. \\

\noindent Well, we find them via a two-step process: first, we find the eigenvalues, then we find the eigenvectors. \\

\noindent \textbf{Step 1: Find the eigenvalues.} Recall that $\lambda$ is an eigenvalue of $A$ if and only if there is a non-zero vector $\v$ such that $A\v = \lambda\v$. This is equivalent to...

\horlines{3}
% Av - \lambda*v = 0. Want to factor out v, but have to be careful... (A - lambda)*v is not a thing. Instead, insert identity matrix
% (A - lambdaI)v = 0

In other words, $\lambda$ is an eigenvalue of $A$ if and only if the matrix $A - \lambda I$ has non-zero null space. How can we find when a matrix has a non-zero null space? Well...
\begin{itemize}
	\item $\mathrm{dim}(\mathrm{null}(A - \lambda I)) > 0$ if and only if...
	
	\horlines{1}\vspace*{-0.6cm}
	% A is not invertible (characterization of invert. matrices)
	
	\item ...if and only if...
	
	\horlines{1}\vspace*{-0.6cm}
	% det(A - \lambdaI) = 0.
\end{itemize}

\noindent A-ha! This is the type of equation we can actually solve! So to find the eigenvalues of $A$, we find all numbers $\lambda$ such that $\mathrm{det}(A - \lambda I) = 0$.

\exx[4]{Find all eigenvalues of $A = \begin{bmatrix}
	1 & 2 \\ 5 & 4
	\end{bmatrix}$.}
% (1 - lam)(4-lam) - 10 = 0, so lam^2 - 5lam - 6 = 0, so (lam-6)(lam+1) = 0, so lam = 6 or -1.


\newpage


\noindent \textbf{Step 2: Find the eigenvectors.} Once you know the eigenvalues (from step~1), the associated eigenvectors are the vectors $\v$ satisfying $A\v = \lambda\v$. But this equation holds if and only if... \\

\horlines{1}
% (A - \lambda*I)*v = 0

In other words, to find all eigenvectors of $A$ associated with the eigenvalue $\lambda$, we compute $\mathrm{null}(A - \lambda I)$. % highlight this line

\exx[8]{Find all eigenvectors of $A = \begin{bmatrix}
	1 & 2 \\ 5 & 4
	\end{bmatrix}$.}
% eigenvalues are 6 and -1, from previous example.
% when lam = 6, we are looking for null(-5, 2; 5, -2). Solving gives $-5x + 2y = 0$, so $y = (5/2)x$, so all vectors of the form $c(2,5)$.
% when lam = -1, we are looking for null(2,2; 5 5). Solving gives $y = -x$, so all vectors of the form $c(1,-1)$.

The eigenvalues and eigenvectors can help us understand what a linear transformation ``looks like.''
% Draw a picture of the last example matrix. Draw two eigenvectors as your basis.

\horlines{5}


\newpage


Since the set of all eigenvectors of $A$ corresponding to $\lambda$ is the nullspace of $A - \lambda I$, the set of eigenvectors forms a subspace (the nullspace is always a subspace). We give this subspace a name:

\begin{definition}[Eigenspace]
	Let $A$ be a square matrix and let $\lambda$ be an eigenvalue of $A$. The set of all eigenvectors of $A$ corresponding to $\lambda$, together with the zero vector, is called the \textbf{eigenspace} of $\lambda$.
\end{definition}

\exx[15]{Find all eigenvalues, and bases of their corresponding eigenspaces, for the matrix $A = \begin{bmatrix} 2 & -3 & 3 \\ 0 & -1 & 3 \\ 0 & -2 & 4 \end{bmatrix}$.}
% eigenvalues: 1, 2, 2
% eigenvectors: (3,3,2) and {(1,0,0),(1,1,1)}


\newpage


There are some matrices that do not have any (real) eigenvalues or eigenvectors. For example...

\exx[9]{Find all eigenvalues and eigenvectors of $A = \begin{bmatrix}
	0 & -1 \\ 1 & 0
	\end{bmatrix}$.}
	% This is a rotation in R^2 CCW by 90 degrees (we saw this early in the course). Geometrically clear that it doesn't have any eigenvectors, since no non-zero vector is mapped to a multiple of itself. HOWEVER...
	% computing eigenvalues gives lam^2 + 1 = 0, so lam = sqrt(-1). Does not work! RETURN TO THIS EXAMPLE LATER AND SAY lam = \pm i.
	
	

\section*{Complex Numbers}

There are a few operations in your mathematical career that you have been told you cannot do:

\horlines{2}
% Can't divide by 0
% Can't square root a negative number

\noindent We now introduce something called \textbf{complex numbers} that let us ``fix'' one of these ``problems'': they let us work with square roots of negative numbers algebraically.

\horlines{2}
% We define $i$ to be a number that satisfies $i^2 = -1$ (clearly, $i$ is not a real number).
% We think of i as a square root of -1


\newpage


Remarkably, you can do arithmetic with $i$ just like you're used to with real numbers, and things have a way of just working out. But first, let's get some terminology out of the way:

\begin{itemize}
	\item An \textbf{imaginary number} is a number of the form
	
	\horlines{2}
	% bi, where b is real
	% note that this terminology is *terrible*
	
	\item A \textbf{complex number} is a number of the form
	
	\horlines{2}
	% $a + bi$, where $a,b$ are real
	% Label a and b as the real and imaginary part of a+bi
\end{itemize}

Arithmetic with complex numbers works just like it does with real numbers, so nothing surprising happens when you add or multiply them.

\exx[3]{Add and multiply some complex numbers.}
% Make up random examples, one of each.

Slightly more generally,\\[0.3cm]

\noindent $(a + bi) + (c + di) = {}$\\[-1.6cm]

\horlines{1}
% (a+c) + (b+d)i

\noindent $(a + bi)(c + di) = {}$\\[-1.6cm]

\horlines{1}
% (ac-bd) + (ad + bc)i
% Mention "FOIL"

\noindent However, division of complex numbers requires one minor ``trick'' to get our hands on.


\newpage



\exx[3]{Divide some complex numbers.}
% One random example. Multiply top and bottom by conjugate of the denominator.

\noindent The number that we multiplied the top and bottom by in the above example was called the \textbf{complex conjugate} of the bottom (denominator). That is,

\horlines{3}
% the complex conjugate of $a + bi$ is $a - bi$.
% We denote this by \overline{a + bi} = a - bi.
% Note that their product is always real (so denominator in previous example is always real)

With just these basic tools under our belt, we can now find roots of quadratics that don't have real roots! We just use the quadratic formula like usual.

\exx[6]{Find the (potentially complex) solutions of the equation $x^2 - 2x + 2 = 0$.}
% Use quadratic formula to get x = 1 \pm i.
% Then plug in x = 1+i to the equation to see that you do, indeed, get 0
% Note that you can factor that quadratic as (x - (1+i))(x - (1-i))

The previous example hints at the following observation, which is indeed true:

\horlines{3}


\newpage


\horlines{3}
% If a quadratic with real coefficients has complex roots, they come in complex conjugate pairs (i.e., one of the roots was the complex conjugate of the other).
% PRoof: take complex conjugate of polynomial, doesn't change, so still a root

Just like we think of $\mathbb{R}$ as a line, we can think of $\mathbb{C}$ as a plane, and the number $a+bi$ has coordinates $(a,b)$ on that plane.

\horlines{9}
% Draw plane. Label real axis and imaginary axis.
% Plot some points on that plane.
% Plot a number and its complex conjugate, note geometric interpretation of reflecting through the real axis.

\exx[6]{Find all eigenvalues and eigenvectors of $A = \begin{bmatrix}
	0 & -1 \\ 1 & 0
	\end{bmatrix}$ (again).}
	% Continue from earlier with lam = \pm i.
	% If lam = -i then null([i,-1;1, i]) is given by y = ix, so span([1,i])
	% If lam = +i then null([-i,-1;1,-i]) is given by y = -ix, so span([1,-i]).
	% Maybe do the multiplication and verify.


\newpage


\section*{Back to Eigenvalues and Eigenvectors}

Recall that the eigenvalues of a matrix $A$ are the solutions $\lambda$ to the equation $\mathrm{det}(A - \lambda I) = 0$. This is a polynomial in $\lambda$, and we give it a special name:

\begin{definition}[Characteristic Polynomial]
	Let $A$ be a square matrix. Then $\mathrm{det}(A - \lambda I)$ is called the \textbf{characteristic polynomial} of $A$, and $\mathrm{det}(A - \lambda I) = 0$ is called the \textbf{characteristic equation} of $A$.
\end{definition}

The characteristic polynomial of an $n \times n$ matrix is always of degree $n$. Since every degree-$n$ polynomial has at most $n$ distinct roots, this immediately tells us that

\horlines{2}
%\begin{center}
%	\Large{An $n \times n$ matrix has at most $n$ distinct (real) eigenvalues.}
%\end{center}

\exx[9]{Find the characteristic polynomial, eigenvalues, and bases of the corresponding eigenspaces, of $A = \begin{bmatrix}1 & -1 & -1 \\	2 & 2 & 1 \\ -1 & 1 & 2 \end{bmatrix}$.}
% When computing the char poly: last 5 terms in determinant just cancel with each other, leaving it already factored by main diagonal.
% Eigenvalues: 1, 2, 2
% Eigenvectors: (0,1,-1) and (1,1,-2) (both eigenspaces are 1-dimensional)


\newpage


\horlines{8}

In the previous example, we had a $3 \times 3$ matrix with only $2$ distinct eigenvalues. However, the matrix has $3$ eigenvalues if we count the multiplicities of the roots of the characteristic polynomial: the eigenvalue $\lambda = 1$ once and the eigenvalue $\lambda = 2$ twice. \\

There is actually another notion of multiplicity of an eigenvalue that is also important: the dimension of the corresponding eigenspace. These ideas lead to the following definition:

\begin{definition}[Multiplicity]
	Let $A$ be a square matrix with eigenvalue $\lambda$.
	\begin{itemize}
		\item The \textbf{algebraic multiplicity} of $\lambda$ is the multiplicity of $\lambda$ as a root of the characteristic polynomial of $A$.
		
		\item The \textbf{geometric multiplicity} of $\lambda$ is the dimension of its eigenspace. % equals number of zero rows when row-reducing A - lambda*I
	\end{itemize}
\end{definition}

In the previous example...

\horlines{3}
% the eigenvalue 1 and 2 each had geometric multiplicty 1, but 1 had algebraic multiplicity 2.


\newpage


The fact that the geometric multiplicity of each eigenvalue was $\leq$ the algebraic multiplicity was not a coincidence: it is our next theorem.

\begin{theorem}[Geo. Mult. $\leq$ Alg. Mult.]
	Let $A$ be a square matrix. Then the geometric multiplicity of each eigenvalue is less than or equal to its algebraic multiplicity.
\end{theorem}

%\noindent For time reasons, we won't prove this theorem---let's spend our time focusing on what we can do with eigenvalues and eigenvectors instead.

A remarkable fact called the Fundamental Theorem of Algebra says that every polynomial of degree $n$ has \emph{exactly} $n$ roots, counted according to multiplicity. This immediately tells us that...

\horlines{6}
% Every matrix has EXACTLY n eigenvalues, counting algebraic multiplicity (in other words, sum of alg. multiplicities equals n always, if complex allowed)
% However, sum of geometric may be smaller than n

\exx[8]{Compute the algebraic and geometric multiplicities of the eigenvalues of all matrices that we considered this week.}


\newpage


Just like with determinants, our eigenvalue life becomes much easier when dealing with triangular matrices.

\exx[6]{Compute the eigenvalues of the matrix $\begin{bmatrix}1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6\end{bmatrix}$.}
% Eigenvalues are diagonal entries 1, 4, 6, eigenvectors are... (1,0,0), (2,3,0), and (16,25,10).
% Maybe note that nothing particularly special about eigenvectors (after the first one anyway).

In general, because the determinant of a triangular matrix is just the product of its diagonal entries, the eigenvalues of a triangular matrix are exactly its diagonal entries:

\begin{theorem}[Eigenvalues of Triangular Matrices]
	Let $A$ be a triangular matrix. Its eigenvalues are exactly the entries on its main diagonal (i.e., $a_{1,1}, a_{2,2}, \ldots, a_{n,n}$).
\end{theorem}
\end{document}