11
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ $A+\tilde A$ is the adjacency matrix of the complete graph regardless of what $G$ is. On your second question, "yes" if $G$ is regular, otherwise "not usually". $\endgroup$
    – Brendan McKay
    Commented Aug 14, 2020 at 7:48
  • $\begingroup$ @BrendanMcKay If $G$ is regular, how to show they have the same set of eigenvectors? Thank you. $\endgroup$
    – GA316
    Commented Aug 14, 2020 at 9:46
  • $\begingroup$ I edited my answer. In particular, I give a complete answer for regular graphs. $\endgroup$
    – Denis Serre
    Commented Aug 14, 2020 at 11:44
  • $\begingroup$ @DenisSerre Thank you. $\endgroup$
    – GA316
    Commented Aug 14, 2020 at 12:09

1 Answer 1

Reset to default
15
$\begingroup$

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.

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

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

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ @vidyarthi. This is a matter of convention. The question should mention whether loops about a vertex are allowed, or not. $\endgroup$
    – Denis Serre
    Commented Aug 14, 2020 at 8:13
  • 2
    $\begingroup$ The orthogonality trick with $\mathbf{1}\mathbf{1}^t - A = \widetilde{A}$ and so $-Av = \widetilde{A}v$ if $\mathbf{1}^t v$ is really nice! (And perhaps even a counterexample to many answers, including mine, on a recent popular question about the virtues of writing $\langle u,v \rangle$ rather than $u^t v$ for inner products.) $\endgroup$
    – Mark Wildon
    Commented Aug 14, 2020 at 14:22
  • 1
    $\begingroup$ I don't see how you get that for regular graphs, the eigenvectots of $A$ remain eigenvectors of $\tilde A$. Yes, $\vec1$ remains an eigenvector, and eigenvectors perpendicular to $\vec1$ as well, and in particular, there is an orthogonal basis of common eigenvectors. However, assume that the graph is disconnected, hence the eigenspace of $d$ has dimension $\ge2$. Then some vectors from this space (namely $\vec1$) will be eigenvectors of $\tilde A$ of value $n-d-1$, and some (those perpendicular to $\vec1$) will be eigenvectors of value $-d-1$. But there are also vectors neither parallel ... $\endgroup$
    – Emil Jeřábek
    Commented Aug 15, 2020 at 7:56
  • 2
    $\begingroup$ In fact, eigenvectors of $A$ remain eigenvectors of $\tilde A$ if and only if $G$ is regular and connected (hence $A$ and $\tilde A$ havce the same eigenvectors iff $G$ is a regular connected graph with connected complement). To see this, if $Av=\lambda v$, then $\tilde Av=(\vec 1^Tv)\vec1-\lambda v$ by your argument, which shows that all eigenvectors remain eigenvectors iff all eigenvectors of $A$ are parallel or orthogonal to $\vec1$. Since eigenvectors of a symmetric matrix span the whole space, they can’t all be orthogonal to $\vec1$, hence $\vec1$ is an eigenvector, ... $\endgroup$
    – Emil Jeřábek
    Commented Aug 15, 2020 at 9:52
  • 2
    $\begingroup$ ... i.e., $G$ is regular of some degree $d$. Then, as I already pointed out, the condition also implies that the eigenvalue $d$ must have multiplicity $1$, thus $G$ is connected. Conversely, if $G$ is regular and connected, then the eigenspace of eigenvalue $d$ consists of multiples of $\vec1$, and other eigenspaces are orthogonal to it. $\endgroup$
    – Emil Jeřábek
    Commented Aug 15, 2020 at 9:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .