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] 

53 Transformations
 53.1 The family and categories of transformations
 53.2 Creating transformations
 53.3 Changing the representation of a transformation
 53.4 Operators for transformations
 53.5 Attributes for transformations
 53.6 Displaying transformations
 53.7 Semigroups of transformations

53 Transformations

This chapter describes the functions in GAP for transformations.

A transformation in GAP is simply a function from the positive integers to the positive integers. Transformations are to semigroup theory what permutations are to group theory, in the sense that every semigroup can be realised as a semigroup of transformations. In GAP transformation semigroups are always finite, and so only finite semigroups can be realised in this way.

A transformation in GAP acts on the positive integers (up to some architecture dependent limit) on the right. The image of a point i under a transformation f is expressed as i ^ f in GAP. This action is also implemented by the function OnPoints (41.2-1). If i ^ f is different from i, then i is moved by f and otherwise it is fixed by f. Transformations in GAP are created using the operations described in Section 53.2.

The degree of a transformation f is usually defined as the largest positive integer where f is defined. In previous versions of GAP, transformations were only defined on positive integers less than their degree, it was only possible to multiply transformations of equal degree, and a transformation did not act on any point exceeding its degree. Starting with version 4.7 of GAP, transformations behave more like permutations, in that they fix unspecified points and it is possible to multiply arbitrary transformations; see Chapter 42. The definition of the degree of a transformation f in the current version of GAP is the largest value n such that n ^ f <> n or i ^ f = n for some i <> n. Equivalently, the degree of a transformation is the least value n such that [ n + 1, n + 2, ... ] is fixed pointwise by f.

The transformations of a given degree belong to the full transformation semigroup of that degree; see FullTransformationSemigroup (53.7-3). Transformation semigroups are hence subsemigroups of the full transformation semigroup.

It is possible to use transformations in GAP without reference to the degree, much as it is possible to use permutations in this way. However, for backwards compatibility, and because it is sometimes useful, it is possible to access the degree of a transformation using DegreeOfTransformation (53.5-1). Certain attributes of transformations are also calculated with respect to the degree, such as the rank, image set, or kernel (these values can also be calculated with respect to any positive integer). So, it is possible to ignore the degree of a transformation if you prefer to think of transformations as acting on the positive integers in a similar way to permutations. For example, this approach is used in the FR package. It is also possible to think of transformations as only acting on the positive integers not exceeding their degree. For example, this was the approach formerly used in GAP and it is also useful in the Semigroups package.

Transformations are displayed, by default, using the list [ 1 ^ f .. n ^ f ] where n is the degree of f. This behaviour differs from that of versions of GAP earlier than 4.7. See Section 53.6 for more information.

The rank of a transformation on the positive integers up to n is the number of distinct points in [ 1 ^ f .. n ^ f ]. The kernel of a transformation f on [ 1 .. n ] is the equivalence relation on [ 1 .. n ] consisting of those pairs (i, j) of positive integers such that i ^ f = j ^ f. The kernel of a transformation is represented in two ways: as a partition of [ 1 .. n ] or as the image list of a transformation g such that the kernel of g on [ 1 .. n ] equals the kernel of f and j ^ g = i for all j in ith class. The latter is referred to as the flat kernel of f. For any given transformation f and value n, there is a unique transformation g with this property.

A functional digraph is a directed graph where every vertex has out-degree 1. A transformation f can be thought of as a functional digraph with vertices the positive integers and edges from i to i ^ f for every i. A component of a transformation is defined as a component of the corresponding functional digraph. More specifically, i and j are in the same component if and only if there are i = v_0, v_1, ..., v_n = j such that either v_k+1=v_k^f or v_k=v_k+1^f for all k. A cycle of a transformation is defined as a cycle (or strongly connected component) of the corresponding functional digraph. More specifically, i belongs to a cycle of f if there are i=v_0, v_1, ..., v_n=i such that either v_k+1=v_k^f or v_k=v_k+1^f for all k.

Internally, GAP stores a transformation f as a list consisting of the images i ^ f for all values of i less than a value which is at least the degree of f and which is determined at the time of the creation of f. When the degree of a transformation f is at most 65536, the images of points under f are stored as 16-bit integers, the kernel and image set are subobjects of f which are plain lists of GAP integers. When the degree of f is greater than 65536, the images of points under f are stored as 32-bit integers; the kernel and image set are stored in the same way as before. A transformation belongs to IsTrans2Rep if it is stored using 16-bit integers and to IsTrans4Rep if it is stored using 32-bit integers.

53.1 The family and categories of transformations

53.1-1 IsTransformation
‣ IsTransformation( obj )( category )

Every transformation in GAP belongs to the category IsTransformation. Basic operations for transformations are ImageListOfTransformation (53.5-2), ImageSetOfTransformation (53.5-3), KernelOfTransformation (53.5-12), FlatKernelOfTransformation (53.5-11), RankOfTransformation (53.5-4), DegreeOfTransformation (53.5-1), multiplication of two transformations via *, and exponentiation with the first argument a positive integer i and second argument a transformation f where the result is the image i ^ f of the point i under f.

53.1-2 IsTransformationCollection
‣ IsTransformationCollection( obj )( category )

Every collection of transformations belongs to the category IsTransformationCollection. For example, transformation semigroups belong to IsTransformationCollection.

53.1-3 TransformationFamily
‣ TransformationFamily( family )

The family of all transformations is TransformationFamily.

53.2 Creating transformations

There are several ways of creating transformations in GAP, which are described in this section.

53.2-1 Transformation
‣ Transformation( list )( operation )
‣ Transformation( list, func )( operation )
‣ TransformationList( list )( operation )

Returns: A transformation.

TransformationList returns the transformation f such that i ^ f = list[i] if i is between 1 and the length of list and i ^ f = i if i is larger than the length of list. An error will occur in TransformationList if list is not dense, if list contains an element which is not a positive integer, or if list contains an integer not in [ 1 .. Length( list ) ].

TransformationList is the analogue in the context of transformations of PermList (42.5-2). Transformation is a synonym of TransformationList when the argument is a list.

When the arguments are a list of positive integers list and a function func, Transformation returns the transformation f such that list[i] ^ f = func( list[i] ) if i is in the range [ 1 .. Length( list ) ] and f fixes all other points.

gap> SetUserPreference( "NotationForTransformations", "input" );
gap> f := Transformation( [ 11, 10, 2, 11, 4, 4, 7, 6, 9, 10, 1, 11 ] );
Transformation( [ 11, 10, 2, 11, 4, 4, 7, 6, 9, 10, 1, 11 ] )
gap> f := TransformationList( [ 2, 3, 3, 1 ] );
Transformation( [ 2, 3, 3, 1 ] )
gap> SetUserPreference( "NotationForTransformations", "fr" );
gap> f := Transformation( [ 10, 11 ], x -> x ^ 2 );
<transformation: 1,2,3,4,5,6,7,8,9,100,121>
gap> SetUserPreference( "NotationForTransformations", "input" );

