Forest matrices around the Laplacian matrix

Simple item page
dc.creatorChebotarev, Pavel
dc.creatorAgaev, Rafig
dc.date2005-08-10
dc.date2006-02-04
dc.date.accessioned2026-07-07T06:42:46Z
dc.date.available2026-07-07T06:42:46Z
dc.descriptionWe study the matrices Q_k of in-forests of a weighted digraph G and their connections with the Laplacian matrix L of G. 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(a*I+L). Thereby they are precisely Faddeev's matrices for -L. Keywords: Weighted digraph; Laplacian matrix; Spanning forest; Matrix-forest theorem; Leverrier-Faddeev method; Markov chain tree theorem; Eigenprojection; Generalized inverse; Singular M-matrix
dc.description19 pages, presented at the Edinburgh (2001) Conference on Algebraic Graph Theory
dc.identifierhttps://arxiv.org/abs/math/0508178
dc.identifierhttp://arxiv.org/abs/math/0508178
dc.identifierLinear Algebra and Its Applications. 2002. V. 356. 253--274
dc.identifierdoi:10.1016/S0024-3795(02)00388-9
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/102164
dc.subjectCombinatorics
dc.subject05C50; 05C05; 05C20; 15A48; 15A09
dc.titleForest matrices around the Laplacian matrix
dc.typetext

Files

Collections

arXiv