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

54 Partial permutations

54.3 Attributes for partial permutations

54.3-1 DegreeOfPartialPerm

54.3-2 CodegreeOfPartialPerm

54.3-3 RankOfPartialPerm

54.3-4 DomainOfPartialPerm

54.3-5 ImageOfPartialPermCollection

54.3-6 ImageListOfPartialPerm

54.3-7 ImageSetOfPartialPerm

54.3-8 FixedPointsOfPartialPerm

54.3-9 MovedPoints

54.3-10 NrFixedPoints

54.3-11 NrMovedPoints

54.3-12 SmallestMovedPoint

54.3-13 LargestMovedPoint

54.3-14 SmallestImageOfMovedPoint

54.3-15 LargestImageOfMovedPoint

54.3-16 IndexPeriodOfPartialPerm

54.3-17 SmallestIdempotentPower

54.3-18 ComponentsOfPartialPerm

54.3-19 NrComponentsOfPartialPerm

54.3-20 ComponentRepsOfPartialPerm

54.3-21 LeftOne

54.3-22 One

54.3-23 MultiplicativeZero

54.3-1 DegreeOfPartialPerm

54.3-2 CodegreeOfPartialPerm

54.3-3 RankOfPartialPerm

54.3-4 DomainOfPartialPerm

54.3-5 ImageOfPartialPermCollection

54.3-6 ImageListOfPartialPerm

54.3-7 ImageSetOfPartialPerm

54.3-8 FixedPointsOfPartialPerm

54.3-9 MovedPoints

54.3-10 NrFixedPoints

54.3-11 NrMovedPoints

54.3-12 SmallestMovedPoint

54.3-13 LargestMovedPoint

54.3-14 SmallestImageOfMovedPoint

54.3-15 LargestImageOfMovedPoint

54.3-16 IndexPeriodOfPartialPerm

54.3-17 SmallestIdempotentPower

54.3-18 ComponentsOfPartialPerm

54.3-19 NrComponentsOfPartialPerm

54.3-20 ComponentRepsOfPartialPerm

54.3-21 LeftOne

54.3-22 One

54.3-23 MultiplicativeZero

This chapter describes the functions in **GAP** for partial permutations.

A *partial permutation* in **GAP** is simply an injective function from any finite set of positive integers to any other finite set of positive integers. The largest point on which a partial permutation can be defined, and the largest value that the image of such a point can have, are defined by certain architecture dependent limits.

Every inverse semigroup is isomorphic to an inverse semigroup of partial permutations and, as such, partial permutations are to inverse semigroup theory what permutations are to group theory and transformations are to semigroup theory. In this way, partial permutations are the elements of inverse partial permutation semigroups.

A partial permutations in **GAP** acts on a finite set of positive integers on the right. The image of a point `i`

under a partial permutation `f`

is expressed as `i^f`

in **GAP**. This action is also implemented by the function `OnPoints`

(41.2-1). The preimage of a point `i`

under the partial permutation `f`

can be computed using `i/f`

without constructing the inverse of `f`

. Partial permutations in **GAP** are created using the operations described in Section 54.2. Partial permutations are, by default, displayed in component notation, which is described in Section 54.6.

The fundamental attributes of a partial permutation are:

**Domain**The

*domain*of a partial permutation is just the set of positive integers where it is defined; see`DomainOfPartialPerm`

(54.3-4). We will denote the domain of a partial permutation`f`

by dom(`f`

).**Degree**The

*degree*of a partial permutation`f`

is just the largest positive integer where`f`

is defined. In other words, the degree of`f`

is the largest element in the domain of`f`

; see`DegreeOfPartialPerm`

(54.3-1).**Image list**The

*image list*of a partial permutation`f`

is the list`[i_1^f, i_2^f, .. , i_n^f]`

where the domain of`f`

is`[i_1, i_2, .., i_n]`

see`ImageListOfPartialPerm`

(54.3-6). For example, the partial perm sending`1`

to`5`

and`2`

to`4`

has image list`[ 5, 4 ]`

.**Image set**The

*image set*of a partial permutation`f`

is just the set of points in the image list (i.e. the image list after it has been sorted into increasing order); see`ImageSetOfPartialPerm`

(54.3-7). We will denote the image set of a partial permutation`f`

by im(`f`

).**Codegree**The

*codegree*of a partial permutation`f`

is just the largest positive integer of the form`i^f`

for any`i`

in the domain of`f`

. In other words, the codegree of`f`

is the largest element in the image of`f`

; see`CodegreeOfPartialPerm`

(54.3-2).**Rank**The

*rank*of a partial permutation`f`

is the size of its domain, or equivalently the size of its image set or image list; see`RankOfPartialPerm`

(54.3-3).

A *functional digraph* is a directed graph where every vertex has out-degree `1`

. A partial permutation `f` can be thought of as a functional digraph with vertices `[1..DegreeOfPartialPerm(f)]`

and edges from `i`

to `i^f`

for every `i`

. A *component* of a partial permutation 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, \ldots, v_n=j\) such that either \(v_{k+1}=v_{k}^f\) or \(v_{k}=v_{k+1}^f\) for all `k`

.

If `S`

is a semigroup and `s`

is an element of `S`

, then an element `t`

in `S`

is a *semigroup inverse* for `s`

if `s*t*s=s`

and `t*s*t=t`

; see, for example, `InverseOfTransformation`

(53.5-13). A semigroup in which every element has a unique semigroup inverse is called an *inverse semigroup*.

Every partial permutation belongs to a symmetric inverse monoid; see `SymmetricInverseSemigroup`

(54.7-3). Inverse semigroups of partial permutations are hence inverse subsemigroups of the symmetric inverse monoids.

The inverse `f^-1`

of a partial permutation `f`

is simply the partial permutation that maps `i^f`

to `i`

for all `i`

in the image of `f`

. It follows that the domain of `f^-1`

equals the image of `f`

and that the image of `f^-1`

equals the domain of `f`

. The inverse `f^-1`

is the unique partial permutation with the property that `f*f^-1*f=f`

and `f^-1*f*f^-1=f^-1`

. In other words, `f^-1`

is the unique semigroup inverse of `f`

in the symmetric inverse monoid.

If `f`

and `g`

are partial permutations, then the domain and image of the product are:

\[ \textrm{dom}(fg)=(\textrm{im}(f)\cap \textrm{dom}(g))f^{-1}\textrm{ and } \textrm{im}(fg)=(\textrm{im}(f)\cap \textrm{dom}(g))g \]

A partial permutation is an idempotent if and only if it is the identity function on its domain. The products `f*f^-1`

and `f^-1*f`

are just the identity functions on the domain and image of `f`

, respectively. It follows that `f*f^-1`

is a left identity for `f`

and `f^-1*f`

is a right identity. These products will be referred to here as the *left one* and *right one* of the partial permutation `f`

; see `LeftOne`

(54.3-21). The *one* of a partial permutation is just the identity on the union of its domain and its image, and the *zero* of a partial permutation is just the empty partial permutation; see `One`

