Ubiquity of synonymity: almost all large binary trees are not uniquely identified by their spectra or their immanantal polynomials

F. A. Matsen, Steven N. Evans

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.

Figure 1: Examples of non-isomorphic rooted binary trees that share the same spectrum (spectral twins) for various matrix representations.

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:

  1. 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.
  2. 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.
  3. 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

Abstract

There are several common ways to encode a tree as a matrix, such as the adjacency matrix, the Laplacian matrix (that is, 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 at least the leaves, and so it is natural to attempt to identify trees by some feature of the associated matrices that is invariant under relabeling. An obvious candidate is the spectrum of eigenvalues (or, equivalently, the characteristic polynomial). We show for any of these choices of matrix that the fraction of binary trees with a unique spectrum goes to zero as the number of leaves goes to infinity. We investigate the rate of convergence of the above fraction to zero using numerical methods. For the adjacency and Laplacian matrices, we show that that the {\em a priori} more informative immanantal polynomials have no greater power to distinguish between trees.
BibTeX
@misc{matsen2005ubiquity,
  author = {F. A. Matsen and Steven N. Evans},
  title = {{Ubiquity of synonymity: almost all large binary trees are not uniquely identified by their spectra or their immanantal polynomials}},
  year = {2005},
  eprint = {q-bio/0512010},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/q-bio/0512010},
}
Figure