Strongly connected graph and the eigenvalues of the laplacian matrix

Question

Given a directed graph $G$, consider that $G$ is strongly connected iff every vertex $i$ in $G$ has inner degree $k_i\geq 1$. Reformulation of this definition: $G$ is strongly connected iff for any two vertices $i,j$ in $G$ there is at least one directed path from $i$ to $j$ and from $j$ to $i$.

The laplacian matrix $L =[l_{ij}]$ $i,j=1,\cdots,n$ is such that $l_{ij}=-1$ if there is a link from $j$ to $i$; $l_{ij} = k_i$ if $j=i$ and $l_{ij}=0$ otherwise.

The conjecture is: Given a directed graph $G$, the eigenvalues of the laplacian matrix $L$ of $G$ are all simple iff $G$ is strongly connected.

Do you know if this "conjecture" is already a well-known result? Any suggestions of references where I can find the proof of this result? In the case its not valid, do you know a counter-example?

Answer 1

I think your conjecture does not fly. Indeed, consider a "Paley tournament": let $p=4k-1$ e a prime, and define a digraph with the set of vertices 0,1,..,$p-1$, so that $i$ is connected to $j$ whenever $i-j$ is a non-0 square modulo $p$. It has in-degree (and out-degree) $(p-1)/2$ for any vertex. Such a digraph has only 3 distinct eigenvalues, and thus it will only have 3 distinct laplacian eigenvalues.

(In particular, this construction gives a counterexample on 7 vertices).

   [ 3 -1 -1  0 -1  0  0]
   [ 0  3 -1 -1  0 -1  0]
   [ 0  0  3 -1 -1  0 -1]
   [-1  0  0  3 -1 -1  0]
   [ 0 -1  0  0  3 -1 -1]
   [-1  0 -1  0  0  3 -1]
   [-1 -1  0 -1  0  0  3]
   sage: mm.characteristic_polynomial().factor()
   x * (x^2 - 7*x + 14)^3