20 Permutations

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

Permutations in GAP3 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 ip of i under p is not i. The largest integer moved by any permutation may not be larger than 228-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".

Subsections

  1. Comparisons of Permutations
  2. Operations for Permutations
  3. IsPerm
  4. LargestMovedPointPerm
  5. SmallestMovedPointPerm
  6. SignPerm
  7. SmallestGeneratorPerm
  8. ListPerm
  9. PermList
  10. RestrictedPerm
  11. MappingPermListList

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 p1 and p2 be two permutations that are not equal. Then there exists at least one point i such that ip1 <> ip2. Let k be the smallest such point. Then p1 is considered smaller than p2 if and only if kp1 < kp2. 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 ip of the positive integer i under the permutation p.

i / p

The operator / evaluates to the preimage ip-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 = ∏i < j(ip - jp) / ∏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( [], [] );
    () 

Previous Up Next
Index

gap3-jm
23 Nov 2017