53.2-2 Transformation
‣ Transformation( src, dst )( operation )
‣ TransformationListList( src, dst )( operation )

Returns: A transformation.

If src and dst are lists of positive integers of the same length, such that src contains no element twice, then TransformationListList( src, dst ) returns a transformation f such that src[i] ^ f = dst[i]. The transformation f fixes all points larger than the maximum of the entries in src and dst.

TransformationListList is the analogue in the context of transformations of MappingPermListList (42.5-3). Transformation is a synonym of TransformationListList when its arguments are two lists of positive integers.

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

53.2-3 TransformationByImageAndKernel
‣ TransformationByImageAndKernel( im, ker )( operation )

Returns: A transformation or fail.

This operation returns the transformation f where i ^ f = im[ker[i]] for i in the range [ 1 .. Length( ker ) ]. This transformation has flat kernel equal to ker and image set equal to Set( im ).

The argument im should be a duplicate free list of positive integers and ker should be the flat kernel of a transformation with rank equal to the length of im. If the arguments do not fulfil these conditions, then fail is returned.

gap> TransformationByImageAndKernel( [ 8, 1, 3, 4 ],
>                                    [ 1, 2, 3, 1, 2, 1, 2, 4 ] );
Transformation( [ 8, 1, 3, 8, 1, 8, 1, 4 ] )
gap> TransformationByImageAndKernel( [ 1, 3, 8, 4 ],
>                                    [ 1, 2, 3, 1, 2, 1, 2, 4 ] );
Transformation( [ 1, 3, 8, 1, 3, 1, 3, 4 ] )

53.2-4 Idempotent
‣ Idempotent( im, ker )( operation )

Returns: A transformation or fail.

Idempotent returns the idempotent transformation with image set im and flat kernel ker if such a transformation exists and fail if it does not. More specifically, a transformation is returned when the argument im is a set of positive integers and ker is the flat kernel of a transformation with rank equal to the length of im and where im has one element in every class of the kernel corresponding to ker.

Note that this is function does not always return the same transformation as TransformationByImageAndKernel with the same arguments.

gap> Idempotent( [ 2, 4, 6, 7, 8, 10, 11 ],
>                [ 1, 2, 1, 3, 3, 4, 5, 1, 6, 6, 7, 5 ] );
Transformation( [ 8, 2, 8, 4, 4, 6, 7, 8, 10, 10, 11, 7 ] )
gap> TransformationByImageAndKernel( [ 2, 4, 6, 7, 8, 10, 11 ],
>                      [ 1, 2, 1, 3, 3, 4, 5, 1, 6, 6, 7, 5 ] );
Transformation( [ 2, 4, 2, 6, 6, 7, 8, 2, 10, 10, 11, 8 ] )

53.2-5 TransformationOp
‣ TransformationOp( obj, list[, func] )( operation )
‣ TransformationOpNC( obj, list[, func] )( operation )

Returns: A transformation or fail.

TransformationOp returns the transformation that corresponds to the action of the object obj on the domain or list list via the function func. If the optional third argument func is not specified, then the action OnPoints (41.2-1) is used by default. Note that the returned transformation refers to the positions in list even if list itself consists of integers.

This function is the analogue in the context of transformations of Permutation (41.9-1).

If obj does not map elements of list into list, then fail is returned.

TransformationOpNC does not check that obj maps elements of list to elements of list or that a transformation is defined by the action of obj on list via func. This function should be used only with caution, and in situations where it is guaranteed that the arguments have the required properties.

gap> f := Transformation( [ 10, 2, 3, 10, 5, 10, 7, 2, 5, 6 ] );;
gap> TransformationOp( f, [ 2, 3 ] );
IdentityTransformation
gap> TransformationOp( f, [ 1, 2, 3 ] );
fail
gap> S := SemigroupByMultiplicationTable( [ [ 1, 1, 1 ],
>                                           [ 1, 1, 1 ],
>                                           [ 1, 1, 2 ] ] );;
gap> TransformationOp( Elements( S )[1], S, OnRight );
Transformation( [ 1, 1, 1 ] )
gap> TransformationOp( Elements( S )[3], S, OnRight );
Transformation( [ 1, 1, 2 ] )

53.2-6 TransformationNumber
‣ TransformationNumber( m, n )( operation )
‣ NumberTransformation( f[, n] )( operation )

Returns: A transformation or a number.

These functions implement a bijection from the transformations with degree at most n to the numbers [ 1 .. n ^ n ].

More precisely, if m and n are positive integers such that m is at most n ^ n, then TransformationNumber returns the mth transformation with degree at most n.

If f is a transformation and n is a positive integer, which is greater than or equal to the degree of f, then NumberTransformation returns the number in [ 1 .. n ^ n ] that corresponds to f. If the optional second argument n is not specified, then the degree of f is used by default.

gap> f := Transformation( [ 3, 3, 5, 3, 3 ] );;
gap> NumberTransformation( f, 5 );
1613
gap> NumberTransformation( f, 10 );
2242256790
gap> TransformationNumber( 2242256790, 10 );
Transformation( [ 3, 3, 5, 3, 3 ] )
gap> TransformationNumber( 1613, 5 );
Transformation( [ 3, 3, 5, 3, 3 ] )

53.2-7 RandomTransformation
‣ RandomTransformation( n )( operation )

Returns: A random transformation.

If n is a positive integer, then RandomTransformation returns a random transformation with degree at most n.

gap> RandomTransformation( 6 );
Transformation( [ 2, 1, 2, 1, 1, 2 ] )

53.2-8 IdentityTransformation
‣ IdentityTransformation( global variable )

This variable is bound to the identity transformation, which has degree 0.

gap> IdentityTransformation;
IdentityTransformation

53.2-9 ConstantTransformation
‣ ConstantTransformation( m, n )( operation )

Returns: A transformation.

This function returns a constant transformation f such that i ^ f = n for all i less than or equal to m, when n and m are positive integers.

gap> ConstantTransformation( 5, 1 );
Transformation( [ 1, 1, 1, 1, 1 ] )
gap> ConstantTransformation( 6, 4 );
Transformation( [ 4, 4, 4, 4, 4, 4 ] )

53.3 Changing the representation of a transformation

It is possible that a transformation in GAP can be represented as another type of object, or that another type of GAP object can be represented as a transformation.

The operations AsPermutation (42.5-6) and AsPartialPerm (54.4-2) can be used to convert transformations into permutations or partial permutations, where appropriate. In this section we describe functions for converting other types of objects into transformations.

