# 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

The blue graph has the big square 2-4-6-8 with little triangles 2-3-4, 4-5,6, 6-7-8, and 8-1-2, and also the little triangle vertices which are opposite relative to the big square are joined, i.e. 1-5 and 3-7.

The red graph has a similar description: there is a big square 1-3-5-7, and triangles 1-6-3, 3-8-5, 5-2-7, and 7-4-2, and also the triangle vertices which are opposite relative to the big square are joined, i.e. 2-6 and 8-4.

This means one can set up an isomorphism by corresponding the vertices as

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

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

-