Published In

The Electronic Journal of Combinatorics

Document Type

Article

Publication Date

2006

Subjects

Laplacian matrices, Associative algebras

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

Share

COinS