(54.3-22) and `MultiplicativeZero`

(54.3-23).

If `S`

is an arbitrary inverse semigroup, the *natural partial order* on `S`

is defined as follows: for elements `x`

and `y`

of `S`

we say `x`

\(\leq\)`y`

if there exists an idempotent element `e`

in `S`

such that `x=ey`

. In the context of the symmetric inverse monoid, a partial permutation `f`

is less than or equal to a partial permutation `g`

in the natural partial order if and only if `f`

is a restriction of `g`

. The natural partial order is a meet semilattice, in other words, every pair of elements has a greatest lower bound; see `MeetOfPartialPerms`

(54.2-5).

Note that unlike permutations, partial permutations do not fix unspecified points but are simply undefined on such points; see Chapter 42. Similar to permutations, and unlike transformations, it is possible to multiply any two partial permutations in **GAP**.

Internally, **GAP** stores a partial permutation `f`

as a list consisting of the codegree of `f`

and the images `i^f`

of the points `i`

that are less than or equal to the degree of `f`

; the value `0`

is stored where `i^f`

is undefined. The domain and image set of `f`

are also stored after either of these values is computed. When the codegree of a partial permutation `f`

is less than 65536, the codegree and images `i^f`

are stored as 16-bit integers, the domain and image set are subobjects of `f`

which are immutable plain lists of **GAP** integers. When the codegree of `f`

is greater than or equal to 65536, the codegree and images are stored as 32-bit integers; the domain and image set are stored in the same way as before. A partial permutation belongs to `IsPPerm2Rep`

if it is stored using 16-bit integers and to `IsPPerm4Rep`

otherwise.

In the names of the **GAP** functions that deal with partial permutations, the word "Permutation" is usually abbreviated to "Perm", to save typing. For example, the category test function for partial permutations is `IsPartialPerm`

(54.1-1).

`‣ IsPartialPerm` ( obj ) | ( category ) |

Returns: `true`

or `false`

.

Every partial permutation in **GAP** belongs to the category `IsPartialPerm`

. Basic operations for partial permutations are `DomainOfPartialPerm`

(54.3-4), `ImageListOfPartialPerm`

(54.3-6), `ImageSetOfPartialPerm`

(54.3-7), `RankOfPartialPerm`

(54.3-3), `DegreeOfPartialPerm`

(54.3-1), multiplication of two partial permutations is via `*`

, and exponentiation with the first argument a positive integer `i`

and second argument a partial permutation `f`

where the result is the image `i^f`

of the point `i`

under `f`

. The inverse of a partial permutation `f`

can be obtains using `f^-1`

.

`‣ IsPartialPermCollection` ( obj ) | ( category ) |

Every collection of partial permutations belongs to the category `IsPartialPermCollection`

. For example, a semigroup of partial permutations belongs in `IsPartialPermCollection`

.

`‣ PartialPermFamily` | ( family ) |

The family of all partial permutations is `PartialPermFamily`

There are several ways of creating partial permutations in **GAP**, which are described in this section.

`‣ PartialPerm` ( dom, img ) | ( function ) |

`‣ PartialPerm` ( list ) | ( function ) |

Returns: A partial permutation.

Partial permutations can be created in two ways: by giving the domain and the image, or the dense image list.

**Domain and image**The partial permutation defined by a domain

`dom`and image`img`, where`dom`is a set of positive integers and`img`is a duplicate free list of positive integers, maps`dom``[i]`

to`img``[i]`

. For example, the partial permutation mapping`1`

and`5`

to`20`

and`2`

can be created using:PartialPerm([1,5],[20,2]);

In this setting,

`PartialPerm`

is the analogue in the context of partial permutations of`MappingPermListList`

(42.5-3).**Dense image list**The partial permutation defined by a dense image list

`list`, maps the positive integer`i`

to`list``[i]`

if`list``[i]<>0`

and is undefined at`i`

if`list``[i]=0`

. For example, the partial permutation mapping`1`

and`5`

to`20`

and`2`

can be created using:PartialPerm([20,0,0,0,2]);

In this setting,

`PartialPerm`

is the analogue in the context of partial permutations of`PermList`

(42.5-2).

Regardless of which of these two methods are used to create a partial permutation in **GAP** the internal representation is the same.

If the largest point in the domain is larger than the rank of the partial permutation, then using the dense image list to define the partial permutation will require less typing; otherwise using the domain and the image will require less typing. For example, the partial permutation mapping `10000`

to `1`

can be defined using:

PartialPerm([10000], [1]);

but using the dense image list would require a list with `9999`

entries equal to `0`

and the final entry equal to `1`

. On the other hand, the identity on `[1,2,3,4,6]`

can be defined using:

PartialPerm([1,2,3,4,0,6]);

Please note that a partial permutation in **GAP** is never a permutation nor is a permutation ever a partial permutation. For example, the permutation `(1,4,2)`

fixes `3`

but the partial permutation `PartialPerm([4,1,0,2]);`

is not defined on `3`

.

`‣ PartialPermOp` ( obj, list[, func] ) | ( operation ) |

`‣ PartialPermOpNC` ( obj, list[, func] ) | ( operation ) |

Returns: A partial permutation or `fail`

.

`PartialPermOp`

returns the partial permutation 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 partial permutation refers to the positions in `list` even if `list` itself consists of integers.

This function is the analogue in the context of partial permutations of `Permutation`

(Reference: Permutation for a group, an action domain, etc.) or `TransformationOp`

(53.2-5).

If `obj` does not map the elements of `list` injectively, then `fail`

is returned.

`PartialPermOpNC`

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

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

`‣ RestrictedPartialPerm` ( f, set ) | ( operation ) |

Returns: A partial permutation.

`RestrictedPartialPerm`

returns a new partial permutation that acts on the points in the set of positive integers `set` in the same way as the partial permutation `f`, and that is undefined on those points that are not in `set`.

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

`‣ JoinOfPartialPerms` ( arg ) | ( function ) |

`‣ JoinOfIdempotentPartialPermsNC` ( arg ) | ( function ) |

Returns: A partial permutation or `fail`

.

The join of partial permutations `f` and `g` is just the join, or supremum, of `f` and `g` under the natural partial ordering of partial permutations.

`JoinOfPartialPerms`

returns the union of the partial permutations in its argument if this defines a partial permutation, and `fail`

if it is not. The argument `arg` can be a partial permutation collection or a number of partial permutations.

The function `JoinOfIdempotentPartialPermsNC`

returns the join of its argument which is assumed to be a collection of idempotent partial permutations or a number of idempotent partial permutations. It is not checked that the arguments are idempotents. The performance of this function is higher than `JoinOfPartialPerms`

when it is known *a priori* that the argument consists of idempotents.

The union of `f` and `g` is a partial permutation if and only if `f` and `g` agree on the intersection dom(`f`)\(\cap\) dom(`g`) of their domains and the images of dom(`f`)\(\setminus\) dom(`g`) and dom(`g`)\(\setminus\) dom(`f`) under `f` and `g`, respectively, are disjoint.

