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.