Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

We are interested in the following notions in the case $G=S_N$, the symmetric group on $\{1,\dots,N\}$.

Fix a group $G$ and a number $d$. For $(g_1,\dots,g_d)\in G^d$ and $x\in G$, define $$(g_1,\dots,g_d)^x := (g_1^x,\dots,g_d^x).$$ (Throughout, $g^x:=x^{-1}gx$.) $d$-tuples $g=(g_1,\dots,g_d)$ and $h=(h_1,\dots,h_d)$ in $G^d$ are conjugate if there is $x\in G$ such that (in the above notation) $g^x=h$. The ($d$-dimensional) Simultaneous Conjugacy Problem (SCP) is $G$ is that of deciding whether given $d$-tuples $g,h\in G^d$ are conjugate.

We need an efficient solution of the SCP in the symmetric group $S_N$. (In fact, for our specific use we are more interested in the search version of this problem (given conjugate $g,h\in G^d$, find $x\in G$ such that $g^x=h$), if that matters.)

One very nice way to solve the SCP is to come up with efficiently computable representatives of conjugacy classes. For ordinary (1-dimensional) conjugacy this is trivial: E.g., the representative of the conjugacy class of the permutation $(7, 9, 5, 3)(1, 2, 4)(6,8)\in S_9$ would be $(1,2,3,4)(5,6,7)(8,9)$. For larger dimension $d$, one can define the representative as follows:

Define a linear order on $S_N$ as follows: Given $g$, order its cycles from longest to shortest. Make each cycle begin with its minimal element, and order every set of cycles of equal length by their first element. This results in a sequence of $N$ natural numbers. Compare two permutations by comparing their corresponding sequences, lexicographically.

Given $(g_1,\dots,g_d)\in S_N^d$, bring $g_1$ by conjugation to the above canonical form $\tilde g_1$. Then minimize $g_2$ by conjugation with elements of the centeralizer of $\tilde g_1$ to obtain $\tilde g_2$, then minimize $g_3$ by conjugation with elements of the centeralizer of $\{\tilde g_1,\tilde g_2\}$ to obtain $\tilde g_3$, etc. The canonical representative is $(\tilde g_1,\dots,\tilde g_d)$ (and we can also keep track how to conjugate there).

Question: In the above notation, can we find $(\tilde g_1,\dots,\tilde g_d)$ in polynomial time?

Of course, I would appreciate any efficient solution of the SCP.

Comments:

  1. In each stage, one can take generators of the centralizers, compute the orbits using them, and choose the minimal elements. This is better than conjugating by the whole centralizer, but seems inefficient in the worst case.

  2. This algorithm is needed to speed up an algorithm for the SCP in Artin's braid group $B_N$.

  3. The answers for a related question do not seem to help here.

share|improve this question
1  
I like your canonical form and Brendan's answer below. I just wanted to comment that Burnside's lemma says there are \begin{equation} \frac{1}{|S_N|} \sum_{\alpha \in S_N} |\text{centralizer}(\alpha)|^d = \frac{1}{N!} \sum_{\alpha} \left( \sum_{\chi} \chi^2(\alpha) \right)^d \end{equation} different orbits of $G^d$ under simultaneous conjugation. So you can compute the corresponding count of types rather easily (but it involves the character table). –  Peter Dukes Apr 4 at 20:28
    
Sorry. I just noticed that my comment about the count of orbits is directly addressed (for $d=2$, anyway) in a "Related" MO problem to the left: mathoverflow.net/questions/41337/… –  Peter Dukes Apr 4 at 22:09

1 Answer 1

up vote 9 down vote accepted

I'll only consider the case of $S_N$ to start with.

Given $(g_1,\ldots,g_d)\in S_N^d$, define a directed graph $G$ on vertices $\lbrace 1,\ldots,N\rbrace$ whose edges are coloured with elements of $Z_2^d$. Edge $i{\to}j$ is coloured $(\epsilon_1,\ldots,\epsilon_d)$, where $\epsilon_t=1$ iff $g_t$ maps $i$ onto $j$. You can remove loops and edges of colour 0 if you like.

