Skip to main content
Kernels of Directed Graph Laplacians
The Electronic Journal of Combinatorics
  • John S. Caughman, IV, Portland State University
  • J. J. P. Veerman, Portland State University
Document Type
Publication Date
  • Laplacian matrices,
  • Associative algebras
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.

This is the publisher's final PDF. This article was originally published in The Electronic Journal of Combinatorics (

Persistent Identifier
Citation Information
Caughman, J.S., and Veerman, J.J.P. "Kernels of directed graph Laplacians." The Electronic Journal of Combinatorics 13.1 (2006).