# 90 Transformation Monoids

A transformation monoid is a monoid of transformations of n points (see chapter Transformations). These monoids occur for example in the theory of finite state automata and as the results of enumerations of finitely presented monoids. In the theory of semigroups and monoids they play to some extend the role that is taken by permutation groups in group theory. In fact, there are close relations between permutation groups and transformation monoids. One of these relations is manifested by the Schaccent127utzenberger group of an element of a transformation monoid, which is represented as a permutation group rather than a group of transformations. Another relation which is used by most functions that deal with transformation monoids is the fact that a transformation monoid can be efficiently described in terms of several permutation groups (for details see~LPRR1 and~LPRR2).

This chapter describes the functions that deal with transformation monoids.

The chapter starts with the description of the function that tests whether or not a given object is a transformation monoid (see IsTransMonoid). Then there is the function that determines the degree of a transformation monoid (see Degree of a Transformation Monoid).

There are a function to construct the full transformation monoid of degree n (see FullTransMonoid) and a function to construct the monoid of all partial transformations of degree n (see PartialTransMonoid).

Then there are a function that determines all images of a transformation monoid (see ImagesTransMonoid) and a function that determines all kernels of a transformation monoid (see KernelsTransMonoid).

Because each transformation monoid is a domain all set theoretic Set Functions for Transformation Monoids). Also because a transformation monoid is after all a monoid all monoid functions can be applied to it Monoid Functions for Transformation Monoids).

Next the functions that determine Green classes in transformation monoids D Classes for Transformation Monoids).

Finally, there is a section about how a transformation monoid is displayed (see Display a Transformation Monoid). The last section in this chapter describes how transformation monoids are represented as records in GAP (see Transformation Monoid Records).

The functions described here are in the file `"monotran.g"`.

## 90.1 IsTransMonoid

`IsTransMonoid( obj )`

`IsTransMonoid` returns `true` if the object obj, which may be an object of an arbitrary type, is a transformation monoid, and `false` otherwise. It will signal an error if obj is an unbound variable.

```    gap> IsTransMonoid( Monoid( [ Transformation( [ 1, 2, 1 ] ) ] ) );
true
gap> IsTransMonoid( Group( (1,2), (1,2,3,4) ) );
false
gap> IsTransMonoid( [ 1, 2, 1 ] );
false ```

## 90.2 Degree of a Transformation Monoid

`Degree( M )`

`Degree` returns the degree of a transformation monoid M, which is the common degree of all the generators of M.

```    gap> Degree( Monoid( Transformation( [ 1, 2, 1 ] ) ) );
3 ```

The degree of a transformation monoid is the number of points it acts upon.

## 90.3 FullTransMonoid

`FullTransMonoid( n )`

`FullTransMonoid` returns the full transformation monoid of degree n.

```    gap> M:= FullTransMonoid( 8 );
Monoid( [ Transformation( [ 2, 1, 3, 4, 5, 6, 7, 8 ] ),
Transformation( [ 8, 1, 2, 3, 4, 5, 6, 7 ] ),
Transformation( [ 2, 2, 3, 4, 5, 6, 7, 8 ] ) ] )
gap> Size( M );
16777216 ```

The full transformation monoid of degree n is the monoid of all transformations of degree n.

## 90.4 PartialTransMonoid

`PartialTransMonoid( n )`

`PartialTransMonoid` returns the monoid of partial transformations of degree n.

```    gap> M:= PartialTransMonoid( 8 );
Monoid( [ Transformation( [ 2, 1, 3, 4, 5, 6, 7, 8, 9 ] ),
Transformation( [ 8, 1, 2, 3, 4, 5, 6, 7, 9 ] ),
Transformation( [ 9, 2, 3, 4, 5, 6, 7, 8, 9 ] ),
Transformation( [ 2, 2, 3, 4, 5, 6, 7, 8, 9 ] ) ] )
gap> Size( M );
1000000000 ```
A partial transformation of degree n is a mapping from {1, ..., n} to itself where every point i in {1, ..., n} has at most one image. Here the undefined point is represented by n+1.

## 90.5 ImagesTransMonoid

`ImagesTransMonoid( M )`

`ImagesTransMonoid` returns the set of images of all elements of the transformation monoid M (see Image of a Transformation).

