Matrix-Tree Theorem

Self-loops affect neither the number of spanning trees nor the calculation of the Laplace matrix below, so the matrix-tree theorem remains valid in the presence of self-loops. There is no need to delete self-loops during computation. If self-loops are deleted, it affects the use of the matrix-tree theorem under the BEST theorem to count the number of Eulerian circuits in a directed graph.

For an undirected graph $G$ and any $k$,

In other words, all principal minors of order $n-1$ of the Laplace matrix of an undirected graph are equal, and all equal the number of spanning trees of the graph.

Let $\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_{n-1}\ge\lambda_n=0$ be the eigenvalues of $L(G)$, of which there are $n$. Then

For a directed graph $G$ and any $k$,

In other words, the principal minor obtained by deleting row $k$ and column $k$ from the out-degree Laplace matrix of a directed graph equals the number of arborescences rooted at $k$.

For a directed graph $G$ and any $k$,

In other words, the principal minor obtained by deleting row $k$ and column $k$ from the in-degree Laplace matrix of a directed graph equals the number of anti-arborescences rooted at $k$.

An arborescence is also called an in-tree, but because the out-degree is used when computing in-trees, the term arborescence is used here to avoid confusion between $\mathrm{in}$ and $\mathrm{out}$.

Given an $n\times m$ matrix $A$ and an $m\times n$ matrix $B$,

where the summation means that $S$ ranges over all subsets of $[m]$ of size $n$. If $n>m$, then necessarily $\det(AB)=0$.

Following the model from 「NOI2021」Path Intersections, first consider the following combinatorial interpretation of a determinant. For an $n\times n$ matrix $C$, construct a directed acyclic graph $G=(V,E)$. Its vertex set is $V=[2]\times[n]\subset\mathbb R^2$, namely two columns of points in the plane. Denote the points in the left column by $L=\{l_i=(1,i):i\in[n]\}$ and those in the right column by $R=\{r_i=(2,i):i\in[n]\}$; the directed edge set is $E=\{(l_i,r_j):i,j\in[n]\}$, and assign edge weight $w(l_i,r_j)=C_{i,j}$. In this graph, call a subset of $n$ edges, $E^\sigma\subset E$, a path family if its starting points are pairwise distinct and its ending points are also pairwise distinct. Clearly, path families $E^\sigma$ and permutations of $[n]$, denoted $\sigma$, are in one-to-one correspondence. Notice that when a path family is drawn in the plane, its edges may intersect pairwise, and the number of intersection points, counted with multiplicity, equals the inversion number of $\sigma$. This is because edges $(l_i,r_{\sigma(i)})$ and $(l_j,r_{\sigma(j)})$ intersect if and only if $(i-j)(\sigma(i)-\sigma(j))< 0$, which is precisely an inversion pair. For convenience, call the parity of the inversion number of the corresponding permutation, equivalently the parity of the number of intersections in the path family, the parity of the path family. Thus, if these path families are counted by weight, the number of path families with an even number of intersections minus the number with an odd number of intersections gives the Leibniz expansion of the determinant:

where $S_n$ is the permutation group on $[n]$, and $\mathrm{sgn}(\sigma)$ is the sign of permutation $\sigma$ (it equals $1$ when the inversion number is even and $-1$ when the inversion number is odd).

Once the combinatorial meaning of the determinant is understood, the Cauchy–Binet formula can be proved using the following combinatorial model. For an $n\times m$ matrix $A$ and an $m\times n$ matrix $B$, construct a directed acyclic graph $G=(V,E)$. Its vertex set is $V=L\cup D\cup R$, where $L=\{l_i=(1,i):i\in[n]\}$, $D=\{d_i=(2,i):i\in[m]\}$, and $R=\{r_i=(3,i):i\in[n]\}$; its directed edge set is $E=E_L\cup E_R$, where $E_L=\{(l_i,d_j):i\in[n],j\in[m]\}$ and $E_R=\{(d_j,r_i):j\in[m],i\in[n]\}$, with edge weights $w(l_i,d_j)=A_{i,j}$ and $w(d_j,r_i)=B_{j,i}$, respectively. Again consider path families from $L$ through $D$ to $R$, with paths pairwise sharing no vertices; count them by weight and subtract the count of path families with an odd number of intersections from the count with an even number of intersections. We now show that the two sides of the Cauchy–Binet formula compute this number in two ways.

