(Disclaimer: I am new here, so be patient with my mistakes, but I welcome corrections, advice or comments.)
I am interested in if anyone knows of ways of characterizing the orbits of an adjacency matrix of a multi-graph when it is conjugated by a permutation matrix. To clarify: The matrices in question are symmetric, with zero diagonal (sometimes called hollow symmetric), and all entries non-negative integers.
Conjugation by a permutation matrix will give another adjacency matrix with all the same properties. From a certain perspective this can be visualized as re-drawing the graph that gave rise to the adjacency matrix (in a manner that is isomorphic in the graph-theory sense).
I want to know if, given two adjacency matrices with the same dimensions, is it possible to determine if they lie in the same orbit (without re-constructing the necessary permutation matrices). However, I am interested in any results that are related to this question, since I believe the answer is not known (correct me if I am wrong here).