gap> f:=PartialPerm( [ 1, 2, 3, 6, 8, 10 ], [ 2, 6, 7, 9, 1, 5 ] ); [3,7][8,1,2,6,9][10,5] gap> g:=PartialPerm( [ 11, 12, 14, 16, 18, 19 ], > [ 17, 20, 11, 19, 14, 12 ] ); [16,19,12,20][18,14,11,17] gap> JoinOfPartialPerms(f, g); [3,7][8,1,2,6,9][10,5][16,19,12,20][18,14,11,17] gap> f:=PartialPerm( [ 1, 4, 5, 6, 7 ], [ 5, 7, 3, 1, 4 ] ); [6,1,5,3](4,7) gap> g:=PartialPerm( [ 100 ], [ 1 ] ); [100,1] gap> JoinOfPartialPerms(f, g); fail gap> f:=PartialPerm( [ 1, 3, 4 ], [ 3, 2, 4 ] ); [1,3,2](4) gap> g:=PartialPerm( [ 1, 2, 4 ], [ 2, 3, 4 ] ); [1,2,3](4) gap> JoinOfPartialPerms(f, g); fail gap> f:=PartialPerm( [ 1 ], [ 2 ] ); [1,2] gap> JoinOfPartialPerms(f, f^-1); (1,2)

`‣ MeetOfPartialPerms` ( arg ) | ( function ) |

Returns: A partial permutation.

The meet of partial permutations `f` and `g` is just the meet, or infimum, of `f` and `g` under the natural partial ordering of partial permutations. In other words, the meet is the greatest partial permuation which is a restriction of both `f` and `g`.

Note that unlike the join of partial permutations, the meet always exists.

`MeetOfPartialPerms`

returns the meet of the partial permutations in its argument. The argument `arg` can be a partial permutation collection or a number of partial permutations.

gap> f:=PartialPerm( [ 1, 2, 3, 6, 100000 ], [ 2, 6, 7, 1, 5 ] ); [3,7][100000,5](1,2,6) gap> g:=PartialPerm( [ 1, 2, 3, 4, 6 ], [ 2, 4, 6, 1, 5 ] ); [3,6,5](1,2,4) gap> MeetOfPartialPerms(f, g); [1,2] gap> g:=PartialPerm( [ 1, 2, 3, 5, 6, 7, 9, 10 ], > [ 4, 10, 5, 6, 7, 1, 3, 2 ] ); [9,3,5,6,7,1,4](2,10) gap> MeetOfPartialPerms(f, g); <empty partial perm>

`‣ EmptyPartialPerm` ( ) | ( function ) |

Returns: The empty partial permutation.

The empty partial permutation is returned by this function when it is called with no arguments. This is just short hand for `PartialPerm([]);`

.

gap> EmptyPartialPerm(); <empty partial perm>

`‣ RandomPartialPerm` ( n ) | ( function ) |

`‣ RandomPartialPerm` ( set ) | ( function ) |

`‣ RandomPartialPerm` ( dom, img ) | ( function ) |

Returns: A random partial permutation.

In its first form, `RandomPartialPerm`

returns a randomly chosen partial permutation where points in the domain and image are bounded above by the positive integer `n`.

gap> RandomPartialPerm(10); [2,9][4,1,6,5][7,3](8)

In its second form, `RandomPartialPerm`

returns a randomly chosen partial permutation with points in the domain and image contained in the set of positive integers `set`.

gap> RandomPartialPerm([1,2,3,1000]); [2,3,1000](1)

In its third form, `RandomPartialPerm`

creates a randomly chosen partial permutation with domain contained in the set of positive integers `dom` and image contained in the set of positive integers `img`. The arguments `dom` and `img` do not have to have equal length.

Note that it is not guarenteed in either of these cases that partial permutations are chosen with a uniform distribution.

In this section we describe the functions available in **GAP** for finding various attributes of partial permutations.

`‣ DegreeOfPartialPerm` ( f ) | ( function ) |

`‣ DegreeOfPartialPermCollection` ( coll ) | ( attribute ) |

Returns: A non-negative integer.

The *degree* of a partial permutation `f` is the largest positive integer where it is defined, i.e. the maximum element in the domain of `f`.

The degree a collection of partial permutations `coll` is the largest degree of any partial permutation in `coll`.

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

`‣ CodegreeOfPartialPerm` ( f ) | ( function ) |

`‣ CodegreeOfPartialPermCollection` ( coll ) | ( attribute ) |

Returns: A non-negative integer.

The *codegree* of a partial permutation `f` is the largest positive integer in its image.

The codegree a collection of partial permutations `coll` is the largest codegree of any partial permutation in `coll`.

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

`‣ RankOfPartialPerm` ( f ) | ( function ) |

`‣ RankOfPartialPermCollection` ( coll ) | ( attribute ) |

Returns: A non-negative integer.

The *rank* of a partial permutation `f` is the size of its domain, or equivalently the size of its image set or image list.

The rank of a partial permutation collection `coll` is the size of the union of the domains of the elements of `coll`, or equivalently, the total number of points on which the elements of `coll` act. Note that this is value may not the same as the size of the union of the images of the elements in `coll`.

gap> f:=PartialPerm( [ 1, 2, 4, 6, 8, 9 ], [ 7, 10, 1, 9, 4, 2 ] ); [6,9,2,10][8,4,1,7] gap> RankOfPartialPerm(f); 6

`‣ DomainOfPartialPerm` ( f ) | ( attribute ) |

`‣ DomainOfPartialPermCollection` ( f ) | ( attribute ) |

Returns: A set of positive integers (maybe empty).

The *domain* of a partial permutation `f` is the set of positive integers where `f` is defined.

The domain of a partial permutation collection `coll` is the union of the domains of its elements.

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

`‣ ImageOfPartialPermCollection` ( coll ) | ( attribute ) |

Returns: A set of positive integers (maybe empty).

The *image* of a partial permutation collection `coll` is the union of the images of its elements.

gap> S := SymmetricInverseSemigroup(5); <symmetric inverse monoid of degree 5> gap> ImageOfPartialPermCollection(GeneratorsOfInverseSemigroup(S)); [ 1 .. 5 ]

`‣ ImageListOfPartialPerm` ( f ) | ( attribute ) |

Returns: The list of images of a partial permutation.

The *image list* of a partial permutation `f` is the list of images of the elements of the domain `f` where `ImageListOfPartialPerm(`

for any `f`)[i]=DomainOfPartialPerm(`f`)[i]^`f``i`

in the range from `1`

to the rank of `f`.

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

`‣ ImageSetOfPartialPerm` ( f ) | ( attribute ) |

Returns: The image set of a partial permutation.

The *image set* of a partial permutation `f`

is just the set of points in the image list (i.e. the image list after it has been sorted into increasing order).

gap> f:=PartialPerm( [ 1, 2, 3, 5, 7, 10 ], [ 10, 2, 3, 5, 7, 6 ] ); [1,10,6](2)(3)(5)(7) gap> ImageSetOfPartialPerm(f); [ 2, 3, 5, 6, 7, 10 ]

