\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{3: Turning Eigenvalues Into Information}{Week 3}

Last lecture/in TAU, I had a number of students ask me just what these eigenvalues ``represent '' in a graph.  Today, we'll start answering that question!
\section{Basic Applications of Eigenvalues}

In our introduction to graph theory course, pretty much the first interesting thing we did was characterize bipartite graphs.  As it turns out, we can do the same thing here in terms of the spectra:
\begin{proposition}
A graph $G$ is bipartite if its spectrum is symmetric about 0 (i.e. $\lambda$ is an eigenvalue of $A_G$ iff $-\lambda$ is.)
\end{proposition}
\begin{proof}
Write $G = (V_1 \cup V_2, E),$, where $V_1 = \{1,2,\ldots k\}$ and  $V_2 = \{k+1, k+2, \ldots n\}$ partition $G$'s vertices.   In this form, we know that the only edges in our graph are from $V_1$ to $V_2$.  Consequently, this means that $A_G$ is of the form
\begin{align*}
\begin{array}{|c|c|}
\hline
0 & B \\
\hline
B^T & 0 \\
\hline
\end{array},
\end{align*}
where the upper-left hand 0 is a $k \times k$ matrix, the lower-right hand 0 is a $n-k \times n-k$ matrix,  $B$ is a $(n - (k+1)) \times k$ matrix, and $B^T$ is the transpose of this matrix.

Choose any eigenvalue $\lambda$ and any eigenvector $(v_1, \ldots v_k, w_{k+1}, \ldots w_{n}) = (\mathbf{v}, \mathbf{w})$.  Then, we have
\begin{align*}
A_G \cdot (\mathbf{v}, \mathbf{w}) =
\begin{array}{|c|c|}
\hline
0 & B \\
\hline
B^T & 0 \\
\hline
\end{array} \cdot \left[ \begin{array}{c} \mathbf{v}\\ \mathbf{w} \end{array} \right] =  \left[ \begin{array}{c} B \cdot \mathbf{w} \\ B^T \cdot \mathbf{v} \end{array} \right] =   \left[ \begin{array}{c} \lambda\cdot \mathbf{v}\\ \lambda \cdot \mathbf{w} \end{array} \right] = \lambda \left[ \begin{array}{c} \mathbf{v}\\  \mathbf{w} \end{array} \right]
\end{align*}

But!  This is not the only eigenvector we can make out of $\mathbf{v}$ and $\mathbf{w}$.  Specifically, notice that if we multiply $A_G$ by the vector $(\mathbf{v}, -\mathbf{w})$, we get

\begin{align*}
A_G \cdot (\mathbf{v}, -\mathbf{w}) =
\begin{array}{|c|c|}
\hline
0 & B \\
\hline
B^T & 0 \\
\hline
\end{array} \cdot \left[ \begin{array}{c} \mathbf{v} \\ -\mathbf{w} \end{array} \right] =  \left[ \begin{array}{c} -B \cdot \mathbf{w} \\ B^T \cdot \mathbf{v} \end{array} \right] =   \left[ \begin{array}{c} -\lambda \cdot \mathbf{v} \\  \lambda \cdot \mathbf{w} \end{array} \right] = -\lambda \left[ \begin{array}{c} \mathbf{v}\\  -\mathbf{w} \end{array} \right].
\end{align*}
In other words, whenever $\lambda$ is an eigenvalue of $A_G$, $-\lambda$ is as well!
\end{proof}



As well, one of the next things we studied was how certain key properties (like $\chi(G)$) depended on the maximum degree of the graph, $\Delta(G)$.  As this provides an upper bound on the overall density of our graph, it seems like a natural candidate for something to bound our eigenvalues by.  We make this explicit in the following proposition:
\begin{proposition}
If $G$ is a graph and $\lambda$ is an eigenvalue of $A_G$, then $|\lambda| \leq \Delta(G)$.
\end{proposition}
\begin{proof}
Take any eigenvalue $\lambda$ of $A_G$, and let $\mathbf{v} = (v_1, \ldots v_n)$ be a corresponding eigenvector to $\lambda$.  Let $v_k$ be the largest co\"ordinate in $\mathbf{v}$, and (by scaling $\mathbf{v}$ if necessary) insure that $v_k = 1$.

We seek to show that $|\lambda| \leq \Delta(G)$.  To see this, simply look at the quantity $|\lambda \cdot v_k |$.  On one hand, we trivially have that this is $|\lambda|.$

On the other, we can use the observation that $\mathbf{v}$ is an eigenvector to notice that
\begin{align*}
|\lambda \cdot v_k | &= \left| (a_{k1}, a_{k2}, \ldots a_{kn}) \cdot (v_1, \ldots v_n) \right| \\
&= \left| \sum_{j=1}^n a_{kj} v_j \right| \leq \left| \sum_{j=1}^n a_{kj} v_k \right| = \left| v_k \sum_{j=1}^n a_{kj} \right| \\
&\leq \left| v_k \cdot \Delta(G) \right|  = \Delta(G).\\
\end{align*}
\end{proof}

When is the above bound tight?  With many graph properties (like, again, $\chi(G)$,) answering this question is usually difficult.  Here, however, it's actually quite doable!, as we demonstrate in the next proposition:
\begin{proposition}
A connected graph $G$ is regular if and only if $\Delta(G)$ is an eigenvalue of $A_G$.
\end{proposition}
\begin{proof}
As this is an if and only if, we have two directions to prove.

