\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\lecture{2: Eigenvalues and their Uses}{Week 3}


As you probably noticed on yesterday's HW, we, um, don't really have any good tools for finding eigenvalues yet.  Let's fix that!

\section{The Determinant}

Specifically, let's fix that by introducing the idea of the \textbf{determinant}.  The motivation for our definition of the determinant, specifically, is coming from the idea of n-dimensional \textbf{signed volume}: in other words, if I give you a list of $n$ vectors in $\mathbb{R}^n$, I want the determinant to tell me the volume of the parallelotope spanned by these $n$ vectors, multiplied by a factor of $\pm 1$ to record the ``orientation\footnote{By ``orientation,'' I am being deliberately vague here.  One good interpretation of this is that we want the sign of the determinant to change if we switch two of these vectors in our list (as visually this kind-of inverts our paralleletope,) and want the paralleletope spanned by all of the standard basis vectors in order to have positive volume.}'' of this paralleletope.

So: in two dimensions, what is this?  Well: if I give you two vectors $(a,b)$ and $(c,d)$, the volume of the parallelogram spanned by these two vectors is just
\begin{align*}
\left| ad- bc \right|,
\end{align*}
something you can show fairly easily/is reserved for the HW.

More trickily, if I give you three vectors $(a,b,c), (d,e,f), (x,y,z)$, if we're really clever, we can show that the area of the parallelepiped spanned by these three vectors is
\begin{align*}
&\left| aez - afy + bfx - bdz + cdy - cex \right|\\
 =& \left| a \cdot (ez - fy) - b(dz - cfx) + c(dy - ex) \right|\\
=& \left| a \cdot \textrm{area}((e,f), (y,z)) - b\cdot \textrm{area}((d,f), (x,z)) + c\cdot \textrm{area}((d,e), (x,y)) \right|.\\
\end{align*}

So: this suggests a recursive definition for our concept of the determinant!  Specifically, it suggests the following definition:

\begin{definition}
For a $n \times n$ matrix A, let $A_{ij}$ denote the matrix formed from $A$ by deleting the $i$-th row and $j$-th column from $A$.

Then, we can define the \textbf{determinant} of $A$ recursively\footnote{A \textbf{recursive} definition is one that is defined recursively!} as follows:  for $1 \times 1$ matrices, we define $\det(A) = a_{11}$, and for larger $n \times n$ matrices $A$, we define
\begin{align*}
\det(A) = \sum^{n}_{i=1} (-1)^{i-1} a_{1i} \cdot \det(A_{1i}).
\end{align*}
\end{definition}

The determinant has a ton of properties.  We list some of them here, and leave the rest for you to prove on the HW:
\begin{enumerate}
\item If $I_n$ is the $n \times n$ identity matrix, then $\det(I_n) = 1$.
\item Suppose that $A$ is a $n \times n$ matrix.  If $A'$ is the matrix acquired by multiplying the $k$-th row of $A$ by some constant $\lambda$, then $\det(A') = \lambda \det(A)$.
\item For any pair of $n \times n$ matrices $A, B$, $\det(AB) = \det(A)\cdot \det(B)$.  In particular, this tells us that $\det(A^{-1}) = 1/\det(A)$, whenever $A$ is an invertible matrix.
\end{enumerate}

With these observations locked down, we move to our stated claim:
\begin{theorem}
If $\textbf{v}_1, \ldots \textbf{v}_n$ are a list of vectors in $\mathbb{R}^n$, then the volume of the parallelotope spanned by these vectors is just the absolute value of the determinant of the following matrix:
\begin{align*}
A = \left( \begin{array}{ccccc}
v_{11} &  v_{12} & v_{13} & \ldots &  v_{1n} \\
v_{21} &  v_{22} & v_{23} & \ldots &  v_{2n} \\
v_{31} &  v_{32} & v_{33} & \ldots &  v_{3n}\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
v_{n1} & v_{n2} & v_{n3} & \ldots & v_{nn} \\
\end{array}\right),
\end{align*}
where $\textbf{v}_i = (v_{i,1}, \ldots v_{i,n})$.
\end{theorem}