The isomorphism type of the graph $G$ exactly corresponds to the conjugacy class of $(g_1,\ldots,g_d)$, so you can use graph isomorphism software to find a canonical form together with the conjugacy that produces it. Generators for the centraliser too, if you want it.

This will be possible in practice for very large examples (say $dN$ up to several million), but whether it is competitive with other methods will depend on the size of your typical example. If $N$ is small it will take milliseconds. What typical values of $N$ and $d$ are you interested in?

Instead of $S_N$, any permutation group which is the full automorphism group of some graph (in its action on vertices) can be handled too, by adding that graph as an extra layer. More general permutation groups are harder.

ADDED: Going back to $S_N$, I'll give a polynomial time algorithm, confusingly using both group and graph terminology all mixed up. First, if $\langle g_1,\ldots,g_d \rangle$ is intransitive (the graph is disconnected), canonically label each component separately and list them in lexicographic order. So now assume connectivity.

For each vertex $v$, we can make a unique labelling $\ell(v)$ of the graph by starting at $v$ and scanning the graph in a deterministic way. There are many possibilities; I'll describe a version of breadth-first search. You have a queue (first-in, first-out store) $Q$, initially containing only $v$. Repeatedly do this: remove the vertex at the head of the queue, say $x$, then push into $Q$ (at the tail) those of $x^{g_1},\ldots,x^{g_d}$ (in that order) which have never previously been put into $Q$. Since the graph is strongly connected (being a union of directed cycles), every vertex is put into $Q$ eventually. Stop when that has happened and define $\ell(v)$ to be the order in which vertices were put into $Q$. Relabelling the vertices in the order they are listed in $\ell(v)$ to get a labelled graph $G(v)$. (This corresponds to $(g_1^\gamma,\ldots,g_d^\gamma)$ where $\gamma$ is the permutation mapping the old labels to the new labels.)

Now you have $G(v)$ for each $v$. Choose the lexicographically smallest and that is your canonical labelling of the graph. Each scan takes $O(Nd)$ time and there are $N$ scans, so the total time is $O(N^2d)$.

Several observations will speed it in practice. (1) You can restrict the starting points of scans to vertices minimising some combinatorial invariant (for example the list of cycle lengths of $g_1,\ldots,g_d$ that involve the vertex). This might greatly reduce the typical number of scans. (2) As all scans except the first are being made, compare the graphs as you go. It might allow some scans to stop early. (3) If $G(v)$ and $G(w)$ are identical (not just isomorphic) you have found an element of the centraliser. You can use such elements to avoid some scans by proving their starting vertices are equivalent to those you already used. (4) Even though I talked about the graph, I wouldn't actually construct it but would work directly with lists of permutations.

The graph is actually a deterministic finite automaton (at most one edge of each colour leaves each vertex). There could be faster isomorphism algorithms out there for DFAs, though I'm dubious that anything would work faster in practice than a well-tuned implementation of the method I described.

share|improve this answer
    
Thanks Brendan. But don't you think there should be a (small degree, in $dN$, say) polynomial time algorithm for this problem? Also, unfortunately, this is supposed to be implemented in Magma, so I cannot use any available software. Perhaps your algorithm could be stated succinctly in this specific case. –  Boaz Tsaban Apr 6 at 10:15
    
@Boaz Tsaban: In Magma you can use the graph isomorphism routines already there. But you are right, there is a polynomial time algorithm for $S_N$. I think $O(N^2d)$. I'll add it to my answer later today. –  Brendan McKay Apr 6 at 11:58
    
Looks awesome. Could you explain what is meant by taking the lex-smallest labeled graph? The way I see it, your algorithm returns, for each $v$, a permutation of $1,\dots,N$ that you can move by conjugation to the identity permutation. –  Boaz Tsaban Apr 6 at 20:54
    
@Boaz Tsaban: $G(v)$ is a labelled graph. You can use any total ordering of labelled graphs. But I would make the corresponding conjugate $(g_1^\gamma,\dots,g_d^\gamma)$ and compare such vectors as if they are $d\times n$ matrices compared element by element. –  Brendan McKay Apr 6 at 22:59
    
Update: I have implemented this algorithm and it works. –  Boaz Tsaban Apr 10 at 18:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.