Reducing the adjacency matrix of a tree
Gerd H. Fricke, Stephen T. Hedetniemi, David Pokrass Jacobs, Vilmar Trevisan · Electronic Journal of Linear Algebra · 1996
Let T be a tree, A its adjacency matrix, and a scalar.We describe a linear-time algorithm for reducing the matrix In + A. Applications include computing the rank of A, nding a maximum matching in T, computing the rank and determinant of the associated neighborhood matrix, and computing the characteristic polynomial of A.