\begin{proof}
First, recall that by the \textbf{singular value decomposition theorem}, we can write \textit{any} matrix $A$ as the product
\begin{align*}
U \cdot D \cdot V^T,
\end{align*}
where $U$ and $V$ are a pair of unitary matrices and $D$ is a diagonal matrix.  Geometrically, this theorem tells us that we can write any linear transformation $A$ as the product of three steps:
\begin{itemize}
\item a rotation/reflection map $V^T$,
\item a map which stretches all of the co\"ordinate axes by constants $d_i$, i.e. the map $D$, and
\item another rotation/reflection map $U$.
\end{itemize}
So: because 
\begin{align*}
\det(A) = \det(UDV^T) = \det(U) \cdot \det(D) \cdot \det(V^T),
\end{align*}
and the determinant of any unitary matrix\footnote{ This is because unitary matrices have their inverses equal to their transposes, and thus we have $\det(I_n) = \det(UU^{-1}) = \det(UU^T) = \det(U)\det(U^T) = \det(U)^2$.} is $\pm1$, we have
\begin{align*}
\det(A) = \det(U) \cdot \det(D) \cdot \det(V^T) = \pm \prod_{i=1}^n d_i,
\end{align*}
where the $d_i$'s are the entries on the diagonal of $D$.

But what is the volume of our paralleletope in the first place?  Well: because $A \cdot I = A$, we can regard it as the volume of the unit cube $[0,1]^n$ under the transformation given by $A$.  But what does $A$ do to a unit cube?  Well: 
\begin{itemize}
\item First, it passes it through a rotation/reflection map $V^T$, which does not change the volume.
\item Then, it passses it through a map which stretches all of the co\"ordinate axes by constants $d_i$.  This scales the volume by $d_i$ for each such stretching; so this changes the volume by a factor of $\prod_{i=1}^n d_i$.
\item Finally, it passes it through another rotation/reflection map $U$, which does not change the volume.
\end{itemize}
Therefore, the volume of our paralleletope is $\prod_{i=1}^n d_i$, as claimed.
\end{proof}

One nice corollary of this proof is that the determinant of a matrix $A$ is zero iff the rows of $A$ are linearly dependent, as the volume of the paralellotope defined by these vectors is zero precisely when their span can be contained in some $n-k$-dimensional space, for $k \geq 1$.



Why did we have this discussion?  Well, primarily, because it gives us a \textbf{really effective tool} for finding eigenvalues!  Why is this?  Well: what does it mean to be an eigenvalue $\lambda$ for some matrix $A$?  It means that there is some vector $\textbf{v}$ such that 
\begin{align*}
& A\textbf{v} = \lambda \textbf{v} \\
\Leftrightarrow & A\textbf{v} - \lambda \textbf{v} = 0 \\
\Leftrightarrow & (A - \lambda I) \textbf{v}= 0, \\
\end{align*}
which holds iff there is some nontrivial way to combine $A - \lambda I$'s rows to get to zero, which holds iff the determinant of $A - \lambda I$ is zero!

In other words, we've just proven the following:
\begin{proposition}
For a matrix $A$, $\lambda$ is an eigenvalue of $A$ iff $\lambda$ is a root of the polynomial
\begin{align*}
\det(A - x I).
\end{align*}
\end{proposition}

We've thus reduced our eigenvalue search to simply finding the roots of a polynomial, something we are generally pretty decent at!  We calculate some actual eigenvalues in the next section:


\section{Calculating Spectra}


\begin{example}
The spectrum of $K_n$:  The adjacency matrix of $K_n$ is
\begin{align*}
\left( \begin{array}{ccccc}
 0 &  1 & 1 & \ldots &  1 \\
 1 &  0 & 1 & \ldots &  1 \\
 1 &  1 & 0 & \ldots &  1 \\
 \vdots &  \vdots & \vdots & \ddots &  \vdots\\
 1 &  1 & 1 & \ldots &  0 \\
\end{array}\right) = \left( \begin{array}{ccccc}
 1 &  1 & 1 & \ldots &  1 \\
 1 &  1 & 1 & \ldots &  1 \\
 1 &  1 & 1 & \ldots &  1 \\
 \vdots &  \vdots & \vdots & \ddots &  \vdots\\
 1 &  1 & 1 & \ldots &  1 \\
\end{array}\right) - I_n.
\end{align*}
Consequently, its characteristic polynomial has roots wherever the rows of
\begin{align*}
\left( \begin{array}{ccccc}
 -\lambda &  1 & 1 & \ldots &  1 \\
 1 &  -\lambda & 1 & \ldots &  1 \\
 1 &  1 & -\lambda & \ldots &  1 \\
 \vdots &  \vdots & \vdots & \ddots &  \vdots\\
 1 &  1 & 1 & \ldots &  -\lambda \\
\end{array}\right)
\end{align*}
are linearly dependent, with multiplicity equal to $n - ($number of linearly independent rows).  What are these roots and multiplicities? Well: when $\lambda = -1$, this matrix is the all-1's matrix, and thus has only one linearly independent row: so the eigenvalue $-1$ occurs with multiplicity $n-1$.  This leaves at most one root in the characteristic polynomial for us to find!

