\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{4: Spectra and $\chi$}{Week 3}

This lecture is going to be \textbf{awesome.}

\begin{theorem}
For any graph $G$ on $n$ vertices, we have $\chi(G) \geq  1 - \frac{\lambda_{\textrm{max}}(G)}{\lambda_{\textrm{min}}(G)}$.
\end{theorem}
\begin{proof}
This proof is easily the hardest/most conceptually difficult thing we're going to do in this class, and involves some rather strange/mysterious steps.  To make this less mysterious, we're going to begin this proof with a ``roadmap:'' i.e. before we start, I want to talk about how the proof is going to go, and what tricks we're going to use later (so that they're not so baffling when they do show up!)

So: roadmap.   We're studying the object $A_G$, $G$'s adjacency matrix; specifically, we want a way to think about $\chi(G)$ while working with $A_G$.  How can we do this?  Well: one way is the following:
\begin{itemize}
\item Take $G$, and turn it into a $n$-dimensional vector space, by associating to each vertex $v_j$ the basis vector $\mathbf{e}_j$ of $\mathbb{R}^n$ that's got a 1 in the $i$-th co\"ordinate and 0's everywhere else.
\item Once you've done this, take any $\chi(G) = k$-coloring of $G$, and let $C_1, \ldots C_k$ be the $k$ distinct color classes of the vertices in $G$.
\item  So we've taken our graph $G$, turned it into a vector space, and used this abstraction to give us a way to ``condense'' $G$ along its color classes $C_1, \ldots C_k$.  How can we use these color classes to talk about $A_G$, and specifically about its eigenvalues?
\item Well: let $\lambda_{\textrm{max}}$ be the largest eigenvalue of $A_G$, and $\textbf{v}$ be a corresponding eigenvector for $\lambda$.  Because the basis vectors $\{\mathbf{e}_1, \ldots \mathbf{e}_n\}$ for $\mathbb{R}^n$ are each in one of the $U_i$'s, we can find a way of writing $\mathbf{v}$ as a sum of elements 
\begin{align*}
\sum_{i=1}^k c_i \cdot \mathbf{u}_i,
\end{align*}
where each $\mathbf{u}_i$ is in $U_i$, and they're all of length 1.  Notice that all of the $\mathbf{u}_i$ are orthogonal, as each $\mathbf{u}_i$ only has nonzero co\"ordinates at the locations where $U_i$ contains the appropriate basis vector $\mathbf{e}_i$. 
\item Now, let $U$ be the vector space generated by taking the vectors $\{\mathbf{u}_1, \mathbf{u}_2, \ldots \mathbf{u}_k \}$ as a \textbf{basis}: i.e. look at the space formed by taking linear combinations made precisely out of these $\mathbf{u}_i$'s.  This is a $k$-dimensional space, and can be thought of as a way to ``collapse'' our original vector space along the $k$ color classes we have, in a way that preserves the largest eigenvector of $A_G$, as it's in this space!
\item Let $S$ denote the $n \times k$ matrix that sends a vector in $U$ (written in the $k$-dimensional form $(a_1 \mathbf{u}_1, a_2 \mathbf{u}_2, \ldots a_k \mathbf{u}_k)$ to the same vector as expressed in $\mathbb{R}^n$ (i.e as the $n$-dimensional vector $\sum a_i \mathbf{u}_i$).  This matrix is specifically given as
\begin{align*}
S = \left[ \begin{array} {cccc}  
\vdots & \vdots &  & \vdots \\
\mathbf{u}_1 & \mathbf{u}_2 & \ldots & \mathbf{u}_n \\
\vdots & \vdots &  & \vdots \\
\end{array} \right].
\end{align*}
\item Finally, examine the linear map $B = S^T \cdot A_G \cdot S$, which takes in $k$-dimensional things (i.e. elements in $U$) and spits out other $k$-dimensional things (because the dimension of this matrix is $(k \times n) \cdot (n \times n) \cdot (n \times k)$ $= (k \times k)$.)  In essence, this map takes in elements in our condensed space $U$, interprets them as vectors in $R^n$, acts on them by $A_G$, and then takes them back into $U$.  This certainly seems like a promising object to study! -- it seems to be designed to preserve the largest eigenvalue of $A_G$, and yet only deal with a $\chi(G)$-sized subspace.
\item Explicitly, we claim that this ``condensing map'' $B$ has the following properties:
\begin{itemize}
\item It has $\chi(G)$-many eigenvalues.
\item Its maximal eigenvalue is the same as the eigenvalue of $A_G$.
\item Its minimal eigenvalue is bounded below by the minimal eigenvalue of $A_G$.
\item The sum of all of the eigenvalues for this graph is 0.
\end{itemize}
\item Notice that if we can prove these observations, we are done!  I.e. if you plug in these three observations together, bounding all of the non-maximal eigenvalues below by $\lambda_{\textrm{min}}$ and noting that the maximal one is $\lambda_{\textrm{max}}$, we will have shown that $\lambda_{\textrm{max}}(G) + (\chi(G) - 1) \lambda_{\textrm{min}}(G) \leq 0$, which after some rearranging\footnote{and noticing that the smallest eigenvalue $\lambda_{\textrm{min}}$ is always negative for adjacency matrices of loopless graphs!} gives our inequality above.
\end{itemize}

So, it suffices to prove these observations.  We do this in the following series of lemmas and definitions:

\begin{definition}
Given two vectors $\mathbf{u}, \mathbf{v}$ in the same vector space, their \textbf{inner product} $\langle \mathbf{u}, \mathbf{v} \rangle$ is just their dot product:
\begin{align*}
\langle \mathbf{u}, \mathbf{v} \rangle = \mathbf{u}^T \cdot \mathbf{v} = \sum_{i=1}^n u_i v_i.
\end{align*}
It's just notation, but it helps clean up a lot of things.  We'll use it heavily throughout the following proofs.
\end{definition}



\begin{lemma}
$B$ is a symmetric matrix.  
\end{lemma}
\begin{proof}
To see this, just take its transpose, remembering that $A_G$ is itself a symmetric matrix: $B^T = (S^T \cdot A_G \cdot  S)^T = (S^T)^T \cdot A_G^T \cdot S^T = S \cdot A_G \cdot A^T.$ 
\end{proof}

\begin{corollary}
$B$ has $\chi(G)$-many eigenvalues.
\end{corollary}
\begin{proof}
Just use the spectral theorem!  
\end{proof}

Furthermore, by applying the spectral theorem on $B$ again, you can prove (on the HW!) the following proposition: 
\begin{proposition}
For any real symmetric matrix $A$ and for any vector $\mathbf{v}$ with $||v|| = 1$, we have
\begin{align*}
\mu_{\textrm{min}} \leq  \langle A \mathbf{v}, \mathbf{v}\rangle \leq \mu_{\textrm{max}},
\end{align*}
where $\mu_{\textrm{min}}, \mu_{\textrm{max}}$ are the smallest and largest eigenvectors of $A$, respectively.  Furthermore, these bounds are always attained (specifically, by taking $\mathbf{v}$ to be an eigenvector corresponding to either the smallest or largest eigenvalue.)
\end{proposition}

The reason we care about the above proposition is the following lemma:
\begin{lemma}
For any two vectors $\mathbf{v}, \mathbf{u} \in U$, we have
\begin{align*}
\langle B \mathbf{u}, \mathbf{v} \rangle  = \langle (S^T \cdot A_G \cdot S) \mathbf{u}, \mathbf{v} \rangle   =\langle (A_G \cdot S) \mathbf{u}, S \mathbf{v} \rangle 
\end{align*}
\end{lemma}
\begin{proof}
By definition, we have 
\begin{align*}
 \langle (S^T \cdot A_G \cdot S) \mathbf{u}, \mathbf{v} \rangle &=  (S^T \cdot A_G \cdot S \mathbf{u})^T \cdot \mathbf{v}\\
 &= (\mathbf{u}^T S^T \cdot A_G^T \cdot S)  \cdot \mathbf{v}\\
 &= (\mathbf{u}^T S^T \cdot A_G^T) \cdot (S  \mathbf{v})\\
 &= (A_G \cdot S \mathbf{u})^T \cdot (S  \mathbf{v})\\
 &= \langle (A_G\cdot S)  \mathbf{u} , S  \mathbf{v}\rangle .\\
\end{align*}
\end{proof}

Why do we mention this lemma?  Well, it allows us to prove another one of $B$'s claimed properties:
\begin{corollary}
The eigenvalues of $B$ are all bounded above by $A_G$'s maximum eigenvalue $\lambda_{\textrm{max}}$, and below by $A_G$'s minimum eigenvalue $\lambda_{\textrm{min}}$.  
\end{corollary}
\begin{proof}
In lemma 4, we proved that every inner product $\langle B \mathbf{v}), \mathbf{v}\rangle$ can be written in the form $\langle (A_G \cdot S) \mathbf{u}, S \mathbf{u} \rangle.$  So, if we apply our proposition above to the real symmetric matrix $A_G$, we have just shown that these values $\langle (A_G \cdot S) \mathbf{u}, S \mathbf{u} \rangle$ are bounded above by $\lambda_{\textrm{max}}$ and below by $\lambda_{\textrm{min}}$, where these are $A_G$'s maximum and minimum eigenvalues. 

 Therefore, we know that we must have $\mu_{\textrm{max}} \leq \lambda_{\textrm{max}}$ and $\mu_{\textrm{min}} \leq \lambda_{\textrm{min}}$, as these values are bounding all of the possible results for $\langle B\mathbf{v}, \mathbf{v} \rangle$, and therefore in specific are bounding $B$'s maximum and minimum eigenvalues $\mu_{\textrm{min}}, \mu_{\textrm{max}}$.
