Forest matrices around the Laplacian matrix
Abstract
We study the matrices Q k of in-forests of a weighted digraph Γ and their connections with the Laplacian matrix L of Γ. The (i, j) entry of Q k 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, Q k, 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 Q k are the matrix coefficients in the polynomial expansion of adj(λI + L). Thereby they are precisely Faddeev’s matrices for −L. AMS classification: 05C50; 15A48