# 20 Permutations

GAP is a system especially designed for the computations in groups. Permutation groups are a very important class of groups and GAP offers a data type permutation to describe the elements of permutation groups.

Permutations in GAP operate on positive integers. Whenever group elements operate on a domain we call the elements of this domain points. Thus in this chapter we often call positive integers points, if we want to emphasize that a permutation operates on them. An integer i is said to be moved by a permutation p if the image i^p of i under p is not i. The largest integer moved by any permutation may not be larger than 2^{28}-1.

Note that permutations do not belong to a specific group. That means that you can work with permutations without defining a permutation group that contains them. This is just like it is with integers, with which you can compute without caring about the domain `Integers` that contains them. It also means that you can multiply any two permutations.

Permutations are entered and displayed in cycle notation.

```    gap> (1,2,3);
(1,2,3)
gap> (1,2,3) * (2,3,4);
(1,3)(2,4) ```

The first sections in this chapter describe the operations that are available for permutations (see Comparisons of Permutations and Operations for Permutations). The next section describes the function that tests whether an object is a permutation (see IsPerm). The next sections describe the functions that find the largest and smallest point moved by a permutation (see LargestMovedPointPerm and SmallestMovedPointPerm). The next section describes the function that computes the sign of a permutation (see SignPerm). The next section describes the function that computes the smallest permutation that generates the same cyclic subgroup as a given permutation (see SmallestGeneratorPerm). The final sections describe the functions that convert between lists and permutations (see ListPerm, PermList, RestrictedPerm, and MappingPermListList).

Permutations are elements of groups operating on positive integers in a natural way, thus see chapter Groups and chapter Operations for more functions.

The external functions are in the file `LIBNAME/"permutat.g"`.

## 20.1 Comparisons of Permutations

`p1 = p2`
`p1 < p2`

The equality operator `=` evaluates to `true` if the two permutations p1 and p2 are equal, and to `false` otherwise. The inequality operator `<` evaluates to `true` if the two permutations p1 and p2 are not equal, and to `false` otherwise. You can also compare permutations with objects of other types, of course they are never equal.

Two permutations are considered equal if and only if they move the same points and if the images of the moved points are the same under the operation of both permutations.

```    gap> (1,2,3) = (2,3,1);
true
gap> (1,2,3) * (2,3,4) = (1,3)(2,4);
true ```

`p1 < p2`
`p1 <= p2`
`p1 p2`
`p1 = p2`

The operators `<`, `<=`, , and `=` evaluate to `true` if the permutation p1 is less than, less than or equal to, greater than, or greater than or equal to the permutation p2, and to `false` otherwise.

Let p_1 and p_2 be two permutations that are not equal. Then there exists at least one point i such that i^{p_1} <> i^{p_2}. Let k be the smallest such point. Then p_1 is considered smaller than p_2 if and only if k^{p_1} < k^{p_2}. Note that this implies that the identity permutation is the smallest permutation.

You can also compare permutations with objects of other types. Integers, rationals, cyclotomics, unknowns, and finite field elements are smaller than permutations. Everything else is larger.

```    gap> (1,2,3) < (1,3,2);
true    # \$1^{(1,2,3)} = 2 \<\ 3 = 1^{(1,3,2)}\$
gap> (1,3,2,4) < (1,3,4,2);
false    # \$2^{(1,3,2,4)} = 4 > 1 = 2^{(1,3,4,2)}\$ ```

## 20.2 Operations for Permutations

`p1 * p2`

The operator `*` evaluates to the product of the two permutations p1 and p2.

`p1 / p2`

The operator `/` evaluates to the quotient p1 * p2^{-1} of the two permutations p1 and p2.

`LeftQuotient( p1, p2 )`

`LeftQuotient` returns the left quotient p1^{-1} * p2 of the two permutations p1 and p2. (This can also be written `p1 mod p2`.)

`p ^ i`

The operator `^` evaluates to the i-th power of the permutation p.

`p1 ^ p2`

The operator `^` evaluates to the conjugate p2^{-1} * p1 * p2 of the permutation p1 by the permutation p2.

`Comm( p1, p2 )`

`Comm` returns the commutator p1^{-1} * p2^{-1} * p1 * p2 of the two permutations p1 and p2.

`i ^ p`

The operator `^` evaluates to the image i^p of the positive integer i under the permutation p.

`i / p`

The operator `/` evaluates to the preimage i^{p^{-1}} of the integer i under the permutation p.

`list * p`
`p * list`