53.3-1 AsTransformation
‣ AsTransformation( f[, n] )( attribute )

Returns: A transformation.

AsTransformation returns the permutation, transformation, partial permutation or binary relation f as a transformation.

for permutations

If f is a permutation and n is a non-negative integer, then AsTransformation( f, n ) returns the transformation g such that i ^ g = i ^ f for all i in the range [ 1 .. n ].

If no non-negative integer n is specified, then the largest moved point of f is used as the value for n; see LargestMovedPoint (42.3-2).

for transformations

If f is a transformation and n is a non-negative integer less than the degree of f such that f is a transformation of [ 1 .. n ], then AsTransformation returns the restriction of f to [ 1 .. n ].

If f is a transformation and n is not specified or is greater than or equal to the degree of f, then f is returned.

for partial permutations

A partial permutation f can be converted into a transformation g as follows. The degree m of g is equal to the maximum of n, the largest moved point of f plus 1, and the largest image of a moved point plus 1. The transformation g agrees with f on the domain of f and maps the points in [ 1 .. m ], which are not in the domain of f to n, i.e. i ^ g = i ^ f for all i in the domain of f, i ^ g = n for all i in [ 1 .. n ], and i ^ g = i for all i greater than n. AsTransformation( f ) returns the transformation g defined in the previous sentences.

If the optional argument n is not present, then the default value of the maximum of the largest moved point and the largest image of a moved point of f plus 1 is used.

for binary relations

In the case that f is a binary relation, which defines a transformation, AsTransformation returns that transformation.

gap> f := Transformation( [ 3, 5, 3, 4, 1, 2 ] );;
gap> AsTransformation( f, 5 );
Transformation( [ 3, 5, 3, 4, 1 ] )
gap> AsTransformation( f, 10 );
Transformation( [ 3, 5, 3, 4, 1, 2 ] )
gap> AsTransformation( (1,3)(2,4) );
Transformation( [ 3, 4, 1, 2 ] )
gap> AsTransformation( (1,3)(2,4), 10 );
Transformation( [ 3, 4, 1, 2 ] )
gap> f := PartialPerm( [ 1, 2, 3, 4, 5, 6 ], [ 6, 7, 1, 4, 3, 2 ] );
[5,3,1,6,2,7](4)
gap> AsTransformation( f, 11 );
Transformation( [ 6, 7, 1, 4, 3, 2, 11, 11, 11, 11, 11 ] )
gap> AsPartialPerm( last, DomainOfPartialPerm( f ) );
[5,3,1,6,2,7](4)
gap> AsTransformation( f, 14 );
Transformation( [ 6, 7, 1, 4, 3, 2, 14, 14, 14, 14, 14, 14, 14, 14 ] )
gap> AsPartialPerm( last, DomainOfPartialPerm( f ) );
[5,3,1,6,2,7](4)
gap> AsTransformation( f );
Transformation( [ 6, 7, 1, 4, 3, 2, 8, 8 ] )
gap> AsTransformation( Transformation( [ 1, 1, 2 ] ), 0 );
IdentityTransformation

53.3-2 RestrictedTransformation
‣ RestrictedTransformation( f, list )( function )

Returns: A transformation.

RestrictedTransformation returns the new transformation g such that i ^ g = i ^ f for all i in list and such that i ^ g = i for all i not in list.

gap> f := Transformation( [ 2, 10, 5, 9, 10, 9, 6, 3, 8, 4, 6, 5 ] );;
gap> RestrictedTransformation( f, [ 1, 2, 3, 10, 11, 12 ] );
Transformation( [ 2, 10, 5, 4, 5, 6, 7, 8, 9, 4, 6, 5 ] )

53.3-3 PermutationOfImage
‣ PermutationOfImage( f )( function )

Returns: A permutation or fail.

If the transformation f is a permutation of the points in its image, then PermutationOfImage returns this permutation. If f does not permute its image, then fail is returned.

If f happens to be a permutation, then PermutationOfImage with argument f returns the same value as AsPermutation with argument f.

gap> f := Transformation( [ 5, 8, 3, 5, 8, 6, 2, 2, 7, 8 ] );;
gap> PermutationOfImage( f );
fail
gap> f := Transformation( [ 8, 2, 10, 2, 4, 4, 7, 6, 9, 10 ] );;
gap> PermutationOfImage( f );
fail
gap> f := Transformation( [ 1, 3, 6, 6, 2, 10, 2, 3, 10, 5 ] );;
gap> PermutationOfImage( f );
(2,3,6,10,5)
gap> f := Transformation( [ 5, 2, 8, 4, 1, 8, 10, 3, 5, 7 ] );;
gap> PermutationOfImage( f );
(1,5)(3,8)(7,10)

53.4 Operators for transformations

53.4-1 \^
‣ \^( i, f )( method )

i ^ f returns the image of the positive integer i under the transformation f.

53.4-2 \^
‣ \^( f, g )( method )

f ^ g returns g ^ -1 * f * g when f is a transformation and g is a permutation \^ (31.12-1). This operation requires essentially the same number of steps as multiplying a transformation by a permutation, which is approximately one third of the number required to first invert g, take the product with f, and then the product with g.

53.4-3 \*
‣ \*( f, g )( method )

f * g returns the composition of f and g when f and g are transformations or permutations. The product of a permutation and a transformation is returned as a transformation.

53.4-4 \/
‣ \/( f, g )( method )

f / g returns f * g ^ -1 when f is a transformation and g is a permutation. This operation requires essentially the same number of steps as multiplying a transformation by a permutation, which is approximately half the number required to first invert g and then take the product with f.

53.4-5 LeftQuotient
‣ LeftQuotient( g, f )( method )

returns g ^ -1 * f when f is a transformation and g is a permutation. This operation uses essentially the same number of steps as multiplying a transformation by a permutation, which is approximately half the number required to first invert g and then take the product with f.

53.4-6 \<
‣ \<( i, f )( method )

f < g returns true if the image list of f is lexicographically less than the image list of g and false if it is not.

53.4-7 \=
‣ \=( f, g )( method )

f = g returns true if the transformation f equals the transformation g and returns false if it does not.

53.4-8 PermLeftQuoTransformation
‣ PermLeftQuoTransformation( f, g )( operation )
‣ PermLeftQuoTransformationNC( f, g )( function )

Returns: A permutation.

Returns the permutation on the image set of f induced by f ^ -1 * g when the transformations f and g have equal kernel and image set.

PermLeftQuoTransformation verifies that f and g have equal kernels and image sets, and returns an error if they do not. PermLeftQuoTransformationNC does no checks.