So: when $\lambda = n-1$, we have that the sum of all of the rows in our matrix is 0; therefore, this is also an eigenvalue of our matrix.  As we've found $n$ eigenvalues, we know that we've found them all, and can thus conclude that the spectrum of $K_n$ is $\{(n-1)^1, (-1)^{n-1}\}$ (where the superscripts here denote multiplicity, not being raised to a power,) and its characteristic polynomial is $(x-n+1)(x+1)^{n-1}$.
\end{example}

\begin{example}
Let $S_n$ denote the star graph, with one central vertex connected to $n-1$ outer leaves.  The adjacency matrix for this graph (if we suppose that the central vertex is numbered $n$) is of the form
\begin{align*}
A = \left( \begin{array}{ccccc}
 0 &  0 & \ldots & 0 & 1 \\
 0 &  0 & \ldots & 0 & 1 \\
 \vdots &  \vdots & \ddots & \vdots &  \vdots\\
 0 &  0 & \ldots & 0 & 1 \\
 1 &  1 & \ldots & 1 & 0 \\
\end{array}\right) 
\end{align*}
Consequently, its characteristic polynomial has roots wherever
\begin{align*}
\det \left( \begin{array}{ccccc}
 -\lambda &  0 & \ldots & 0 & 1 \\
 0 &  -\lambda & \ldots & 0 & 1 \\
 \vdots &  \vdots & \ddots & \vdots &  \vdots\\
 0 &  0 & \ldots & -\lambda & 1 \\
 1 &  1 & \ldots & 1 & -\lambda \\
\end{array}\right) 
\end{align*}
is zero.  By applying the recursive definition of the determinant, we can expand along the top row of our matrix and see that 

