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

  • 1
    $\begingroup$ How do you define the complement of a directed graph? $\endgroup$ – G_0_pi_i_e Sep 26 '16 at 3:32
  • $\begingroup$ @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). $\endgroup$ – Yuanzhao Sep 26 '16 at 4:19
  • $\begingroup$ Here again you are getting $L(G)+L(G^c)=nI-J$. So the result holds. $\endgroup$ – G_0_pi_i_e Sep 26 '16 at 10:40
  • $\begingroup$ @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. $\endgroup$ – Yuanzhao Sep 26 '16 at 14:54
  • $\begingroup$ 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. $\endgroup$ – 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)$.

  • $\begingroup$ please prove eigenvectors of $L(G)$ are also eigenvectors of $J$ for directed graph (asymmetric matrix). $\endgroup$ – Yuanzhao Sep 27 '16 at 15:15
  • $\begingroup$ 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. $\endgroup$ – G_0_pi_i_e Sep 28 '16 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.