Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

54 Transformations
 54.1 Functions for Transformations

54 Transformations

This chapter describes functions for transformations.

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

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

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.

54.1 Functions for Transformations

54.1-1 IsTransformation
‣ IsTransformation( obj )( category )
‣ IsTransformationCollection( obj )( category )

We declare it as IsMultiplicativeElementWithOne (31.14-11) since the identity automorphism of \(\{ 1, \ldots, n \}\) is a multiplicative two sided identity for any transformation on the same set.

54.1-2 TransformationFamily
‣ TransformationFamily( n )( function )
‣ TransformationType( n )( function )
‣ TransformationData( n )( function )

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)]

54.1-3 Transformation
‣ Transformation( images )( function )
‣ TransformationNC( images )( function )

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

54.1-4 IdentityTransformation
‣ IdentityTransformation( n )( function )

returns the identity transformation of degree n.

54.1-5 RandomTransformation
‣ RandomTransformation( n )( function )

returns a random transformation of degree n.

54.1-6 DegreeOfTransformation
‣ DegreeOfTransformation( trans )( attribute )

returns the degree of trans.

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

54.1-7 ImageListOfTransformation
‣ ImageListOfTransformation( trans )( attribute )

returns the image list of trans.

gap> ImageListOfTransformation(t);
[ 2, 3, 4, 2, 4 ]

54.1-8 ImageSetOfTransformation
‣ ImageSetOfTransformation( trans )( attribute )

returns the image of trans as a set.

gap> ImageSetOfTransformation(t);
[ 2, 3, 4 ]

54.1-9 RankOfTransformation
‣ RankOfTransformation( trans )( attribute )

returns the rank of trans.

gap> RankOfTransformation(t);
3

54.1-10 KernelOfTransformation
‣ KernelOfTransformation( trans )( attribute )

returns the kernel of trans as an equivalence relation, see 33.1).

gap> KernelOfTransformation(t);         
[ [ 1, 4 ], [ 2 ], [ 3, 5 ] ]

54.1-11 PreimagesOfTransformation
‣ PreimagesOfTransformation( trans, i )( operation )

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

gap> PreimagesOfTransformation(t, 2);
[ 1, 4 ]

54.1-12 RestrictedTransformation
‣ RestrictedTransformation( trans, alpha )( operation )

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

54.1-13 AsTransformation
‣ AsTransformation( O[, n] )( operation )
‣ AsTransformationNC( O, n )( operation )

returns the object O as a transformation. Supported objects are permutations and binary relations on points. Called with two arguments, 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;

54.1-14 PermLeftQuoTransformation
‣ PermLeftQuoTransformation( tr1, tr2 )( operation )

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.

54.1-15 BinaryRelationTransformation
‣ BinaryRelationTransformation( trans )( operation )

returns trans when considered as a binary relation.

54.1-16 TransformationRelation
‣ TransformationRelation( R )( operation )

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

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind

generated by GAPDoc2HTML