If Laplacian L = D-A where D is the degree matrix and A is an 0-1 adjacency matrix for a directed graph. How can we prove that this Laplacian has an eigenvalue at 0?
Prove that the Laplacian for a directed graph has an eigenvalue at 0
directed graphsgraph theory
Related Solutions
I can make two sort of hand-wavy observations. From basic linear algebra properties we know that given a matrix $ \mathbf{L} $ \begin{equation} \sum_{i}d_{i}= \sum_{i}\lambda_{i} \end{equation}
where $ \lambda $ are the eigenvalues, and $ d $ are the the diagonal elements of your matrix $ \mathbf{L} $.
The elements on the diagonal of the Laplacian correspond to the degrees of the vertices. Assuming no isolated vertices and that the graph is simple (i.e weights are either $0$ or $1$), $ d_{i} \geq 1 $.
If most of your eigenvalues are equal to $1$, then their sum is also likely a small number. That means that the sum of degrees is also a small number, which means that your graph is probably sparsely connected.
The next observation has to do with star graphs. In general, complete bipartite graphs with $n$ and $m$ vertices on each group respectively, have Laplacian eigenvalues:
- $n$ with multiplicity $m-1$
- $m$ with multiplicity $n-1$
- $0$ with multiplicity $1$
- $m+n$ with multiplicity 1
Consider the star graph below which is a complete bipartite graph with $n=1$ and $m=8$
Its eigenvalues are $1$ with multiplicity $7$, $0$ with multiplicity $1$ and $9$ with multiplicity $1$.
So, if your graph contains starlike subgraphs, then your Laplacian is going to have a bunch of $1$-eigenvalues. I include two examples below (the random isolated component belongs to the graph on the right).
. 
Both of these graphs have eigenvalue $1$ with multiplicity $9$.
First let me give another common way of computing the Laplacian of an undirected graph $G=(V, E)$ that generalizes more easily to the directed weighted graphs you are interested in.
Suppose $V = (v_1, \dots, v_n)$ and $E = \{1, \dots, m\}$ and fix an arbitrary orientation on the edges. Consider the vertex space $\mathbb{R}^V$ with standard basis $\{\mathbf{e}_1, \dots, \mathbf{e}_n\}$ and, for each edge $i \in \{1,\dots,m\}$, let $\mathbf{n}_i = \mathbf{e}_j - \mathbf{e}_k$. Then the $n \times m$ matrix $N$ whose columns are the $\mathbf{n}_i$ ($i\in[m]$) is called the signed vertex-edge incidence matrix of $G$ (with respect to the fixed orientation).
The key fact is that the Laplacian $L$ of the $G$ is the (transpose of the) Gram matrix of $N$, that is, $L = NN^{\top}$. In particular, the matrix product $NN^{\top}$ does not depend on the orientation we fixed.
Now let $G$ be a weighted directed graph and let $W$ be the $m \times m$ diagonal matrix with entries $W_{ij}$ equal to the weight of edge $i$ if $i=j$ and zero else. Then we can define the Laplacian of $G$ as the matrix product $NWN^{\top}$ where $N$ is the signed vertex-edge incidence matrix of the underlying unweighted graph of $G$. And this definition generalizes the case for unweighted undirected graphs. See Section 3 of this paper for more on the subject.
Best Answer
Let $\textbf{1}$ be the function taking the value $1$ at each vertex. Then by explicit calculation, we see that both $D\textbf{1}$ and $A\textbf{1}$ are equal to the function taking the value $\deg(v)$ at each vertex $v$. Consequently, $$ (D-A)\textbf{1}=0, $$ which means that $\textbf{1}$ is an eigenvector of the Laplacian with eigenvalue $0$.