> < ^ 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[1]' 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[1]' and 'gp.transversal[2]' 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[1]  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[1]  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]