I'm trying to tackle a question from a homework assignment and one of the problems concerns the relation between eigenvalues of a graph's laplacian and its complement's laplacian. The relation is:
$$λ_j (G') = n − λ_{n+2−j} (G)\;,$$
or more comfortably:
$$λ_j (G') + λ_{n+2−j} (G) = n\;,$$
where $G'$ is the graph's complement and $n$ is the number of vertices. Does anybody have any words of wisdom for me concerning this particular relation?
Asked differently, I would like to ask for advice concerning the relation between a laplacian of a graph to the laplacian of its complement. I know, and can easily prove that the following relation holds:
$$L(G) + L(G') = nI - J\;,$$
where $J$ is the matrix of ones; however, I fail to use that to prove the earlier.
I would appreciate any guidance in the matter. Thank you
Update: Let's say we take the equation: $L(G)+L(G')=nI-J$. First of all, I notice that $nI-J$ is also the laplacian of $K_n$ (meaning $G$ completed to all edges), therefore its eigenvalues are $0$ and $(n-1)$ eigenvalues of $n$ (I believe this is what you were saying before). If I multiply both sides by the matrix of $L(G)$'s eigenvectors, $L(G)$ goes to the eigenvalues matrix of $G$ and $L(G')$ goes to its eigenvalue matrix, only I notice said reversing occurs, which allows the relation which started the question. Could you possibly afford an explanation as to why the reversing occurs?
The matrix $J$ has one eigenvalue $n$, with the corresponding eigenspace $E_n$ formed by the vectors with all entries equal, and $n-1$ eigenvalues $0$, with the corresponding eigenspace $E_0$ formed by all vectors that sum to $0$. A Laplacian matrix has eigenvalue $0$ for $E_n$, and since it's symmetric, its eigenspaces are orthogonal, so the remaining eigenspaces together form $E_0$. Knowing this, you can use the relation $L(G)+L(G')=nI-J$ to show that the eigenvectors of $L(G)$ are also eigenvectors of $L(G')$ and vice versa, and to express their eigenvalues in terms of each other. Since a Laplacian matrix is positive-semidefinite, the $0$ eigenvalue is the least eigenvalue, corresponding to $j=1$, and the order of the remaining eigenvalues is reversed; that explains the change in indexing from $j$ running from $2$ to $n$ to $n+2-j$ running from $n$ to $2$.