The operator `*` evaluates to the list of products of the permutations in list with the permutation p. That means that the value is a new list new such that `new[i] = list[i] * p` respectively `new[i] = p * list[i]`.

`list / p`

The operator `/` evaluates to the list of quotients of the permutations in list with the permutation p. That means that the value is a new list new such that `new[i] = list[i] / p`.

For the precedence of the operators see Operations.

## 20.3 IsPerm

`IsPerm( obj )`

`IsPerm` returns `true` if obj, which may be an object of arbitrary type, is a permutation and `false` otherwise. It will signal an error if obj is an unbound variable.

```    gap> IsPerm( (1,2) );
true
gap> IsPerm( 1 );
false ```

## 20.4 LargestMovedPointPerm

`LargestMovedPointPerm( perm )`

`LargestMoverPointPerm` returns the largest point moved by the permutation perm, i.e., the largest positive integer i such that `i^perm < i`. It will signal an error if perm is trivial (see also SmallestMovedPointPerm).

```    gap> LargestMovedPointPerm( (2,3,1) );
3
gap> LargestMovedPointPerm( (1,2)(1000,1001) );
1001 ```

## 20.5 SmallestMovedPointPerm

`SmallestMovedPointPerm( perm )`

`SmallestMovedPointPerm` returns the smallest point moved by the permutation perm, i.e., the smallest positive integer i such that `i^perm < i`. It will signal an error if perm is trivial (see also LargestMovedPointPerm).

```    gap> SmallestMovedPointPerm( (4,7,5) );
4 ```

## 20.6 SignPerm

`SignPerm( perm )`

`SignPerm` returns the sign of the permutation perm.

The sign s of a permutation p is defined by s = prod_{i < j}{(i^p - j^p)} / prod_{i < j}{(i - j)}, where n is the largest point moved by p and i,j range over 1...n.

One can easily show that sign is equivalent to the determinant of the permutation matrix of perm. Thus it is obvious that the function sign is a homomorphism.

```    gap> SignPerm( (1,2,3)(5,6) );
-1 ```

## 20.7 SmallestGeneratorPerm

`SmallestGeneratorPerm( perm )`

`SmallestGeneratorPerm` returns the smallest permutation that generates the same cyclic group as the permutation perm.

```    gap> SmallestGeneratorPerm( (1,4,3,2) );
(1,2,3,4) ```

Note that `SmallestGeneratorPerm` is very efficient, even when perm has huge order.

## 20.8 ListPerm

`ListPerm( perm )`

`ListPerm` returns a list list that contains the images of the positive integers under the permutation perm. That means that ```list[i] = i^perm```, where i lies between 1 and the largest point moved by perm (see LargestMovedPointPerm).

```    gap> ListPerm( (1,2,3,4) );
[ 2, 3, 4, 1 ]
gap> ListPerm( () );
[  ] ```

`PermList` (see PermList) performs the inverse operation.

## 20.9 PermList

`PermList( list )`

`PermList` returns the permutation perm that moves points as describes by the list list. That means that `i^perm = list[i]` if i lies between 1 and the length of list, and `i^perm = i` if i is larger than the length of the list list. It will signal an error if list does not define a permutation, i.e., if list is not a list of integers without holes, or if list contains an integer twice, or if list contains an integer not in the range `[1..Length(list)]`.

```    gap> PermList( [6,2,4,1,5,3] );
(1,6,3,4)
gap> PermList( [] );
() ```

`ListPerm` (see ListPerm) performs the inverse operation.

## 20.10 RestrictedPerm

`RestrictedPerm( perm, list )`

`RestrictedPerm` returns the new permutation new that operates on the points in the list list in the same way as the permutation perm, and that fixes those points that are not in list. list must be a list of positive integers such that for each i in list the image `i^perm` is also in list, i.e., it must be the union of cycles of perm.

```    gap> RestrictedPerm( (1,2,3)(4,5), [4,5] );
(4,5) ```

## 20.11 MappingPermListList

`MappingPermListList( list1, list2 )`

`MappingPermListList` returns a permutation perm such that `list1[i] ^ perm = list2[i]`. perm fixes all points larger then the maximum of the entries in list1 and list2. If there are several such permutations, it is not specified which `MappingPermListList` returns. list1 and list2 must be lists of positive integers of the same length, and neither may contain an element twice.

```    gap> MappingPermListList( [3,4], [6,9] );
(3,6,4,9,8,7,5)
gap> MappingPermListList( [], [] );
() ```

GAP 3.4.4
April 1997