Gerd H. Fricke, Stephen T. Hedetniemi, David P. Jacobs and Vilmar Trevisan, Reducing the Adjacency Matrix of a Tree, pp. 34-43

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.