\end{proof}
This is another one of the properties we wanted to prove: i.e. that all of $B$'s eigenvalues are bounded below by $\lambda_{\textrm{min}}$!  

We only have two more things to show, then: that $\lambda_{\textrm{max}}$ is an eigenvalue of $B$ (by the above lemma, we know that it would be a maximal eigenvalue if it is one), and that the sum of the eigenvalues of $B$ is 0.  We do this in two more lemmas:
\begin{lemma}
$B$ has $\lambda_{\textrm{max}}$ as an eigenvalue.
\end{lemma}
\begin{proof}
 Specifically, notice that $\mathbf{v} = \sum_{i=1}^k c_i \cdot \mathbf{u}_i$ from earlier is an eigenvector for $\lambda_{\textrm{max}}$. This is because for any of the basis vectors $\mathbf{u}_i$, we have
\begin{align*}
\langle B \mathbf{v},  \mathbf{u}_i \rangle&= \langle A_G \mathbf{v},  \mathbf{u}_i \rangle \\
&=(A_G \mathbf{v})^T \cdot   \mathbf{u}_i \\
&= \lambda_{\textrm{max}}(\mathbf{v})^T \cdot \mathbf{u}_i \\
&= \lambda_{\textrm{max}}\left(\sum_{j=1}^k c_j \cdot \mathbf{u}_j^T\right) \cdot \mathbf{u}_i \\
&= \lambda_{\textrm{max}}\left(\sum_{j=1}^k c_j \cdot (\mathbf{u}_j^T\cdot \mathbf{u}_i) \right)\\
&= \lambda_{\textrm{max}} \cdot c_i \cdot ||\mathbf{u}_i||\\
&= \lambda_{\textrm{max}} \cdot c_i,\\
\end{align*}
where we justify those last two steps because the $\mathbf{u}_i$'s are all orthogonal and have norm 1.  But this means that the $i$-th co\"ordinate of $(S^T \cdot A_G \cdot S \mathbf{v}) \cdot \mathbf{v}$ is precisely $\lambda_{\textrm{max}} \cdot c_i$, for every $i$: i.e. that 
\begin{align*}
S^T \cdot A_G \cdot S \mathbf{v} = \lambda_{\textrm{max}}  \cdot (c_1\mathbf{u}_1, \ldots c_n \mathbf{u}_n) = \lambda_{\textrm{max}}  \cdot \mathbf{v},
\end{align*}
and thus that $\lambda_{\textrm{max}}$ is an eigenvalue, as claimed.
\end{proof}

