Is weak connectivity sufficient for $0$ to be a simple eigenvalue of the weighted Laplacian?

75 Views Asked by At

$L$ is the weighted Laplacian of a weakly connected directed graph $G$,$$L=D-A$$ with the $L_{ij} \leq 0$ when $i \neq j$, $L_{ii} \geq 0$ and $\sum_{i=1}^{n}L_{ij}=0$.

My question is: Is $0$ a simple eigenvalue of $L$ ?

1

There are 1 best solutions below

0
On BEST ANSWER

Counterexample 1:

$$\begin{bmatrix} 2 & -1 & -1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$$

which is to say $A \leftarrow B \rightarrow C$.

Counterexample 2:

In a previous version, you imposed a requirement that $D$ has a kernel with dimension at most $1$. You can make it zero, in fact, by doing this:

$$\begin{bmatrix} 2 & -1 & -1 & 0 & 0 \\ 0 & 1 & 0 & -1 & 0 \\ 0 & 0 & 1 & 0 & -1 \\ 0 & -1 & 0 & 1 & 0 \\ 0 & 0 & -1 & 0 & 1 \end{bmatrix}.$$

This is two cycles plus a single vertex that enters both cycles. Now there are two eigenvectors with eigenvalue zero (as can be seen by the fact that rows 2 and 4 are multiples of each other and rows 3 and 5 are as well).