For the left-hand side, based on the graph $G$ described above, construct a new graph $G'$ whose vertex set is $V'=L\cup R$ and whose edge set is $E'=\{(l_i,r_j):i,j\in[n]\}$. Assign edge $(l_i,r_j)$ the weight $\sum_{k\in[m]}A_{i,k}B_{k,j}$, namely, in the original graph $G$, the weighted count of simple paths from $l_i$ to $r_j$. This edge weight is exactly $(AB)_{i,j}$. This amounts to simplifying the three-layer graph into a two-layer graph. However, path families in the two-layer graph $G'$ do not correspond one-to-one with path families in the three-layer graph $G$. Since each path in the two-layer graph corresponds to several simple paths in the three-layer graph, counting path families in the two-layer graph requires multiplying their weights, which amounts to pairing the corresponding path sets in the three-layer graph. This inevitably produces cases in which paths share an intermediate stop. However, pairs of paths sharing an intermediate stop do not contribute to the final answer: for $i_1< i_2$, $j_1< j_2$, and any intermediate point $d$, there are two pairs of simple paths, $(l_{i_1}\rightarrow d\rightarrow r_{j_1}, l_{i_2}\rightarrow d\rightarrow r_{j_2})$ and $(l_{i_1}\rightarrow d\rightarrow r_{j_2}, l_{i_2}\rightarrow d\rightarrow r_{j_1})$, but the parities of their numbers of intersections in the three-layer graph are necessarily opposite, because if only the starting and ending points are considered, the two path pairs exchange their endpoints. Therefore, these paths sharing an intermediate stop cancel in pairs when path families are counted in the simplified two-layer graph. For the remaining cases, once the starting and ending points of two paths are fixed, the parity of the number of their intersections does not change regardless of how the intermediate points are selected, as long as the same point is not selected twice. Thus, for each path family in $G'$, all corresponding path families in the original graph $G$ have the same parity. Consequently, $\det(AB)$ provides one way to compute the difference in the number of path families described above.

For the right-hand side, it enumerates all possible combinations of intermediate points. Given any intermediate-point set $S\subset D=[m]$ with $|S|=n$, consider path families from $L$ to $S$ and from $S$ to $R$, respectively. They can be joined to obtain a path family from $L$ to $R$, and the composition of the permutations corresponding to the first two path families is exactly the permutation corresponding to the resulting path family, so the product of the parities of the first two path families equals the parity of the resulting path family. Therefore, the difference in the counts of all path families whose intermediate-point set is $S$ is exactly the product of the difference in the counts of path families from $L$ to $S$ and from $S$ to $R$. Summing over all possible $S$ gives the right-hand side, so it is precisely the difference in the number of path families described above.

The combinatorial proof above can in fact be translated into an algebraic proof word for word. Here we instead give a more technically involved algebraic proof, using several common results. When $m< n$, the determinant is zero because

When $m=n$, the Cauchy–Binet formula is simply the fact that the determinant of a product of square matrices equals the product of their determinants.

When $m>n$, note that

It is also known that, for $\det(xI_n+C)$, the coefficient of $x^{n-k}$ is the sum of all principal minors of $C$ of order $k$. Therefore, comparing coefficients on both sides of the equation above gives

Here, the second equality uses the result for the case $m=n$.

For $G$ and one of its subgraphs $(W,S)$, if it satisfies $|W|=|S|\le n$, then the subgraph $T=(V,S)$ is a rooted forest with $V\setminus W$ as its roots if and only if

