> < ^ Date: Fri, 11 Feb 1994 15:12:00 +0100
> < ^ From: Martin Schoenert <martin.schoenert@math.rwth-aachen.de >
> < ^ Subject: Re: on permutation group "transversals".
```Paul Igodt asks in his e-mail message of 1994/02/07
```

When one looks at the output of 'gp.stabilizer'.
If 'gp' is a well defined permutation group,
than one finds a record containing many "transversals".
How should these transversals be understood?
E.g. they contain often many "extra comma's".

The entries 'gp.orbit' and 'gp.transversal' belong together.
The point 'gp.orbit' is called the basepoint 'bpt'.

For each 'i' in 'gp.orbit' there is an entry 'gp.transversal[i]'.
This is the reason why there can be ``extra commas'' in 'gp.transversal'.
E.g., if 'gp.orbit' is '[1,3,5,7]', then only the entries at positions
1, 3, 5, and 7 have assigned values in 'gp.transversal'.

The entry 'gp.transversal[i]' is a permutation 'p' that takes 'i' to a
point earlier in the orbit, i.e.,
'Position( gp.orbit, i ) > Position( gp.orbit, i^p )'.
Actually this is only true if 'i' is not 'bpt',
'gp.transversal[bpt]' is always the identity '()'.

So for example assume that 'gp.orbit' is '[ 3, 7, 5, 4, 8, 6 ]' and
'gp.transversal' is '[,,(),(3,4,5),(3,5,7),(6,8),(3,5,7),(5,8,7)]'.
'gp.transversal' and 'gp.transversal' are unbound because 1 and 2
are not in 'gp.orbit'. We can picture the structure represented by
'gp.orbit' and 'gp.transversal' as follows.

```              (3,5,7)     (3,4,5)
.--<---- 5 ----<---- 4
(3,5,7)   /
3 ----<---- 7
\
`--<---- 8 ----<---- 6
(5,8,7)      (6,8)
```

To compute a representative for a point 'i' we start with that point and
follow the path to the basepoint 'bpt' multiplying the permutations along
the edges as we go along. The result is a permuation mapping 'i' to
'bpt', so to get a representative we have to invert this.

```For example, suppose we start with the point '6'.  Then we multiply the
permutations along the edges '(6,8) * (5,8,7) * (3,5,7) = (3,5,8,6)'.
To get a representative we invert this '(3,6,8,5)'.
```

In GAP code this looks as follows

```# we want to compute a representative for 'i'
r := ();
while i <> gp.orbit  do
i := i ^ gp.transversal[i];
r := r * gp.transversal[i];
od;
r := r^-1;
```

One can avoid the extra inversion as follows

```# we want to compute a representative for 'i'
r := ();
while i <> gp.orbit  do
i := i ^ gp.transversal[i];
r := LeftQuotient( gp.transversal[i], r );
od;
```

Note that 'LeftQuotient(<x>,<y>)' means '<x>^-1 * <y>', is sometimes
written as '<x> mod <y>', and is for permutations just as fast as an
ordinary multiplication.

Martin.

```-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany
```

> < [top]