`‣ FixedPointsOfPartialPerm` ( f ) | ( attribute ) |

`‣ FixedPointsOfPartialPerm` ( coll ) | ( method ) |

Returns: A set of positive integers.

`FixedPointsOfPartialPerm`

returns the set of points `i`

in the domain of the partial permutation `f` such that `i^`

.`f`=i

When the argument is a collection of partial permutations `coll`, `FixedPointsOfPartialPerm`

returns the set of points fixed by every element of the collection of partial permutations `coll`.

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

`‣ MovedPoints` ( f ) | ( attribute ) |

`‣ MovedPoints` ( coll ) | ( method ) |

Returns: A set of positive integers.

`MovedPoints`

returns the set of points `i`

in the domain of the partial permutation `f` such that `i^`

.`f`<>i

When the argument is a collection of partial permutations `coll`, `MovedPoints`

returns the set of points moved by some element of the collection of partial permutations `coll`.

gap> f := PartialPerm( [ 1, 2, 3, 4 ], [ 5, 7, 1, 6 ] ); [2,7][3,1,5][4,6] gap> MovedPoints(f); [ 1, 2, 3, 4 ] gap> FixedPointsOfPartialPerm(f); [ ] gap> FixedPointsOfPartialPerm(PartialPerm([1 .. 4])); [ 1, 2, 3, 4 ]

`‣ NrFixedPoints` ( f ) | ( attribute ) |

`‣ NrFixedPoints` ( coll ) | ( method ) |

Returns: A positive integer.

`NrFixedPoints`

returns the number of points `i`

in the domain of the partial permutation `f` such that `i^`

.`f`=i

When the argument is a collection of partial permutations `coll`, `NrFixedPoints`

returns the number of points fixed by every element of the collection of partial permutations `coll`.

gap> f := PartialPerm( [ 1, 2, 3, 4, 5 ], [ 3, 2, 4, 6, 1 ] ); [5,1,3,4,6](2) gap> NrFixedPoints(f); 1 gap> NrFixedPoints(PartialPerm([1 .. 10])); 10

`‣ NrMovedPoints` ( f ) | ( attribute ) |

`‣ NrMovedPoints` ( coll ) | ( method ) |

Returns: A positive integer.

`NrMovedPoints`

returns the number of points `i`

in the domain of the partial permutation `f` such that `i^`

.`f`<>i

When the argument is a collection of partial permutations `coll`, `NrMovedPoints`

returns the number of points moved by some element of the collection of partial permutations `coll`.

gap> f := PartialPerm( [ 1, 2, 3, 4, 5, 7, 8 ], [ 4, 5, 6, 7, 1, 3, 2 ] ); [8,2,5,1,4,7,3,6] gap> NrMovedPoints(f); 7 gap> NrMovedPoints(PartialPerm([1 .. 4])); 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 an identity partial permutation, then `infinity`

is returned.

If the argument is a collection of partial permutations `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 partial permutations, then `SmallestMovedPoint`

returns `infinity`

.

gap> f := PartialPerm( [ 1, 3 ], [ 4, 3 ] ); [1,4](3) gap> SmallestMovedPoint(f); 1 gap> SmallestMovedPoint(PartialPerm([1 .. 10])); infinity

`‣ LargestMovedPoint` ( f ) | ( attribute ) |

`‣ LargestMovedPoint` ( coll ) | ( method ) |

Returns: A positive integer or `infinity`

.

`LargestMovedPoint`

returns the largest positive integers `i`

such that `i^`

if such an `f`<>i`i`

exists. If `f` is the identity partial permutation, then `0`

is returned.

If the argument is a collection of partial permutations `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 partial permutations, then `LargestMovedPoint`

returns `0`

.

gap> f := PartialPerm( [ 1, 3, 4, 5 ], [ 5, 1, 6, 4 ] ); [3,1,5,4,6] gap> LargestMovedPoint(f); 5 gap> LargestMovedPoint(PartialPerm([1 .. 10])); 0

`‣ 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 partial permutation, then `infinity`

is returned.

If the argument is a collection of partial permutations `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 partial permutations, then `SmallestImageOfMovedPoint`

returns `infinity`

.

gap> S := SymmetricInverseSemigroup(5); <symmetric inverse monoid of degree 5> gap> SmallestImageOfMovedPoint(S); 1 gap> S := Semigroup(PartialPerm([10 .. 100], [10 .. 100]));; gap> SmallestImageOfMovedPoint(S); infinity gap> f := PartialPerm( [ 1, 2, 3, 6 ] ); [4,6](1)(2)(3) 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 an identity partial permutation, then `0`

is returned.

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

returns `0`

.

gap> S := SymmetricInverseSemigroup(5); <symmetric inverse monoid of degree 5> gap> LargestImageOfMovedPoint(S); 5 gap> S := Semigroup(PartialPerm([10 .. 100], [10 .. 100]));; gap> LargestImageOfMovedPoint(S); 0 gap> f := PartialPerm( [ 1, 2, 3, 6 ] );; gap> LargestImageOfMovedPoint(f); 6

`‣ IndexPeriodOfPartialPerm` ( f ) | ( attribute ) |

Returns: A pair of positive integers.

Returns the least positive integers `m, r`

such that

, which are known as the `f`^(m+r)=`f`^m*index* and *period* of the partial permutation `f`.

gap> f:=PartialPerm( [ 1, 2, 3, 5, 6, 7, 8, 11, 12, 16, 19 ], > [ 9, 18, 20, 11, 5, 16, 8, 19, 14, 13, 1 ] ); [2,18][3,20][6,5,11,19,1,9][7,16,13][12,14](8) gap> IndexPeriodOfPartialPerm(f); [ 6, 1 ] gap> f^6=f^7; true

`‣ SmallestIdempotentPower` ( f ) | ( attribute ) |

Returns: A positive integer.

This function returns the least positive integer `n`

such that the partial permutation

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

(54.3-16).

gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 18, 19, 20 ], > [ 5, 1, 7, 3, 10, 2, 12, 14, 11, 16, 6, 9, 15 ] ); [4,3,7,2,1,5,10,14][8,12][13,16][18,6][19,9][20,15](11) gap> SmallestIdempotentPower(f); 8 gap> f^8; <identity partial perm on [ 11 ]>

`‣ ComponentsOfPartialPerm` ( f ) | ( attribute ) |

Returns: A list of lists of positive integer.

`ComponentsOfPartialPerm`

returns a list of the components of the partial permutation `f`. Each component is a subset of the domain of `f`, and the union of the components equals the domain.

gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 7, 8, 10, 11, 12, 13, 19 ], > [ 20, 4, 6, 19, 9, 14, 3, 12, 17, 5, 15, 13 ] ); [1,20][2,4,19,13,15][7,14][8,3,6][10,12,5,9][11,17] gap> ComponentsOfPartialPerm(f); [ [ 1, 20 ], [ 2, 4, 19, 13, 15 ], [ 7, 14 ], [ 8, 3, 6 ], [ 10, 12, 5, 9 ], [ 11, 17 ] ]