is nonzero. Moreover, when this expression is nonzero, it necessarily equals $\prod_{e\in S}w(e)$; denote it by $w(T)$.

Without loss of generality, assume $w(e)=1$. By the multilinearity of determinants, each determinant can have $\sqrt{w(e)}$ factored out of every row, and the product of these factors is $w(T)$.

First analyze the conditions under which the two factors are zero. Each row of the first factor $\det(M^\mathrm{out}_{S,W})$ has at most one nonzero entry, namely $+1$. If any row is all zero, the determinant must be zero. Thus, the determinant is nonzero if and only if every row has exactly one $+1$; that is, every vertex in $W$ is the starting point of exactly one edge in $S$, and no two edges share the same starting point. If $T$ is a rooted forest with $V\setminus W$ as its roots, a necessary condition is that every non-root vertex has exactly one outgoing edge, which necessarily makes this factor nonzero; but the converse does not always hold, because it does not guarantee the absence of cycles, so the second factor must also be examined. Note that the endpoints of edges in $S$ need not lie in $W$.

Assume that the first factor is nonzero. Then the subgraph $T$ is a rooted forest if and only if $T$ contains no cycle. In this case, every row of the latter expression $\det(M^\mathrm{out}_{S,W}-M^\mathrm{in}_{S,W})$ has one $+1$, but may have either one or zero $-1$ entries. For an edge whose endpoint is also in $W$, if the endpoint of $e_i$ is the starting point of $e_j$, add to the row for $e_i$ the row for $e_j$; this eliminates, in row $e_i$, the $-1$. One may imagine that this row now describes the simple path formed by joining $e_i$ and $e_j$ end to end. If a new $-1$ appears in the row, then the endpoint of $e_j$ is also in $W$, and the position of $-1$ is the endpoint of $e_j$. We can therefore continue by finding the edge starting at the endpoint of $e_j$ and adding its row to the current row. Such an edge always exists, because the preceding argument shows that every point in $W$ is the starting point of exactly one edge in $S$. This process continues until the row no longer contains a $-1$, which is equivalent to continuously adding new edges to the simple path $e_i\rightarrow e_j\rightarrow \cdots\rightarrow e_k$. If the row then contains only one $+1$, the endpoint of $e_k$ is not in the selected vertex set $W$, so the process terminates; if the last added edge happens to cancel the existing $+1$, leaving the row all zero, then the endpoint of the new edge $e_k$ is the starting point of the initial edge $e_i$, so a cycle has appeared. Thus, the necessary and sufficient condition for the absence of cycles is that this determinant can, after the operations above, be transformed into a form in which every row has exactly one $+1$. Since these $+1$ entries are at the starting points of the corresponding edges, the resulting matrix is exactly $\det(M^\mathrm{out}_{S,W})$.

In summary, if $T$ is not a rooted forest, then either $\det(M^\mathrm{out}_{S,W})=0$ or $\det(M^\mathrm{out}_{S,W}-M^\mathrm{in}_{S,W})=0$; otherwise, both are nonzero and their product is $\left(\det(M^\mathrm{out}_{S,W})\right)^2=1$.

For any $k$,

Here, $\mathcal T^\mathrm{root}(G,k)$ is the set of arborescences of $G$ rooted at $k$.

Let $W=[n]\setminus\{k\}$ be the set of vertices other than $k$. Then, by the Cauchy–Binet formula, the right-hand side can be written as

As $S$ ranges over all possibilities, by Lemma 2, if and only if $T=(V,S)$ forms a rooted forest with $V\setminus W=\{k\}$ as its root set, that is, if and only if $T$ is an arborescence rooted at $k$, the right-hand side accumulates $w(T)$.

For an undirected graph $G$ and any $k$,

Here, $\mathcal T(G)$ is the set of spanning trees of $G$. This also shows that all principal minors of $L(G)$ of order $(n-1)$ are equal.

