A matrix algebra approach to tree shape

F. A. Matsen, Steven N. Evans

Abstract: In this paper we investigate eigenvalues of matrix representations of trees as a means by which one might quantify the shape of a tree. We consider the adjacency matrix, the Laplacian matrix, and the pairwise distance matrix of the tree. We then demonstrate that for any of these choices of matrix the fraction of trees with a unique set of eigenvalues goes to zero as the number of leaves goes to infinity. This implies that the eigenvalues of these matrix representations may not give as much information as might be hoped. We investigate the rate of convergence of the above fraction to zero using numerical methods.

Introduction: The Search for a Tree Fingerprint

In fields such as phylogenetics, researchers are tasked with summarizing and comparing complex evolutionary relationships represented as trees. A persistent challenge is finding a "canonical" statistic—a unique identifier or "fingerprint" that captures a tree's shape without being influenced by node labeling.

A popular approach involves converting a tree into a matrix representation and calculating its spectrum (its set of eigenvalues). Common choices include the adjacency matrix (mapping direct connections), the Laplacian matrix (related to graph connectivity and random walks), and the pairwise distance matrix (recording path lengths between leaves). The hope was that these spectra would provide a unique signature for every possible tree shape. However, this research demonstrates that for large rooted binary trees, this uniqueness is almost always lost.

Methodology: The Exchange Property and Spectral Twins

The authors utilize a combination of algebraic graph theory and asymptotic analysis to test the limits of spectral uniqueness. The core of the proof relies on the exchange property. By identifying specific small subtrees ($S_1$ and $S_2$) that can be swapped within a larger tree structure without altering the overall spectrum, the authors prove the existence of "spectral twins."

Figure 1: Examples of spectral twins—distinct tree topologies that share the same matrix spectrum.

To generalize this from specific examples to a universal proof, the authors employed generating functions to count the prevalence of trees that avoid these swappable modules. They found that as the number of leaves ($n$) approaches infinity, the number of trees avoiding these "bad" subtrees becomes a vanishingly small fraction of the total tree space.

Furthermore, the study investigated immanantal polynomials, a more complex algebraic generalization of the determinant. The authors proved that for adjacency and Laplacian matrices, even this sophisticated tool fails to distinguish trees better than simple eigenvalues do; if the eigenvalues are identical, the immanants are redundant.

Key Insights: The Ubiquity of Synonymity

The central finding of the paper is the "ubiquity of synonymity." In the mathematical limit, uniqueness is the exception rather than the rule. Most large trees are "synonyms"—structurally different entities that produce identical algebraic outputs. This occurs because as trees grow, they almost certainly contain the specific swappable modules required to create a spectral twin.

Interestingly, the research also highlights that while uniqueness eventually disappears, it does so quite slowly. Numerical results suggest that for the tree sizes typically encountered in biological research, spectral statistics may still retain significant distinguishing power.

Results and Empirical Findings

The study's primary theoretical result is Theorem 1, which states that for adjacency, Laplacian, and distance matrices, the fraction of trees with a unique spectrum converges to zero as $n \to \infty$.

To understand the practical implications, the authors performed exhaustive enumerations for all unlabeled rooted binary trees with up to $n=18$ leaves (a total of 56,011 possible trees). The empirical results were surprisingly robust for these smaller sizes:

  • Generalized Laplacian: 55,931 trees (99.8%) maintained unique spectra.
  • Distance Matrix: 56,009 trees (99.99%) maintained unique spectra.

Numerical iterations up to 10,000 leaves confirmed the downward trend, though the rate of decay is slow enough that spectral methods remain practically useful for many current biological applications.

Limitations and Future Directions

While the authors successfully proved the limitations of adjacency and Laplacian matrices, a gap remains regarding the distance matrix. It is currently unknown if immanantal polynomials could provide additional distinguishing power for distance matrices where they failed for the others.

Future work may focus on the "informative" nature of these statistics for real-world datasets. Even if they are not mathematically perfect in the limit, their high performance at moderate tree sizes suggests they still hold value for phylogenetic analysis and comparative biology.

Summary updated

Abstract

In this paper we investigate eigenvalues of matrix representations of trees as a means by which one might quantify the shape of a tree. We consider the adjacency matrix, the Laplacian matrix, and the pairwise distance matrix of the tree. We then demonstrate that for any of these choices of matrix the fraction of trees with a unique set of eigenvalues goes to zero as the number of leaves goes to infinity. This implies that the eigenvalues of these matrix representations may not give as much information as might be hoped. We investigate the rate of convergence of the above fraction to zero using numerical methods. 1
BibTeX
@misc{matsen2005matrix,
  author = {F. A. Matsen and Steven N. Evans},
  title = {{A matrix algebra approach to tree shape}},
  year = {2005},
  eprint = {q-bio/0512010},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/q-bio/0512010},
}
Figure