gap> f := Transformation( [ 5, 6, 7, 1, 4, 3, 2, 7 ] );;
gap> g := Transformation( [ 5, 7, 1, 6, 4, 3, 2, 1 ] );;
gap> PermLeftQuoTransformation( f, g );
(1,6,7)
gap> PermLeftQuoTransformation( g, f );
(1,7,6)

53.4-9 IsInjectiveListTrans
‣ IsInjectiveListTrans( list, obj )( function )

Returns: true or false.

The argument obj should be a transformation or the list of images of a transformation and list should be a list of positive integers. IsInjectiveListTrans checks if obj is injective on list.

More precisely, if obj is a transformation, then we define f := obj and if obj is the image list of a transformation we define f := Transformation( obj ). IsInjectiveListTrans returns true if f is injective on list and false if it is not. If list is not duplicate free, then false is returned.

gap> f := Transformation( [ 2, 6, 7, 2, 6, 9, 9, 1, 1, 5 ] );;
gap> IsInjectiveListTrans( [ 1, 5 ], f );
true
gap> IsInjectiveListTrans( [ 5, 1 ], f );
true
gap> IsInjectiveListTrans( [ 5, 1, 5, 1, 1, ], f );
false
gap> IsInjectiveListTrans( [ 5, 1, 2, 3 ], [ 1, 2, 3, 4, 5 ] );
true

53.4-10 ComponentTransformationInt
‣ ComponentTransformationInt( f, n )( operation )

Returns: A list of positive integers.

If f is a transformation and n is a positive integer, then ComponentTransformationInt returns those elements i such that n ^ f ^ j = i for some positive integer j, i.e. the elements of the component of f containing n that can be obtained by applying powers of f to n.

gap> f := Transformation( [ 6, 2, 8, 4, 7, 5, 8, 3, 5, 8 ] );;
gap> ComponentTransformationInt( f, 1 );
[ 1, 6, 5, 7, 8, 3 ]
gap> ComponentTransformationInt( f, 12 );
[ 12 ]
gap> ComponentTransformationInt( f, 5 );
[ 5, 7, 8, 3 ]

53.4-11 PreImagesOfTransformation
‣ PreImagesOfTransformation( f, n )( operation )

Returns: A set of positive integers.

Returns the preimages of the positive integer n under the transformation f, i.e. the positive integers i such that i ^ f = n.

gap> f := Transformation( [ 2, 6, 7, 2, 6, 9, 9, 1, 1, 5 ] );;
gap> PreImagesOfTransformation( f, 1 );
[ 8, 9 ]
gap> PreImagesOfTransformation( f, 3 );
[  ]
gap> PreImagesOfTransformation( f, 100 );
[ 100 ]

53.5 Attributes for transformations

In this section we describe the functions available in GAP for finding various properties and attributes of transformations.

53.5-1 DegreeOfTransformation
‣ DegreeOfTransformation( f )( function )
‣ DegreeOfTransformationCollection( coll )( attribute )

Returns: A positive integer.

The degree of a transformation f is the largest value such that n ^ f <> n or i ^ f = n for some i <> n. Equivalently, the degree of a transformation is the least value n such that [ n + 1, n + 2, ... ] is fixed pointwise by f.

The degree of a collection of transformations coll is the maximum degree of any transformation in coll.

gap> DegreeOfTransformation( IdentityTransformation );
0
gap> DegreeOfTransformationCollection(
> [ Transformation( [ 1, 3, 4, 1 ] ),
>   Transformation( [ 3, 1, 1, 3, 4 ] ),
>   Transformation( [ 2, 4, 1, 2 ] ) ] );
5

53.5-2 ImageListOfTransformation
‣ ImageListOfTransformation( f[, n] )( operation )
‣ ListTransformation( f[, n] )( operation )

Returns: The list of images of a transformation.

Returns the list of images of [ 1 .. n ] under the transformation f, which is [ 1 ^ f .. n ^ f ]. If the optional second argument n is not present, then the degree of f is used by default.

This is the analogue for transformations of ListPerm (42.5-1) for permutations.

gap> f := Transformation( [ 2 ,3, 4, 2, 4 ] );;
gap> ImageListOfTransformation( f );
[ 2, 3, 4, 2, 4 ]
gap> ImageListOfTransformation( f, 10 );
[ 2, 3, 4, 2, 4, 6, 7, 8, 9, 10 ]

53.5-3 ImageSetOfTransformation
‣ ImageSetOfTransformation( f[, n] )( attribute )

Returns: The set of images of the transformation.

Returns the set of points in the list of images of [ 1 .. n ] under f, i.e. the sorted list of images with duplicates removed. If the optional second argument n is not given, then the degree of f is used.

gap> f := Transformation( [ 5, 6, 7, 1, 4, 3, 2, 7 ] );;
gap> ImageSetOfTransformation( f );
[ 1, 2, 3, 4, 5, 6, 7 ]
gap> ImageSetOfTransformation( f, 10 );
[ 1, 2, 3, 4, 5, 6, 7, 9, 10 ]

53.5-4 RankOfTransformation
‣ RankOfTransformation( f[, n] )( attribute )
‣ RankOfTransformation( f[, list] )( attribute )

Returns: The rank of a transformation.

When the arguments are a transformation f and a positive integer n, RankOfTransformation returns the size of the set of images of the transformation f in the range [ 1 .. n ]. If the optional second argument n is not specified, then the degree of f is used.

When the arguments are a transformation f and a list list of positive integers, this function returns the size of the set of images of the transformation f on list.

gap> f := Transformation( [ 8, 5, 8, 2, 2, 8, 4, 7, 3, 1 ] );;
gap> ImageSetOfTransformation( f );
[ 1, 2, 3, 4, 5, 7, 8 ]
gap> RankOfTransformation( f );
7
gap> RankOfTransformation( f, 100 );
97
gap> RankOfTransformation( f, [ 2, 5, 8 ] );
3

53.5-5 MovedPoints
‣ MovedPoints( f )( attribute )
‣ MovedPoints( coll )( attribute )

Returns: A set of positive integers.

When the argument is a transformation, MovedPoints returns the set of positive integers i such that i ^ f <> i.

MovedPoints returns the set of points moved by some element of the collection of transformations coll.

gap> f := Transformation( [ 6, 10, 1, 4, 6, 5, 1, 2, 3, 3 ] );;
gap> MovedPoints( f );
[ 1, 2, 3, 5, 6, 7, 8, 9, 10 ]
gap> f := IdentityTransformation;
IdentityTransformation
gap> MovedPoints( f );
[  ]

53.5-6 NrMovedPoints
‣ NrMovedPoints( f )( attribute )
‣ NrMovedPoints( coll )( attribute )

Returns: A positive integer.

