Forest matrices around the Laplacian matrix

We study the matrices Q(k) of in-forests of a weighted digraph F and their connections with the Laplacian matrix L of F. The (i, j) entry Of Qk is the total weight of spanning converging forests (in-forests) with k arcs such that i belongs to a tree rooted at j. The forest matrices, Qk, can be calculated recursively and expressed by polynomials in the Laplacian matrix; they provide representations for the generalized inverses, the powers, and some eigenvectors of L. The normalized in-forest matrices are row stochastic; the normalized matrix of maximum in-forests is the eigen-projection of the Laplacian matrix, which provides an immediate proof of the Markov chain tree theorem. A source of these results is the fact that matrices Qk are the matrix coefficients in the polynomial expansion of adj(lambdaI + L). Thereby they are precisely Faddeev's matrices for -L. (C) 2002 Elsevier Science Inc. All rights reserved.