\documentclass{article}%
\usepackage{amsmath}%
\setcounter{MaxMatrixCols}{30}%
\usepackage{amsfonts}%
\usepackage{amssymb}%
\usepackage{graphicx}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{CSTFile=40 LaTeX article.cst}
%TCIDATA{Created=Sunday, October 19, 2014 22:15:17}
%TCIDATA{LastRevised=Sunday, October 19, 2014 22:35:40}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Standard LaTeX\Blank - Standard LaTeX Article">}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\begin{document}
\section{Proof of the Matrix Tree Theorem}

In order to prove the Matrix Tree Theorem, we need another characterization of
the Laplacian.

\begin{definition}
Let $G$ be a directed $\left(  p,q\right)  $-graph. The oriented vertex-edge
incidence graph is a $p\times q$ matrix $Q=\left[  q_{ir}\right]  ,$ such that
$q_{ir}=1$ if $e_{r}=\left(  v_{i},v_{j}\right)  $ for some $j$ and
$q_{ir}=-1$ if $e_{r}=\left(  v_{j},v_{i}\right)  $ for some $j.$
\end{definition}

\begin{definition}
An orientation of a graph is a choice of direction for each edge, resulting in
a directed graph.
\end{definition}

We will first show the following:

\begin{proposition}
The Laplacian matrix $L$ satisfies
\[
-L=QQ^{T}%
\]
for any oriented vertex-edge incidence graph (so, given an undirected graph,
we can take any orientation), i.e.,
\[
L_{ij}=-\sum_{r=1}^{q}q_{ir}q_{jr}.
\]

\end{proposition}

P1) If $i=j,$ then we see that $L_{ii}=-\deg v_{i}.$ Note that $q_{ir}$ is
nonzero if $v_{i}$ is in edge $e_{r}.$ Show that
\[
\sum_{r=1}^{q}\left(  q_{ir}\right)  ^{2}=\deg v_{i}.
\]


P2) Now for $i\neq j,$ show that $q_{ir}q_{jr}=-1$ if $e_{r}=v_{i}v_{j},$
giving the result.

\begin{remark}
This observation can be used to give a different proof that $L_{ij}$ has all
nonpositive eigenvalues.
\end{remark}

The proof of the matrix tree theorem proceeds as follows. We will compute
\[
\det\left(  -\hat{L}_{11}\right)  .
\]
A property of determinants allows us to use the fact that $-L=QQ^{T}$ to
compute this determinant in terms of determinants of submatrices of $Q.$

\begin{proposition}
[Binet-Cauchy Formula]Let $A$ be an $n\times m$ matrix and $B$ be an $n\times
m$ matrix (usually we think $n<m).$ We can compute
\[
\det\left(  AB\right)  =\sum_{S}\det A_{S}\det B_{S}^{T}%
\]
where $A_{S}$ is matrix consisting of the columns of $A$ specified by $S,$ and
$S$ ranges over all choices of $n$ columns.
\end{proposition}

Note: We will not prove this theorem, but it is quite geometric in the case
that $B=A^{T},$ which is our case. If we consider the rows of $A,$ then $\det
AA^{T}$ is equal to the square of the volume of the parallelopiped determines
by these rows (since we can rotate $A$ to be in $\mathbb{R}^{n}$). The formula
says that the volume squared is equal to the sum of the squares of the volumes
when projected onto the coordinate planes. These are generalizations of the
pythagorean theorem!

\bigskip

We now begin the proof of the Matrix Tree Theorem. Recall that we have
\[
-L=QQ^{T}%
\]
for a choice of orientation. 

MT1) Show that
\begin{align*}
t\left(  G\right)   &  =\det\left(  -\hat{L}_{11}\right)  =\det\left(  \hat
{Q}\hat{Q}^{T}\right)  \\
&  =\sum_{S}\left(  \det\hat{Q}_{S}\right)  ^{2}%
\end{align*}
where $\hat{Q}$ is $Q$ with the first row removed and $S$ ranges over
collections of $p-1$ edges in $G$. 

MT2) Show that if $S$ forms a disconnected graph (assume this for MT2,MT3),
then $\hat{Q}_{S}$ looks like
\[
\left(
\begin{array}
[c]{cc}%
M & 0\\
0 & M^{\prime}%
\end{array}
\right)  .
\]


MT3) Since $M^{\prime}$ consists of columns with exactly one $1$ and one $-1,$
show that $\left(  0,0,\ldots,0,1,1,1,\ldots1\right)  ^{T}$ (respecting the
form above) is a zero eigenvector, and that it follows that  $\det\hat{Q}%
_{S}=0.$ 

MT4) Return to general $S.$ Show that if $S$ contains a cycle, then since it
has $p-1$ edges, the corresponding graph must be disconnected, and so $\det$
$\hat{Q}_{S}=0.$

MT5) Let $Q\in\mathbb{R}^{p\times\left(  p-1\right)  }$ be a directed
edge-vertex adjacency matrix corresponding to a tree. Let $\hat{Q}$ be the
$\mathbb{R}^{\left(  p-1\right)  \times\left(  p-1\right)  }$ matrix gotten by
removing the first row from $Q$. Show that $\det\hat{Q}=\pm1.$ Hint: induct on
$p$ using the fact that a tree must have at least two vertices of degree one.

MT6) Show that it follows that
\[
t\left(  G\right)  =\sum_{S}\left(  \det\hat{Q}_{S}\right)  ^{2}%
\]
is equal to the number of spanning trees.




\end{document}