When the argument is a transformation,NrMovedPoints returns the number of positive integers i such that i ^ f <> i.

MovedPoints returns the number of points which are moved by at least one element of the collection of transformations coll.

gap> f := Transformation( [ 7, 1, 4, 3, 2, 7, 7, 6, 6, 5 ] );;
gap> NrMovedPoints( f );
9
gap> NrMovedPoints( IdentityTransformation );
0

53.5-7 SmallestMovedPoint
‣ SmallestMovedPoint( f )( attribute )
‣ SmallestMovedPoint( coll )( method )

Returns: A positive integer or infinity.

SmallestMovedPoint returns the smallest positive integer i such that i ^ f <> i if such an i exists. If f is the identity transformation, then infinity is returned.

If the argument is a collection of transformations coll, then the smallest point which is moved by at least one element of coll is returned, if such a point exists. If coll only contains identity transformations, then SmallestMovedPoint returns infinity.

gap> S := FullTransformationSemigroup( 5 );
<full transformation monoid of degree 5>
gap> SmallestMovedPoint( S );
1
gap> S := Semigroup( IdentityTransformation );
<trivial transformation group of degree 0 with 1 generator>
gap> SmallestMovedPoint( S );
infinity
gap> f := Transformation( [ 1, 2, 3, 6, 6, 6 ] );;
gap> SmallestMovedPoint( f );
4

53.5-8 LargestMovedPoint
‣ LargestMovedPoint( f )( attribute )
‣ LargestMovedPoint( coll )( method )

Returns: A positive integer.

LargestMovedPoint returns the largest positive integers i such that i ^ f <> i if such an i exists. If f is the identity transformation, then 0 is returned.

If the argument is a collection of transformations coll, then the largest point which is moved by at least one element of coll is returned, if such a point exists. If coll only contains identity transformations, then LargestMovedPoint returns 0.

gap> S := FullTransformationSemigroup( 5 );
<full transformation monoid of degree 5>
gap> LargestMovedPoint( S );
5
gap> S := Semigroup( IdentityTransformation );
<trivial transformation group of degree 0 with 1 generator>
gap> LargestMovedPoint( S );
0
gap> f := Transformation( [ 1, 2, 3, 6, 6, 6 ] );;
gap> LargestMovedPoint( f );
5

53.5-9 SmallestImageOfMovedPoint
‣ SmallestImageOfMovedPoint( f )( attribute )
‣ SmallestImageOfMovedPoint( coll )( method )

Returns: A positive integer or infinity.

SmallestImageOfMovedPoint returns the smallest positive integer i ^ f such that i ^ f <> i if such an i exists. If f is the identity transformation, then infinity is returned.

If the argument is a collection of transformations coll, then the smallest integer which is the image a point moved by at least one element of coll is returned, if such a point exists. If coll only contains identity transformations, then SmallestImageOfMovedPoint returns infinity.

gap> S := FullTransformationSemigroup( 5 );
<full transformation monoid of degree 5>
gap> SmallestImageOfMovedPoint( S );
1
gap> S := Semigroup( IdentityTransformation );
<trivial transformation group of degree 0 with 1 generator>
gap> SmallestImageOfMovedPoint( S );
infinity
gap> f := Transformation( [ 1, 2, 3, 6, 6, 6 ] );;
gap> SmallestImageOfMovedPoint( f );
6

53.5-10 LargestImageOfMovedPoint
‣ LargestImageOfMovedPoint( f )( attribute )
‣ LargestImageOfMovedPoint( coll )( method )

Returns: A positive integer.

LargestImageOfMovedPoint returns the largest positive integer i ^ f such that i ^ f <> i if such an i exists. If f is the identity transformation, then 0 is returned.

If the argument is a collection of transformations coll, then the largest integer which is the image a point moved by at least one element of coll is returned, if such a point exists. If coll only contains identity transformations, then LargestImageOfMovedPoint returns 0.

gap> S := FullTransformationSemigroup( 5 );
<full transformation monoid of degree 5>
gap> LargestImageOfMovedPoint( S );
5
gap> S := Semigroup( IdentityTransformation );;
gap> LargestImageOfMovedPoint( S );
0
gap> f := Transformation( [ 1, 2, 3, 6, 6, 6 ] );;
gap> LargestImageOfMovedPoint( f );
6

53.5-11 FlatKernelOfTransformation
‣ FlatKernelOfTransformation( f[, n] )( attribute )

Returns: The flat kernel of a transformation.

If the kernel classes of the transformation f on [ 1 .. n ] are K_1, dots, K_r, then FlatKernelOfTransformation returns a list L such that L[i] = j for all i in K_j. For a given transformation and positive integer n, there is a unique such list.

If the optional second argument n is not present, then the degree of f is used by default.

gap> f := Transformation( [ 10, 3, 7, 10, 1, 5, 9, 2, 6, 10 ] );;
gap> FlatKernelOfTransformation( f );
[ 1, 2, 3, 1, 4, 5, 6, 7, 8, 1 ]

53.5-12 KernelOfTransformation
‣ KernelOfTransformation( f[, n, bool] )( attribute )

Returns: The kernel of a transformation.

When the arguments are a transformation f, a positive integer n, and true, KernelOfTransformation returns the kernel of the transformation f on [ 1 .. n ] as a set of sets of positive integers. If the argument bool is false, then only the non-singleton classes are returned.

The second and third arguments are optional, the default values are the degree of f and true.

gap> f := Transformation( [ 2, 6, 7, 2, 6, 9, 9, 1, 11, 1, 12, 5 ] );;
gap> KernelOfTransformation( f );
[ [ 1, 4 ], [ 2, 5 ], [ 3 ], [ 6, 7 ], [ 8, 10 ], [ 9 ], [ 11 ],
  [ 12 ] ]
gap> KernelOfTransformation( f, 5 );
[ [ 1, 4 ], [ 2, 5 ], [ 3 ] ]
gap> KernelOfTransformation( f, 5, false );
[ [ 1, 4 ], [ 2, 5 ] ]
gap> KernelOfTransformation( f, 15 );
[ [ 1, 4 ], [ 2, 5 ], [ 3 ], [ 6, 7 ], [ 8, 10 ], [ 9 ], [ 11 ],
  [ 12 ], [ 13 ], [ 14 ], [ 15 ] ]
gap> KernelOfTransformation( f, false );
[ [ 1, 4 ], [ 2, 5 ], [ 6, 7 ], [ 8, 10 ] ]

53.5-13 InverseOfTransformation
‣ InverseOfTransformation( f )( function )

Returns: A transformation.

InverseOfTransformation returns a semigroup inverse of the transformation f in the full transformation semigroup. An inverse of f is any transformation g such that f * g * f = f and g * f * g = g. Every transformation has at least one inverse.

