Principal minors of tree distance matrices

David Harry Richman, Farbod Shokrieh, Chenxi WuarXiv 2024 · DOI · arXiv

Abstract

We prove that the principal minors of the distance matrix of a tree satisfy a combinatorial expression involving counts of rooted spanning forests of the underlying tree. This generalizes a result of Graham and Pollak, and refines a result of Graham and Lovász on the coefficients of the characteristic polynomial of the distance matrix. We also give such an expression for the case of trees with edge lengths. We use arguments motivated by potential theory on graphs. Our formulas can be expressed in terms of evaluations of Symanzik polynomials.

Introduction

In 1971, Graham and Pollak discovered a mathematical "magic trick": the determinant of the distance matrix of any tree depends only on the number of vertices $n$, completely ignoring how those vertices are connected. Whether the tree is a simple path or a star-shaped explosion, the determinant is always the same. This paper provides the first general combinatorial formulas for the principal minors of a tree's distance matrix, successfully generalizing this famous identity.

While the full determinant is "shape-blind," its sub-determinants—formed by choosing a subset of vertices $S$—encode deep structural information about the underlying graph. Until now, a unified combinatorial language to describe how these minors behave was missing. By leveraging potential theory and "rooted spanning forests," the authors reveal the "missing link" between the algebraic properties of these matrices and the combinatorial properties of the trees they represent.

A tree $G$ with a subset of vertices $S = \{v_1, v_2, v_3\}$ highlighted.

Combinatorial Methods and Potential Theory

The researchers move away from pure linear algebra and instead utilize Potential Theory on Graphs. Their primary tools include:

  • Rooted Spanning Forests: They define two sets of forests: $\mathcal{F}_1(G; S)$ (where each component contains exactly one vertex from the subset $S$) and $\mathcal{F}_2(G; S)$ (which includes an extra "floating" component).
  • Equilibrium Vectors: They introduce a vector $\mathbf{m}$ that acts as a "canonical measure" for the vertex subset. This vector is rooted in the physics of electrical networks, where distances in a tree are analogous to effective resistance.
  • Symanzik Polynomials: They show that their formulas can be elegantly translated into the language of Symanzik polynomials, which are frequently used in quantum field theory to calculate Feynman amplitudes.
Examples of rooted spanning forests in the set $\mathcal{F}_1(G; S)$ for the tree shown above.

Key Insights and Results

The paper establishes several key results that refine our understanding of tree distance matrices:

  • The "Shape-Blind" Exception: The Graham-Pollak identity is confirmed as a special case where the subset $S$ is the entire vertex set. In this scenario, complex structural terms in the new formula cancel out, leaving the classic result.
  • Monotonicity of Normalized Minors: Theorem D shows that "normalized" principal minors (the ratio $\det D[S] / \text{cof } D[S]$) are monotonic. Adding more vertices to the subset $S$ always increases this ratio.
  • The Role of Outdegrees: The formulas aren't just based on the number of forests, but on the outdegrees of the components within those forests. The "branchiness" of the tree directly dictates the algebraic value of the minor.
  • Optimization Link: The paper establishes that the normalized principal minor is the maximum value of a quadratic form $\mathbf{u}^\intercal D[S] \mathbf{u}$ subject to the constraint that the entries of $\mathbf{u}$ sum to 1.

Applications and Future Work

These results could lead to new tests in phylogenetics (the study of evolutionary trees), helping researchers determine which tree structure best fits a given set of pairwise genetic distances.

Currently, the paper is strictly limited to trees. While trees are fundamental, many real-world networks contain cycles. The authors are working on generalizing these results to arbitrary finite graphs. Additionally, while the formulas are combinatorial, calculating them for extremely large graphs involves counting spanning forests, which can be computationally intensive. Future work might focus on more efficient algorithmic approximations for these minors in massive networks.

Summary updated

Abstract

We prove that the principal minors of the distance matrix of a tree satisfy a combinatorial expression involving counts of rooted spanning forests of the underlying tree. This generalizes a result of Graham and Pollak, and refines a result of Graham and Lovász on the coefficients of the characteristic polynomial of the distance matrix. We also give such an expression for the case of trees with edge lengths. We use arguments motivated by potential theory on graphs. Our formulas can be expressed in terms of evaluations of Symanzik polynomials.
BibTeX
@misc{richman2024principal,
  author = {David Harry Richman and Farbod Shokrieh and Chenxi Wu},
  title = {{Principal minors of tree distance matrices}},
  year = {2024},
  eprint = {2411.11488},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2411.11488},
}
Figure