There is a well-known relation between the spectrum of graph laplacian and its complement's laplacian, namely


$$λ\_j (G^c) + λ\_{n+2−j} (G) = n\;,$$


where the eigenvalues $λ\_j$ are sorted in increasing order ($λ\_1$ is always 0), $G^c$ is the graph's complement, and $n$ is the number of vertices. This can be easily proved by making use of the fact that the eigenvectors of symmetric matrices are orthogonal and the following relation


$$L(G) + L(G^c) = nI - J\;,$$


where $J$ is the matrix of ones.


This argument breaks down when we consider directed networks (digraphs), whose edges become directed and the laplacian matrix is no longer symmetric. Yet I found numerically that the relation $λ\_j (G^c) + λ\_{n+2−j} (G) = n$ still holds for digraphs, when we sort the eigenvalues according to their real part.


Is anyone aware of a proof or counterexample of the above claim?



Laplacian spectrum of directed network (digraph) and its complement
This is true even if you allow your digraph to have edges with arbitrary weight. Let's denote the characteristic polynomial of a weighted digraph, $G$, by $P\_{G}(\lambda)=\det\left(\lambda I-L(G)\right)$. The complement $G'$ has characteristic polynomial 
$$P\_{G'}(\lambda)=\det\left(\lambda I-L(G')\right)=(-1)^n\det\left((n-\lambda)I-(J+L(G))\right).$$
If we substitute the first row of the matrix $(n-\lambda)I-(J+L(G))$ by the sum of all rows, we get a first row with entries all equal to $-\lambda$, and the determinant is unchanged. Next, if we add $1$ to every entry not in the first row this also doesn't change the determinant (the all 1's vector is a multiple of the new first row). Denote this resulting matrix by $A\_1$


Next, we can compare this to the matrix $(n-\lambda)I-L(G)$. If we substitute the first row for the sum of all rows we don't change the determinant. The resulting matrix $A\_2$ has all entries in the first row equal to $n-\lambda$ and the rest of them identical to $A\_1$. Therefore 
$$(n-\lambda)\det A\_1=(-\lambda)\det A\_2$$
which tells us
$$(-1)^n (n-\lambda)P\_{G'}(\lambda)=(-\lambda)P\_{G}(n-\lambda).$$
By comparing the roots of both sides we obtain the desired relation between the roots.