\begin{lemma}
The trace\footnote{The \textbf{trace} of a matrix is the sum $\sum_{i=1}^n a_{i,i}$ of its diagonal elements.} of $B$ is 0.
\end{lemma}
\begin{proof}
 To see why, simply notice that we have
\begin{align*}
\langle B \mathbf{u}_i, \mathbf{u}_i \rangle &= \langle A_G  \mathbf{u}_i,  \mathbf{u}_i \rangle.\\
\end{align*}
However, notice that for any two basis vectors $e_x, e_y$ of $\mathbb{R}^n$ that lie in the same color class $C_i$ , we have
\begin{align*}
\langle A_G \mathbf{e}_x, \mathbf{e}_y \rangle =\langle (a_{1,x}, a_{2,x}, \ldots a_{n,x}) , \mathbf{e}_y \rangle = a_{y,x} = 0,
\end{align*}
as there are no edges between two vertices $x,y$ with the same color $i$.  

Because we can write $\mathbf{u}_i$ as the linear combination of several orthogonal elements all from the same color class, we know that in fact we have 
\begin{align*}
\langle A_G  \mathbf{u}_i,  \mathbf{u}_i \rangle = 0,
\end{align*}
and therefore that $\langle B \mathbf{u}_i, \mathbf{u}_i \rangle$ is also 0.  Why do we care?  Well, $ B \mathbf{u}_i$ is the $i$-th column of $B$: taking its dot product with $\mathbf{u}_i$ then gives you the $i$-th element of that $i$-th column, i.e. the entry in $(i,i)$.  We've just proven that all of these entries are 0; therefore, the trace of $B$ is trivially 0 as well.
\end{proof}
\begin{proposition}
The trace of a matrix is equal to the sum of its eigenvalues (counted with respect to their algebraic multiplicity.) 
\end{proposition}
\begin{proof}
The proof of this is simple: consider the characteristic polynomial!  We defer the details to the HW.
\end{proof}


