# 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 $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') = 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 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 (with $λ_1=0$).

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

Here is a relevant post on the undirected case

• How do you define the complement of a directed graph? – G_0_pi_i_e Sep 26 '16 at 3:32
• @G_0_pi_i_e Take the adjacency matrix of a directed graph, then flip all the non diagonal entities (0 to 1, 1 to 0). – Yuanzhao Sep 26 '16 at 4:19
• Here again you are getting $L(G)+L(G^c)=nI-J$. So the result holds. – G_0_pi_i_e Sep 26 '16 at 10:40
• @G_0_pi_i_e This relation alone doesn't imply $λ_j (G^c) + λ_{n+2−j} (G) = n$, we also need the eigenvectors to be orthogonal, which is not true for directed case. – Yuanzhao Sep 26 '16 at 14:54
• The vector of all ones $\mathbb{1}$ is an eigenvector for both $J$ and $L(G)$. So they could share the same set of eigenvectors. – G_0_pi_i_e Sep 27 '16 at 10:41

$L(G^c)=nI-J-L(G).$ Because eigenvectors of $L(G)$ are also eigenvectors of $J$, the eigenvalues of $L(G^c)$ are $0, n-\lambda_n(G), \ldots, n-\lambda_2(G)$.
• please prove eigenvectors of $L(G)$ are also eigenvectors of $J$ for directed graph (asymmetric matrix). – Yuanzhao Sep 27 '16 at 15:15
• Consider $L(G)$. Here each row sum is zero. Hence, $0$ is an eigenvalue of $L(G)$ afforded by $\mathbf{1}$. All other eigenvectors are orthogonal to $\mathbf{1}$. Similarly, in case of $J$, $n$ is an eigenvalue afforded by $\mathbf{1}$. All other eigenvectors of $J$ can be chosen any vector orthogonal to $\mathbf{1}$ which will give $0$ as the eigenvalue of $J$. Hence the result. – G_0_pi_i_e Sep 28 '16 at 7:06