Forest matrices around the Laplacian matrix

Details Forest matrices around the Laplacian matrix Forest matrices around the Laplacian matrix

2005-08-10

arxiv.org/abs/math/0508178v2

Linear Algebra and Its Applications. 2002. V. 356. 253--274

Mathematics

Combinatorics

19 pages, presented at the Edinburgh (2001) Conference on Algebraic Graph Theory

Scientific paper

10.1016/S0024-3795(02)00388-9

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

Affiliated with

Also associated with

No associations

Rating

Forest matrices around the Laplacian matrix does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Forest matrices around the Laplacian matrix, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Forest matrices around the Laplacian matrix will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-322443