# [r-t] Conjugate permutations

Richard Smith richard at ex-parrot.com
Tue Aug 24 13:40:30 UTC 2010

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

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

```