```    gap> M:= Monoid( Transformation( [ 1, 4, 4, 2 ] ),
>       Transformation( [ 2, 4, 4, 4 ] ) );;
gap> ImagesTransMonoid(M);
[ [ 1, 2, 3, 4 ], [ 1, 2, 4 ], [ 2 ], [ 2, 4 ], [ 4 ] ] ```

## 90.6 KernelsTransMonoid

`KernelsTransMonoid( M )`

`KernelsTransMonoid` returns the set of kernels of all elements of the transformation monoid M (see Kernel of a Transformation).

```    gap> M:= Monoid( [ Transformation( [ 1, 4, 4, 2 ] ),
>       Transformation( [ 2, 4, 4, 4 ] ) ] );;
gap> KernelsTransMonoid(M);
[ [ [ 1 ], [ 2 ], [ 3 ], [ 4 ] ], [ [ 1 ], [ 2, 3 ], [ 4 ] ],
[ [ 1 ], [ 2, 3, 4 ] ], [ [ 1, 2, 3, 4 ] ] ] ```

## 90.7 Set Functions for Transformation Monoids

All set theoretic functions described in chapter "Domains" are also applicable to transformation monoids. This section describes which functions are implemented specially for transformation monoids. Functions not mentioned here are handled by the default methods described in the respective sections of chapter "Domains".

`Size( M )`

`Size` calls `RClasses` (see RClasses), if necessary, and returns the sum of the sizes of all R classes of M.

```    gap> Size( Monoid( Transformation( [ 1, 2, 1 ] ) ) );
2 ```

`Elements( M )`

`Elements` calls `RClasses` (see RClasses) if necessary, and returns the union of the elements of all R classes of M.

```    gap> Elements( Monoid( Transformation( [ 1, 2, 1 ] ) ) );
[ Transformation( [ 1, 2, 1 ] ), Transformation( [ 1 .. 3 ] ) ] ```

`obj in M`

The membership test of elements of transformation monoids first checks whether obj is a transformation in the first place (see Degree of a Transformation Monoid). Then the image and the kernel of obj is used to locate the possible R class of obj in M and the membership test is delegated to that R class (see Set Functions for Green Classes).

```    gap> M:= Monoid( Transformation( [ 1, 2, 1 ] ) );;
gap> (1,2,3) in M;
false
gap> Transformation( [ 1, 2, 1 ] ) in M;
true
gap> Transformation( [ 1, 2, 2 ] ) in M;
false
gap> Transformation( [ 1, 2, 1, 4 ] ) in M;
false ```

## 90.8 Monoid Functions for Transformation Monoids

All functions described in chapter Monoids and Semigroups can be applied to transformation monoids.

Green classes are special subsets of a transformation monoid. In particular, they are domains so all set theoretic functions for domains (see chapter "Domains") can be applied to Green classes. This is described in Set Functions for Green Classes. Single Green classes of a transformation monoid are constructed by the functions `RClass` (see RClass and R Classes for Transformation Monoids), `LClass` (see LClass and L Classes for Transformation Monoids), `DClass` (see DClass and D Classes for Transformation Monoids), and `HClass` (see HClass and H Classes for Transformation Monoids). The list of all Green classes of a given type in a transformation monoid is constructed by the functions `RClasses` (see RClasses), `LClasses` (see LClasses), `DClasses` (see DClasses), and `HClasses` (see HClasses).

## 90.9 SchutzenbergerGroup for Transformation Monoids

`SchutzenbergerGroup( M, s )`
`SchutzenbergerGroup( class )`

`SchutzenbergerGroup` returns the Schaccent127utzenberger group of the element s in the transformation monoid M as a permutation group on the image of s.

In the second form `SchutzenbergerGroup` returns the Schaccent127utzenberger group of the Green class class of a transformation monoid, where class is either an H class, an R class or a D class. The Schaccent127utzenberger group of an H class class is the same as the Schaccent127utzenberger group of class. The Schaccent127utzenberger group of an R class class is the generalised right Schaccent127utzenberger group of the representative of class and the Schaccent127utzenberger group of an L class class is the generalised left Schaccent127utzenberger group of the representative of class. Note that the Schaccent127utzenberger of an R class is only unique up to conjugation.

## 90.10 H Classes for Transformation Monoids

In addition to the usual components of an H class record, the record representing the H class hClass of s in a transformation monoid can have the following components. They are created by the function `SchutzenbergerGroup` (see SchutzenbergerGroup) which is called whenever the size, the list of elements of hClass, or a membership test in hClass is asked for.

`schutzenbergerGroup`:

