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 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 (i, j) 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 and value n, there is a unique transformation 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 and a cycle is just a cycle (or strongly connected 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, \ldots, 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, \ldots, 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 of the points in i less than some value, which is at least the degree of f and which is determined at the time of creation. 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.
‣ 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.
‣ IsTransformationCollection( obj ) | ( category ) |
Every collection of transformations belongs to the category IsTransformationCollection. For example, transformation semigroups belong to IsTransformationCollection.
‣ TransformationFamily | ( family ) |
The family of all transformations is TransformationFamily.
There are several ways of creating transformations in GAP, which are described in this section.
‣ Transformation( list ) | ( operation ) |
‣ Transformation( list, func ) | ( operation ) |
‣ TransformationList( list ) | ( operation ) |
Returns: A transformation or fail.
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. TransformationList will return fail 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)].
This 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");
‣ Transformation( src, dst ) | ( operation ) |
‣ TransformationListList( src, dst ) | ( operation ) |
Returns: A transformation or fail.
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.
This 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 ] )
‣ TransformationByImageAndKernel( im, ker ) | ( operation ) |
Returns: A transformation or fail.
Transformation returns the transformation f 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 ] )
‣ 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 ] )
‣ 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 (Reference: Permutation for a group, an action domain, etc.).
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 ] )
‣ 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 ] )
‣ 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 ] )
‣ IdentityTransformation | ( global variable ) |
Returns: The identity transformation.
Returns the identity transformation, which has degree 0.
gap> f:=IdentityTransformation; IdentityTransformation
‣ 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 ] )
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-5) 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.
‣ AsTransformation( f[, n] ) | ( attribute ) |
Returns: A transformation.
AsTransformation returns the permutation, transformation, partial permutation or binary relation f as a transformation.
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).
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 equals a is greater than or equal to the degree of f, then f is returned.
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.
In the case that f is a binary relation, which defines a transformation, then 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
‣ RestrictedTransformation( f, list ) | ( operation ) |
‣ RestrictedTransformationNC( f, list ) | ( operation ) |
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.
RestrictedTransformation checks that list is a duplicate free dense list consisting of positive integers, whereas RestrictedTransformationNC performs no checks.
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 ] )
‣ PermutationOfImage( f ) | ( attribute ) |
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)
i ^ freturns the image of the positive integer i under the transformation f.
f ^ greturns g^-1*f*g when f is a transformation and g is a permutation \^ (Reference: ^). 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 produce with f, and then the product with g.
f * greturns 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.
f / greturns 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 produce with f.
LQUO(g, f)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 produce with f.
f < greturns true if the image list of f is lexicographically less than the image list of g and false if it is not.
f = greturns true if the transformation f equals the transformation g and returns false if it does not.
‣ PermLeftQuoTransformation( f, g ) | ( operation ) |
‣ PermLeftQuoTransformationNC( f, g ) | ( operation ) |
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)
‣ IsInjectiveListTrans( obj, list ) | ( operation ) |
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
‣ 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 ]
‣ 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 ]
In this section we describe the functions available in GAP for finding various properties and attributes of transformations.
‣ 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 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
‣ 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 ]
‣ 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 ]
‣ 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
‣ 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); [ ]
‣ 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
‣ 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
‣ 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
‣ 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
‣ 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
‣ 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 defualt.
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 ]
‣ 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 ] ]
‣ InverseOfTransformation( f ) | ( operation ) |
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 in a full transformation semigroup.
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 ] )
‣ 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 ] )
‣ IndexPeriodOfTransformation( f ) | ( attribute ) |
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 ]
‣ 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
‣ 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, 4, 6, 9 ], [ 2, 3, 5, 7, 10, 11, 12 ], [ 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, 2, 4, 5, 8, 10, 11 ], [ 3, 7 ], [ 6 ], [ 9, 12 ] ]
‣ 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
‣ 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 ] ]
‣ CyclesOfTransformation( f[, list] ) | ( attribute ) |
Returns: A list of lists of positive integers.
When the arguments of this function are a transformationf 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 ] ]
‣ 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 ]
‣ 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
‣ 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 has belongs to IsTrans4Rep and has its images stored 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.
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
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 degree n 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:
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.
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>
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.
‣ 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).
‣ 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
‣ 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>
‣ 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 return 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
‣ 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> gens := [ [ [ 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> S := Semigroup(gens);; gap> Size(S); 81 gap> IsomorphismTransformationSemigroup(S);; gap> S := SymmetricInverseSemigroup(4); <symmetric inverse semigroup on 4 pts> gap> IsomorphismTransformationMonoid(S); MappingByFunction( <symmetric inverse semigroup on 4 pts>, <transformation monoid on 5 pts 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 on 3 pts with 1 generator> , function( x ) ... end, function( x ) ... end )
‣ 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 )
generated by GAPDoc2HTML