An $O(n^2)$ Algorithm for the Characteristic Polynomial of a Tree

Abstract

We describe an algorithm that uses $O(n)$ arithmetic operations for computing the determinant of the matrix $M=(A+\alpha I)$, where $A$ is the adjacency matrix of an order $n$ tree. Combining this algorithm with interpolation, we derive a simple algorithm requiring $O(n^2)$ arithmetic operations to find the characteristic polynomial of the adjacency matrix of any tree. We apply our algorithm and recompute a 22-degree characteristic polynomial, which had been incorrectly reported in the quantum chemistry literature.