REDUCING THE ADJACENCY MATRIX OF A TREE

GERD H. FRICKE y, STEPHEN T. HEDETNIEMI z, DAVID P. JACOBS z{, AND VILMAR TREVISAN x{

Abstract. Let T be a tree, A its adjacency matrix, and a scalar. We describe a linear-time algorithm for reducing the matrix ffIn + 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.

Key words. tree, graph, adjacency matrix, determinant, rank, eigenvalue

AMS subject classifications. 05C05, 15A15, 15A18, 68R10

1. Introduction. Let G = (V; E) be an undirected graph with vertices V = (v1; : : : ; vn) and edge set E. The adjacency matrix A = [aij ] of G is the n ? n (0 ? 1) symmetric matrix in which aij = 1 if and only if i <> j and vi is adjacent to vj (that is, there is an edge between vi and vj ). The neighborhood matrix of G, which we denote with N , is obtained by placing 1's along the diagonal of the adjacency matrix (i.e. N = A+In). Note that the rank and determinant of these matrices are independent of the vertex ordering, since interchanging two rows and then interchanging two columns leaves the rank and determinant unchanged.

In this paper, we are concerned only with trees T (i.e., connected, acyclic graphs), their adjacency matrices A, and neighborhood matrices N . In [3], it was shown that the rank of A is exactly twice the mathcing number of T (i.e., the maximum number of edges in a set, no two of which have a common vertex). Recently, it was shown how the determinant of N can be computed in linear-time [9]. In this paper we present a single linear-time algorithm for computing the rank and determinant, over a field F , of the matrix ffIn + A, for arbitrary 2 F . As special cases, we obtain linear-time algorithms for the rank and determinant of the adjacency and neighborhood matrices, by taking = and = 1, respectively. By treating symbolically, we can also
compute the characteristic polynomial of A.

The primary contribution is that our algorithm offers a general way of looking at several seemingly unrelated topics including rank, determinant, matching number, independence, and the characteristic polynomial. Several known results are looked at in this new light, in addition to some new applications.

2. The reduction algorithm. Let F be any field, T a tree having adjacency matrix A, and M = ffIn + A, for some 2 F . We wish to compute rank(M) and det(M) over F . Instead of computing with the matrix M , however, we compute directly on T in the following way.

Our algorithm associates with each vertex v, a scalar a(v) 2 F . Initially, a(v) = , for all v 2 V . A variable d (for deletions) is initialized to 0. The tree is rooted at an arbitrary vertex. The algorithm then processes the vertices bottom-up, beginning with the leaves, which are initially declared to be processed. In general, we choose any unprocessed vertex v of maximum depth, and mark it processed. If there exist

{ The third and fourth authors thank CNPq and Clemson University for their generous support. y Dept. of Math., Wright State Univ., Dayton, OH 45435 US, [email protected] z Dept. Comp. Sci., Clemson Univ., Clemson, SC 29634 US, fhedet,[email protected] x UFRGS, Instituto de Matem?atica, 91509{900 Porto Alegre, RS, Brasil, [email protected]