{
  "id": "math/0508178",
  "version": "v2",
  "published": "2005-08-10T11:15:17.000Z",
  "updated": "2006-02-04T12:30:45.000Z",
  "title": "Forest matrices around the Laplacian matrix",
  "authors": [
    "Pavel Chebotarev",
    "Rafig Agaev"
  ],
  "comment": "19 pages, presented at the Edinburgh (2001) Conference on Algebraic Graph Theory",
  "journal": "Linear Algebra and Its Applications. 2002. V. 356. 253--274",
  "doi": "10.1016/S0024-3795(02)00388-9",
  "categories": [
    "math.CO"
  ],
  "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",
  "revisions": [
    {
      "version": "v2",
      "updated": "2006-02-04T12:30:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50",
      "05C05",
      "05C20",
      "15A48",
      "15A09"
    ],
    "keywords": [
      "laplacian matrix",
      "markov chain tree theorem",
      "generalized inverse",
      "weighted digraph",
      "polynomial"
    ],
    "tags": [
      "conference paper",
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math......8178C"
    }
  }
}