Forest matrices around the Laplacian matrix Original Research Article

We study the matrices Qk of in-forests of a weighted digraph Γ and their connections with the Laplacian matrix L of Γ. 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 eigenprojection 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(λI+L). Thereby they are precisely Faddeev’s matrices for −L.