gap> f := Transformation( [ 2, 6, 7, 2, 6, 9, 9, 1, 1, 5 ] );;
gap> g := InverseOfTransformation( f );
Transformation( [ 8, 1, 1, 1, 10, 2, 3, 1, 6, 1 ] )
gap> f * g * f;
Transformation( [ 2, 6, 7, 2, 6, 9, 9, 1, 1, 5 ] )
gap> g * f * g;
Transformation( [ 8, 1, 1, 1, 10, 2, 3, 1, 6, 1 ] )

53.5-14 Inverse
‣ Inverse( f )( attribute )

Returns: A transformation.

If the transformation f is a bijection, then Inverse or f ^ -1 returns the inverse of f. If f is not a bijection, then fail is returned.

gap> Transformation( [ 3, 8, 12, 1, 11, 9, 9, 4, 10, 5, 10, 6 ] ) ^ -1;
fail
gap> Transformation( [ 2, 3, 1 ] ) ^ -1;
Transformation( [ 3, 1, 2 ] )

53.5-15 IndexPeriodOfTransformation
‣ IndexPeriodOfTransformation( f )( function )

Returns: A pair of positive integers.

Returns the least positive integers m and r such that f ^ (m + r) = f ^ m, which are known as the index and period of the transformation f.

gap> f := Transformation( [ 3, 4, 4, 6, 1, 3, 3, 7, 1 ] );;
gap> IndexPeriodOfTransformation( f );
[ 2, 3 ]
gap> f ^ 2 = f ^ 5;
true
gap> IndexPeriodOfTransformation( IdentityTransformation );
[ 1, 1 ]
gap> IndexPeriodOfTransformation( Transformation( [ 1, 2, 1 ] ) );
[ 1, 1 ]
gap> IndexPeriodOfTransformation( Transformation( [ 1, 2, 3 ] ) );
[ 1, 1 ]
gap> IndexPeriodOfTransformation( Transformation( [ 1, 3, 2 ] ) );
[ 1, 2 ]

53.5-16 SmallestIdempotentPower
‣ SmallestIdempotentPower( f )( attribute )

Returns: A positive integer.

This function returns the least positive integer n such that the transformation f ^ n is an idempotent. The smallest idempotent power of f is the least multiple of the period of f that is greater than or equal to the index of f; see IndexPeriodOfTransformation (53.5-15).

gap> f := Transformation( [ 6, 7, 4, 1, 7, 4, 6, 1, 3, 4 ] );;
gap> SmallestIdempotentPower( f );
3
gap> f := Transformation( [ 6, 6, 6, 2, 7, 1, 5, 3, 10, 6 ] );;
gap> SmallestIdempotentPower( f );
2

53.5-17 ComponentsOfTransformation
‣ ComponentsOfTransformation( f )( attribute )

Returns: A list of lists of positive integers.

ComponentsOfTransformation returns a list of the components of the transformation f. Each component is a subset of [ 1 .. DegreeOfTransformation( f ) ], and the union of the components is [ 1 .. DegreeOfTransformation( f ) ].

gap> f := Transformation( [ 6, 12, 11, 1, 7, 6, 2, 8, 4, 7, 5, 12 ] );
Transformation( [ 6, 12, 11, 1, 7, 6, 2, 8, 4, 7, 5, 12 ] )
gap> ComponentsOfTransformation( f );
[ [ 1, 6, 4, 9 ], [ 2, 12, 3, 11, 5, 7, 10 ], [ 8 ] ]
gap> f := AsTransformation( (1,8,2,4,11,5,10)(3,7)(9,12) );
Transformation( [ 8, 4, 7, 11, 10, 6, 3, 2, 12, 1, 5, 9 ] )
gap> ComponentsOfTransformation( f );
[ [ 1, 8, 2, 4, 11, 5, 10 ], [ 3, 7 ], [ 6 ], [ 9, 12 ] ]

53.5-18 NrComponentsOfTransformation
‣ NrComponentsOfTransformation( f )( attribute )

Returns: A positive integer.

NrComponentsOfTransformation returns the number of components of the transformation f on the range [ 1 .. DegreeOfTransformation( f ) ].

gap> f := Transformation( [ 6, 12, 11, 1, 7, 6, 2, 8, 4, 7, 5, 12 ] );
Transformation( [ 6, 12, 11, 1, 7, 6, 2, 8, 4, 7, 5, 12 ] )
gap> NrComponentsOfTransformation( f );
3
gap> f := AsTransformation( (1,8,2,4,11,5,10)(3,7)(9,12) );
Transformation( [ 8, 4, 7, 11, 10, 6, 3, 2, 12, 1, 5, 9 ] )
gap> NrComponentsOfTransformation( f );
4

53.5-19 ComponentRepsOfTransformation
‣ ComponentRepsOfTransformation( f )( attribute )

Returns: A list of lists of positive integers.

ComponentRepsOfTransformation returns the representatives, in the following sense, of the components of the transformation f. For every i in [ 1 .. DegreeOfTransformation( f ) ] there exists a representative j and a positive integer k such that i ^ (f ^ k) = j. The representatives returned by ComponentRepsOfTransformation are partitioned according to the component they belong to. ComponentRepsOfTransformation returns the least number of representatives.

gap> f := Transformation( [ 6, 12, 11, 1, 7, 6, 2, 8, 4, 7, 5, 12 ] );
Transformation( [ 6, 12, 11, 1, 7, 6, 2, 8, 4, 7, 5, 12 ] )
gap> ComponentRepsOfTransformation( f );
[ [ 3, 10 ], [ 9 ], [ 8 ] ]
gap> f := AsTransformation( (1,8,2,4,11,5,10)(3,7)(9,12) );
Transformation( [ 8, 4, 7, 11, 10, 6, 3, 2, 12, 1, 5, 9 ] )
gap> ComponentRepsOfTransformation( f );
[ [ 1 ], [ 3 ], [ 6 ], [ 9 ] ]

53.5-20 CyclesOfTransformation
‣ CyclesOfTransformation( f[, list] )( attribute )

Returns: A list of lists of positive integers.

When the arguments of this function are a transformation f and a list list, it returns a list of the cycles of the components of f containing any element of list.

If the optional second argument is not present, then the range [ 1 .. DegreeOfTransformation( f ) ] is used as the default value for list.

