# Laplacian spectrum of directed network (digraph) and its complement

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?

• Duplicate of math.stackexchange.com/questions/1939688/… Oct 3 '16 at 21:48
• @IgorRivin I couldn't get a satisfactory answer there, and don't have enough reputation to migrate the question here. Oct 3 '16 at 21:54

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.