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

53 Transformations

53.5 Attributes for transformations

53.5-1 DegreeOfTransformation

53.5-2 ImageListOfTransformation

53.5-3 ImageSetOfTransformation

53.5-4 RankOfTransformation

53.5-5 MovedPoints

53.5-6 NrMovedPoints

53.5-7 SmallestMovedPoint

53.5-8 LargestMovedPoint

53.5-9 SmallestImageOfMovedPoint

53.5-10 LargestImageOfMovedPoint

53.5-11 FlatKernelOfTransformation

53.5-12 KernelOfTransformation

53.5-13 InverseOfTransformation

53.5-14 Inverse

53.5-15 IndexPeriodOfTransformation

53.5-16 SmallestIdempotentPower

53.5-17 ComponentsOfTransformation

53.5-18 NrComponentsOfTransformation

53.5-19 ComponentRepsOfTransformation

53.5-20 CyclesOfTransformation

53.5-21 CycleTransformationInt

53.5-22 LeftOne

53.5-23 TrimTransformation

53.5-1 DegreeOfTransformation

53.5-2 ImageListOfTransformation

53.5-3 ImageSetOfTransformation

53.5-4 RankOfTransformation

53.5-5 MovedPoints

53.5-6 NrMovedPoints

53.5-7 SmallestMovedPoint

53.5-8 LargestMovedPoint

53.5-9 SmallestImageOfMovedPoint

53.5-10 LargestImageOfMovedPoint

53.5-11 FlatKernelOfTransformation

53.5-12 KernelOfTransformation

53.5-13 InverseOfTransformation

53.5-14 Inverse

53.5-15 IndexPeriodOfTransformation

53.5-16 SmallestIdempotentPower

53.5-17 ComponentsOfTransformation

53.5-18 NrComponentsOfTransformation

53.5-19 ComponentRepsOfTransformation

53.5-20 CyclesOfTransformation

53.5-21 CycleTransformationInt

53.5-22 LeftOne

53.5-23 TrimTransformation

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 `i`

th 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.

`‣ 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.

`TransformationList`

returns the transformation `f`

such that `i ^ `

if `f` = `list`[i]`i`

is between `1`

and the length of `list` and `i ^ `

if `f` = i`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

if `list`[i] ^ f = `func`( `list`[i] )`i`

is in the range `[ 1 .. Length( `

and `list` ) ]`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.

If `src` and `dst` are lists of positive integers of the same length, such that `src` contains no element twice, then `TransformationListList( `

returns a transformation `src`, `dst` )`f`

such that `src[i] ^ `

. The transformation `f` = dst[i]`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 ] )

`‣ TransformationByImageAndKernel` ( im, ker ) | ( operation ) |

Returns: A transformation or `fail`

.

This operation returns the transformation `f`

where `i ^ f = `

for `im`[`ker`[i]]`i`

in the range `[ 1 .. Length( `

. This transformation has flat kernel equal to `ker` ) ]`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`

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

`‣ 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

, then `n` ^ `n``TransformationNumber`

returns the `m`th 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 .. `

that corresponds to `n` ^ `n` ]`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 ) |

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

.

gap> IdentityTransformation; IdentityTransformation

`‣ ConstantTransformation` ( m, n ) | ( operation ) |

Returns: A transformation.

This function returns a constant transformation `f`

such that `i ^ f = `

for all `n``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-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.

`‣ 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(`

returns the transformation`f`,`n`)`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 ..`

, then`n`]`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 ^`

for all`f``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(`

returns the transformation`f`)`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

`‣ RestrictedTransformation` ( f, list ) | ( function ) |

Returns: A transformation.

`RestrictedTransformation`

returns the new transformation `g`

such that ` i ^ g = i ^ `

for all `f``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 ] )

`‣ 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-1 \^`

`‣ \^` ( i, f ) | ( method ) |

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

`53.4-2 \^`

`‣ \^` ( f, g ) | ( method ) |

returns `f` ^ `g`

when `g` ^ -1 * `f` * `g``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 ) |

returns the composition of `f` * `g``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 ) |

returns `f` / `g`

when `f` * `g` ^ -1`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`.

`‣ LeftQuotient` ( g, f ) | ( method ) |

returns

when `g` ^ -1 * `f``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 ) |

returns `f` < `g``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 ) |

returns `f` = `g``true`

if the transformation `f` equals the transformation `g` and returns `false`

if it does not.

`‣ PermLeftQuoTransformation` ( f, g ) | ( operation ) |

`‣ PermLeftQuoTransformationNC` ( f, g ) | ( function ) |

Returns: A permutation.

Returns the permutation on the image set of `f` induced by

when the transformations `f` ^ -1 * `g``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` ( 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 := `

and if `obj``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

for some positive integer `n` ^ `f` ^ j = i`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 ^ `

or `f` <> n`i ^ `

for some `f` = n`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

`‣ ImageListOfTransformation` ( f[, n] ) | ( operation ) |

`‣ ListTransformation` ( f[, n] ) | ( operation ) |

Returns: The list of images of a transformation.

Returns the list of images of `[ 1 .. `

under the transformation `n` ]`f`, which is `[ 1 ^ `

. If the optional second argument `f` .. `n` ^ `f` ]`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 .. `

under `n` ]`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 .. `

. If the optional second argument `n` ]`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 ^ `

if such an `f` <> i`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 ^ `

if such an `f` <> i`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 ^ `

such that `f``i ^ `

if such an `f` <> i`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 ^ `

such that `f``i ^ `

if such an `f` <> i`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 .. `

are K_1, dots, K_r, then `n` ]`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 .. `

as a set of sets of positive integers. If the argument `n` ]`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 ) | ( 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

and `f` * g * `f` = `f``g * `

. Every transformation has at least one inverse.`f` * g = g

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

returns the inverse of `f` ^ -1`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 ) | ( function ) |

Returns: A pair of positive integers.

Returns the least positive integers `m`

and `r`

such that

, which are known as the `f` ^ (m + r) = `f` ^ m*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

is an idempotent. The smallest idempotent power of `f` ^ n`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, 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 ] ]

`‣ 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 ^ (`

. The representatives returned by `f` ^ k) = j`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 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( `

is used as the default value for `f` ) ]`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` 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 ^ `

for all `f` <= n`i`

in the range `[ 1 .. `

otherwise the resulting object will not define a transformation.`n` ]

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 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(`

where`f`, n ) )`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(`

where`f`, n )>`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

elements, and is generated by any set containing transformations that generate the symmetric group on `n` ^ `n``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`

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

`‣ 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

denote the monoid obtained from `S` ^ 1`S` by adjoining an identity element. Then `S` acts faithfully on

by right multiplication, i.e. every element of `S` ^ 1`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 )

`‣ 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 )

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