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:
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).
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).
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 ].
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).
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).
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, ..., 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≤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.
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).
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 (41.9-1) 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)∩ dom(g) of their domains and the images of dom(f)∖ dom(g) and dom(g)∖ 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 permutation 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 guaranteed 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(f)[i]=DomainOfPartialPerm(f)[i]^f for any 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^f<>i if such an 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^f<>i if such an 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^f such that i^f<>i if such an 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^f such that i^f<>i if such an 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 f^(m+r)=f^m, which are known as the 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 f^n is an idempotent. The smallest idempotent power of f is the least multiple of the period of f that is greater than or equal to the index of f; see 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 jnot=i in the component of i, there exists a positive integer k such that i ^ (f ^ k) = j. Unlike transformations, there is exactly one representative for every component of 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 (31.10-2), 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 (35.4-11), 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-6). 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:
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.
AsPartialPerm returns the partial permutation that agrees with f on [1..LargestMovedPoint(f)] and that is not defined on any other positive integer.
AsPartialPerm returns the partial permutation that agrees with f on [1..n], when 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:
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.
AsPartialPerm returns the partial permutation that agrees with f on [1..n] when 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]
‣ Inverse( f ) | ( method ) |
returns the inverse of the partial permutation f.
54.5-2 \^‣ \^( i, f ) | ( method ) |
returns the image of the positive integer i under the partial permutation f if it is defined and 0 if it is not.
54.5-3 \/‣ \/( i, f ) | ( method ) |
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.
54.5-4 \^‣ \^( f, g ) | ( method ) |
f ^ g returns g^-1*f*g when 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.
54.5-5 \*‣ \*( f, g ) | ( method ) |
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.
54.5-6 \/‣ \/( f, g ) | ( method ) |
f / g returns f*g^-1 when 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.
‣ LeftQuotient( g, f ) | ( method ) |
returns g^-1*f when 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.
54.5-8 \<‣ \<( f, g ) | ( method ) |
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-13) and ShortLexLeqPartialPerm (54.5-14) for additional orders for partial permutations.
54.5-9 \=‣ \=( f, g ) | ( method ) |
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 f^-1*g when the partial permutations 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 i/f as described in Section 54.5.
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 ≤ on an inverse semigroup S is defined by s≤t if there exists an idempotent e in S such that s=et. Hence if f and g are partial permutations, then f≤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.
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]^f=c[i+1] for all 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.
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 ]
With this option a partial permutation f is displayed as: PartialPerm(DomainOfPartialPerm(f), ImageListOfPartialPerm(f)) which corresponds to the input (of the first type described in 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 ∑_r=0^nnchoose r^2⋅ 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 ≤ on an inverse semigroup S is defined by s≤t if there exists an idempotent e in S such that s=et. Hence if f and g are partial permutations, then f≤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(S) is the set of positions in Elements(S) of elements which are less than Elements(S)[i]. See also NaturalLeqPartialPerm (54.5-13).
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(S) is the set of positions in Elements(S) of elements which are greater than Elements(S)[i]. See also NaturalLeqPartialPerm (54.5-13).
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(S) returns an isomorphism from the inverse semigroup S to an inverse semigroup of partial permutations.
IsomorphismPartialPermMonoid(S) returns an isomorphism from the inverse semigroup S to an inverse monoid of partial permutations, if possible.
We only describe IsomorphismPartialPermMonoid, the corresponding statements for IsomorphismPartialPermSemigroup also hold.
If S is a partial permutation semigroup that does not satisfy IsMonoid (51.2-1) but where MultiplicativeNeutralElement(S)<>fail, then IsomorphismPartialPermMonoid(S) returns an isomorphism from S to an inverse monoid of partial permutations.
If S is a permutation group, then IsomorphismPartialPermMonoid returns an isomorphism from S to an inverse monoid of partial permutations on the set MovedPoints(S) obtained using AsPartialPerm (54.4-1). The inverse of this isomorphism is obtained using AsPermutation (42.5-6).
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 ]
generated by GAPDoc2HTML