gap> f := Transformation( [ 6, 12, 11, 1, 7, 6, 2, 8, 4, 7, 5, 12 ] );
Transformation( [ 6, 12, 11, 1, 7, 6, 2, 8, 4, 7, 5, 12 ] )
gap> CyclesOfTransformation( f );
[ [ 6 ], [ 12 ], [ 8 ] ]
gap> CyclesOfTransformation( f, [ 1, 2, 4 ] );
[ [ 6 ], [ 12 ] ]
gap> CyclesOfTransformation( f, [ 1 .. 17 ] );
[ [ 6 ], [ 12 ], [ 8 ], [ 13 ], [ 14 ], [ 15 ], [ 16 ], [ 17 ] ]

53.5-21 CycleTransformationInt
‣ CycleTransformationInt( f, n )( operation )

Returns: A list of positive integers.

If f is a transformation and n is a positive integer, then CycleTransformationInt returns the cycle of the component of f containing n.

gap> f := Transformation( [ 6, 2, 8, 4, 7, 5, 8, 3, 5, 8 ] );;
gap> CycleTransformationInt( f, 1 );
[ 8, 3 ]
gap> CycleTransformationInt( f, 12 );
[ 12 ]
gap> CycleTransformationInt( f, 5 );
[ 8, 3 ]

53.5-22 LeftOne
‣ LeftOne( f )( attribute )
‣ RightOne( f )( attribute )

Returns: A transformation.

LeftOne returns an idempotent transformation e such that the kernel (with respect to the degree of f) of e equals the kernel of the transformation f and e * f = f.

RightOne returns an idempotent transformation e such that the image set (with respect to the degree of f) of e equals the image set of f and f * e = f.

gap> f := Transformation( [ 11, 10, 2, 11, 4, 4, 7, 6, 9, 10, 1, 11 ] );;
gap> e := RightOne( f );
Transformation( [ 1, 2, 2, 4, 4, 6, 7, 7, 9, 10, 11, 11 ] )
gap> IsIdempotent( e );
true
gap> f * e = f;
true
gap> e := LeftOne( f );
Transformation( [ 1, 2, 3, 1, 5, 5, 7, 8, 9, 2, 11, 1 ] )
gap> e * f = f;
true
gap> IsIdempotent( e );
true

53.5-23 TrimTransformation
‣ TrimTransformation( f[, n] )( operation )

Returns: Nothing.

It can happen that the internal representation of a transformation uses more memory than necessary. For example, this can happen when composing transformations where it is possible that the resulting transformation f belongs to IsTrans4Rep and stores its images as 32-bit integers, while none of its moved points exceeds 65536. The purpose of TrimTransformation is to change the internal representation of such an f to remove the trailing fixed points in the internal representation of f.

If the optional second argument n is provided, then the internal representation of f is reduced to the images of the first n positive integers. Please note that it must be the case that i ^ f <= n for all i in the range [ 1 .. n ] otherwise the resulting object will not define a transformation.

If the optional second argument is not included, then the degree of f is used by default.

The transformation f is changed in-place, and nothing is returned by this function.

gap> f := Transformation( [ 1 .. 2 ^ 16 ], x -> x + 1 );
<transformation on 65537 pts with rank 65536>
gap> g := Transformation( [ 1 .. 2 ^ 16 + 1 ],
> function( x )
>   if x = 1 or x = 65537 then
>     return x;
>   else
>     return x - 1;
>   fi;
> end );
<transformation on 65536 pts with rank 65535>
gap> h := g * f;
Transformation( [ 2, 2 ] )
gap> DegreeOfTransformation( h ); IsTrans4Rep( h ); MemoryUsage( h );
65537
true
262188
gap> TrimTransformation( h ); h;
Transformation( [ 2, 2 ] )
gap> DegreeOfTransformation( h ); IsTrans4Rep( h ); MemoryUsage( h );
2
false
44

53.6 Displaying transformations

It is possible to change the way that GAP displays transformations using the user preferences TransformationDisplayLimit and NotationForTransformations; see Section UserPreference (3.2-3) for more information about user preferences.

If f is a transformation where the degree n of f exceeds the value of the user preference TransformationDisplayLimit, then f is displayed as:

<transformation on n pts with rank r>

where r is the rank of f relative to n. The idea is to abbreviate the display of transformations defined on many points. The default value for the TransformationDisplayLimit is 100.

If the degree of f does not exceed the value of TransformationDisplayLimit, then how f is displayed depends on the value of the user preference NotationForTransformations.

There are two possible values for NotationForTransformations:

input

With this option a transformation f is displayed in as: Transformation( ImageListOfTransformation( f, n ) ) where n is the degree of f. The only exception is the identity transformation, which is displayed as: IdentityTransformation.

fr

With this option a transformation f is displayed in as: <transformation: ImageListOfTransformation( f, n )> where n is the largest moved point of f. The only exception is the identity transformation, which is displayed as: <identity transformation>.

gap> SetUserPreference( "TransformationDisplayLimit", 12 );
gap> f := Transformation( [ 3, 8, 12, 1, 11, 9, 9, 4, 10, 5, 10, 6 ] );
<transformation on 12 pts with rank 10>
gap> SetUserPreference( "TransformationDisplayLimit", 100 );
gap> f;
Transformation( [ 3, 8, 12, 1, 11, 9, 9, 4, 10, 5, 10, 6 ] )
gap> SetUserPreference( "NotationForTransformations", "fr" );
gap> f;
<transformation: 3,8,12,1,11,9,9,4,10,5,10,6>

53.7 Semigroups of transformations

As mentioned at the start of the chapter, every semigroup is isomorphic to a semigroup of transformations, and in this section we describe the functions in GAP specific to transformation semigroups. For more information about semigroups in general see Chapter 51.

The Semigroups package contains many additional functions and methods for computing with semigroups of transformations. In particular, Semigroups contains more efficient methods than those available in the GAP library (and in many cases more efficient than any other software) for creating semigroups of transformations, calculating their Green's classes, size, elements, group of units, minimal ideal, small generating sets, testing membership, finding the inverses of a regular element, factorizing elements over the generators, and more. Since a transformation semigroup is also a transformation collection, there are special methods for MovedPoints (53.5-5), NrMovedPoints (53.5-6), LargestMovedPoint (53.5-8), SmallestMovedPoint (53.5-7), LargestImageOfMovedPoint (53.5-10), and SmallestImageOfMovedPoint (53.5-9), when applied to a transformation semigroup.

53.7-1 IsTransformationSemigroup
‣ IsTransformationSemigroup( obj )( synonym )
‣ IsTransformationMonoid( obj )( synonym )

Returns: true or false.

A transformation semigroup is simply a semigroup consisting of transformations. An object obj is a transformation semigroup in GAP if it satisfies IsSemigroup (51.1-1) and IsTransformationCollection (53.1-2).

A transformation monoid is a monoid consisting of transformations. An object obj is a transformation monoid in GAP if it satisfies IsMonoid (51.2-1) and IsTransformationCollection (53.1-2).

