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...
• 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$ – Thomas Lesgourgues May 3 at 8:46
• 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 – thibo May 3 at 9:09