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?
Are the zero eigenvalues of a Laplacian matrix semi-simple
eigenvalues-eigenvectorsgraph theorygraph-laplacianlinear algebramatrices
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$.
For (a), yes, the matrices in (2) and (3) are positive definite (assuming $G$ was connected). They are easily seen to be PSD as any principal submatrix of a PSD matrix is also PSD; however, the matrix-tree theorem you cite implies the determinant submatrix in (2) is a positive integer as any connected graph has at least one spanning tree, so the matrix is PSD and nonsingular, therefore positive definite. This implies that the matrices in (3) are also positive definite by applying Cauchy's interlacing theorem. Of course, symmetry alone here implies diagonalizability.
The matrix in (4) is not positive semi-definite in the traditional sense as it is not symmetric, but nonethless is diagonalizable and has nonnegative eigenvalues (see (c)).
For (b), the algebraic multiplicity of the zero eigenvalue of $\Delta^{-1}\mathbf{L}$ is the same as the algebraic multiplicity of the zero eigenvalue of $\mathbf{L}$ (because assuming $G$ has no isolated vertices, $\Delta^{-1}$ is full-rank), which is equal to the number of connected components.
For (c), again, assuming no isolated vertices, then $\Delta^{-1}\mathbf{L}$ is similar to $\Delta^{-1/2}\mathbf{L}\Delta^{-1/2}$, which is easily seen to be PSD by inspecting the quadratic form and applying a change of variables. Thus, $\Delta^{-1}\mathbf{L}$ is similar to a diagonalizable matrix with nonnegative eigenvalues, so the same holds.
For (d), see the above answers.
Best Answer
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.