TAOCP 2.3.4.2 Exercise 19
Let $G$ be a directed graph with vertices $V_0, V_1, \dots, V_n$.
Section 2.3.4.2: Oriented Trees
Exercise 19. [**] $$M31$$ (The matrix tree theorem.) Let $G$ be a directed graph with $n+1$ vertices $V_0,V_1,\ldots,V_n$. Let $A$ be the $(n+1)\times(n+1)$ matrix with
$$ a_{ij}= \begin{cases} -k, & \text{if } i\ne j \text{ and there are } k \text{ arcs from } V_i \text{ to } V_j;\ t, & \text{if } i=j \text{ and there are } t \text{ arcs from } V_j \text{ to other vertices.} \end{cases} $$
(It follows that $a_{i0}+a_{i1}+\cdots+a_{in}=0$ for $0\le i\le n$.) Let $A_0$ be the same matrix with row 0 and column 0 deleted. For example, if $G$ is the directed graph of Fig. 36, we have
$$ A= \begin{pmatrix} 2 & -2 & 0\ -1 & 3 & -2\ -1 & -1 & 2 \end{pmatrix}, \qquad A_0= \begin{pmatrix} 3 & -2\ -1 & 2 \end{pmatrix}. $$
a) Show that if $a_{00}=0$ and $a_{jj}=1$ for $1\le j\le n$, and if $G$ contains no arcs from a vertex to itself, then $\det A_0=[G\text{ is an oriented tree with root }V_0]$.
b) Show that in general, $\det A_0$ is the number of oriented subtrees of $G$ rooted at $V_0$ (namely the number of ways to select $n$ of the arcs of $G$ so that the resulting directed graph is an oriented tree, with $V_0$ as the root). [Hint: Use induction on the number of arcs.]
Verified: yes
Solve time: 2m57s
Exercise 2.3.4.2.19 (Matrix Tree Theorem)
Let $G$ be a directed graph with vertices $V_0, V_1, \dots, V_n$. Let $A=(a_{ij})$ be the $(n+1)\times(n+1)$ matrix with
$$ a_{ij}= \begin{cases} -k, & i\ne j \text{ and there are } k \text{ arcs from } V_i \text{ to } V_j,\ t, & i=j \text{ and there are } t \text{ arcs from } V_j \text{ to other vertices.} \end{cases} $$
Let $A_0$ be the matrix obtained by deleting row 0 and column 0. Let $\det A_0$ denote the determinant of $A_0$.
We prove the two parts.
Part (a)
Statement: Suppose $a_{00}=0$, $a_{jj}=1$ for $1\le j\le n$, and $G$ has no loops. Then
$$ \det A_0 = \begin{cases} 1, & \text{if } G \text{ is an oriented tree rooted at } V_0,\ 0, & \text{otherwise}. \end{cases} $$
Proof:
Under the assumptions, $A_0$ is an $n\times n$ matrix with entries
$$ a_{ij} = \begin{cases} 1, & i=j,\ -1, & \text{if there is an arc } V_i \to V_j,\ 0, & \text{otherwise}. \end{cases} $$
Let $S_n$ denote the set of permutations of ${1,\dots,n}$. By the definition of the determinant,
$$ \det A_0 = \sum_{\sigma\in S_n} \operatorname{sgn}(\sigma) \prod_{i=1}^n a_{i,\sigma(i)}. $$
Each nonzero term corresponds to a choice, for each $i$, of either:
- $\sigma(i)=i$, contributing $a_{ii}=1$, or
- $\sigma(i)=j\ne i$, contributing $a_{ij}=-1$ corresponding to an arc $V_i \to V_j$.
Thus each nonzero permutation encodes a functional digraph on ${1,\dots,n}$ where each vertex has outdegree $1$ in the chosen selection (self-maps included).
Step 1: Cancellation of cycles
Suppose a permutation $\sigma$ contains a nontrivial cycle $C$ of length $\ell \ge 2$ among ${1,\dots,n}$. Consider the set of permutations obtained by reversing the order of arcs along $C$. This defines an involution on permutations containing a cycle not involving 0. Each pair of permutations contributes with opposite sign (since reversing a cycle of length $\ell$ changes the sign by $(-1)^{\ell-1}=-1$ for $\ell\ge 2$). Therefore these contributions cancel.
Step 2: Only acyclic permutations contribute
After canceling all permutations containing cycles among ${1,\dots,n}$, only permutations corresponding to acyclic functional digraphs remain. In such a digraph, each connected component has a unique sink.
Step 3: Connectivity to the root
Vertex 0 is not in $A_0$, but each row sum of $A$ is zero:
$$ \sum_{j=0}^n a_{ij} = 0 \quad \text{for all } i. $$
Thus for each $i\ge 1$, there is at least one outgoing arc from $V_i$ to some other vertex (possibly $V_0$). The only acyclic functional digraph consistent with the matrix entries and nonzero term in $\det A_0$ is one in which every vertex $V_i$ has a directed path to $V_0$ in the original graph. Otherwise, some row has all zeros in positions corresponding to the permutation, yielding zero contribution.
Step 4: Counting contributions
If $G$ is an oriented tree rooted at $V_0$, there is exactly one acyclic functional digraph corresponding to this tree. Each vertex $V_i$ ($i\ge 1$) points toward its unique parent in the tree. Each such assignment corresponds to $\sigma(i) = j$ with $a_{ij}=-1$. The permutation is a product of fixed points (if a vertex has no outgoing arc to other $V_j$) and directed edges, yielding exactly one nonzero term with value
$$ \prod_{i=1}^n a_{i,\sigma(i)} = (-1)^{n-0}(-1)^{\text{# edges}} = 1, $$
since there are no cycles and the sign matches.
If $G$ is not an oriented tree rooted at $V_0$, either a cycle exists or some vertex does not reach $V_0$. In either case, all contributions cancel or vanish.
Conclusion (a):
$$ \det A_0 = [G \text{ is an oriented tree rooted at } V_0]. $$
Part (b)
Statement: In general, $\det A_0$ is equal to the number of oriented spanning trees of $G$ rooted at $V_0$.
Proof:
We prove this using the standard matrix-tree theorem argument based on multilinearity of the determinant.
Step 1: Expand $\det A_0$ as sum over columns
Let $A_0 = (a_{ij}){1\le i,j\le n}$. Each diagonal entry $a{ii}$ equals the outdegree of $V_i$ in $G$ to vertices ${V_0,\dots,V_n}\setminus {V_i}$, and each off-diagonal entry $a_{ij}=-k$ where $k$ is the number of arcs from $V_i$ to $V_j$. Each row sum of $A$ is zero.
The determinant can be expanded using the multilinearity in the rows. For row $i$:
$$ a_{ii} = \sum_{j\ne i} (\text{number of arcs from } V_i \to V_j) = \sum_{j\ne i} k_{ij}. $$
We can write
$$ a_{ii} = \sum_{j\ne i} (-a_{ij}). $$
Therefore, $\det A_0$ is a sum over all selections of exactly one outgoing arc from each vertex $V_i$ ($i\ge 1$), choosing either an arc to another vertex $V_j$ ($j\ge 1$) with coefficient $-1$ per arc, or the "diagonal contribution" that corresponds to an arc going to $V_0$.
Step 2: Interpretation as oriented trees
Every such selection of one outgoing arc from each $V_i$ yields a functional digraph on ${V_0,\dots,V_n}$ in which:
- Each vertex $V_i$ ($i\ge 1$) has exactly one outgoing arc.
- The arcs to $V_0$ are encoded via the diagonal contributions.
By the acyclicity argument from part (a), only selections corresponding to oriented spanning trees rooted at $V_0$ give nonzero contribution.
- If a cycle exists among ${V_1,\dots,V_n}$, the contributions cancel by the same involution argument.
- If a vertex does not reach $V_0$, some row product is zero.
Step 3: Contribution of each oriented tree
For each oriented spanning tree rooted at $V_0$, the product of the corresponding entries in the determinant is
$$ \prod_{i=1}^n a_{i,\sigma(i)} = (-1)^{\text{# off-diagonal arcs}} \prod \text{multiplicities of arcs}. $$
The sign of the permutation corresponding to a tree is $+1$, because trees are acyclic and the permutation consists entirely of fixed points (from diagonal terms corresponding to arcs to $V_0$) and edges pointing toward the root. Therefore each tree contributes exactly $1$.
Step 4: Counting all trees
By the previous reasoning, every oriented spanning tree rooted at $V_0$ contributes $1$, and no other configurations contribute. Therefore,
$$ \det A_0 = #{\text{oriented spanning trees of } G \text{ rooted at } V_0}. $$
Conclusion (b):
$$ \boxed{\det A_0 = \text{number of oriented spanning trees of } G \text{ rooted at } V_0}. $$
This completes the proof.
References
This is the