[r-t] Conjugate permutations

[Richard Smith]

I've been writing some code to look at various aspects of 
inter-method falseness and while trying to work out how to 
write efficient code, I stumbled across a interesting result 
that I thought I'd share.

We all know that a permutation can be written as a row, e.g. 
23154.  Another way of writing the same permutation is as a 
product of disjoint cycles, e.g. 231546 = (123)(45)(6). 
Cycle notation does not provide a unique way of writing a 
permutation.  Within a cycle, we can rotate the bells -- 
i.e. (123) = (231) = (312).  We can order the cycles however 
we like -- or expressed more mathematically, disjoint cycles 
commute -- so (123)(45)(6) = (6)(45)(123).  Finally, fixed 
bells are often omitted -- i.e. (1)(234) = (234).

Let's select one of these cycle notations as the canonical 
one by using the following rules.

   0. Do not omit fixed bells, thus on six bells,
   (1)(2453)(6) is preferred to (2453).

   1. Smaller cycles are written to the left of larger ones,
   thus (45)(123) is preferred over (123)(45).

   2. Where two cycles are of the same size, the one with
   the smallest bell is written to the left, thus (14)(23)
   is preferred over (23)(14).

   3. Each cycle is rotated to start with the smallest bell,
   thus we write (24653) instead of, say, (53246).

Next is the interesting bit.  Take the canonical cycle 
notation and concatenate each cycle so that we have 
something that looks like a row.  Thus 231546 = (6)(45)(123) 
=> 645123.  Let's call this mapping r => c(r) -- thus 
c(231546) = 645123.

Bizarrely, this function, c(r), turns out to have some very 
interesting properties.  But first, a few basic and less 
interesting observations.  It maps several rows to the same 
row, for example, c(12345) = c(12354) = c(12453) = 12345. 
Thus given c(a) = c(b) you cannot infer that a = b.  Or put 
more mathematically, c is not injective.  As a consequence 
there are rows that are never mapped to -- e.g. there is no 
r such that c(r) is back-rounds (except in the trivial case 
of one bell).  Thus c is also not surjective.

Now some interesting properties.  Two rows, a and b, are 
conjugate if there exists some row, r, such that

    b = r^-1 a r.

The set of all mututally conjugate rows is called a 
conjugacy class and contains all rows with the same cyclic 
structure.  So for example, on four bells we have the 
following conjugacy classes:

   { 1234 }
   { 1243, 1324, 1432, 2134, 3214, 4231 }
   { 2143, 3412, 4321 }
   { 1342, 1423, 2314, 2431, 3124, 3241, 4132, 4213 }
   { 2341, 2413, 3142, 3421, 4123, 4312 }

These are respectively: rounds, rows with one pair swapping, 
rows with two pairs swapping, rows that rotate three bells, 
and rows that rotate four bells.

It's sometimes useful to label each conjugacy class and one 
common way of doing this is to use the 
lexicographically-smallest elemet of the class as its label. 
For example we can use 2143 as the label for { 2143, 3412, 
4321 }.

So far so good.  But how is this related to c(r)?  Given a 
row, r, the lexicographically-smallest element of its 
conjugacy class is equal to

   c(r)^-1 r c(r).

Of itself this is only marginally useful.  It provides an 
algorithm for finding the conjugacy class label without 
having to enumerate the whole conjugacy class looking for 
the lexicographically-smallest element, but there are plenty 
of other ways of doing that.

However, what is particularly useful is that it provides an 
efficient algorithm for constructing r from a and b when 
solving the equation:

   b = r^-1 a r.

The need to do this turns up all over the place in ringing 
theory and I've never previously had an efficient way of 
solving it.

By definition we know that there is only a solution if a and 
b are in the same conjugacy class.  We can easily determine 
this by testing whether

   c(a)^-1 a c(a) = c(b)^-1 b c(b).

Rearranging this gives

   b = c(b) c(a)^-1 a c(a) c(b)^-1
     = (c(a) c(b)^-1)^-1 a (c(a) c(b)^-1),

which gives the solution:

   r = c(a) c(b)^-1.

RAS