Abstract
There are several common ways to encode a tree as a matrix, such as the adjacency matrix, the Laplacian matrix (the infinitesimal generator of the natural random walk), and the matrix of pairwise distances between leaves. Such representations involve a specific labeling of the vertices or leaves, making it natural to attempt to identify trees by features invariant under relabeling, such as the spectrum of eigenvalues. This paper demonstrates that for any of these matrix choices, the fraction of binary trees with a unique spectrum goes to zero as the number of leaves $n$ approaches infinity. Furthermore, for adjacency and Laplacian matrices, even the more complex immanantal polynomials offer no greater power to distinguish between trees.
The Challenge of Tree Identification
In fields like phylogenetics, rooted binary trees are essential for representing evolutionary histories. To compare these structures mathematically, researchers often convert them into matrices. However, because these trees are typically "unlabeled"—meaning the identity of specific leaves is less important than the overall topology—we require matrix features that are invariant under row and column permutations.
For decades, the spectrum (the set of eigenvalues) has been the primary candidate for a unique algebraic "fingerprint." The central question is whether a tree's shape can be uniquely recovered from its spectrum. This research proves that for large trees, this is almost never possible.
Spectral Twins and the Exchange Property
The failure of spectra to uniquely identify trees stems from local structural redundancies. The authors identify an "Exchange Property" where specific pairs of small subtrees are algebraically equivalent. If one such subtree is swapped for its "twin" within a larger tree, the global spectrum remains unchanged, creating what are known as spectral twins.
As shown in the figure above, these pairs (a, b, and c) represent different topologies that are indistinguishable to the matrix's eigenvalues. The research shows that as trees grow, the probability of containing these "swappable" modules approaches 1, leading to the "ubiquity of synonymity."
Methods and Asymptotic Analysis
The study employs a combination of algebraic theory and complex analysis:
- Subtree Ubiquity: Using generating functions (extending the work of Wedderburn and Otter), the authors prove that any specific finite subtree will almost certainly appear in a sufficiently large random binary tree.
- Immanantal Polynomials: The authors investigated whether immanantal polynomials—a generalization of the characteristic polynomial using characters of the symmetric group—could provide better resolution. Mathematically, they proved that for adjacency and Laplacian matrices, if two trees share a spectrum, they also share the same immanantal polynomials, rendering the more complex tool redundant.
- Numerical Verification: To bridge the gap between theory and practice, the authors used recursive OCaml algorithms to exhaustively enumerate trees up to $n=18$ leaves and perform simulations for larger $n$.
Key Results
- The Limit of Uniqueness: The primary theorem states that for adjacency, Laplacian, and pairwise distance matrices, the fraction of unique trees $l_n/t_n \to 0$ as $n \to \infty$.
- Slow Convergence: While the theoretical limit is zero, the numerical results show this loss of identity happens remarkably slowly. At 18 leaves, only 80 out of 56,011 possible trees share a Laplacian spectrum with another tree. This suggests that for many practical applications involving hundreds of leaves, spectra remain a highly effective, if theoretically imperfect, heuristic.
- Distance Matrix Performance: The pairwise distance matrix, frequently used in biology, was found to be slightly more robust at distinguishing small trees than the Laplacian, though it remains subject to the same eventual failure in the limit.
Limitations and Future Directions
The main limitation is the extremely slow rate of convergence, which means the "ubiquity" of these twins may not be felt in small-scale empirical studies. Future work remains to determine if immanantal polynomials provide any additional distinguishing power specifically for distance matrices, and to identify other algebraic invariants that might resist this asymptotic loss of identity.
Summary updated