For an undirected graph $G=(V,E)$, construct a directed graph $G'=(V,E')$, where $E'=\{(v_i,v_j):(v_i,v_j)\in E\}\cup\{(v_j,v_i):(v_i,v_j)\in E\}$; that is, every undirected edge in $G$ is split into two oppositely directed edges in the directed graph. Fix any $k$. Then the arborescences in $G'$ rooted at $k$ and the spanning trees in $G$ are in one-to-one correspondence. From the former to the latter, we only need to remove the orientations of the edges and the choice of root; from the latter to the former, we only need to start from the selected root $k$ and orient each edge toward the root. Therefore,

Here we use $L^\mathrm{out}(G')=L(G)$, which is straightforward to verify directly.

For a directed graph $G$, define the multivariate polynomial

Here, $\mathrm{diag}(x_1,\cdots,x_n)$ denotes the diagonal matrix whose diagonal entries are $x_1,\cdots,x_n$. Then,

equals the weighted count of rooted forests of $G$ whose root set is $\{k_1,\cdots,k_r\}$.

Following the proof of Theorem 4, let $W=[n]\setminus\{k_1,\cdots,k_r\}$. Then the coefficient in the theorem is $\det L^\mathrm{out}(G)_{W,W}$ (this can be seen directly from the Leibniz expansion of the determinant). By the Cauchy–Binet formula, it equals

As $S$ ranges over all possibilities, by Lemma 2, the condition that $T=(V,S)$ forms a rooted forest with $V\setminus W=\{k_1,\cdots,k_r\}$ as its root set is exactly the condition for the right-hand side to accumulate $w(T)$.

The Laplace matrix $L^\mathrm{out}(G)$ has at least one eigenvalue equal to zero.

It suffices to prove that its determinant is zero. Following the proofs of Theorems 4 and 5, take $W=\varnothing$. Then this determinant should equal the number of rooted forests with zero trees. Such a forest does not exist, so the determinant is zero.

For a directed graph $G$, the sum of the weights of all rooted forests consisting of $k$ trees equals the coefficient

Sum over all possible choices of the $k$ roots.

For an undirected graph $G$, let the set of its $k$-spanning forests be $\mathcal T_k(G)$. Then

Here, $Q(T)$ is the product of the numbers of vertices in each connected component of the forest $T$. In particular, when $k=1$, we have $Q(T)=n$, and hence

As in the proof of Corollary 4, we can directly use the conclusion of Corollary 5. Every rooted forest consisting of $k$ trees in the directed graph corresponds to a $k$-spanning forest in the undirected graph. However, each $k$-spanning forest $T$ has $Q(T)$ choices of roots, so it appears in $Q(T)$ rooted forests of the directed graph.

There are $n$-vertex labeled unrooted trees, of which there are $n^{n-2}$.

Equivalently, it suffices to show that the number of spanning trees of the complete graph on $n$ vertices is $n^{n-2}$. To this end, write its Laplace matrix as

Computing any principal minor gives

The result follows from Theorem 1.

A directed graph has an Eulerian circuit if and only if its nonzero-degree vertices are strongly connected and the out-degree equals the in-degree at every vertex.

Let $G$ be a directed Eulerian graph, and let $k$ be any vertex. Then the total number of distinct Eulerian circuits of $G$, $\mathrm{ec}(G)$, is

This also shows that for any Eulerian graph $G$ and any two vertices $k, k'$, we have $t^\mathrm{root}(G,k)=t^\mathrm{root}(G,k')$.

The basic idea of the proof is to establish a correspondence between Eulerian circuits starting at $k$, arborescences rooted at $k$, and permutations of the outgoing edges at each vertex. After fixing the starting vertex of the Eulerian circuit, the count to be proved should be

The combinatorial meaning of this count leads to the following construction. For an Eulerian circuit starting at $k$, according to the order in which each edge appears in the circuit, construct

• an arborescence rooted at $k$, consisting of the last outgoing edge at every non-root vertex, giving $t^\mathrm{root}(G,k)$;
• the ordering of all outgoing edges at the root $k$, giving $\mathrm{deg}(k)!$; and
• at each non-root vertex $v\neq k$, the ordering of all outgoing edges other than the last one, giving $(\mathrm{deg}(v)-1)!$.

