ELA, Volume 1, pp. 34-43, abstract.
Reducing the Adjacency Matrix of a Tree
Gerd H. Fricke, Stephen T. Hedetniemi, David P. Jacobs and
Vilmar Trevisan
Let T be a tree, A its adjacency matrix, and a be a scalar.
We describe a linear-time algorithm for reducing the matrix
aI + A. Applications include computing the rank of A,
finding a maximum matching in T, computing the rank and
determinant of the associated neighborhood matrix, and
computing the characteristic polynomial of A.