> < ^ Date: Thu, 09 Apr 1998 09:24:04 +0200 (MET DST)
> ^ From: Markus Pueschel <pueschel@earthlink.net >
< ^ Subject: Re: Factors of a permutation cycle

Dear forum,

Javaid Aslam asked:

I am trying to see if somebody has a routine for
factoring a given permutation cycle into a product of the
the transpositions (cycles of length 2);
e.g., the cycle (1,2,3,4) factors into (3,4)*(2,3)*(1,2).

a routine for this question was given by Burkhard.

Here is a function which decomposes a given permutation into
a product of two involutions (perms of order 2):

#F InvolutionFactors( perm )
#F returns a pair [x, y] of permutations such that
#F x*y = perm and x^2 = y^2 = (). The involutions
#F x and y move at most the points moved by perm.

InvolutionFactors := function ( perm )
local x, y, c, n, i;

if not IsPerm(perm) then
  Error("<perm> must be a permutation");
if OrderPerm(perm) <= 2 then
  return [ perm, () ];
  x := ();
  y := ();
  for c in Cycles(perm, [1..LargestMovedPointPerm(perm)]) do
    n := Length(c);
    for i in [1..QuoInt(n-1, 2)] do
      x := x * (c[i], c[n-i]);
    for i in [1..QuoInt(n, 2)] do
      y := y * (c[i], c[n+1-i]);
  return [x, y];

Maybe this is interesting for you too

Markus Pueschel,
Sebastian Egner

> < [top]