We now show that this construction gives a bijection.

In one direction, given an Eulerian circuit, we must prove that the last outgoing edges at all non-root vertices form an arborescence. By construction, every non-root vertex in the tree has exactly one outgoing edge, so it remains only to prove that these outgoing edges do not form a cycle. If all vertices are ordered according to the order of their last appearances in the Eulerian circuit, then the last outgoing edge of every non-root vertex must point to a vertex that appears strictly later in this order. If a cycle existed, it would contain a vertex that appears latest in the order; because this vertex lies on the cycle, it would point to a vertex that does not appear later, contradicting the statement above. Thus, the last outgoing edges of all non-root vertices necessarily form an arborescence.

In the other direction, given any arborescence and an ordering of all the other outgoing edges, we can reconstruct an Eulerian circuit such that applying the construction above to it yields the given arborescence and ordering. Starting from the root $k$, whenever a vertex is reached, choose as the next edge of the Eulerian circuit the earliest unused outgoing edge according to the given ordering at that vertex; if all outgoing edges in the ordering at that vertex have been used, choose the outgoing edge of that vertex in the arborescence as the next edge of the Eulerian circuit. Since the graph is Eulerian, every vertex has equal in-degree and out-degree, so this process cannot terminate at a non-root vertex; the resulting path is therefore a circuit. To prove that the resulting path is a valid Eulerian circuit, it suffices to show that this process traverses every edge.

If it does not, there must be some vertex $v$ with an outgoing edge that has not been traversed. Consider vertex $v$. Vertex $v$ cannot be the root, because the process eventually terminates at the root, and if the root still had an unused outgoing edge, that would contradict the termination of the process. Thus, $v$ is not the root. By the process described above, as long as a non-root vertex $v$ has any outgoing edge remaining, its outgoing edge $e$ in the arborescence must also remain. Let $e=(v,u)$. Since some incoming edge of $u$ has not been traversed, and the out-degree of $u$ equals its in-degree, some outgoing edge of $u$ must not have been traversed either. We can then examine vertex $u$ in the same way. This reasoning moves the vertex under consideration from $v$ to $u$, namely one step toward the root along the arborescence. By induction, there must then be an unused outgoing edge of the root $k$. The preceding argument has already shown that this is impossible, giving a contradiction. Therefore, the path obtained in the preceding paragraph is indeed a valid Eulerian circuit.

It can be verified that these maps are injective, and hence they are bijections. The proposition follows.

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
constexpr int MOD = 100000007;
constexpr double eps = 1e-7;

struct matrix {
  static constexpr int MAXN = 20;
  int n, m;
  double mat[MAXN][MAXN];

  matrix() { memset(mat, 0, sizeof(mat)); }

  void print() {
    cout << "MATRIX " << n << " " << m << endl;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cout << mat[i][j] << "\t";
      }
      cout << endl;
    }
  }

  void random(int n) {
    this->n = n;
    this->m = n;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) mat[i][j] = rand() % 100;
  }

  void initSquare() {
    this->n = 4;
    this->m = 4;
    memset(mat, 0, sizeof(mat));
    mat[0][1] = mat[0][3] = 1;
    mat[1][0] = mat[1][2] = 1;
    mat[2][1] = mat[2][3] = 1;
    mat[3][0] = mat[3][2] = 1;
    mat[0][0] = mat[1][1] = mat[2][2] = mat[3][3] = -2;
    this->n--;  // remove one row
    this->m--;  // remove one column
  }

  double gauss() {
    double ans = 1;
    for (int i = 0; i < n; i++) {
      int sid = -1;
      for (int j = i; j < n; j++)
        if (abs(mat[j][i]) > eps) {
          sid = j;
          break;
        }
      if (sid == -1) continue;
      if (sid != i) {
        for (int j = 0; j < n; j++) {
          swap(mat[sid][j], mat[i][j]);
          ans = -ans;
        }
      }
      for (int j = i + 1; j < n; j++) {
        double ratio = mat[j][i] / mat[i][i];
        for (int k = 0; k < n; k++) {
          mat[j][k] -= mat[i][k] * ratio;
        }
      }
    }
    for (int i = 0; i < n; i++) ans *= mat[i][i];
    return abs(ans);
  }
};

