Reducing the adjacency matrix of a tree

Abstract

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.