`‣ NrComponentsOfPartialPerm` ( f ) | ( attribute ) |

Returns: A positive integer.

`NrComponentsOfPartialPerm`

returns the number of components of the partial permutation `f` on its domain.

gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 7, 8, 10, 11, 12, 13, 19 ], > [ 20, 4, 6, 19, 9, 14, 3, 12, 17, 5, 15, 13 ] ); [1,20][2,4,19,13,15][7,14][8,3,6][10,12,5,9][11,17] gap> NrComponentsOfPartialPerm(f); 6

`‣ ComponentRepsOfPartialPerm` ( f ) | ( attribute ) |

Returns: A list of positive integers.

`ComponentRepsOfPartialPerm`

returns the representatives, in the following sense, of the components of the partial permutation `f`. Every component of `f` contains a unique element in the domain but not the image of `f`; this element is called the *representative* of the component. If `i`

is a representative of a component of `f`, then for every `j`

\(\not=\)`i`

in the component of `i`

, there exists a positive integer `k`

such that `i ^ (`

. Unlike transformations, there is exactly one representative for every component of `f` ^ k) = j`f`. `ComponentRepsOfPartialPerm`

returns the least number of representatives.

gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 7, 8, 10, 11, 12, 13, 19 ], > [ 20, 4, 6, 19, 9, 14, 3, 12, 17, 5, 15, 13 ] ); [1,20][2,4,19,13,15][7,14][8,3,6][10,12,5,9][11,17] gap> ComponentRepsOfPartialPerm(f); [ 1, 2, 7, 8, 10, 11 ]

`‣ LeftOne` ( f ) | ( attribute ) |

`‣ RightOne` ( f ) | ( attribute ) |

Returns: A partial permutation.

`LeftOne`

returns the identity partial permutation `e`

such that the domain and image of `e`

equal the domain of the partial permutation `f` and such that `e*`

.`f`=f

`RightOne`

returns the identity partial permutation `e`

such that the domain and image of `e`

equal the image of `f` and such that

.`f`*e=f

gap> f:=PartialPerm( [ 1, 2, 4, 5, 6, 7 ], [ 10, 1, 6, 5, 8, 7 ] ); [2,1,10][4,6,8](5)(7) gap> RightOne(f); <identity partial perm on [ 1, 5, 6, 7, 8, 10 ]> gap> LeftOne(f); <identity partial perm on [ 1, 2, 4, 5, 6, 7 ]>

`‣ One` ( f ) | ( method ) |

Returns: A partial permutation.

As described in `OneImmutable`

(Reference: OneImmutable), `One`

returns the multiplicative neutral element of the partial permutation `f`, which is the identity partial permutation on the union of the domain and image of `f`. Equivalently, the one of `f` is the join of the right one and left one of `f`.

gap> f:=PartialPerm([ 1, 2, 3, 4, 5, 7, 10 ], [ 3, 7, 9, 6, 1, 10, 2 ]);; gap> One(f); <identity partial perm on [ 1, 2, 3, 4, 5, 6, 7, 9, 10 ]>

`‣ MultiplicativeZero` ( f ) | ( method ) |

Returns: The empty partial permutation.

As described in `MultiplicativeZero`

(Reference: MultiplicativeZero), `Zero`

returns the multiplicative zero element of the partial permutation `f`, which is the empty partial permutation.

gap> f := PartialPerm([ 1, 2, 3, 4, 5, 7, 10 ], [ 3, 7, 9, 6, 1, 10, 2 ]);; gap> MultiplicativeZero(f); <empty partial perm>

It is possible that a partial permutation in **GAP** can be represented by other types of objects, or that other types of **GAP** objects can be represented by partial permutations. Partial permutations which are mathematically permutations can be converted into permutations in **GAP** using the function `AsPermutation`

(42.5-5). Similarly, a partial permutation can be converted into a transformation using `AsTransformation`

(53.3-1).

In this section we describe functions for converting other types of objects in **GAP** into partial permutations.

`‣ AsPartialPerm` ( f, set ) | ( operation ) |

`‣ AsPartialPerm` ( f ) | ( method ) |

`‣ AsPartialPerm` ( f, n ) | ( method ) |

Returns: A partial permutation.

A permutation `f` defines a partial permutation when it is restricted to any finite set of positive integers. `AsPartialPerm`

can be used to obtain this partial permutation.

There are several possible arguments for `AsPartialPerm`

:

**for a permutation and set of positive integers**`AsPartialPerm`

returns the partial permutation that equals`f`on the set of positive integers`set`and that is undefined on every other positive integer.Note that as explained in

`PartialPerm`

(54.2-1)*a permutation is never a partial permutation*in**GAP**, please keep this in mind when using`AsPartialPerm`

.**for a permutation**`AsPartialPerm`

returns the partial permutation that agrees with`f`on`[1..LargestMovedPoint(`

and that is not defined on any other positive integer.`f`)]**for a permutation and a positive integer**`AsPartialPerm`

returns the partial permutation that agrees with`f`on`[1..`

, when`n`]`n`is a positive integer, and that is not defined on any other positive integer.

The operation `PartialPermOp`

(54.2-2) can also be used to convert permutations into partial permutations.

gap> f:=(2,8,19,9,14,10,20,17,4,13,12,3,5,7,18,16);; gap> AsPartialPerm(f); (1)(2,8,19,9,14,10,20,17,4,13,12,3,5,7,18,16)(6)(11)(15) gap> AsPartialPerm(f, [ 1, 2, 3 ] ); [2,8][3,5](1)

`‣ AsPartialPerm` ( f, set ) | ( operation ) |

`‣ AsPartialPerm` ( f, n ) | ( method ) |

Returns: A partial permutation or `fail`

.

A transformation `f` defines a partial permutation when it is restricted to a set of positive integers where it is injective. `AsPartialPerm`

can be used to obtain this partial permutation.

There are several possible arguments for `AsPartialPerm`

:

**for a transformation and set of positive integers**`AsPartialPerm`

returns the partial permutation obtained by restricting`f`to the set of positive integers`set`when:`set`contains no elements exceeding the degree of`f`;`f`is injective on`set`.

**for a transformation and a positive integer**`AsPartialPerm`

returns the partial permutation that agrees with`f`on`[1..`

when`n`]`A`is a positive integer and this set satisfies the conditions given above.

The operation `PartialPermOp`

(54.2-2) can also be used to convert transformations into partial permutations.

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

`f`^ -1returns the inverse of the partial permutation

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

`i`under the partial permutation`f`if it is defined and`0`

if it is not.`i`/`f`returns the preimage of the positive integer

`i`under the partial permutation`f`if it is defined and`0`

if it is not. Note that the inverse of`f`is not calculated to find the preimage of`i`.`f`^`g`returns

when`g`^-1*`f`*`g``f`is a partial permutation and`g`is a permutation or partial permutation; see`\^`

(31.12-1). This operation requires essentially the same number of steps as multiplying partial permutations, which is around one third as many as inverting and multiplying twice.`f`*`g`returns the composition of