int main() {
  srand(1);
  matrix T;
  // T.random(2);
  T.initSquare();
  T.print();
  double ans = T.gauss();
  T.print();
  cout << ans << endl;
}

Solution This is a basic application of the matrix-tree theorem. Treat each empty room as a node, build the graph according to the input, obtain the Laplace matrix, then delete from $L$ row $i$ and column $i$, and compute the determinant of the resulting minor. The determinant is computed by using Gaussian elimination to reduce the matrix to upper triangular form and then taking the product of the diagonal entries. In addition, this problem requires Gaussian elimination over the integer subring modulo $k$, $\mathbb{Z}_k$; the Euclidean algorithm can be used.

Solution There are many solutions to this problem, and using the matrix-tree theorem is the most direct. When the input is $n$, it is easy to write its Laplace matrix of order $n+1$ as:

It suffices to compute the determinant of its order-$n$ minor; the only remaining issue is high-precision computation.

Strengthen the data of Example 2 by requiring $n\leq 100000$, while the answer is taken modulo 1000007. (Solving this problem requires some linear algebra knowledge.)

Solution After deriving the recurrence, it can be computed using matrix exponentiation.

The derivation of the recurrence is as follows:

Notice that after deleting the first row and first column of $L_n$, the resulting matrix has a very regular form, so we are actually computing the determinant of

Expanding the determinant of $M_n$ along its first column gives

Denote the determinants of the three matrices above by $d_{n-1}, a_{n-1}, b_{n-1}$, respectively.
Notice that $d_n$ is a tridiagonal determinant; by a similar expansion, we obtain that $d_n$ satisfies the recurrence $d_n=3d_{n-1}-d_{n-2}$. Similarly, expanding gives $a_{n-1}=-d_{n-2}-1$ and $(-1)^n b_{n-1}=-d_{n-2}-1$.
Substituting these recurrences into the expression above gives:

We can therefore conjecture that $\det M_n$ also satisfies a nonhomogeneous second-order linear recurrence. Using the method of undetermined coefficients, the final recurrence is

Rewriting it as $(\det M_n+2) = 3(\det M_{n-1}+2) - (\det M_{n-2} + 2)$ and then using matrix exponentiation yields the answer.

Solution This problem is a direct application of the BEST theorem. However, note that because the problem specifies that 「two ways of completing the task are considered different if and only if the order of using the keys is different」, for every Eulerian circuit, room 1 may start along any outgoing edge, so the answer must also be multiplied by the out-degree of room 1.

Solution First, Möbius inversion is needed to transform the problem into computing the sum of the edge weights of all spanning trees; this is omitted because it is not closely related to this article.

Write the terms of the determinant as $w_ix+1$. The final answer is the coefficient of the first-degree term of the determinant, because the answer is actually the number of spanning trees after designating one edge $\times$ the sum of the weight of that edge, so the edge whose weight contributes to the first-degree coefficient is the designated edge. Terms of degree higher than one can be ignored, giving complexity $O(n^3)$.

「Beijing Provincial Selection Training 2019」Counting Spanning Trees is a more general case: to compute the sum of the $k$-th powers of the sums of spanning-tree weights, construct the terms of the determinant in a similar way; see the Luogu solution for details.

Solution Counting Eulerian circuits in an undirected graph is an NPC problem, but the graph in this problem is relatively simple. Once the number of edges among the $S-T$ edges directed from $S$ to $T$ is determined, the orientations of the other three types of edges are determined, and the BEST theorem directly gives a solution with complexity $O(a+b+c+d)$.