\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{5: The Matrix-Tree Theorem}{Week 3}

This lecture is also going to be awesome, but shorter, because we're finishing up yesterday's proof with the first half of lecture today.

So: a result we've proven in like 3-4 MC classes this year, in different ways, is the following:
\begin{theorem}
(Cayley)  There are $n^{n-2}$ labeled trees on $n$ vertices.
\end{theorem}

Today, we're going to prove the ridiculously tricked-out version of this theorem:

\begin{theorem}
(The Matrix-Tree Theorem)  Suppose we have any graph $G$.  Let $L_G$ denote the Laplacian\footnote{The Laplacian of a graph $G$ is the $n \times n$ matrix with rows/columns indexed by vertices, with a $-1$ in every $(i,j)$ where an edge runs from $(i,j)$, the degree of vertex $i$ in the entry $(i,i)$, and 0's elsewhere.} of $G$.  Let $\Gamma$ denote the number of spanning trees\footnote{A \textbf{spanning tree} of a graph $G$ is a subgraph that uses every vertex in $G$ and is also a tree.} of $G$: then, we have
\begin{align*}
\Gamma = \frac{1}{n} \cdot \mu_2 \cdot\ldots \mu_n,
\end{align*}
where $\mu_1 \leq \mu_2 \leq  \ldots \leq \mu_n$ are the $n$ eigenvalues of the Laplacian of $G$ written in increasing order, and we've removed the first one of these from our product above. 
\end{theorem}
\begin{proof}
Before we begin, we first review some key facts about the Laplacian:
\begin{enumerate}
\item The Laplacian is real-valued and symmetric: so it has $n$ eigenvalues counting multiplicity, by the spectral theorem.
\item The Laplacian has 0 as an eigenvalue: this is because summing any of its rows yields 0, and therefore the all-1's vector is an eigenvalue for 0.
\item The Laplacian is positive-definite\footnote{A matrix $A$ is called \textbf{positive-semidefinite} iff $\mathbf{x}^T (A\mathbf{x}) \geq 0$, for any vector $\mathbf{x}$.}, and therefore all of its eigenvalues are $\geq 0$.
\end{enumerate}
Prove these things on the HW, if you don't believe them!

Also: for notational clarity, let $L^{\{v_1, \ldots v_k\}}$ denote the matrix $L_G$ if we delete the $k$ rows and columns corresponding to these vectors, and $l_{x,x}$ denote the quantity $ \det(L^{\{x\}})$. We now proceed to prove our claim in two parts: first, we claim that 
\begin{align*}
\Gamma = l_{x,x}
\end{align*}
for any $x \in V(G)$.

We prove this claim by a pair of nested inductions: first on the number $n$ of vertices in $G$, and then (at each level) by inducting on the number of edges in this $n$-vertex graph.

The first case where our notation makes sense is $n=2$: there, we have that $l_{x,x}$ is simply the degree of the other remaining vertex, which is either 0 (in which case our graph is disconnected and no spanning trees exist) or 1 (in which case this one edge forms the unique spanning tree.)  So our claim holds here.

We assume that we've proven our case for all $k<n$, and proceed to $n$ vertices.  In the case where there are no edges leaving the vertex $x$, we are trivially done: $\Gamma = 0$ because $\{x\}$ is disconnected from the graph, while $L^{\{x\}}$ is just $L_G$ where we've removed an all-zero row and column, which is therefore a matrix that still has zero row sums (and thus one whose determimant, $l_{x,x}$, is 0.)

Otherwise, there is an edge involving $x$: denote it as $\{x,y\}$.  How does deleting this edge from $L_G$ change $l_{x,x}$?  Well: deleting this edge decreases the $(x,x)$ and $(y,y)$-th entries of $L_G$ by 1, and increases the $(x,y)$ and $(y,x)$ entries of $L_G$ to 0.  However, in $L^{\{x\}}$, the only one of those changes that we can still see is the decrement of the $(y,y)$-th entry by 1, as we deleted the row and column involving $x$!

Expanding, if we denote this modified matrix as $M$, we can see that
\begin{align*}
\det(M) &= (-1)^{y-1} \det \left( M, \textrm{with row }y\textrm{ switched to the top}\right)\\
&= (-1)^{y-1} \sum_{1 \leq i \leq n-1} (-1)^{i-1} \cdot m_{i,y} \cdot \det \left( M, \textrm{row }y\textrm{ at top, row } y\textrm{ and col }j\textrm{ deleted} \right)\\
&= (-1)^{y-1} \sum_{1 \leq i \leq n-1} (-1)^i \cdot m_{i,y} \cdot \det \left(M \textrm{ with row } y\textrm{ and col }j\textrm{ deleted} \right)\\
&= -(-1)^{2y-2} \cdot \det M_{y,y} + (-1)^{y-1} \sum_{1 \leq i \leq n-1, i \neq y} (-1)^i \cdot m_{i,y} \cdot \det \left(M_{y,j} \right)\\
&= -\det(L^{\{x,y\}}) + l_{x,x}.
\end{align*}
Thus, we've shown that removing an edge from $G$ decreases $l_{x,x}$ by $\det(L^{\{x,y\}})$, which (by induction) is the number of spanning trees on the graph $G$ if we contracted the edge $\{x,y\}$ to a point.  But this is just the number of spanning trees on $G$ that specifically use the edge $\{x,y\}$.  Therefore, by repeatedly doing this process, our inductive claim holds (i.e. we've proven that $\Gamma = l_{x,x}$.)

To finish this proof, we just need to do the following two things, which you will prove on the HW:
\begin{enumerate}
\item Notice that because we can factor the characteristic polynomial $\det(xI - L)$ by its roots, we have that \begin{align*}
\frac{\partial}{\partial x} \left( \det(xI - L) \right) \Big|_{x=0} = (-1)^{n-1} \cdot \mu_2\cdot \ldots \cdot \mu_n.
\end{align*}
\item  Conversely: notice as well that
\begin{align*}
\frac{\partial}{\partial x} \left( \det(xI - L) \right) = \sum_{x=1}^n \det( tI - L^{\{x\}}),
\end{align*}
and thus that when we plug in zero to the above equation, we get $(-1)^{n-1} \cdot \sum_{x=1}^n l_{x,x}$.
\end{enumerate}
Combining these two observations with our earlier one that $\Gamma = l_{x,x}$ gives us that 
\begin{align*}
\Gamma = \frac{1}{n} \cdot \mu_2 \cdot\ldots \mu_n,
\end{align*}
as claimed.
\end{proof}
\end{document}