6
$\begingroup$

I read a lemma.

$J$ is the all ones $n \times n$ matrix, $I_n$ is the $n \times n$ identity matrix. Let the adjacency matrix of a simple graph $G$ on $n$ vertices be $A = A(G)$. Then the adjacency matrix of its complement is $\bar A = A \bar{(G)} = J - I - A$.

From a previous posting, I know that $\bar A=J-I-A$. Can anyone help me understand how? The linked question has no comments regarding this.

$\endgroup$
1
  • $\begingroup$ Think about what needs to happen to $A(G)$. All the 1's need to become 0's all the zeros (except those on the diagonal) need to become 1's. $\endgroup$
    – TravisJ
    Commented May 25, 2016 at 14:21

1 Answer 1

Reset to default
5
$\begingroup$

You want to prove that if the adjacency matrix of the graph $G$ is $A$, then the adjacency matrix $\overline{A}$ of the complement graph $\overline{G}$ is $J-I-A$. Observe that vertices $i$ and $j$ are adjacent in $G$ iff vertices $i$ and $j$ are nonadjacent in $\overline{G}$. Hence, the edge set of $G$ and of $\overline{G}$ together form the edge set of the complete graph $K_n$. Observe that the adjacency matrix of the complete graph is $J-I$. Hence, $A + \overline{A} = J-I$. So, $\overline{A} = J-I-A$.

$\endgroup$

You must log in to answer this question.

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