\begin{align*}
\det \left( A_{S_n} - \lambda I \right) &= -\lambda \cdot \det \left( A_{S_{n-1}} - \lambda I \right)  + (-1)^{n-1} \cdot \det \left( \begin{array}{ccccc}
 0 & -\lambda &  0 & \ldots & 0\\ 
 0 & 0 &  -\lambda & \ldots & 0\\
 \vdots & \vdots &  \vdots & \ddots & \vdots\\
 0 & 0 &  0 & \ldots & -\lambda \\
 1 & 1 &  1 & \ldots & 1 \\
\end{array}\right) \\
\end{align*}
From here, we apply the permutation $(1,2,\ldots n-1) \mapsto (n-1, 1, 2, \ldots)$ to the right-side matrix, which changes its determinant by $(-1)^{n-2}$:
\begin{align*}
&= -\lambda \cdot \det \left( A_{S_{n-1}} - x I \right)  + (-1)^{2n-3} \cdot \det \left( \begin{array}{ccccc}
 1 & 1 &  1 & \ldots & -\lambda \\
 0 & -\lambda &  0 & \ldots & 0\\ 
 0 & 0 &  -\lambda & \ldots & 0\\
 \vdots & \vdots &  \vdots & \ddots & \vdots\\
 0 & 0 &  0 & \ldots & -\lambda \\
\end{array}\right) \\
\end{align*}
Finally, we take the transpose of this matrix, which does not affect the determinant.  From there, applying the definition of the determinant makes it obvious that its determinant is the product of the diagonal entries in this matrix, as after one expansion the diagonal is the only thing left:
\begin{align*}
&= -\lambda \cdot \det \left( A_{S_{n-1}} - x I \right)  + (-1)^{2n-3} \cdot \det \left( \begin{array}{ccccc}
 1 & 0 &  0 & \ldots & 0 \\
 1 & -\lambda &  0 & \ldots & 0\\ 
 1 & 0 &  -\lambda & \ldots & 0\\
 \vdots & \vdots &  \vdots & \ddots & \vdots\\
 -\lambda & 0 &  0 & \ldots & -\lambda \\
\end{array}\right)\\
&= -\lambda \cdot \det \left( A_{S_{n-1}} - x I \right)  + (-1)^{2n-3} \cdot 1 \cdot  \det \left( \begin{array}{cccc}
 -\lambda &  0 & \ldots & 0\\ 
 0 &  -\lambda & \ldots & 0\\
 \vdots &  \vdots & \ddots & \vdots\\
 0 &  0 & \ldots & -\lambda \\
\end{array}\right)\\
&= -\lambda \cdot \det \left( A_{S_{n-1}} - \lambda I \right) + (-1)^{3n-5} \cdot \lambda^{n-2} \\
&= -\lambda \cdot \det \left( A_{S_{n-1}} - \lambda I \right) + (-1)^{n-1}\lambda^{n-2}.\\
\end{align*}
Plugging in the observation that $\det(A_{S_2} - \lambda I) = \lambda^2 - 1$, we recursively have that 
\begin{itemize}
\item $\det(A_{S_3} - \lambda I) = -\lambda(\lambda^2 - 1)+ \lambda^1 = -\lambda^3 + 2\lambda$ \\
\item $\det(A_{S_4} - \lambda I) = -\lambda(-\lambda^3 +2\lambda) - \lambda^2 = \lambda^4 - 3\lambda^2,$ \\
\item and in general $\det(A_{S_n} - \lambda I) = (-1)^{n} \cdot \lambda^{n-2}\cdot(\lambda^2 - (n-1))$.
\end{itemize}

Consequently, by solving for the roots of this polynomial, we can see that the spectrum of $S_n$ is $\{(\sqrt{n-1})^2, 0^{n-2}\}$.
\end{example}


\begin{example}
The spectrum of $C_n$:  The adjacency matrix of $C_n$ is
\begin{align*}
A_{C_n}\left[ \begin{array}{cccccc}
0 & 1 & 0 & 0 &\ldots  & 1 \\
1 & 0 & 1 & 0 & \ldots  & 0 \\
0 & 1 & 0 & 1 & \ldots & 0 \\
0 & 0 & 1 & 0 & \ddots & 0 \\
\vdots & \vdots & \vdots & \ddots & \ddots  & 1 \\
1 & 0  & 0 & \ldots & 1 & 0 \\
\end{array} \right].
\end{align*}

This \ldots is kinda awful.  So: let's be clever!  Specifically, let's consider instead the \textbf{directed cycle} $D_n$, formed by taking the cycle graph $C_n$ and orienting each edge $\{i,i+1\}$ so that it goes from $i$ to $i+1$.  This graph has adjacency matrix given by the following:
\begin{align*}
A_{D_n} =  \left[ \begin{array}{cccccc}
0 & 1 & 0 & 0 &\ldots  & 0 \\
0 & 0 & 1 & 0 & \ldots  & 0 \\
0 & 0 & 0 & 1 & \ldots & 0 \\
0 & 0 & 0 & 0 & \ddots & 0 \\
\vdots & \vdots & \vdots & \ddots & \ddots  & 1 \\
1 & 0  & 0 & \ldots & 0 & 0 \\
\end{array} \right].
\end{align*}

