\documentclass
[numbers=enddot,12pt,final,onecolumn,notitlepage,abstracton]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{tabu}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage[breaklinks]{hyperref}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, June 27, 2016 12:11:26}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Language=American English}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{soln}{Solution}
\newenvironment{solution}[1][]
{\begin{soln}[#1]}
{\end{soln}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\kk}{{\mathbf{k}}}
\newcommand{\xx}{{\mathbf{x}}}
\newcommand{\id}{{\operatorname{id}}}
\newcommand{\ev}{\operatorname{ev}}
\newcommand{\NN}{{\mathbb{N}}}
\newcommand{\ZZ}{{\mathbb{Z}}}
\newcommand{\QQ}{{\mathbb{Q}}}
\ihead{A generalization of Chio Pivotal Condensation}
\ohead{page \thepage}
\cfoot{}
\begin{document}
\author{Darij Grinberg, Karthik Karnik, Anya Zhang}
\title{From Chio Pivotal Condensation to the Matrix-Tree theorem}
\date{\today}
\maketitle
\begin{abstract}
We show a determinant identity which generalizes both the Chio pivotal
condensation theorem and the Matrix-Tree theorem.
\end{abstract}
\section{Introduction}
The Chio pivotal condensation theorem (Theorem \ref{thm.chio} below, or
\cite[Theorem 3.6.1]{Eves}) is a simple particular case of the Dodgson-Muir
determinantal identity (\cite[(4)]{BerBru08}), which can be used to reduce the
computation of an $n\times n$-determinant to that of an $\left( n-1\right)
\times\left( n-1\right) $-determinant (provided that an entry of the matrix
can be divided by\footnote{We work with matrices over arbitrary commutative
rings, so this is not a moot point. Of course, if the ring is a field, then
this just means that the matrix has a nonzero entry.}). On the other hand, the
Matrix-Tree theorem (Theorem \ref{thm.mtt}, or \cite[Section 4]{Zeilbe}, or
\cite[Theorem 1]{Verstraete}) expresses the number of spanning trees of a
graph as a determinant\footnote{And not just the number; rather, a
\textquotedblleft weighted number\textquotedblright\ from which the spanning
trees can be read off if the weights are chosen generically enough.}. In this
note, we show that these two results have a common generalization (Theorem
\ref{thm.supergen}). As we have tried to keep the note self-contained, using
only the well-known fundamental properties of determinants, it also provides
new proofs for both results.
\subsection{Acknowledgments}
We thank the PRIMES project at MIT, during whose 2015 iteration this paper was
created, and in particular George Lusztig for sponsoring the first author's
mentorship in this project.
\section{The theorems}
We shall use the (rather standard) notations defined in \cite{detnotes}. In
particular, $\mathbb{N}$ means the set $\left\{ 0,1,2,\ldots\right\} $. For
any $n\in\mathbb{N}$, we let $S_{n}$ denote the group of permutations of the
set $\left\{ 1,2,\ldots,n\right\} $. The $n\times m$-matrix whose $\left(
i,j\right) $-th entry is $a_{i,j}$ for each $\left( i,j\right) \in\left\{
1,2,\ldots,n\right\} \times\left\{ 1,2,\ldots,m\right\} $ will be denoted
by $\left( a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq m}$.
Let $\mathbb{K}$ be a commutative ring. We shall regard $\mathbb{K}$ as fixed
throughout this note (so we won't always write \textquotedblleft Let
$\mathbb{K}$ be a commutative ring\textquotedblright\ in our propositions);
the notion \textquotedblleft matrix\textquotedblright\ will always mean
\textquotedblleft matrix with entries in $\mathbb{K}$\textquotedblright.
\subsection{Chio Pivotal Condensation}
We begin with a statement of the Chio Pivotal Condensation theorem (see, e.g.,
\cite[Theorem 0.1]{KarZha16} and the reference therein):
\begin{theorem}
\label{thm.chio}Let $n\geq2$ be an integer. Let $A=\left( a_{i,j}\right)
_{1\leq i\leq n,\ 1\leq j\leq n}\in\mathbb{K}^{n\times n}$ be a matrix. Then,
\[
\det\left( \left( a_{i,j}a_{n,n}-a_{i,n}a_{n,j}\right) _{1\leq i\leq
n-1,\ 1\leq j\leq n-1}\right) =a_{n,n}^{n-2}\cdot\det\left( \left(
a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}\right) .
\]
\end{theorem}
\begin{example}
If $n=3$ and $A=\left(
\begin{array}
[c]{ccc}%
a & a^{\prime} & a^{\prime\prime}\\
b & b^{\prime} & b^{\prime\prime}\\
c & c^{\prime} & c^{\prime\prime}%
\end{array}
\right) $, then Theorem \ref{thm.chio} says that%
\[
\det\left(
\begin{array}
[c]{cc}%
ac^{\prime\prime}-a^{\prime\prime}c & a^{\prime}c^{\prime\prime}%
-a^{\prime\prime}c^{\prime}\\
bc^{\prime\prime}-b^{\prime\prime}c & b^{\prime}c^{\prime\prime}%
-b^{\prime\prime}c^{\prime}%
\end{array}
\right) =\left( c^{\prime\prime}\right) ^{3-2}\cdot\det\left(
\begin{array}
[c]{ccc}%
a & a^{\prime} & a^{\prime\prime}\\
b & b^{\prime} & b^{\prime\prime}\\
c & c^{\prime} & c^{\prime\prime}%
\end{array}
\right) .
\]
\end{example}
Theorem \ref{thm.chio} (originally due to F\'{e}lix Chio in 1853\footnote{See
\cite[footnote 2]{Heinig} and \cite[\S 2]{Abeles} for some historical
background.}) is nowadays usually regarded either as a particular case of the
Dodgson-Muir determinantal identity (\cite[(4)]{BerBru08}), or as a relatively
easy exercise on row operations and the method of universal
identities\footnote{In more detail:
\par
\begin{itemize}
\item In order to derive Theorem \ref{thm.chio} from \cite[(4)]{BerBru08}, it
suffices to set $k=n-1$ and recognize the right hand side of \cite[(4)]%
{BerBru08} as $\det\left( \left( a_{i,j}a_{n,n}-a_{i,n}a_{n,j}\right)
_{1\leq i\leq n-1,\ 1\leq j\leq n-1}\right) $.
\par
\item A proof of Theorem \ref{thm.chio} using row operations can be found in
\cite[Theorem 3.6.1]{Eves}, up to a few minor issues: First of all,
\cite[Theorem 3.6.1]{Eves} proves not exactly Theorem \ref{thm.chio} but the
analogous identity
\[
\det\left( \left( a_{i+1,j+1}a_{1,1}-a_{i+1,1}a_{1,j+1}\right) _{1\leq
i\leq n-1,\ 1\leq j\leq n-1}\right) =a_{1,1}^{n-2}\cdot\det\left( \left(
a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}\right) .
\]
Second, \cite[Theorem 3.6.1]{Eves} assumes $a_{1,1}$ to be invertible (and all
$a_{i,j}$ to belong to a field); however, assumptions like this can easily be
disposed of using the method of universal identities (see \cite{Conrad09}).
\end{itemize}
\par
A more explicit and self-contained proof of Theorem \ref{thm.chio} can be
found in \cite{KarZha16}. References to other proofs appear in \cite[\S 2]%
{Abeles}.}. We, however, shall generalize it in a different direction.
\subsection{Generalization, step 1}
Our generalization will proceed in two steps. In the first step, we shall
replace some of the $n$'s on the left hand side by $f\left( i\right) $'s
(see Theorem \ref{thm.chio-gen} below). We first define some notations:
\begin{definition}
Let $n$ be a positive integer. Let $f:\left\{ 1,2,\ldots,n\right\}
\rightarrow\left\{ 1,2,\ldots,n\right\} $ be any map such that $f\left(
n\right) =n$.
We say that the map $f$ is $n$\textit{-potent} if for every $i\in\left\{
1,2,\ldots,n\right\} $, there exists some $k\in\mathbb{N}$ such that
$f^{k}\left( i\right) =n$. (In less formal terms, $f$ is $n$-potent if and
only if every element of $\left\{ 1,2,\ldots,n\right\} $ eventually arrives
at $n$ when being subjected to repeated application of $f$.)
\end{definition}
(Note that, by definition, any $n$-potent map $f:\left\{ 1,2,\ldots
,n\right\} \rightarrow\left\{ 1,2,\ldots,n\right\} $ must satisfy $f\left(
n\right) =n$.)
\begin{example}
For this example, let $n=3$. The map $\left\{ 1,2,3\right\} \rightarrow
\left\{ 1,2,3\right\} $ sending $1,2,3$ to $2,1,3$, respectively, is not
$n$-potent (because applying it repeatedly to $1$ can only give $1$ or $2$,
but never $3$). The map $\left\{ 1,2,3\right\} \rightarrow\left\{
1,2,3\right\} $ sending $1,2,3$ to $3,3,2$, respectively, is not $n$-potent
(since it does not send $n$ to $n$). The map $\left\{ 1,2,3\right\}
\rightarrow\left\{ 1,2,3\right\} $ sending $1,2,3$ to $3,1,3$, respectively,
is $n$-potent (indeed, every element of $\left\{ 1,2,3\right\} $ goes to $3$
after at most two applications of this map).
\end{example}
\begin{remark}
\label{rmk.n-potent.trees}Given a positive integer $n$, the $n$-potent maps
$f:\left\{ 1,2,\ldots,n\right\} \rightarrow\left\{ 1,2,\ldots,n\right\} $
are in 1-to-1 correspondence with the trees with vertex set $\left\{
1,2,\ldots,n\right\} $. Namely, an $n$-potent map $f$ corresponds to the tree
whose edges are $\left\{ i,f\left( i\right) \right\} $ for all
$i\in\left\{ 1,2,\ldots,n-1\right\} $. If we regard the tree as a rooted
tree with root $n$, and if we direct every edge towards the root, then the
edges are $\left( i,f\left( i\right) \right) $ for all $i\in\left\{
1,2,\ldots,n-1\right\} $.
\end{remark}
\begin{remark}
\label{rmk.n-potent.atleast1}Let $n\geq2$ be an integer. Let $f:\left\{
1,2,\ldots,n\right\} \rightarrow\left\{ 1,2,\ldots,n\right\} $ be any
$n$-potent map. Then:
\textbf{(a)} There exists some $g\in\left\{ 1,2,\ldots,n-1\right\} $ such
that $f\left( g\right) =n$.
\textbf{(b)} We have $\left\vert f^{-1}\left( n\right) \right\vert \geq2$.
\end{remark}
The (very simple) proof of Remark \ref{rmk.n-potent.atleast1} can be found in
the Appendix (Section \ref{sect.app}).
\begin{definition}
\label{def.n-potent.weightabut}Let $n\geq2$ be an integer. Let $A=\left(
a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}\in\mathbb{K}^{n\times n}$ be
an $n\times n$-matrix. Let $f:\left\{ 1,2,\ldots,n\right\} \rightarrow
\left\{ 1,2,\ldots,n\right\} $ be any $n$-potent map.
\textbf{(a)} We define an element $\operatorname*{weight}\nolimits_{f}A$ of
$\mathbb{K}$ by%
\[
\operatorname*{weight}\nolimits_{f}A=\prod_{i=1}^{n-1}a_{i,f\left( i\right)
}.
\]
\textbf{(b)} We define an element $\operatorname*{abut}\nolimits_{f}A$ of
$\mathbb{K}$ by%
\[
\operatorname*{abut}\nolimits_{f}A=a_{n,n}^{\left\vert f^{-1}\left( n\right)
\right\vert -2}\prod_{\substack{i\in\left\{ 1,2,\ldots,n-1\right\}
;\\f\left( i\right) \neq n}}a_{f\left( i\right) ,n}.
\]
(This is well-defined, since Remark \ref{rmk.n-potent.atleast1} \textbf{(b)}
shows that $\left\vert f^{-1}\left( n\right) \right\vert -2\in\mathbb{N}$.)
\end{definition}
\begin{remark}
\label{rmk.n-potent.abut}Let $n$, $A$ and $f$ be as in Definition
\ref{def.n-potent.weightabut}. Here are two slightly more intuitive ways to
think of $\operatorname*{abut}\nolimits_{f}A$:
\textbf{(a)} If $a_{n,n}\in\mathbb{K}$ is invertible, then
$\operatorname*{abut}\nolimits_{f}A$ is simply $\dfrac{1}{a_{n,n}}\prod
_{i\in\left\{ 1,2,\ldots,n-1\right\} }a_{f\left( i\right) ,n}$.
\textbf{(b)} Remark \ref{rmk.n-potent.atleast1} \textbf{(a)} shows that there
exists some $g\in\left\{ 1,2,\ldots,n-1\right\} $ such that $f\left(
g\right) =n$. Fix such a $g$. Then,%
\[
\operatorname*{abut}\nolimits_{f}A=\prod_{\substack{i\in\left\{
1,2,\ldots,n-1\right\} ;\\i\neq g}}a_{f\left( i\right) ,n}.
\]
\end{remark}
The (nearly trivial) proof of Remark \ref{rmk.n-potent.abut} is again found in
the Appendix.
Now, we can state our first generalization of Theorem \ref{thm.chio}:
\begin{theorem}
\label{thm.chio-gen}Let $n$ be a positive integer. Let $A=\left(
a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}\in\mathbb{K}^{n\times n}$ be
an $n\times n$-matrix. Let $f:\left\{ 1,2,\ldots,n\right\} \rightarrow
\left\{ 1,2,\ldots,n\right\} $ be any map such that $f\left( n\right) =n$.
Let $B$ be the $\left( n-1\right) \times\left( n-1\right) $-matrix%
\[
\left( a_{i,j}a_{f\left( i\right) ,n}-a_{i,n}a_{f\left( i\right)
,j}\right) _{1\leq i\leq n-1,\ 1\leq j\leq n-1}\in\mathbb{K}^{\left(
n-1\right) \times\left( n-1\right) }.
\]
{}
\textbf{(a)} If the map $f$ is not $n$-potent, then $\det B=0$.
\textbf{(b)} Assume that $n\geq2$. Assume that the map $f$ is $n$-potent.
Then,%
\[
\det B=\left( \operatorname*{abut}\nolimits_{f}A\right) \cdot\det A.
\]
\end{theorem}
\begin{example}
For this example, let $n=3$ and $A=\left(
\begin{array}
[c]{ccc}%
a_{1,1} & a_{1,2} & a_{1,3}\\
a_{2,1} & a_{2,2} & a_{2,3}\\
a_{3,1} & a_{3,2} & a_{3,3}%
\end{array}
\right) $.
If $f:\left\{ 1,2,3\right\} \rightarrow\left\{ 1,2,3\right\} $ is the map
sending $1,2,3$ to $3,1,3$, respectively, then the matrix $B$ defined in
Theorem \ref{thm.chio-gen} is $\left(
\begin{array}
[c]{cc}%
a_{1,1}a_{3,3}-a_{1,3}a_{3,1} & a_{1,2}a_{3,3}-a_{1,3}a_{3,2}\\
a_{2,1}a_{1,3}-a_{2,3}a_{1,1} & a_{2,2}a_{1,3}-a_{2,3}a_{1,2}%
\end{array}
\right) $. Since this map $f$ is $n$-potent, Theorem \ref{thm.chio-gen}
\textbf{(b)} predicts that this matrix $B$ satisfies $\det B=\left(
\operatorname*{abut}\nolimits_{f}A\right) \cdot\det A$. This is indeed easily
checked (indeed, we have $\operatorname*{abut}\nolimits_{f}A=a_{1,3}$ in this case).
On the other hand, if $f:\left\{ 1,2,3\right\} \rightarrow\left\{
1,2,3\right\} $ is the map sending $1,2,3$ to $1,1,3$, respectively, then the
matrix $B$ defined in Theorem \ref{thm.chio-gen} is $\left(
\begin{array}
[c]{cc}%
a_{1,1}a_{1,3}-a_{1,3}a_{1,1} & a_{1,2}a_{1,3}-a_{1,3}a_{1,2}\\
a_{2,1}a_{1,3}-a_{2,3}a_{1,1} & a_{2,2}a_{1,3}-a_{2,3}a_{1,2}%
\end{array}
\right) $. Since this map $f$ is not $n$-potent, Theorem \ref{thm.chio-gen}
\textbf{(a)} predicts that this matrix $B$ satisfies $\det B=0$. This, too, is
easily checked (and arguably obvious in this case).
\end{example}
Applying Theorem \ref{thm.chio-gen} \textbf{(b)} to $f\left( i\right) =n$
yields Theorem \ref{thm.chio}. (The map $f:\left\{ 1,2,\ldots,n\right\}
\rightarrow\left\{ 1,2,\ldots,n\right\} $ defined by $f\left( i\right) =n$
is clearly $n$-potent, and satisfies $\operatorname*{abut}\nolimits_{f}%
A=a_{n,n}^{n-2}$.)
We defer the proof of Theorem \ref{thm.chio-gen} until later; first, let us
see how it can be generalized a bit further (not substantially, anymore) and
how this generalization also encompasses the matrix-tree theorem.
\subsection{The matrix-tree theorem}
\begin{definition}
For any two objects $i$ and $j$, we define an element $\delta_{i,j}%
\in\mathbb{K}$ by $\delta_{i,j}=%
\begin{cases}
1, & \text{if }i=j;\\
0, & \text{if }i\neq j
\end{cases}
$.
\end{definition}
Let us first state the matrix-tree theorem.
To be honest, there is no \textquotedblleft the matrix-tree
theorem\textquotedblright, but rather a network of \textquotedblleft
matrix-tree theorems\textquotedblright\ (some less, some more general), each
of which has a reasonable claim to this name. Here we shall prove the
following one:
\begin{theorem}
\label{thm.mtt}Let $n\geq1$ be an integer. Let $W:\left\{ 1,2,\ldots
,n\right\} \times\left\{ 1,2,\ldots,n\right\} \rightarrow\mathbb{K}$ be any
function. For every $i\in\left\{ 1,2,\ldots,n\right\} $, set%
\[
d^{+}\left( i\right) =\sum_{j=1}^{n}W\left( i,j\right) .
\]
Let $L$ be the matrix $\left( \delta_{i,j}d^{+}\left( i\right) -W\left(
i,j\right) \right) _{1\leq i\leq n-1,\ 1\leq j\leq n-1}\in\mathbb{K}%
^{\left( n-1\right) \times\left( n-1\right) }$. Then,%
\begin{equation}
\det L=\sum_{\substack{f:\left\{ 1,2,\ldots,n\right\} \rightarrow\left\{
1,2,\ldots,n\right\} ;\\f\left( n\right) =n;\\f\text{ is }n\text{-potent}%
}}\prod_{i=1}^{n-1}W\left( i,f\left( i\right) \right) .
\label{eq.thm.mtt.detL=}%
\end{equation}
\end{theorem}
Since our notation differs from that in most other sources on the matrix-tree
theorem, let us explain the equivalence between our Theorem \ref{thm.mtt} and
one of its better-known avatars: The version of the matrix-tree theorem stated
in \cite[Section 4]{Zeilbe} involves some \textquotedblleft
weights\textquotedblright\ $a_{k,m}$, a determinant of an $\left( n-1\right)
\times\left( n-1\right) $-matrix, and a sum over a set $\mathcal{T}%
=\mathcal{T}\left( n\right) $. These correspond (respectively) to the values
$W\left( k,m\right) $, the determinant $\det L$, and the sum over all
$n$-potent maps $f$ in our Theorem \ref{thm.mtt}. In fact, the only nontrivial
part of this correspondence is the bijection between the trees in
$\mathcal{T}$ and the $n$-potent maps $f$ over which the sum in
(\ref{eq.thm.mtt.detL=}) ranges. This bijection is precisely the one
introduced in Remark \ref{rmk.n-potent.trees}.\footnote{A slightly different
version of the matrix-tree theorem appears in \cite[Theorem 1]{Verstraete}
(and various other places); it involves a function $W$, a number $v\in\left\{
1,2,\ldots,n\right\} $, a matrix $L_{v}$, a set $\mathcal{T}_{v}$ and a sum
$\tau\left( W,v\right) $. Our Theorem \ref{thm.mtt} is equivalent to the
case of \cite[Theorem 1]{Verstraete} for $v=n$; but this case is easily seen
to be equivalent to the general case of \cite[Theorem 1]{Verstraete} (since
the elements of $\left\{ 1,2,\ldots,n\right\} $ can be permuted at will).
Our matrix $L$ is the $L_{n}$ of \cite[Theorem 1]{Verstraete}. Furthermore,
our sum over all $n$-potent maps $f$ corresponds to the sum $\tau\left(
W,n\right) $ in \cite{Verstraete}, which is a sum over all $n$-arborescences
on $\left\{ 1,2,\ldots,n\right\} $; the correspondence is again due to
Remark \ref{rmk.n-potent.trees}.}
It might seem weird to call Theorem \ref{thm.mtt} the \textquotedblleft
matrix-tree theorem\textquotedblright\ if the word \textquotedblleft
tree\textquotedblright\ never occurs inside it. However, as we have already
noticed in Remark \ref{rmk.n-potent.trees}, the trees on the set $\left\{
1,2,\ldots,n\right\} $ are in bijection with the $n$-potent maps $\left\{
1,2,\ldots,n\right\} \rightarrow\left\{ 1,2,\ldots,n\right\} $, and
therefore the sum on the right hand side of (\ref{eq.thm.mtt.detL=}) can be
viewed as a sum over all these trees. Moreover, the function $W$ can be viewed
as an $n\times n$-matrix; when this matrix is specialized to the adjacency
matrix of a directed graph, the sum on the right hand side of
(\ref{eq.thm.mtt.detL=}) becomes the number of directed spanning trees of this
directed graph directed towards the root $n$.
\subsection{Generalization, step 2}
Now, as promised, we will generalize Theorem \ref{thm.chio-gen} a step
further. While the result will not be significantly stronger (we will actually
derive it from Theorem \ref{thm.chio-gen} quite easily), it will lead to a
short proof of Theorem \ref{thm.mtt}:
\Needspace{8cm}
\begin{theorem}
\label{thm.supergen}Let $n\geq2$ be an integer. Let $A=\left( a_{i,j}\right)
_{1\leq i\leq n,\ 1\leq j\leq n}\in\mathbb{K}^{n\times n}$ and $B=\left(
b_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}\in\mathbb{K}^{n\times n}$ be
$n\times n$-matrices. Write the $n\times n$-matrix $BA$ in the form
$BA=\left( c_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$.
Let $G$ be the $\left( n-1\right) \times\left( n-1\right) $-matrix%
\[
\left( a_{i,j}c_{i,n}-a_{i,n}c_{i,j}\right) _{1\leq i\leq n-1,\ 1\leq j\leq
n-1}\in\mathbb{K}^{\left( n-1\right) \times\left( n-1\right) }.
\]
Then,%
\[
\det G=\left( \sum_{\substack{f:\left\{ 1,2,\ldots,n\right\} \rightarrow
\left\{ 1,2,\ldots,n\right\} ;\\f\left( n\right) =n;\\f\text{ is
}n\text{-potent}}}\left( \operatorname*{weight}\nolimits_{f}B\right) \left(
\operatorname*{abut}\nolimits_{f}A\right) \right) \cdot\det A.
\]
\end{theorem}
To obtain Theorem \ref{thm.chio-gen} from Theorem \ref{thm.supergen}, we have
to define $B$ by $B=\left( \delta_{j,f\left( i\right) }\right) _{1\leq
i\leq n,\ 1\leq j\leq n}$. Below we shall show how to obtain the matrix-tree
theorem from Theorem \ref{thm.supergen}.
\begin{example}
Let us see what Theorem \ref{thm.supergen} says for $n=3$. There are three
$n$-potent maps $f:\left\{ 1,2,3\right\} \rightarrow\left\{ 1,2,3\right\}
$:
\begin{itemize}
\item one map $f_{33}$ which sends both $1$ and $2$ to $3$;
\item one map $f_{23}$ which sends $1$ to $2$ and $2$ to $3$;
\item one map $f_{31}$ which sends $2$ to $1$ and $1$ to $3$.
\end{itemize}
The definition of the $c_{i,j}$ as the entries of $BA$ shows that
$c_{i,j}=b_{i,1}a_{1,j}+b_{i,2}a_{2,j}+b_{i,3}a_{3,j}$ for all $i$ and $j$. We
have%
\[
G=\left(
\begin{array}
[c]{cc}%
a_{1,1}c_{1,3}-c_{1,1}a_{1,3} & a_{1,2}c_{1,3}-c_{1,2}a_{1,3}\\
a_{2,1}c_{2,3}-c_{2,1}a_{2,3} & a_{2,2}c_{2,3}-c_{2,2}a_{2,3}%
\end{array}
\right) .
\]
Theorem \ref{thm.supergen} says that%
\begin{align*}
\det G & =\left( \left( \operatorname*{weight}\nolimits_{f_{33}}B\right)
\left( \operatorname*{abut}\nolimits_{f_{33}}A\right) +\left(
\operatorname*{weight}\nolimits_{f_{23}}B\right) \left( \operatorname*{abut}%
\nolimits_{f_{23}}A\right) \right. \\
& \ \ \ \ \ \ \ \ \ \ \left. +\left( \operatorname*{weight}%
\nolimits_{f_{31}}B\right) \left( \operatorname*{abut}\nolimits_{f_{31}%
}A\right) \right) \cdot\det A\\
& =\left( b_{1,3}b_{2,3}a_{3,3}+b_{1,2}b_{2,3}a_{2,3}+b_{1,3}b_{2,1}%
a_{1,3}\right) \cdot\det A.
\end{align*}
\end{example}
\section{The proofs}
\subsection{Deriving Theorem \ref{thm.supergen} from Theorem
\ref{thm.chio-gen}}
Let us see how Theorem \ref{thm.supergen} can be proven using Theorem
\ref{thm.chio-gen} (which we have not proven yet). We shall need two lemmas:
\begin{lemma}
\label{lem.supergen.sum1}Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$. Let
$b_{i,k}$ be an element of $\mathbb{K}$ for every $i\in\left\{ 1,2,\ldots
,m\right\} $ and every $k\in\left\{ 1,2,\ldots,n\right\} $. Let $d_{i,j,k}$
be an element of $\mathbb{K}$ for every $i\in\left\{ 1,2,\ldots,m\right\} $,
$j\in\left\{ 1,2,\ldots,m\right\} $ and $k\in\left\{ 1,2,\ldots,n\right\}
$. Let $G$ be the $m\times m$-matrix $\left( \sum_{k=1}^{n}b_{i,k}%
d_{i,j,k}\right) _{1\leq i\leq m,\ 1\leq j\leq m}$. Then,%
\[
\det G=\sum_{f:\left\{ 1,2,\ldots,m\right\} \rightarrow\left\{
1,2,\ldots,n\right\} }\left( \prod_{i=1}^{m}b_{i,f\left( i\right)
}\right) \det\left( \left( d_{i,j,f\left( i\right) }\right) _{1\leq
i\leq m,\ 1\leq j\leq m}\right) .
\]
\end{lemma}
Lemma \ref{lem.supergen.sum1} is merely a scary way to state the
multilinearity of the determinant as a function of its rows. See the Appendix
for a proof.
Let us specialize Lemma \ref{lem.supergen.sum1} in a way that is closer to our goal:
\begin{lemma}
\label{lem.supergen.sum2}Let $n$ be a positive integer. Let $b_{i,k}$ be an
element of $\mathbb{K}$ for every $i\in\left\{ 1,2,\ldots,n-1\right\} $ and
every $k\in\left\{ 1,2,\ldots,n\right\} $. Let $d_{i,j,k}$ be an element of
$\mathbb{K}$ for every $i\in\left\{ 1,2,\ldots,n-1\right\} $, $j\in\left\{
1,2,\ldots,n-1\right\} $ and $k\in\left\{ 1,2,\ldots,n\right\} $. Let $G$
be the $\left( n-1\right) \times\left( n-1\right) $-matrix $\left(
\sum_{k=1}^{n}b_{i,k}d_{i,j,k}\right) _{1\leq i\leq n-1,\ 1\leq j\leq n-1}$.
Then,%
\[
\det G=\sum_{\substack{f:\left\{ 1,2,\ldots,n\right\} \rightarrow\left\{
1,2,\ldots,n\right\} ;\\f\left( n\right) =n}}\left( \prod_{i=1}%
^{n-1}b_{i,f\left( i\right) }\right) \det\left( \left( d_{i,j,f\left(
i\right) }\right) _{1\leq i\leq n-1,\ 1\leq j\leq n-1}\right) .
\]
\end{lemma}
\begin{proof}
[Proof of Lemma \ref{lem.supergen.sum2}.]Lemma \ref{lem.supergen.sum1}
(applied to $m=n-1$) shows that%
\[
\det G=\sum_{f:\left\{ 1,2,\ldots,n-1\right\} \rightarrow\left\{
1,2,\ldots,n\right\} }\left( \prod_{i=1}^{n-1}b_{i,f\left( i\right)
}\right) \det\left( \left( d_{i,j,f\left( i\right) }\right) _{1\leq
i\leq n-1,\ 1\leq j\leq n-1}\right) .
\]
The only difference between this formula and the claim of Lemma
\ref{lem.supergen.sum2} is that the sum here is over all $f:\left\{
1,2,\ldots,n-1\right\} \rightarrow\left\{ 1,2,\ldots,n\right\} $, whereas
the sum in the claim of Lemma \ref{lem.supergen.sum2} is over all $f:\left\{
1,2,\ldots,n\right\} \rightarrow\left\{ 1,2,\ldots,n\right\} $ satisfying
$f\left( n\right) =n$. But this is not much of a difference: Each map
$\left\{ 1,2,\ldots,n-1\right\} \rightarrow\left\{ 1,2,\ldots,n\right\} $
is a restriction (to $\left\{ 1,2,\ldots,n-1\right\} $) of a unique map
$f:\left\{ 1,2,\ldots,n\right\} \rightarrow\left\{ 1,2,\ldots,n\right\} $
satisfying $f\left( n\right) =n$, and therefore the two sums are equal.
\end{proof}
\begin{proof}
[Proof of Theorem \ref{thm.supergen}.]For every $i\in\left\{ 1,2,\ldots
,n-1\right\} $, $j\in\left\{ 1,2,\ldots,n-1\right\} $ and $k\in\left\{
1,2,\ldots,n\right\} $, define an element $d_{i,j,k}$ of $\mathbb{K}$ by%
\begin{equation}
d_{i,j,k}=a_{i,j}a_{k,n}-a_{i,n}a_{k,j}. \label{pf.thm.supergen.dijk}%
\end{equation}
For every $f:\left\{ 1,2,\ldots,n\right\} \rightarrow\left\{ 1,2,\ldots
,n\right\} $ satisfying $f\left( n\right) =n$, we have%
\begin{align}
& \det\left( \left( \underbrace{d_{i,j,f\left( i\right) }}%
_{\substack{=a_{i,j}a_{f\left( i\right) ,n}-a_{i,n}a_{f\left( i\right)
,j}\\\text{(by (\ref{pf.thm.supergen.dijk}))}}}\right) _{1\leq i\leq
n-1,\ 1\leq j\leq n-1}\right) \nonumber\\
& =\det\left( \left( a_{i,j}a_{f\left( i\right) ,n}-a_{i,n}a_{f\left(
i\right) ,j}\right) _{1\leq i\leq n-1,\ 1\leq j\leq n-1}\right) \nonumber\\
& =%
\begin{cases}
0, & \text{if }f\text{ is not }n\text{-potent};\\
\left( \operatorname*{abut}\nolimits_{f}A\right) \cdot\det A, & \text{if
}f\text{ is }n\text{-potent}%
\end{cases}
\label{pf.thm.supergen.det1}%
\end{align}
(by Theorem \ref{thm.chio-gen}, applied to the matrix $\left( a_{i,j}%
a_{f\left( i\right) ,n}-a_{i,n}a_{f\left( i\right) ,j}\right) _{1\leq
i\leq n-1,\ 1\leq j\leq n-1}$ instead of $B$).
We have
\[
\left( c_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}=BA=\left( \sum
_{k=1}^{n}b_{i,k}a_{k,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}%
\]
(by the definition of the product of two matrices). Thus,%
\begin{equation}
c_{i,j}=\sum_{k=1}^{n}b_{i,k}a_{k,j}\ \ \ \ \ \ \ \ \ \ \text{for every
}\left( i,j\right) \in\left\{ 1,2,\ldots,n\right\} ^{2}.
\label{pf.thm.supergen.cij}%
\end{equation}
Now, for every $\left( i,j\right) \in\left\{ 1,2,\ldots,n-1\right\} ^{2}$,
we have%
\begin{align*}
& a_{i,j}\underbrace{c_{i,n}}_{\substack{=\sum_{k=1}^{n}b_{i,k}%
a_{k,n}\\\text{(by (\ref{pf.thm.supergen.cij}), applied to }n\\\text{instead
of }j\text{)}}}-a_{i,n}\underbrace{c_{i,j}}_{\substack{=\sum_{k=1}^{n}%
b_{i,k}a_{k,j}\\\text{(by (\ref{pf.thm.supergen.cij}))}}}\\
& =a_{i,j}\sum_{k=1}^{n}b_{i,k}a_{k,n}-a_{i,n}\sum_{k=1}^{n}b_{i,k}%
a_{k,j}=\sum_{k=1}^{n}b_{i,k}\underbrace{\left( a_{i,j}a_{k,n}-a_{i,n}%
a_{k,j}\right) }_{\substack{=d_{i,j,k}\\\text{(by (\ref{pf.thm.supergen.dijk}%
))}}}=\sum_{k=1}^{n}b_{i,k}d_{i,j,k}.
\end{align*}
Hence,
\[
G=\left( \underbrace{a_{i,j}c_{i,n}-a_{i,n}c_{i,j}}_{=\sum_{k=1}^{n}%
b_{i,k}d_{i,j,k}}\right) _{1\leq i\leq n-1,\ 1\leq j\leq n-1}=\left(
\sum_{k=1}^{n}b_{i,k}d_{i,j,k}\right) _{1\leq i\leq n-1,\ 1\leq j\leq n-1}.
\]
Hence, Lemma \ref{lem.supergen.sum2} yields%
\begin{align*}
\det G & =\sum_{\substack{f:\left\{ 1,2,\ldots,n\right\} \rightarrow
\left\{ 1,2,\ldots,n\right\} ;\\f\left( n\right) =n}}\underbrace{\left(
\prod_{i=1}^{n-1}b_{i,f\left( i\right) }\right) }%
_{\substack{=\operatorname*{weight}\nolimits_{f}B\\\text{(by the
definition}\\\text{of }\operatorname*{weight}\nolimits_{f}B\text{)}%
}}\underbrace{\det\left( \left( d_{i,j,f\left( i\right) }\right) _{1\leq
i\leq n-1,\ 1\leq j\leq n-1}\right) }_{=%
\begin{cases}
0, & \text{if }f\text{ is not }n\text{-potent};\\
\left( \operatorname*{abut}\nolimits_{f}A\right) \cdot\det A, & \text{if
}f\text{ is }n\text{-potent}%
\end{cases}
}\\
& =\sum_{\substack{f:\left\{ 1,2,\ldots,n\right\} \rightarrow\left\{
1,2,\ldots,n\right\} ;\\f\left( n\right) =n}}\left( \operatorname*{weight}%
\nolimits_{f}B\right)
\begin{cases}
0, & \text{if }f\text{ is not }n\text{-potent};\\
\left( \operatorname*{abut}\nolimits_{f}A\right) \cdot\det A, & \text{if
}f\text{ is }n\text{-potent}%
\end{cases}
\\
& =\sum_{\substack{f:\left\{ 1,2,\ldots,n\right\} \rightarrow\left\{
1,2,\ldots,n\right\} ;\\f\left( n\right) =n;\\f\text{ is }n\text{-potent}%
}}\left( \operatorname*{weight}\nolimits_{f}B\right) \left(
\operatorname*{abut}\nolimits_{f}A\right) \cdot\det A\\
& =\left( \sum_{\substack{f:\left\{ 1,2,\ldots,n\right\} \rightarrow
\left\{ 1,2,\ldots,n\right\} ;\\f\left( n\right) =n;\\f\text{ is
}n\text{-potent}}}\left( \operatorname*{weight}\nolimits_{f}B\right) \left(
\operatorname*{abut}\nolimits_{f}A\right) \right) \cdot\det A.
\end{align*}
\end{proof}
\subsection{Deriving Theorem \ref{thm.mtt} from Theorem \ref{thm.supergen}}
Now let us see why Theorem \ref{thm.supergen} generalizes the matrix-tree theorem.
\begin{proof}
[Proof of Theorem \ref{thm.mtt}.]WLOG assume that $n\geq2$ (since the case
$n=1$ is easy to check by hand). Define an $n\times n$-matrix $A$ by
$A=\left( a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$, where
\[
a_{i,j}=\delta_{i,j}+\delta_{j,n}\left( 1-\delta_{i,n}\right) .
\]
(This scary formula hides a simple idea: this is the matrix whose entries on
the diagonal and in its last column are $1$, and all other entries are $0$.
Thus,%
\[
A=\left(
\begin{array}
[c]{ccccccc}%
1 & 0 & 0 & 0 & \cdots & 0 & 1\\
0 & 1 & 0 & 0 & \cdots & 0 & 1\\
0 & 0 & 1 & 0 & \cdots & 0 & 1\\
0 & 0 & 0 & 1 & \cdots & 0 & 1\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & 0 & 0 & \cdots & 1 & 1\\
0 & 0 & 0 & 0 & \cdots & 0 & 1
\end{array}
\right) .
\]
) Note that every $\left( i,j\right) \in\left\{ 1,2,\ldots,n-1\right\}
^{2}$ satisfies%
\begin{equation}
a_{i,j}=\delta_{i,j}+\underbrace{\delta_{j,n}}_{\substack{=0\\\text{(since
}j\neq n\\\text{(since }j\in\left\{ 1,2,\ldots,n-1\right\} \text{))}%
}}\left( 1-\delta_{i,n}\right) =\delta_{i,j}. \label{pf.thm.mtt.aij=}%
\end{equation}
Also, every $i\in\left\{ 1,2,\ldots,n-1\right\} $ satisfies%
\begin{align}
a_{i,n} & =\underbrace{\delta_{i,n}}_{\substack{=0\\\text{(since }i\neq
n\text{)}}}+\underbrace{\delta_{n,n}}_{\substack{=1\\\text{(since }%
n=n\text{)}}}\left( 1-\underbrace{\delta_{i,n}}_{\substack{=0\\\text{(since
}i\neq n\text{)}}}\right) \ \ \ \ \ \ \ \ \ \ \left( \text{by the definition
of }a_{i,n}\right) \nonumber\\
& =0+1\left( 1-0\right) =1. \label{pf.thm.mtt.ain=}%
\end{align}
Also, let $B$ be the $n\times n$-matrix $\left( W\left( i,j\right) \right)
_{1\leq i\leq n,\ 1\leq j\leq n}$. Write the $n\times n$-matrix $BA$ in the
form $BA=\left( c_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$. Then, it
is easy to see that every $\left( i,j\right) \in\left\{ 1,2,\ldots
,n\right\} ^{2}$ satisfies%
\begin{equation}
c_{i,j}=W\left( i,j\right) +\delta_{j,n}\left( d^{+}\left( i\right)
-W\left( i,n\right) \right) \label{pf.thm.mtt.cij=}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.thm.mtt.cij=}):} For every $i\in\left\{
1,2,\ldots,n\right\} $, we have%
\begin{align*}
d^{+}\left( i\right) & =\sum_{j=1}^{n}W\left( i,j\right)
\ \ \ \ \ \ \ \ \ \ \left( \text{by the definition of }d^{+}\left( i\right)
\right) \\
& =\sum_{j=1}^{n-1}W\left( i,j\right) +W\left( i,n\right) =\sum
_{k=1}^{n-1}W\left( i,k\right) +W\left( i,n\right)
\end{align*}
(here, we renamed the summation index $j$ as $k$) and thus%
\begin{equation}
\sum_{k=1}^{n-1}W\left( i,k\right) =d^{+}\left( i\right) -W\left(
i,n\right) . \label{pf.thm.mtt.fn1.1}%
\end{equation}
\par
But%
\[
\left( c_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}=BA=\left( \sum
_{k=1}^{n}W\left( i,k\right) a_{k,j}\right) _{1\leq i\leq n,\ 1\leq j\leq
n}%
\]
(by the definition of the product of two matrices, since $B=\left( W\left(
i,j\right) \right) _{1\leq i\leq n,\ 1\leq j\leq n}$ and $A=\left(
a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$). Hence, every $\left(
i,j\right) \in\left\{ 1,2,\ldots,n\right\} ^{2}$ satisfies%
\begin{align*}
c_{i,j} & =\sum_{k=1}^{n}W\left( i,k\right) \underbrace{a_{k,j}%
}_{\substack{=\delta_{k,j}+\delta_{j,n}\left( 1-\delta_{k,n}\right)
\\\text{(by the definition of }a_{k,j}\text{)}}}\\
& =\sum_{k=1}^{n}W\left( i,k\right) \left( \delta_{k,j}+\delta
_{j,n}\left( 1-\delta_{k,n}\right) \right) \\
& =\underbrace{\sum_{k=1}^{n}W\left( i,k\right) \delta_{k,j}}%
_{\substack{=W\left( i,j\right) \\\text{(because the factor }\delta
_{k.j}\text{ in the sum}\\\text{kills every addend except the one for
}k=j\text{)}}}+\delta_{j,n}\underbrace{\sum_{k=1}^{n}W\left( i,k\right)
\left( 1-\delta_{k,n}\right) }_{=\sum_{k=1}^{n-1}W\left( i,k\right)
\left( 1-\delta_{k,n}\right) +W\left( i,n\right) \left( 1-\delta
_{n,n}\right) }\\
& =W\left( i,j\right) +\delta_{j,n}\left( \sum_{k=1}^{n-1}W\left(
i,k\right) \left( 1-\underbrace{\delta_{k,n}}_{\substack{=0\\\text{(since
}k