[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(αβ) = (iα)β for i in {1, ..., n}.

For a transformation α on the set {1, …, n}, we define its degree to be n, its image list to be the list, [1α, …, nα], 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 α to be the equivalence relation containing the pair (i, j) if and only if iα = jα.

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 permutations 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
  August 2005