So: let's combine these observations!  We know that 
\begin{itemize}
\item $\lambda_{\textrm{max}}$ is an eigenvalue of this matrix.    
\item All of the other eigenvalues range from $\lambda_{\textrm{max}}$ to $\lambda_{\textrm{min}}$.
\item There are $k$ such eigenvalues counting multiplicity, by the spectral theorem.
\item We know that the sum of all of these eigenvalues is 0. 
\end{itemize}

So: if we bound the sum of all of the eigenvalues below by $\lambda_{\textrm{max}} + (k-1)\lambda_{\textrm{min}}$ by replacing all of the other nonmaximal eigenvalues with $\lambda_{\textrm{min}}$
s, we get that 
\begin{align*}
& \lambda_{\textrm{max}} + (k-1)\lambda_{\textrm{min}} \leq 0\\
\Rightarrow &( k-1) \lambda_{\textrm{min}} \leq -\lambda_\textrm{max}\\
\Rightarrow & k-1  \geq -\frac{\lambda_\textrm{max}}{\lambda_{\textrm{min}}}\\
\Rightarrow & k  \geq 1-\frac{\lambda_\textrm{max}}{\lambda_{\textrm{min}}},\\
\end{align*}
(where we switched the direction on our inequality above because $\lambda_{\textrm{min}}$ is negative!)

This is what we sought to prove.  Win.
\end{proof}



\end{document}