`f`and`g`when`f`and`g`are partial permutations or permutations. The product of a permutation and a partial permutation is returned as a partial permutation.`f`/`g`returns

when`f`*`g`^-1`f`is a partial permutation and`g`is a permutation or partial permutation. This operation requires essentially the same number of steps as multiplying partial permutations, which is approximately half that required to first invert`g`and then take the product with`f`.`LQUO(`

`g`,`f`)returns

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

`true`

if the image of`f`on the range from 1 to the degree of`f`is lexicographically less than the corresponding image for`g`and`false`

if it is not. See`NaturalLeqPartialPerm`

(54.5-4) and`ShortLexLeqPartialPerm`

(54.5-5) for additional orders for partial permutations.`f`=`g`returns

`true`

if the partial permutation`f`equals the partial permutation`g`and returns`false`

if it does not.

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

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

Returns: A permutation.

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

when the partial permutations `f`^-1*`g``f` and `g` have equal domain and image set.

`PermLeftQuoPartialPerm`

verifies that `f` and `g` have equal domains and image sets, and returns an error if they do not. `PermLeftQuoPartialPermNC`

does no checks.

gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 7 ], [ 7, 9, 10, 4, 2, 5 ] ); [1,7,5,2,9][3,10](4) gap> g:=PartialPerm( [ 1, 2, 3, 4, 5, 7 ], [ 7, 4, 9, 2, 5, 10 ] ); [1,7,10][3,9](2,4)(5) gap> PermLeftQuoPartialPerm(f, g); (2,5,10,9,4)

`‣ PreImagePartialPerm` ( f, i ) | ( operation ) |

Returns: A positive integer or `fail`

.

`PreImagePartialPerm`

returns the preimage of the positive integer `i` under the partial permutation `f` if `i` belongs to the image of `f`. If `i` does not belong to the image of `f`, then `fail`

is returned.

The same result can be obtained by using

as described in Section 54.5.`i`/`f`

gap> f:=PartialPerm( [ 1, 2, 3, 5, 9, 10 ], [ 5, 10, 7, 8, 9, 1 ] ); [2,10,1,5,8][3,7](9) gap> PreImagePartialPerm(f, 8); 5 gap> PreImagePartialPerm(f, 5); 1 gap> PreImagePartialPerm(f, 1); 10 gap> PreImagePartialPerm(f, 10); 2 gap> PreImagePartialPerm(f, 2); fail

`‣ ComponentPartialPermInt` ( f, i ) | ( operation ) |

Returns: A set of positive integers.

`ComponentPartialPermInt`

returns the elements of the component of `f` containing `i` that can be obtained by repeatedly applying `f` to `i`.

gap> f:=PartialPerm( [ 1, 2, 4, 5, 6, 7, 8, 10, 14, 15, 16, 17, 18 ], > [ 11, 4, 14, 16, 15, 3, 20, 8, 17, 19, 1, 6, 12 ] ); [2,4,14,17,6,15,19][5,16,1,11][7,3][10,8,20][18,12] gap> ComponentPartialPermInt(f, 4); [ 4, 14, 17, 6, 15, 19 ] gap> ComponentPartialPermInt(f, 3); [ ] gap> ComponentPartialPermInt(f, 10); [ 10, 8, 20 ] gap> ComponentPartialPermInt(f, 100); [ ]

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

Returns: `true`

or `false`

.

The *natural partial order* \(\leq\) on an inverse semigroup `S`

is defined by `s`

\(\leq\)`t`

if there exists an idempotent `e`

in `S`

such that `s=et`

. Hence if `f` and `g` are partial permutations, then `f`\(\leq\)`g` if and only if `f` is a restriction of `g`; see `RestrictedPartialPerm`

(54.2-3).

`NaturalLeqPartialPerm`

returns `true`

if `f` is a restriction of `g` and `false`

if it is not. Note that since this is a partial order and not a total order, it is possible that `f` and `g` are incomparable with respect to the natural partial order.

gap> f:=PartialPerm( > [ 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 16, 17, 18, 19 ], > [ 3, 12, 14, 4, 11, 18, 17, 2, 9, 5, 15, 8, 20, 10, 19 ] );; gap> g:=RestrictedPartialPerm(f, [ 1, 2, 3, 9, 13, 20 ] ); [1,3,14][2,12] gap> NaturalLeqPartialPerm(g,f); true gap> NaturalLeqPartialPerm(f,g); false gap> g:=PartialPerm( [ 1, 2, 3, 4, 5, 8, 10 ], > [ 7, 1, 4, 3, 2, 6, 5 ] );; gap> NaturalLeqPartialPerm(f, g); false gap> NaturalLeqPartialPerm(g, f); false

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

Returns: `true`

or `false`

.

`ShortLexLeqPartialPerm`

returns `true`

if the concatenation of the domain and image list of `f` is short-lex less than the corresponding concatenation for `g` and `false`

otherwise.

Note that this is not the natural partial order on partial permutation or the same as comparing `f` and `g` using `\<`

.

gap> f:=PartialPerm( [ 1, 2, 3, 4, 6, 7, 8, 10 ], > [ 3, 8, 1, 9, 4, 10, 5, 6 ] ); [2,8,5][7,10,6,4,9](1,3) gap> g:=PartialPerm( [ 1, 2, 3, 4, 5, 8, 10 ], > [ 7, 1, 4, 3, 2, 6, 5 ] ); [8,6][10,5,2,1,7](3,4) gap> f<g; true gap> g<f; false gap> ShortLexLeqPartialPerm(f, g); false gap> ShortLexLeqPartialPerm(g, f); true gap> NaturalLeqPartialPerm(f, g); false gap> NaturalLeqPartialPerm(g, f); false

`‣ TrimPartialPerm` ( f ) | ( operation ) |

Returns: Nothing.

It can happen that the internal representation of a partial permutation uses more memory than necessary. For example, by composing a partial permutation with codegree less than 65536 with a partial permutation with codegree greater than 65535. It is possible that the resulting partial permutation `f` has its codegree and images stored as 32-bit integers, while none of its image points exceeds 65536. The purpose of this function is to change the internal representation of such an `f` from using 32-bit to using 16-bit integers.

Note that the partial permutation `f` is changed in-place, and nothing is returned by this function.

gap> f:=PartialPerm( [ 1, 2 ], [ 3, 4 ] ) > *PartialPerm( [ 3, 5 ], [ 3, 100000 ] ); [1,3] gap> IsPPerm4Rep(f); true gap> TrimPartialPerm(f); f; [1,3] gap> IsPPerm4Rep(f); false

It is possible to change the way that **GAP** displays partial permutations using the user preferences `PartialPermDisplayLimit`

and `NotationForPartialPerms`

; see Section `UserPreference`

(3.2-3) for more information about user preferences.

If `f`

is a partial permutation of rank `r`

exceeding the value of the user preference `PartialPermDisplayLimit`

, then `f`

is displayed as:

<partial perm on r pts with degree m, codegree n>

