# Orbits of adjacency matrices under conjugation by permutation matrices.

(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).

• I believe you asking for a (full) solution to the weighted graph isomorphism problem. Practically, I have found nauty to be very good at unweighted graph isomorphism. I have used GAP (to refine nauty's answers) when the unweighted algorithm in nauty was not sufficient. Apr 11, 2012 at 15:18
• Possible? Yes. Write down all the permutations of each adjacency matrix and then check whether any two of them are the same. However, it's a big open question whether this can be done efficiently; your problem contains graph isomorphism (en.wikipedia.org/wiki/Graph_isomorphism_problem) as a subproblem and graph isomorphism isn't known to be in P. Apr 11, 2012 at 15:54
• @Qiaochu Yuan - I did specifically state "without reconstructing the necessary permutation matrices," however, the reference to the wikipedia topic is welcome. I feel kind dumb for not noticing that connection... Apr 11, 2012 at 16:10
• @ Jack Schmidt - Though I didn't realize it at the time, that is what I was looking for. I knew a lot of research had been done in the area, but I just didn't know how to find it. (There are numerous ways to characterize the problem, it has implications for the reconstruction problem, Hamiltonian circuits, arbitrary subgraphs, and probably many more. Thanks for the practical workaround. Apr 11, 2012 at 16:15

$$P^T \sigma[(W^i_KX)^T(W^i_QX)] P.$$