# Given two adjacency matrices, how can I find if they're isomorphic?

Matrix 1: \begin{matrix} 0&1&1&0\\ 1&0&1&0\\ 1&1&0&1\\ 0&0&1&0 \end{matrix}

Matrix 2: \begin{matrix} 0&1&1&1\\ 1&0&0&0\\ 1&0&0&1\\ 1&0&1&0 \end{matrix}

I've looked on google to find out how to do this, but I can't find an answer that makes sense to me. As far as I can tell, there is no efficient algorithm to do this, so you need to check all the permutations... but I don't even know how to start. Any help would be great, Thanks.

-
Draw the graphs... –  draks ... Nov 28 '12 at 14:40

As isomorphims have to preserve degree, there are only 2 possible ones, the first given by $$\phi_1 \colon 1\mapsto 3, 2 \mapsto 4, 3 \mapsto 1, 4 \mapsto 2$$ and $$\phi_2 \colon 1\mapsto 4, 2 \mapsto 3, 3 \mapsto 1, 4 \mapsto 2$$ $\phi_1$ maps the first matrix to (that means the following matrix has $a_{\phi_1^{-1}(i), \phi_1^{-1}(j)}$ as $(i,j)$-th entry. $$\begin{pmatrix} 0&1&1&1\\ 1&0&0&0\\ 1&0&0&1\\ 1&0&1&0 \end{pmatrix}$$ and so $\phi_1$ is an isomorphism.