where the degree and codegree are `m`

and `n`

, respectively. The idea is to abbreviate the display of partial permutations defined on many points. The default value for the `PartialPermDisplayLimit`

is `100`

.

If the rank of `f`

does not exceed the value of `PartialPermDisplayLimit`

, then how `f`

is displayed depends on the value of the user preference `NotationForPartialPerms`

except in the case that `f`

is the empty partial permutation or an identity partial permutation.

There are three possible values for `NotationForPartialPerms`

user preference, which are described below.

**component**Similar to permutations, and unlike transformations, partial permutations can be expressed as products of disjoint permutations and chains. A

*chain*is a list`c`

of some length`n`

such that:`c[1]`

is an element of the domain of`f`but not the image`c[i]^`

for all`f`=c[i+1]`i`

in the range from`1`

to`n-1`

.`c[n]`

is in the image of`f`but not the domain.

In the display, permutations are displayed as they usually are in

**GAP**, except that fixed points are displayed enclosed in round brackets, and chains are displayed enclosed in square brackets.gap> f := PartialPerm([ 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 16, 17, 18, 19 ], > [ 3, 12, 14, 4, 11, 18, 17, 2, 9, 5, 15, 8, 20, 10, 19 ]); [1,3,14][16,8,2,12,15](4)(5,11)[6,18,10,9][7,17,20](19)

This option is the most compact way to display a partial permutation and is the default value of the user preference

`NotationForPartialPerms`

.**domainimage**With this option a partial permutation

`f`

is displayed in the format:`DomainOfPartialPerm(`

.`f`)-> ImageListOfPartialPerm(`f`)gap> f:=PartialPerm( [ 1, 2, 4, 5, 6, 7 ], [ 10, 1, 6, 5, 8, 7 ]); [ 1, 2, 4, 5, 6, 7 ] -> [ 10, 1, 6, 5, 8, 7 ]

**input**With this option a partial permutation

`f`is displayed as:`PartialPerm(DomainOfPartialPerm(`

which corresponds to the input (of the first type described in`f`), ImageListOfPartialPerm(`f`))`PartialPerm`

(54.2-1)).gap> f:=PartialPerm( [ 1, 2, 3, 5, 6, 9, 10 ], > [ 4, 7, 3, 8, 2, 1, 6 ] ); PartialPerm( [ 1, 2, 3, 5, 6, 9, 10 ], [ 4, 7, 3, 8, 2, 1, 6 ] )

gap> SetUserPreference("PartialPermDisplayLimit", 12); gap> UserPreference("PartialPermDisplayLimit"); 12 gap> f:=PartialPerm([1,2,3,4,5,6], [6,7,1,4,3,2]); [5,3,1,6,2,7](4) gap> f:=PartialPerm( > [ 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 16, 17, 18, 19 ], > [ 3, 12, 14, 4, 11, 18, 17, 2, 9, 5, 15, 8, 20, 10, 19 ] ); <partial perm on 15 pts with degree 19, codegree 20> gap> SetUserPreference("PartialPermDisplayLimit", 100); gap> f; [1,3,14][6,18,10,9][7,17,20][16,8,2,12,15](4)(5,11)(19) gap> UserPreference("NotationForPartialPerms"); "component" gap> SetUserPreference("NotationForPartialPerms", "domainimage"); gap> f; [ 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 16, 17, 18, 19 ] -> [ 3, 12, 14, 4, 11, 18, 17, 2, 9, 5, 15, 8, 20, 10, 19 ] gap> SetUserPreference("NotationForPartialPerms", "input"); gap> f; PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 16, 17, 18, 19 ], [ 3, 12, 14, 4, 11, 18, 17, 2, 9, 5, 15, 8, 20, 10, 19 ] )

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

The **Semigroups** package contains many additional functions and methods for computing with semigroups of partial permutations. 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 partial permutation semigroup is also a partial permutation collection, there are special methods for `DomainOfPartialPermCollection`

(54.3-4), `ImageOfPartialPermCollection`

(54.3-5), `FixedPointsOfPartialPerm`

(54.3-8), `MovedPoints`

(54.3-9), `NrFixedPoints`

(54.3-10), `NrMovedPoints`

(54.3-11), `LargestMovedPoint`

(54.3-13), and `SmallestMovedPoint`

(54.3-12) when applied to a partial permutation semigroup.

`‣ IsPartialPermSemigroup` ( obj ) | ( filter ) |

`‣ IsPartialPermMonoid` ( obj ) | ( filter ) |

Returns: `true`

or `false`

.

A *partial perm semigroup* is simply a semigroup consisting of partial permutations, which may or may not be an inverse semigroup. An object `obj` in **GAP** is a partial perm semigroup if and only if it satisfies `IsSemigroup`

(51.1-1) and `IsPartialPermCollection`

(54.1-2).

A *partial perm monoid* is a monoid consisting of partial permutations. An object in **GAP** is a partial perm monoid if it satisfies `IsMonoid`

(51.2-1) and `IsPartialPermCollection`

(54.1-2).

Note that it is possible for a partial perm semigroup to have a multiplicative neutral element (i.e. an identity element) but not to satisfy `IsPartialPermMonoid`

. For example,

gap> f := PartialPerm( [ 1, 2, 3, 6, 8, 10 ], [ 2, 6, 7, 9, 1, 5 ] );; gap> S := Semigroup(f, One(f)); <commutative partial perm monoid of rank 9 with 1 generator> gap> IsMonoid(S); true gap> IsPartialPermMonoid(S); true

Note that unlike transformation semigroups, the `One`

(31.10-2) of a partial permutation semigroup must coincide with the multiplicative neutral element, if either exists.

For more details see `IsMagmaWithOne`

(35.1-2).

`‣ DegreeOfPartialPermSemigroup` ( S ) | ( attribute ) |

`‣ CodegreeOfPartialPermSemigroup` ( S ) | ( attribute ) |

`‣ RankOfPartialPermSemigroup` ( S ) | ( attribute ) |

Returns: A non-negative integer.

The *degree* of a partial permutation semigroup `S` is the largest degree of any partial permutation in `S`.

The *codegree* of a partial permutation semigroup `S` is the largest positive integer in its image.

The *rank* of a partial permutation semigroup `S` is the number of points on which it acts.

gap> S := Semigroup( PartialPerm( [ 1, 5 ], [ 10000, 3 ] ) ); <commutative partial perm semigroup of rank 2 with 1 generator> gap> DegreeOfPartialPermSemigroup(S); 5 gap> CodegreeOfPartialPermSemigroup(S); 10000 gap> RankOfPartialPermSemigroup(S); 2

`‣ SymmetricInverseSemigroup` ( n ) | ( operation ) |

`‣ SymmetricInverseMonoid` ( n ) | ( operation ) |

Returns: The symmetric inverse semigroup of degree `n`.

If `n` is a non-negative integer, then `SymmetricInverseSemigroup`

returns the inverse semigroup consisting of all partial permutations with degree and codegree at most `n`. Note that `n` must be non-negative, but in particular, can equal `0`

