2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, Gjergji! Just a minor here, should the row in your answer be column instead? Since it is the sum of each row in the Laplacian matrix that are zero, but not column sums. $\endgroup$ – Yuanzhao Oct 7 '16 at 20:25
  • $\begingroup$ @Yuanzhao, You're right, I guess that's a matter of which convention you chose. $\endgroup$ – Gjergji Zaimi Oct 7 '16 at 23:18

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.