Let $L$ be the out-degree Laplacian of a directed graph (with at least one vertex), in which there is a directed path from any vertex $i$ to any vertex $j$. In this case the kernel is one dimensional.
I have observed that the kernel is spanned by a vector with non-negative entries. Is this something known or straightforward to show? Are there any results for the left-kernel of directed Laplacians?
PS. Left-kernel is just the kernel of the transpose.
Best Answer
[This answer is an extended version of my comment, with more references.]
Let $V$ be the set of vertices of your digraph. Let $A$ be the transpose adjacency matrix of $V$ (that is, the $V \times V$-matrix whose $\left(i,j\right)$-entry is the number of edges from $j$ to $i$). Let $D$ be the diagonal $V \times V$-matrix whose $\left(i,i\right)$-th entry is the outdegree of vertex $i$. Depending on whom you ask, the Laplacian $L$ of the digraph is either $D - A$ or $A - D$ or $\left(D - A\right)^T$ or $\left(A - D\right)^T$. Of course, any statement about one of these four Laplacians can easily be translated into a statement about the other three, so it does not matter which one we take to be "the" Laplacian. In the following, I shall define the Laplacian $L$ to be $A - D$. It is easy to see that the row vector $e := \left(1\right)_{v \in V} \in \mathbb{Z}^V$ satisfies $eL = 0$.
Your claim is that if the digraph is strongly connected, then we can find a column vector $v \in \mathbb{Z}^V$ that satisfies $Lv = 0$ and whose entries are positive.
Here are three sources that prove this:
Siddhartha Sahi, Harmonic vectors and matrix tree theorems, arXiv:1309.4047v1. (Sahi defines the Laplacian $L$ to be $D - A$ rather than $A - D$, but this is of course insubstantial, since it's just a matter of replacing $D$ by $-D$. Also, instead of allowing multiple edges, Sahi puts weights on the edges of the digraph; this is a more general setting, to which you can easily reduce yours because you can replace $k$ parallel edges by a single edge with weight $k$.) Sahi defines a "harmonic vector" as a column vector $v \in \mathbb{Z}^V$ that satisfies $Lv = 0$; then he explicitly constructs a certain vector (called the "weight vector"), and proves that it is harmonic (in his Theorem 1). The entries of this weight vector count "$i$-trees" (= directed spanning trees with root $i$); it is easy to see that when the digraph is strongly connected, these entries are all positive integers (i.e., for each vertex $i$, there exists at least one $i$-tree). So this weight vector is a column vector $v \in \mathbb{Z}^V$ that satisfies $Lv = 0$ and whose entries are positive.
Arash Asadi, Spencer Backman, Chip-Firing and Riemann-Roch Theory for Directed Graphs, arXiv:1012.0287v2 . Lemma 3.1 here shows that if the digraph is strongly connected, then there exists a vector $R \in \mathbb{Z}^V$ such that $\overrightarrow{Q}^T R = 0$, where their matrix $\overrightarrow{Q}^T$ is easily seen to be our $D - A = -L$. Note that the proof of Lemma 3.1 in this paper omits explaining why there exists any nonzero vector $R\in \mathbb{Q}^V$ satisfying $\overrightarrow{Q}^{T}R=0$; but this is easy to see: We already know that the nonzero row vector $e$ satisfies $eL = 0$, and thus the matrix $L$ is singular; hence, there exists a nonzero vector $R\in \mathbb{Q}^V$ satisfying $LR = 0$. This vector $R$ thus must also satisfy $\overrightarrow{Q}^T R = 0$, since $\overrightarrow{Q}^T = -L$.
A. Björner and L. Lovasz, Chip-firing games on directed graphs, J. Algebraic Combin., 1(4), 1992, pp. 305–328. Proposition 4.1 (i) proves that the digraph has a strictly positive period vector -- which is defined to be a column vector $v \in \mathbb{Z}^V$ that satisfies $Lv = 0$ and whose entries are positive. The proof here is a bit of an overkill, due to the authors showing several things at once.