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


1. Is there any relation between the eigenvalues of $A + \widetilde A$ and the eigenvalues of $A$ and $\widetilde A$?
2. Also, do $A$ and $\widetilde A$ have the same set of eigenvectors?


Thank you.



Eigenvalues of the complement of a graph
**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.


1. 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.


2. 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.


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