set to the Schaccent127utzenberger group of hClass as a permutation group on the set of images of SchutzenbergerGroup for Transformation Monoids).

`R`:

the R class of `hClass.representative.`

`L`:

the L class of `hClass.representative.` The following functions have a special implementation in terms of these components.

`Size( hClass )`

returns the size of the H class hClass. This function calls `SchutzenbergerGroup` and determines the size of hClass as the size of the resulting group.

`Elements( hClass )`

returns the set of elements of the H class hClass. This function calls `SchutzenbergerGroup` and determines the set of elements of hClass as the set of elements of the resulting group multiplied by the representative of hClass.

`x in hClass`

returns `true` if x is an element of the H class hClass and `false` otherwise. This function calls `SchutzenbergerGroup` and tests whether the quotient of the representative of hClass and x (see PermLeftQuoTrans) is in the resulting group.

## 90.11 R Classes for Transformation Monoids

In addition to the usual components of an R class record, the record representing the R class rClass of s in a transformation monoid can have the following components. They are created by the function `SchutzenbergerGroup` (see SchutzenbergerGroup) which is called whenever the size, the list of elements of rClass, or a membership test in rClass is asked for.

`schutzenbergerGroup`:

set to the Schaccent127utzenberger group of rClass as a permutation group on the set of images of SchutzenbergerGroup for Transformation Monoids). `images`:
is the list of different image sets occurring in the R class rClass. The first entry in this list is the image set of `rClass.representative`. `rMults`:
is a list of permutations such that the product of the representative of rClass and the inverse of the ith entry in the list yields an element of rClass whose image set is the ith entry in the list `rClass.images`.

The following functions have a special implementation in terms of these components.

`Size( rClass )`

returns the size of the R class rClass. This function calls `SchutzenbergerGroup` and determines the size of rClass as the size of the resulting group times the length of the list `rClass.images`.

`Elements( rClass )`

returns the set of elements of the R class rClass. This function calls `SchutzenbergerGroup` and determines the set of elements of rClass as the set of elements of the resulting group multiplied by the representative of rClass and each single permutation in the list `rClass.rMults`.

`x in rClass`

returns `true` if x is an element of the R class rClass and `false` otherwise. This function calls `SchutzenbergerGroup` and tests whether the quotient of the representative of rClass and ```x * rClass.rMults[i]``` (see PermLeftQuoTrans) is in the resulting group where i is the position of the image set of x in `rClass.images`.

`HClasses( rClass )`

returns the list of H classes contained in the R class rClass.

## 90.12 L Classes for Transformation Monoids

In addition to the usual components of an L class record, the record representing the L class lClass of s in a transformation monoid can have the following components. They are created by the function `SchutzenbergerGroup` (see SchutzenbergerGroup) which is called whenever the size, the list of elements of lClass, or a membership test in lClass is asked for.

`schutzenbergerGroup`:

set to the Schaccent127utzenberger group of lClass as a permutation group on the set of images of SchutzenbergerGroup for Transformation Monoids). `kernels`:
is the list of different kernels occurring in the L class lClass. The first entry in this list is the kernel of `rClass.representative`. `lMults`:
is a list of binary relations such that the product of the inverse of the ith entry in the list and the representative of rClass yields an element of rClass whose kernel is the ith entry in the list `rClass.kernels`.

The following functions have a special implementation in terms of these components.

`Size( lClass )`

returns the size of the L class lClass. This function calls `SchutzenbergerGroup` and determines the size of lClass as the size of the resulting group times the length of the list `lClass.kernels`.

`Elements( lClass )`

returns the set of elements of the L class lClass. This function calls `SchutzenbergerGroup` and determines the set of elements of lClass as the set of elements of the resulting group premultiplied by the representative of lClass and each single binary relation in the list `lClass.lMults`.

`x in lClass`

returns `true` if x is an element of the L class lClass and `false` otherwise. This function calls `SchutzenbergerGroup` and tests whether the quotient of the representative of lClass and ```lClass.lMults[i] * x``` (see PermLeftQuoTrans) is in the resulting group where i is the position of the kernel of x in `lClass.kernels`.

`HClasses( lClass )`

returns the list of H classes contained in the L class lClass.

## 90.13 D Classes for Transformation Monoids

In addition to the usual components of a D class record, the record representing the D class dClass of s in a transformation monoid can have the following components. They are created by the function `SchutzenbergerGroup` (see SchutzenbergerGroup) which is called whenever the size, the list of elements of dClass, or a membership test in dClass is asked for.