($\Rightarrow$:)  If $G$ is regular, then each vertex in $G$ has degree $\Delta(G)$.  This means (amongst other things) that there are precisely $\Delta(G)$ 1's in every row of $A_G$.  Consequently, if we look at $A_G \cdot (1,1,1\ldots 1)$, we know that we get the vector $(\Delta(G), \Delta(G), \ldots \Delta(G))$: i.e. $\Delta(G)$ is an eigenvector!

($\Leftarrow$:)  As before, pick an eigenvector $\mathbf{v}$ for our eigenvalue $\Delta(G)$, let $v_k$ be the largest component of $\mathbf{v}$, and rescale $\mathbf{v}$ so that $v_k = 1$.  Then, just as before, we have
\begin{align*}
|\Delta(G)| &= |\Delta(G) \cdot v_k| = \left| (a_{k1}, \ldots a_{kn}) \cdot (v_1, \ldots v_n) \right|\\
&= \left| \sum_{i=1}^n a_{ki}v_i \right| \leq \left| \sum_{i=1}^n a_{ki}v_k \right| = \left| v_k\right| \left| \sum_{i=1}^n a_{ki} \right| = \deg(v_k) \\
&\leq \Delta(G),\\
\end{align*} 
and therefore $\deg(v) = \Delta(G)$.

But wait!   If the above is true, we actually have
\begin{align*}
|\Delta(G)|= \left| \sum_{i=1}^n a_{ki}v_i \right| = \Delta(G),\\
\end{align*} 
and therefore $v_i$ is equal to 1 for \textbf{every} $i$ adjacent to $k$!  Therefore, we can repeat the above argument for every $i$ adjacent to $k$, and show that the degree of all of these vertices are also $\Delta(G)$.  Repeating this process multiple times shows that the degree of \textbf{every} vertex is $\Delta(G)$, and therefore that $G$ is regular.
\end{proof}


\begin{proposition}
If $G$ is a graph with diameter\footnote{The \textbf{diameter} of a graph $G$ is the length of the longest cycle in $G$ with no repeated edges.} $d$, then $A_G$ has at least $d + 1$ distinct eigenvalues.
\end{proposition}
\begin{proof}
First, recall the spectral theorem, which says that (because $A_G$ is real-valued and symmetric) we can find an orthonormal basis for $\mathbb{R}^n$ made out of $A_G$'s eigenvectors.  Let $\mathbb{e}_1, \ldots \mathbb{e}_n$ be such a basis of orthonormal eigenvectors, and let the collection of distinct eigenvalues of $A_G$ be $\theta_1, \ldots \theta_t$. 

Examine the product $D = (M - \theta_1 \cdot I)\cdot(M - \theta_2 \cdot I)\cdot\ldots (M - \theta_t \cdot I)$; specifically, notice that the order of the $\theta_i$'s doesn't matter in this above product, as
\begin{align*}
 &(M - \theta_1 \cdot I)\cdot(M - \theta_2 \cdot I)\cdot\ldots (M - \theta_t \cdot I)\\
 =& M^t - \left(\sum_{i=1}^n \theta_i\right)M^{t-1} + \ldots + \prod_{i=1}^t \theta_i \cdot I,\\
\end{align*}
and the $\theta$s in each of the coefficients above clearly commute.

What happens when we multiply $D$ on the right by any of these $e_{i_t}$'s?  Well: if we permute the $(M-\theta I)$'s around so that $(M - \theta_{i_t} I)$ is the first term, we have
\begin{align*}
& (M - \theta_{i_1} \cdot I)\cdot(M - \theta_{i_2} \cdot I)\cdot\ldots (M - \theta_{i_t} \cdot I) \cdot e_{i_t}\\
=& (M - \theta_{i_1} \cdot I)\cdot(M - \theta_{i_2} \cdot I)\cdot\ldots \cdot (M\cdot e_{i_t} - (\theta_{i_t}\cdot I) \cdot e_{i_t} )\\
= &(M - \theta_{i_1} \cdot I)\cdot(M - \theta_{i_2} \cdot I)\cdot\ldots \cdot 0\\
=& 0.\\
\end{align*}

But this means that $D$ sends \textbf{all} of the $e_i$'s to 0: i.e. that $D$ sends all of these basis vectors for $\mathbb{R}^n$ to 0!  In other words, this forces $D = 0$.

But what does this mean?  Using our expansion above of $D$ into a polynomial, we've just shown that
\begin{align*}
M^t - \left(\sum_{i=1}^n \theta_i\right)M^{t-1} + \ldots + \prod_{i=1}^t \theta_i \cdot I = 0,\\
\end{align*}
which means that 
\begin{align*}
M^t  =  \left(\sum_{i=1}^n \theta_i\right)M^{t-1} + \ldots - \prod_{i=1}^t \theta_i \cdot I. \\
\end{align*}

What would happen if the diameter $d$ is greater than $t - 1$?  It would mean that there are two vertices $i,j$ such that $d(i,j) = t$, at the very least!  But this would mean that the $(i,j)$-th entry of $M^t$ would be nonzero (as there is a path of length $t$ between them), while the $(i,j)$-th entry of $M^k$ would be zero for every $k < t$ (as there are no paths of shorter length linking them.)  But this is impossible, because we've written $M^t$ as the sum of these smaller matrices!  

Therefore, this cannot occur: i.e. we have $d \leq t-1$, which is what we wanted to prove.
\end{proof}
\end{document}