Number of strongly connected components of a digraph and the Laplacian

Question

The multiplicity of the zero eigenvalue of the Laplacian matrix of an undirected graph is equal to the number of its connected components. I am wondering if a similar result holds for directed graphs? In other words, is the number of strongly connected components also equal to the multiplicity of the zero eigenvalue of the digraph Laplacian? I only found a couple of papers that discuss the spectral properties of digraphs based on their Laplacians (e.g., Chung 2005), but I see no mention of such result.

Chung, F. (2005). Laplacians and the Cheeger inequality for directed graphs. Annals of Combinatorics, 9(1), 1-19.

Answer 1

I don't think Chung's definition of the directed Laplacian even makes sense for graphs that aren't strongly connected. It requires first finding the Perron vector $\boldsymbol\phi$ of the graph; this is the stationary distribution of a random walk on the directed graph. For strongly connected directed graphs, this is unique, and we can proceed with the definition as usual.

For a directed graph $G$ that is not strongly connected, let $H$ be the directed acyclic graph formed by contracting every strongly connected component of $G$ to a single vertex. If $H$ has multiple sink vertices, then there are multiple stationary distributions: one for each of the corresponding strongly connected components, but we can also take any convex combination of them to get infinitely many. The Perron vector $\boldsymbol\phi$ is not well-defined.

If $H$ has only one sink vertex (corresponding to a strongly connected component $C$ of $G$ with no edges leaving it), then there is a unique stationary distribution $\boldsymbol\phi$. Its support is $C$ only: we have $\boldsymbol\phi(v) = 0$ for $v \notin C$.

This still causes us trouble in the definition of the Laplacian, where $\boldsymbol\phi$ is no longer strictly positive, and we can't use it to normalize the matrix as Chung does. I'm not sure whether there's any way to make an analogous definition that still works when some components of $\boldsymbol\phi$ are $0$. However, even if there is, I expect that the resulting Laplacian would end up forgetting about everything $G$ does outside of $C$, and you would not be able to learn about any of $G$'s other strongly connected components.

Answer 2

Your question is answered Multiplicity of 0 eigenvalue of directed graph Laplacian matrix , I'm just rewriting it there.

A nice reference seems to be https://arxiv.org/pdf/2002.02605.pdf

They use the notion of Reach :

Definition 2.3 :

i) Let $i\in V$. The reachable set $R(i)$ consists of all $j\in V$ such that there exists a path from $i$ to $j$

ii) A reach $R$ is a maximal reachable set

so basically the number of reach is the number of (oriented) trees needed to cover the graph (notice that the number of reaches might not be the number of strongly connected components).

The paper then claim

Theorem 4.6:

Given a digraph $G$. The algebraic and geometric multiplicity of the eigenvalue $0$ of $L$ equals the number of reaches.

The paper does contain a proof (which is actually quite nice) and detailed examples