Note that it is possible for a transformation semigroup to have a multiplicative neutral element (i.e. an identity element) but not to satisfy IsTransformationMonoid. For example,

gap> f := Transformation( [ 2, 6, 7, 2, 6, 9, 9, 1, 1, 5 ] );;
gap> S := Semigroup( f, One( f ) );
<commutative transformation monoid of degree 10 with 1 generator>
gap> IsMonoid( S );
true
gap> IsTransformationMonoid( S );
true
gap> S := Semigroup(
> Transformation( [ 3, 8, 1, 4, 5, 6, 7, 1, 10, 10 ] ),
> Transformation( [ 1, 2, 3, 4, 5, 6, 7, 8, 10, 10 ] ) );
<transformation semigroup of degree 10 with 2 generators>
gap> One( S );
fail
gap> MultiplicativeNeutralElement( S );
Transformation( [ 1, 2, 3, 4, 5, 6, 7, 8, 10, 10 ] )
gap> IsMonoid( S );
false

In this example S cannot be converted into a monoid using AsMonoid (51.2-5) since the One (31.10-2) of any element in S differs from the multiplicative neutral element.

For more details see IsMagmaWithOne (35.1-2).

53.7-2 DegreeOfTransformationSemigroup
‣ DegreeOfTransformationSemigroup( S )( attribute )

Returns: A non-negative integer.

The degree of a transformation semigroup S is just the maximum of the degrees of the elements of S.

gap> S := Semigroup(
> Transformation( [ 3, 8, 1, 4, 5, 6, 7, 1, 10, 10, 11 ] ),
> Transformation( [ 1, 2, 3, 4, 5, 6, 7, 8, 1, 1, 11 ] ) );
<transformation semigroup of degree 10 with 2 generators>
gap> DegreeOfTransformationSemigroup( S );
10

53.7-3 FullTransformationSemigroup
‣ FullTransformationSemigroup( n )( function )
‣ FullTransformationMonoid( n )( function )

Returns: The full transformation semigroup of degree n.

If n is a positive integer, then FullTransformationSemigroup returns the monoid consisting of all transformations with degree at most n, called the full transformation semigroup.

The full transformation semigroup is regular, has n ^ n elements, and is generated by any set containing transformations that generate the symmetric group on n points and any transformation of rank n - 1.

FulTransformationMonoid is a synonym for FullTransformationSemigroup.

gap> FullTransformationSemigroup( 1234 );
<full transformation monoid of degree 1234>

53.7-4 IsFullTransformationSemigroup
‣ IsFullTransformationSemigroup( S )( property )
‣ IsFullTransformationMonoid( S )( property )

Returns: true or false.

If the transformation semigroup S of degree n contains every transformation of degree at most n, then IsFullTransformationSemigroup returns true and otherwise it returns false.

IsFullTransformationMonoid is a synonym of IsFullTransformationSemigroup. It is common in the literature for the full transformation monoid to be referred to as the full transformation semigroup.

gap> S := Semigroup( AsTransformation( (1,3,4,2), 5 ),
>                    AsTransformation( (1,3,5), 5 ),
>                    Transformation( [ 1, 1, 2, 3, 4 ] ) );
<transformation semigroup of degree 5 with 3 generators>
gap> IsFullTransformationSemigroup( S );
true
gap> S;
<full transformation monoid of degree 5>
gap> IsFullTransformationMonoid( S );
true
gap> S := FullTransformationSemigroup( 5 );;
gap> IsFullTransformationSemigroup( S );
true

53.7-5 IsomorphismTransformationSemigroup
‣ IsomorphismTransformationSemigroup( S )( attribute )
‣ IsomorphismTransformationMonoid( S )( attribute )

Returns: An isomorphism to a transformation semigroup or monoid.

Returns an isomorphism from the finite semigroup S to a transformation semigroup. For most types of objects in GAP the degree of this transformation semigroup will be equal to the size of S plus 1.

Let S ^ 1 denote the monoid obtained from S by adjoining an identity element. Then S acts faithfully on S ^ 1 by right multiplication, i.e. every element of S describes a transformation on 1, .. , |S| + 1. The isomorphism from S to the transformation semigroup described in this way is called the right regular representation of S. In most cases, IsomorphismTransformationSemigroup will return the right regular representation of S.

As exceptions, if S is a permutation group or a partial perm semigroup, then the elements of S act naturally and faithfully by transformations on the values from 1 to the largest moved point of S.

If S is a finitely presented semigroup, then the Todd-Coxeter approach will be attempted.

IsomorphismTransformationMonoid differs from IsomorphismTransformationSemigroup only in that its range is a transformation monoid, and not only a semigroup, when the semigroup S is a monoid.

gap> S := Semigroup( [ [ [ Z(3), 0*Z(3) ], [ 0*Z(3), Z(3) ^ 0 ] ],
>  [ [ Z(3), Z(3)^0 ], [ Z(3), 0*Z(3) ] ],
>  [ [ Z(3)^0, 0*Z(3) ], [ 0*Z(3), 0*Z(3) ] ] ] );;
gap> Size( S );
81
gap> IsomorphismTransformationSemigroup( S );;
gap> S := SymmetricInverseSemigroup( 4 );
<symmetric inverse monoid of degree 4>
gap> IsomorphismTransformationMonoid( S );
MappingByFunction( <symmetric inverse monoid of degree 4>,
<transformation monoid of degree 5 with 4 generators>
 , function( x ) ... end, <Operation "AsPartialPerm"> )
gap> G := Group( (1,2,3) );
Group([ (1,2,3) ])
gap> IsomorphismTransformationMonoid( G );
MappingByFunction( Group([ (1,2,3) ]), <commutative transformation
 monoid of degree 3 with 1 generator>
 , function( x ) ... end, function( x ) ... end )

53.7-6 AntiIsomorphismTransformationSemigroup
‣ AntiIsomorphismTransformationSemigroup( S )( attribute )

Returns: An anti-isomorphism.

If S is a semigroup, then AntiIsomorphismTransformationSemigroup returns an anti-isomorphism from S to a transformation semigroup. At present, the degree of the resulting transformation semigroup equals the size of S plus 1, and, consequently, this function is of limited use.

gap> S := Semigroup( Transformation( [ 5, 5, 1, 1, 3 ] ),
>                    Transformation( [ 2, 4, 1, 5, 5 ] ) );
<transformation semigroup of degree 5 with 2 generators>
gap> Size( S );
172
gap> AntiIsomorphismTransformationSemigroup( S );
MappingByFunction( <transformation semigroup of size 172, degree 5
 with 2 generators>, <transformation semigroup of degree 173 with 2
 generators>, function( x ) ... end, function( x ) ... end )
 [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