Eigenvalues of the complement of a graph Let $A$ and $\widetilde A$ be the adjacency matrices of a graph $G$ and of its complement, respectively.

*

*Is there any relation between the eigenvalues of $A + \widetilde A$ and the eigenvalues of $A$ and $\widetilde A$?


*Also, do $A$ and $\widetilde A$ have the same set of eigenvectors?
Thank you.
 A: Edit (bis). There are two answers, depending on whether loops about vertices are allowed or not. In addition, the case of regular graphs is completely described.

*

*If loops are allowed

The relation between matrices is
$$A+{\widetilde A}=J$$
where $J={\bf1}{\bf1}^T$ is the all-ones matrix. The first consequence is that the sum of the eigenvalues of $A$ and ${\widetilde A}$ equals $|V|$ where $V$ is the set of vertices.
A second consequence concerns multiple eigenvalues. If $\lambda$ is an eigenvalue of $A$, of multiplicity $m\ge2$, then $-\lambda$ is an eigenvalue of ${\widetilde A}$, of multiplicity larger than or equal to $m-1$. Just consider the intersection of the eigenspace with the hyperplane ${\bf1}^\bot$. In particular, this is a case where $A$ and ${\widetilde A}$ share common eigenvectors.


*If loops are not allowed

Here
$$A+{\widetilde A}=K:=J-I_V$$
The sum of the eigenvalues of $A$ is the opposite of that of ${\widetilde A}$.
If $\lambda$ is an eigenvalue of $A$, of multiplicity $m\ge2$, then $-1-\lambda$ is an eigenvalue of ${\widetilde A}$, of multiplicity larger than or equal to $m-1$. Again, this is a case where $A$ and ${\widetilde A}$ share common eigenvectors.


*Regular graphs

If a graph is regular and connected (thanks to Emil for having pinned the point), then $\bf1$ is an eigenvector, with eigenvalue $d$, the degree of each vertex. It is a simple eigenvalue because $A$ is irreducible (connectedness). The other eigenspaces are contained in $\bf1^\bot$, because $A$ is symmetric. Thus eigenvectors of $A$ remain eigenvectors for $\widetilde A$, with the same multiplicity. The correspondance between eigenvalues is $\lambda\rightarrow-1-\lambda$.
Remark also that $d$ is the Perron eigenvalue of $A$, $n-1-d$ being that of $\widetilde A$. We thus deduce
$$\lambda\in D(0;d)\cap D(-1;n-1-d)$$
for all the other eigenvalues of $A$.
