Published In
The Electronic Journal of Combinatorics
Document Type
Article
Publication Date
2006
Subjects
Matrices, Directed graphs, Laplacian matrices -- Eigenvalues, Stochastic matrices
Abstract
Let G denote a directed graph with adjacency matrix Q and in- degree matrix D. We consider the Kirchhoff matrix L = D − Q, sometimes referred to as the directed Laplacian. A classical result of Kirchhoff asserts that when G is undirected, the multiplicity of the eigenvalue 0 equals the number of connected components of G. This fact has a meaningful generalization to directed graphs, as was observed by Chebotarev and Agaev in 2005. Since this result has many important applications in the sciences, we offer an independent and self-contained proof of their theorem, showing in this paper that the algebraic and geometric multiplicities of 0 are equal, and that a graph-theoretic property determines the dimension of this eigenspace--namely, the number of reaches of the directed graph. We also extend their results by deriving a natural basis for the corresponding eigenspace. The results are proved in the general context of stochastic matrices, and apply equally well to directed graphs with non-negative edge weights.
Persistent Identifier
http://archives.pdx.edu/ds/psu/10279
Citation Details
Caughman, J.S., and Veerman, J.J.P. "Kernels of directed graph Laplacians." The Electronic Journal of Combinatorics 13.1 (2006).
Description
This is the publisher's final PDF. This article was originally published in The Electronic Journal of Combinatorics (http://www.combinatorics.org/ojs/index.php/eljc/index)