Skip to main content
Article
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
Article
Publication Date
1-1-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.

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)

Persistent Identifier
http://archives.pdx.edu/ds/psu/10279
Citation Information
Caughman, J.S., and Veerman, J.J.P. "Kernels of directed graph Laplacians." The Electronic Journal of Combinatorics 13.1 (2006).