Are the zero eigenvalues of a Laplacian matrix semi-simple? It is known that the Laplacian matrix $\mathcal{L}$ for a directed weighted graph has at least one zero eigenvalue. If it has more than one zero eigenvalue, will there be non-trivial Jordan blocks associating with the zero eigenvalues?
 A: The zero eigenvalues must be semi-simple. For convenience, let us write $A$ for $\mathcal L$. My convention here is that $a_{ij}<0$ if there is a directed arc connecting node $i$ to node $j$. We shall prove that the zero eigenvalues of $A$ are semi-simple by mathematical induction on the size $n$ of $A$. The base case $n=2$ is easy and its proof is omitted.
In the inductive step, suppose for some $n>2$ there is a graph Laplacian matrix $A\in M_n(\mathbb R)$ with a zero eigenvalue that is not semi-simple. Then there exists an eigenvector $v\in\mathbb C^n$ and also a generalised eigenvector $u\in\mathbb C^n$ such that $Au=v$ and $Av=0$. By scaling $u$ and $v$ if necessary, we may assume that $|v_j|\le1$ for all $j$.
We first observe that being graph Laplacian, $A$ has the property described in the lemma below:
Lemma. Suppose $a_{ii}>0$ and $v_i=1$. If $a_{ij}<0$ for some $j\ne i$, i.e. if there is an arc joining node $i$ to node $j$, we must have $v_j=1$.
For, if $S=\{j: a_{ij}<0\}$, then from $\sum_{j=1}^na_{ij}=0$ and $Av=0$, we get
$$
-\sum_{j\in S}a_{ij}=a_{ii}=-\sum_{j\in S}a_{ij}v_j\tag{1}
$$
and hence
$$
a_{ii}=\left|\sum_{j\in S}a_{ij}v_j\right|
\overset{(2)}{\le}\sum_{j\in S}|a_{ij}||v_j|
\overset{(3)}{\le}\sum_{j\in S}|a_{ij}|=-\sum_{j\in S}a_{ij}=a_{ii}.
$$
Therefore, equalities must hold in the above. Since $|v_j|\le1$ for all $j$, the equality in $(3)$ implies that $|v_j|=1$ for all $j\in S$. In turn, the equality in $(2)$ implies that $v_j$ is constant over $S$. But then $(1)$ implies that $v_j=1$ for all $j\in S$ and our lemma is proved. $\square$
We may now make use of the lemma. By assumption, $|v_j|\le1$ for all $j$. By scaling $u$ and $v$ (by a complex scalar) if necessary, we may assume in addition that $v_i=1$ for some $i$. Since $Au=v$, the $i$-th row of $A$ cannot be zero. Hence $a_{ii}>0$ and the premises of the lemma are satisfied. By applying the above lemma recursively, we see that for every node $j$ that is reachable from node $i$ by a directed path, we must have $v_j=1$. In other words, if we put
$$
\mathcal I=\{i\}\cup\{j:\text{ node } j \text{ is reachable by a directed path from node } i\}
$$
and let $\mathcal J$ be its complement, then
$$
\pmatrix{
A[\mathcal I,\mathcal I]&A[\mathcal I,\mathcal J]\\
A[\mathcal J,\mathcal I]&A[\mathcal J,\mathcal J]}
=\pmatrix{A[\mathcal I,\mathcal I]&0\\ \ast&\ast}
\text{ and } \pmatrix{v[\mathcal I]\\ v[\mathcal J]}=\pmatrix{e\\ \ast},
$$
where $e$ is an all-one vector. It follows that $A[\mathcal I,\mathcal I]$ is graph Laplacian,
$$
A[\mathcal I,\mathcal I]e=0\ \text{ and }\ A[\mathcal I,\mathcal I]u[\mathcal I]=e,
$$
meaning that $0$ is a non-semi-simple eigenvalue of $A[\mathcal I,\mathcal I]$. Therefore, we must have $|\mathcal I|=n$, or else this will contradict the induction assumption.
Thus all nodes other than $i$ are reachable from node $i$ and $v$ is the all-one vector. As $Au=v$, $A$ cannot possess any zero row. Therefore $A$ has a positive diagonal, and by relabelling the nodes of the graph, we may assume that $A$ is a block upper triangular matrix whose diagonal sub-blocks are irreducible. We now look at the last diagonal sub-block. Let us call it $\widehat{A}$ and let it be $m\times m$. Since $Av=0,\,Au=v$, $v$ is the all-one vector and $A$ is block upper triangular, we see that $\widehat{A}$ is graph Laplacian, $\widehat{A}\widehat{e}=0$ and $\widehat{A}\widehat{u}=\widehat{e}$, where $\widehat{e}$ is the all-one vector in $\mathbb R^m$ and $\widehat{u}$ is the sub-vector taken from the last $m$ entries of $u$.
Thus $\widehat{e}$ is a positive eigenvector corresponding to a non-semi-simple zero eigenvalue of $\widehat{A}$. In turn, it is a positive eigenvector corresponding to a non-semi-simple eigenvalue $c$ of the matrix $P=cI_m-\widehat{A}$. But this is impossible, because $P$ is irreducible and nonnegative when $c>0$ is sufficiently large, and by Perron-Frobenius theorem, the only eigenvalue of a nonnegative matrix $P$ that can possibly have a positive eigenvector is $\rho(P)$ and $\rho(P)$ must be simple when $P$ is irreducible.
Therefore, at the beginning, the zero eigenvalues of $A$ must be semi-simple.