`schutzenbergerGroup`:

set to the Schaccent127utzenberger group of dClass as a permutation group on the set of images of SchutzenbergerGroup for Transformation Monoids). `H`:
set to the H class of `dClass.representative`.

`L`:

set to the L class of `dClass.representative`.

`R`:

set to the R class of `dClass.representative`. `rCosets`:
contains a list of (right) coset representatives of the Schaccent127utzenberger group of dClass in the Schaccent127utzenberger group of the R class `dClass.R`.

The following functions have a special implementation in terms of these components.

`Size( dClass )`

returns the size of the D class dClass. This function calls `SchutzenbergerGroup` and determines the size of dClass in terms of the sizes of the resulting group and the Schaccent127utzenberger groups of the R class `dClass.R` and the L class `dClass.L`.

`Elements( dClass )`

returns the set of elements of the D class dClass. This function calls `SchutzenbergerGroup` and determines the set of elements of dClass as the union of cosets of the Schaccent127utzenberger group of the L class `dClass.L` determined through the multipliers `dClass.rCosets` and `dClass.R.rMults`.

`x in dClass`

returns `true` if x is an element of the D class dClass and `false` otherwise. This function calls `SchutzenbergerGroup` and tests whether the quotient of the representative of dClass and a suitable translate of x can be found in one of the cosets of the Schaccent127utzenberger group of the L class `dClass.L` determined by the list `dClass.rCosets`.

`HClasses( dClass )`

returns the list of H classes contained in the D class dClass.

`LClasses( dClass )`

returns the list of L classes contained in the D class dClass.

`RClasses( dClass )`

returns the list of R classes contained in the D class dClass.

## 90.14 Display a Transformation Monoid

`Display( M )`

`Display` displays the Green class structure of the transformation monoid M. Each D class is displayed as its index in the list of all D classes followed by some information about its structure in parenthesis. A D class displayed as

`[a.b.d]`

is a regular D class with a Schaccent127utzenberger group of size a, consisting of b L classes, or d R classes. A D class displayed as

`{a.bxc.dxe}`

is a nonregular D class with a Schaccent127utzenberger group of size a, consisting of <b> times <c> L classes (of which c have the same kernel), or <d> times <e> R classes (of which e have the same image).

```    gap> M:= Monoid( Transformation( [ 7, 7, 1, 1, 5, 6, 5, 5 ] ),
> Transformation( [ 3, 8, 3, 7, 4, 6, 4, 5 ] ) );;
gap> Size( M );
27
gap> Display( M );
Rank 8: 1[1.1.1]
Rank 6: 3{1.1x1.1x1}
Rank 5: 6{1.1x1.1x1}
Rank 4: 2{1.1x1.1x1} 8[2.1.1]
Rank 3: 4{1.1x1.4x1} 5[1.3.4]
Rank 2: 7[1.5.1] ```

The partial order of D classes (see PartialOrderDClasses) is determined in terms of the indices that serve as names of D classes for `Display`.

```    gap> HasseDiagram(PartialOrderDClasses(M));
Relation( [ [ 2, 3 ], [ 5 ], [ 6 ], [ 7 ], [ 4 ], [ 8 ], [  ],
[ 5 ] ] ) ```

## 90.15 Transformation Monoid Records

Monoid Records and Semigroup Records) the record representing a transformation monoid M has a component

`isTransMonoid`:

which is always set to `true`. Moreover, such a record will (after a while) acquire the following components.

`orbitClasses`:

a list of R classes of M such that every orbit of image sets is represented exactly once.

`images`:

the list of lists where `images[ k ]` is the list of all different image sets of size k of the elements of M. `imagePos`:
stores the relation between `orbitClasses` and `images`. The image set `images[k][l]` occurs in the orbit of the R class with index `imagePos[k][l]` in the list `orbitClasses`. `rClassReps`:
a list of lists, where `rClassReps[l]` contains the complete list of representatives of the R classes with the same image orbit as the R class `orbitClasses[l]`. `lTrans`:
a list of lists, where `lTrans[l][k]` is a transformation alpha such that `lTrans[l][k] * rClassReps[l][k]` is an element of the R class `orbitClasses[l]`. `kernels`:
a list of lists, where `kernels[l][k]` is the common kernel of the elements in the R class of `rClassReps[l][k]`.

GAP 3.4.4
April 1997