[Top] [Up] [Previous] [Next] [Index]

52 Transformations

This chapter describes functions for transformations.

A transformation in GAP is an endomorphism of a set of integers of the form {1,..., n}. Transformations are taken to act on the right, which defines the composition i(ab) = (ia)b for i in {1, ..., n}.

For a transformation a on the set {1, ¼, n}, we define its degree to be n, its image list to be the list, [1a, ¼, na], its image to be the image list considered as a set, and its rank to be the size of the image. We also define the kernel of a to be the equivalence relation containing the pair (i, j) if and only if ia = ja.

Note that unlike permutations, we do not consider unspecified points to be fixed by a transformation. Therefore multiplication is only defined on two transformations of the same degree.

  • IsTransformation( obj ) C
  • IsTransformationCollection( obj ) C

    We declare it as IsMultiplicativeElementWithOne since the identity automorphism of {1,¼,n} is a multiplicative two sided identity for any transformation on the same set.

  • TransformationFamily( n ) F
  • TransformationType( n ) F
  • TransformationData( n ) F

    For each n > 0 there is a single family and type of transformations on n points. To speed things up, we store these in a database of types. The three functions above a then access functions. If the nth entry isn't yet created, they trigger creation as well.

    For n > 0, element n of the type database is [TransformationFamily(n), TransformationType(n)]

  • Transformation( images ) F
  • TransformationNC( images ) F

    both return a transformation with the image list images. The normal version checks that the all the elements of the given list lie within the range {1,...,n} where n is the length of images, but for speed purposes, a non-checking version is also supplied.

  • IdentityTransformation( n ) F

    return the identity transformation of degree n

  • RandomTransformation( n ) F

    returns a random transformation of degree n

  • DegreeOfTransformation( trans ) A

    returns the degree of trans. 

    gap> t:= Transformation([2, 3, 4, 2, 4]);
Transformation( [ 2, 3, 4, 2, 4 ] )
gap> DegreeOfTransformation(t);
5
  • ImageListOfTransformation( trans ) A

    returns the image list of trans. 

    gap> ImageListOfTransformation(t);
[ 2, 3, 4, 2, 4 ]
  • ImageSetOfTransformation( trans ) A

    returns the image of trans as a set. 

    gap> ImageSetOfTransformation(t);
[ 2, 3, 4 ]
  • RankOfTransformation( trans ) A

    returns the rank of trans. 

    gap> RankOfTransformation(t);
3
  • KernelOfTransformation( trans ) A

    Returns the kernel of trans as an equivalence relation (See General Binary Relations). 

    gap> KernelOfTransformation(t);
<equivalence relation on <object> >
gap> EquivalenceRelationPartition(last);
[ [ 1, 4 ], [ 3, 5 ] ]
  • PreimagesOfTransformation( trans, i ) O

    returns the subset of {1,...,n} which maps to i under trans. 

    gap> PreimagesOfTransformation(t, 2);
[ 1, 4 ]
  • RestrictedTransformation( trans, alpha ) O

    The transformation trans is restricted to only those points of alpha.

  • AsTransformation( O ) O
  • AsTransformation( O, n ) O
  • AsTransformationNC( O, n ) O

    returns the object O as a transformation. Supported objects are permuations and binary relations on points. In the second form, the operation returns a transformation of degree n, signalling an error if such a representation is not possible. AsTransformationNC does not perform this check. 

    gap> AsTransformation((1, 3)(2, 4));
Transformation( [ 3, 4, 1, 2 ] )
gap> AsTransformation((1, 3)(2, 4), 10);
Transformation( [ 3, 4, 1, 2, 5, 6, 7, 8, 9, 10 ] )

    gap> AsTransformation((1, 3)(2, 4), 3);
Error, Permutation moves points over the degree specified called from
<function>( <arguments> ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> quit;

  • PermLeftQuoTransformation( tr1, tr2 ) O

    Given transformations tr1 and tr2 with equal kernel and image, we compute the permutation induced by (tr1)-1*tr2 on the set of images of tr1. If the kernels and images are not equal, an error is signaled.

  • BinaryRelationTransformation( trans ) O

    returns trans when considered as a binary relation.

  • TransformationRelation( R ) O

    returns the binary relation R when considered as a transformation. Only makes sense for injective binary relations over [1..n]. Returns an error if the relation is not over [1..n], and fail if it is not injective.

    [Top] [Up] [Previous] [Next] [Index]

    GAP 4 manual
    May 2002