.

The symmetric inverse semigroup has \(\sum_{r=0}^n{n\choose r}^2\cdot r!\) elements and is generated by any set that of partial permutations that generate the symmetric group on `n` points and any partial permutation of rank

.`n`-1

`SymmetricInverseMonoid`

is a synonym for `SymmetricInverseSemigroup`

.

gap> S := SymmetricInverseSemigroup(5); <symmetric inverse monoid of degree 5> gap> Size(S); 1546 gap> GeneratorsOfInverseMonoid(S); [ (1,2,3,4,5), (1,2)(3)(4)(5), [5,4,3,2,1] ]

`‣ IsSymmetricInverseSemigroup` ( S ) | ( property ) |

`‣ IsSymmetricInverseMonoid` ( S ) | ( property ) |

Returns: `true`

or `false`

.

If the partial perm semigroup `S` of degree and codegree `n` equals the symmetric inverse semigroup on `n` points, then `IsSymmetricInverseSemigroup`

return `true`

and otherwise it returns `false`

.

`IsSymmetricInverseMonoid`

is a synonym of `IsSymmetricInverseSemigroup`

. It is common in the literature for the symmetric inverse monoid to be referred to as the symmetric inverse semigroup.

gap> S := Semigroup(AsPartialPerm((1, 3, 4, 2), 5), AsPartialPerm((1, 3, 5), 5), > PartialPerm( [ 1, 2, 3, 4 ] ) ); <partial perm semigroup of rank 5 with 3 generators> gap> IsSymmetricInverseSemigroup(S); true gap> S; <symmetric inverse monoid of degree 5>

`‣ NaturalPartialOrder` ( S ) | ( attribute ) |

`‣ ReverseNaturalPartialOrder` ( S ) | ( attribute ) |

Returns: The natural partial order on an inverse semigroup.

The *natural partial order* \(\leq\) on an inverse semigroup `S` is defined by `s`

\(\leq\)`t`

if there exists an idempotent `e`

in `S` such that `s=et`

. Hence if `f`

and `g`

are partial permutations, then `f`

\(\leq\)`g`

if and only if `f`

is a restriction of `g`

; see `RestrictedPartialPerm`

(54.2-3).

`NaturalPartialOrder`

returns the natural partial order on the inverse semigroup of partial permutations `S` as a list of sets of positive integers where entry `i`

in `NaturalPartialOrder(`

is the set of positions in `S`)`Elements(`

of elements which are less than `S`)`Elements(`

. See also `S`)[i]`NaturalLeqPartialPerm`

(54.5-4).

`ReverseNaturalPartialOrder`

returns the reverse of the natural partial order on the inverse semigroup of partial permutations `S` as a list of sets of positive integers where entry `i`

in `ReverseNaturalPartialOrder(`

is the set of positions in `S`)`Elements(`

of elements which are greater than `S`)`Elements(`

. See also `S`)[i]`NaturalLeqPartialPerm`

(54.5-4).

gap> S := InverseSemigroup([ PartialPerm( [ 1, 3 ], [ 1, 3 ] ), > PartialPerm( [ 1, 2 ], [ 3, 2 ] ) ] ); <inverse partial perm semigroup of rank 3 with 2 generators> gap> Size(S); 11 gap> NaturalPartialOrder(S); [ [ ], [ 1 ], [ 1 ], [ 1 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 1 ], [ 1 ], [ 1, 4, 7 ], [ 1, 4, 8 ], [ 1, 2, 8 ] ] gap> NaturalLeqPartialPerm(Elements(S)[4], Elements(S)[10]); true gap> NaturalLeqPartialPerm(Elements(S)[4], Elements(S)[1]); false

`‣ IsomorphismPartialPermSemigroup` ( S ) | ( attribute ) |

`‣ IsomorphismPartialPermMonoid` ( S ) | ( attribute ) |

Returns: An isomorphism.

`IsomorphismPartialPermSemigroup(`

returns an isomorphism from the inverse semigroup `S`)`S` to an inverse semigroup of partial permutations.

`IsomorphismPartialPermMonoid(`

returns an isomorphism from the inverse semigroup `S`)`S` to an inverse monoid of partial permutations, if possible.

We only describe `IsomorphismPartialPermMonoid`

, the corresponding statements for `IsomorphismPartialPermSemigroup`

also hold.

**Partial permutation semigroups**If

`S`is a partial permutation semigroup that does not satisfy`IsMonoid`

(Reference: IsMonoid) but where`MultiplicativeNeutralElement(`

, then`S`)<>fail`IsomorphismPartialPermMonoid(`

returns an isomorphism from`S`)`S`to an inverse monoid of partial permutations.**Permutation groups**If

`S`is a permutation group, then`IsomorphismPartialPermMonoid`

returns an isomorphism from`S`to an inverse monoid of partial permutations on the set`MovedPoints(`

obtained using`S`)`AsPartialPerm`

(54.4-1). The inverse of this isomorphism is obtained using`AsPermutation`

(42.5-5).**Transformation semigroups**If

`S`is a transformation semigroup which is mathematically a monoid but which does not necessarily belong to the category`IsMonoid`

(51.2-1), then`IsomorphismPartialPermMonoid`

returns an isomorphism from`S`to an inverse monoid of partial permutations.

gap> S := InverseSemigroup( > PartialPerm( [ 1, 2, 3, 4, 5 ], [ 4, 2, 3, 1, 5 ] ), > PartialPerm( [ 1, 2, 4, 5 ], [ 3, 1, 4, 2 ] ) );; gap> IsMonoid(S); false gap> Size(S); 508 gap> iso := IsomorphismPartialPermMonoid(S); MappingByFunction( <inverse partial perm semigroup of size 508, rank 5 with 2 generators>, <inverse partial perm monoid of size 508, rank 5 with 2 generators> , function( object ) ... end, function( object ) ... end ) gap> Size(S); 508 gap> Size(Range(iso)); 508 gap> G := Group((1,2)(3,8)(4,6)(5,7), (1,3,4,7)(2,5,6,8), (1,4)(2,6)(3,7)(5,8));; gap> IsomorphismPartialPermSemigroup(G); MappingByFunction( Group([ (1,2)(3,8)(4,6)(5,7), (1,3,4,7) (2,5,6,8), (1,4)(2,6)(3,7) (5,8) ]), <partial perm group of rank 8 with 3 generators> , function( p ) ... end, <Attribute "AsPermutation"> ) gap> S := Semigroup(Transformation( [ 2, 5, 1, 7, 3, 7, 7 ] ), > Transformation( [ 3, 6, 5, 7, 2, 1, 7 ] ) );; gap> iso := IsomorphismPartialPermMonoid(S);; gap> MultiplicativeNeutralElement(S) ^ iso; <identity partial perm on [ 1, 2, 3, 4, 5, 6 ]> gap> One(Range(iso)); <identity partial perm on [ 1, 2, 3, 4, 5, 6 ]> gap> MovedPoints(Range(iso)); [ 1 .. 5 ]

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