What's the characteristic polynomial of this matrix?  Well: it's what you get when you take the determinant
\begin{align*}
\det(A_{D_n} - \lambda I) = \det\left( \left[ \begin{array}{cccccc}
-\lambda & 1 & 0 & 0 &\ldots  & 0 \\
0 & -\lambda & 1 & 0 & \ldots  & 0 \\
0 & 0 & -\lambda & 1 & \ldots & 0 \\
0 & 0 & 0 & -\lambda & \ddots & 0 \\
\vdots & \vdots & \vdots & \ddots & \ddots  & 1 \\
1 & 0  & 0 & \ldots & 0 & -\lambda \\
\end{array} \right]\right).
\end{align*}
If we apply the definition of the determinant, we can expand along the top row of this matrix and write $\det(A_{D_n} - \lambda I)$ as 
\begin{align*}
&-\lambda \cdot \det \left(\left[ \begin{array}{ccccc}
-\lambda & 1 & 0 & \ldots  & 0 \\
 0 & -\lambda & 1 & \ldots & 0 \\
0 & 0 & -\lambda & \ddots & 0 \\
 \vdots & \vdots & \ddots & \ddots  & 1 \\
 0  & 0 & \ldots & 0 & -\lambda \\
\end{array} \right]\right) - 1 \cdot \det\left( \left[ \begin{array}{ccccc}
0 & 1 & 0 & \ldots  & 0 \\
0 & -\lambda & 1 & \ldots & 0 \\
0 & 0 & -\lambda & \ddots & 0 \\
\vdots & \vdots & \ddots & \ddots  & 1 \\
1  & 0 & \ldots & 0 & -\lambda \\
\end{array} \right]\right).\\
\end{align*}
The left matrix has determinant equal to the product of its diagonal entries: this can be seen by taking its transpose and repeatedly applying the definition of the determinant.  The right matrix is a bit trickier: however, if we permute the columns of this matrix by sending $(1,2,\ldots n-1) \mapsto (n-1, 1,2, \ldots)$, we will change the determinant by $(-1)^{n-2}$, and have our sum of matrices in the following form:
\begin{align*}
=&(-1)^n\lambda^n - (-1)^{n-2} \det\left( \left[ \begin{array}{ccccc}
1 & 0 & \ldots  & 0 & 0\\
-\lambda & 1 & \ldots & 0 & 0\\
0 & -\lambda & \ddots & 0 & 0\\
\vdots & \vdots & \ddots  & 1 & \vdots\\
0 & \ldots & 0 & -\lambda & 1\\
\end{array} \right]\right).\\
\end{align*}
This right matrix now has determinant given by $1$, which we can see by just repeatedly applying the definition of the determinant.  Therefore, we've shown that 
\begin{align*}
\det( A_{D_n} - \lambda I) = (\lambda^{n} - 1)\cdot (-1)^{n}.\\
\end{align*}
The roots of this are precisely the \textbf{$n$-th roots of unity}, i.e. the $n$ distinct numbers $1, e^{(2\pi i)/n}, e^{(2 \pi i)2/n}, \ldots  e^{(2 \pi i)(n-1)/n}$ such that any of these numbers $\zeta$, when raised to the $n$-th power, is 1.  Furthermore, we can actually see that each of these eigenvalues $\zeta$ has corresponding eigenvector given by $(1, \zeta, \zeta^2, \ldots \zeta^{n-1}),$ because
\begin{align*}
\left[ \begin{array}{cccccc}
0 & 1 & 0 & 0 &\ldots  & 0 \\
0 & 0 & 1 & 0 & \ldots  & 0 \\
0 & 0 & 0 & 1 & \ldots & 0 \\
0 & 0 & 0 & 0 & \ddots & 0 \\
\vdots & \vdots & \vdots & \ddots & \ddots  & 1 \\
1 & 0  & 0 & \ldots & 0 & 0 \\
\end{array} \right] \cdot \left[ \begin{array}{c} 1 \\ \zeta \\ \zeta^2 \\ \zeta^3 \\ \vdots \\ \zeta^{n-1} \\ \end{array} \right] = \left[ \begin{array}{c} \zeta \\ \zeta^2 \\ \zeta^3 \\ \zeta^4 \\ \vdots \\ 1 = \zeta^n \\ \end{array} \right] = \zeta \cdot \left[ \begin{array}{c} 1 \\ \zeta \\ \zeta^2 \\ \zeta^3 \\ \vdots \\ \zeta^{n-1} \\ \end{array} \right].
\end{align*}

Turning this into information about $C_n$ is not a difficult thing to do: therefore, we leave it for the homework!
\end{example}


With these examples worked, we can close with a question we placed on the last HW set, whose answer we should now be able to answer:

\begin{question}
If $G_1$ and $G_2$ are a pair of graphs with the same spectrum, are $G_1$ and $G_2$ isomorphic?
\end{question}
\end{document}