Are the zero eigenvalues of a Laplacian matrix semi-simple?

Question

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?

Answer 1

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.