\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf J.$\,$S.~Caughman and J.$\,$J.$\,$P.~Veerman}
%
%
\medskip
\noindent
%
%
{\bf Kernels of Directed Graph Laplacians}
%
%
\vskip 5mm
\noindent
%
%
%
%
Let $G$ denote a directed graph with adjacency matrix $Q$ and
in-degree matrix $D$. We consider the {\em Kirchhoff matrix} $L=D-Q$,
sometimes referred to as the {\em 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 recently 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.
\bye