Forest matrices around the Laplacian matrix
arXiv:math/0508178 · doi:10.1016/S0024-3795(02)00388-9
Abstract
We 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
19 pages, presented at the Edinburgh (2001) Conference on Algebraic Graph Theory
References in corpus (2)
Cited by in corpus (27)
- A Tutorial on Modeling and Analysis of Dynamic Social Networks. Part I
- On the spectra of nonsymmetric Laplacian matrices
- Coordination in multiagent systems and Laplacian spectra of digraphs
- A Class of Graph-Geodetic Distances Generalizing the Shortest-Path and the Resistance Distances
- Spanning Forests and the Golden Ratio
- The Walk Distances in Graphs
- Topologically-constrained fluctuations and thermodynamics regulate nonequilibrium response
- Tree formulas, mean first passage times and Kemeny's constant of a Markov chain
- A graph interpretation of the least squares ranking method
- On Determining the Eigenprojection and Components of a Matrix
- Trees and forests for nonequilibrium purposes: an introduction to graphical representations
- The graph bottleneck identity
- On graph theoretic results underlying the analysis of consensus in multi-agent systems
- Comments on "Consensus and Cooperation in Networked Multi-Agent Systems"
- The Projection Method for Reaching Consensus and the Regularized Power Limit of a Stochastic Matrix
- Which Digraphs with Ring Structure are Essentially Cyclic?
- Hitting Time Quasi-metric and Its Forest Representation
- On resistance distance of Markov chain and its sum rules
- On the Poisson equation for nonreversible Markov jump processes
- Mutual Multilinearity of Nonequilibrium Network Currents
- Covariance and Correlation Kernels on a Graph in the Generalized Bag-of-Paths Formalism
- Models of latent consensus
- Drazin-Inverse and heat capacity for driven random walks on the ring
- A Cyclic Representation of Discrete Coordination Procedures
- Second-Order Agents on Ring Digraphs
- Matrices of forests, analysis of networks, and ranking problems
- The projection method for continuous-time consensus seeking