2005/12/03 by F. A. Matsen, Frederick A. Matsen, Steven N. Evans +2
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #FOS: Biological sciences #Graph theory and applications #Populations and Evolution (q-bio.PE) #Random Matrices and Applications #Topological and Geometric Data Analysis #q-bio.PE
paper · pdf · doi:10.48550/arxiv.q-bio/0512010
openalex publication_date 2005/12/03 · arxiv created 2006/01/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.