Laplacian spectrum of directed network (digraph) and its complement

572 Views Asked by At

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

There are 1 best solutions below

2
On

$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)$.