Suppose $G_1$ and $G_2$ are two finite undirected simple graphs, such, that their adjacency matrices are conjugate over $\mathbb{Z}_2$ (as their only possible entries are always either $0$ or $1$, we can consider those entries to be not from $\mathbb{Z}$, but from $\mathbb{Z}_2$). Is it true, that in this case $G_1 \cong G_2$? We call matrices $A$ and $B$ conjugate over the field $F$ if there exists an invertible matrix $C$ with entries from $F$, such that $A = C^{-1}BC$.

Personally, I do not believe, that it is true, but I failed to find the counterexample manually: for $1$ vertice, $2$ vertices and $3$ vertices, the statement is true, for four vertices there is already too many possible graphs for exhaustive manual search of a counterexample...

  • $\begingroup$ What is your definition of "conjugate in $\mathbb{Z}_2$ ? I usually work with transpose conjugate of matrices only when working in Complex field, which make no sense here as $A^*=A$ $\endgroup$ – Thomas Lesgourgues May 3 at 8:46
  • 2
    $\begingroup$ If your definitioh of conjugate is . $A_{G_1} = PA_{G_2}P^{-1}$? Then have a look to math.stackexchange.com/questions/480961/…. It gives an example of two non-isomorphic graphs whose matrices are conjugate $\endgroup$ – thibo May 3 at 9:09
  • 1
    $\begingroup$ I think the example of the link is not correct. However you can check the graphs p14 of win.tue.nl/~aeb/2WF02/spectra.pdf, if I haven't fail to copy the adjacency matrices to wolfram, then the two graph have conjugate adjacency matrices and are not isomorphic. $\endgroup$ – thibo May 3 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.