# Proving that a graph is self complementary

I've been given the following adjacency matrix:

$$\left(\begin{array}{cccccccc} 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ \end{array}\right)$$

and I need to prove that it is a self complementary graph. All this must be done by hand so I found the complementary graph but I don't know how to continue.

Do I need to solve

$$Ax=b$$

or

$$x^{t}Ax=b$$

is $x$ a matrix defined by 8 columns and 8 rows?

-
you want $x$ to be a permutation matrix, and that $x^T A x = J-I-A$. THe LHS is the isomorphism under permutation, and the RHS is the complement of $A$, where $J$ is the all 1's matrix, and $I$ is the identity matrix (since there are no self loops). – Calvin Lin Jun 21 '13 at 15:35
x is then a matrix with 8 columns and 8 rows? – Cristian Eduardo Lehuede Lyon Jun 21 '13 at 17:54

Blue: $[1,2,3,4,5,6,7,8],$
Red: $[4,1,6,3,8,5,2,7].$