Math Solutions 1995 October

home *** CD-ROM | disk | FTP | other *** search

/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / permutat.tex < prev next >

Wrap

Text File | 1993-05-05 | 11.7 KB | 338 lines

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A permutat.tex GAP documentation Udo Polis %% %A @(#)$Id: permutat.tex,v 3.5 1993/02/09 16:29:11 felsch Exp $ %% %Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %% This file describes those functions that deal with permutation groups %% %H $Log: permutat.tex,v $ %H Revision 3.5 1993/02/09 16:29:11 felsch %H another example adjusted %H %H Revision 3.4 1993/02/01 16:28:08 felsch %H example fixed %H %H Revision 3.3 1992/04/07 13:07:55 martin %H fixed some more typos %H %H Revision 3.2 1992/03/13 10:44:47 martin %H changed two section titles %H %H Revision 3.1 1992/01/15 14:09:18 martin %H initial revision under RCS %H %% \Chapter{Permutations} {\GAP} is a system especially designed for the computations in groups. Permutation groups are a very important class of groups and {\GAP} offers a data type *permutation* to describe the elements of permutation groups. Permutations in {\GAP} operate on *positive integers*. Whenever group elements operate on a domain we call the elements of this domain *points*. Thus in this chapter we often call positive integers points, if we want to emphasize that a permutation operates on them. An integer $i$ is said to be *moved* by a permutation $p$ if the image $i^p$ of $i$ under $p$ is not $i$. The largest integer moved by any permutation may not be larger than $2^{16}$. This bound, however, is not a permanent one. We are going to remove this restriction as soon as possible. Note that permutations do not belong to a specific group. That means that you can work with permutations without defining a permutation group that contains them. This is just like it is with integers, with which you can compute without caring about the domain 'Integers' that contains them. It also means that you can multiply any two permutations. Permutations are entered and displayed in cycle notation. | gap> (1,2,3); (1,2,3) gap> (1,2,3) * (2,3,4); (1,3)(2,4) | The first sections in this chapter describe the operations that are available for permutations (see "Comparisons of Permutations" and "Operations for Permutations"). The next section describes the function that tests whether an object is a permutation (see "IsPerm"). The next sections describe the functions that find the largest and smallest point moved by a permutation (see "LargestMovedPointPerm" and "SmallestMovedPointPerm"). The next section describes the function that computes the sign of a permutation (see "SignPerm"). The next section describes the function that computes the smallest permutation that generates the same cyclic subgrop as a given permutation (see "SmallestGeneratorPerm"). The final sections describe the functions that convert between lists and permutations (see "ListPerm", "PermList", "RestrictedPerm", and "MappingPermListList"). Permutations are elements of groups operating on positive integers in a natural way, thus see chapter "Groups" and chapter "Operations" for more functions. The external functions are in the file 'LIBNAME/\"permutat.g\"'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Comparisons of Permutations}% '<p1> = <p2>' \\ '<p1> \<> <p2>' The equality operator '=' evaluates to 'true' if the two permutations <p1> and <p2> are equal, and to 'false' otherwise. The inequality operator '\<>' evaluates to 'true' if the two permutations <p1> and <p2> are not equal, and to 'false' otherwise. You can also compare permutations with objects of other types, of course they are never equal. Two permutations are considered equal if and only if they move the same points and if the images of the moved points are the same under the operation of both permutations. | gap> (1,2,3) = (2,3,1); true gap> (1,2,3) * (2,3,4) = (1,3)(2,4); true | '<p1> \< <p2>' \\ '<p1> \<= <p2>' \\ '<p1> > <p2>' \\ '<p1> >= <p2>' The operators '\<', '\<=', '>', and '>=' evaluate to 'true' if the permutation <p1> is less than, less than or equal to, greater than, or greater than or equal to the permutation <p2>, and to 'false' otherwise. Let $p_1$ and $p_2$ be two permutations that are not equal. Then there exists at least one point $i$ such that $i^{p_1} \<> i^{p_2}$. Let $k$ be the smallest such point. Then $p_1$ is considered smaller than $p_2$ if and only if $k^{p_1} \<\ k^{p_2}$. Note that this implies that the identity permutation is the smallest permutation. You can also compare permutations with objects of other types. Integers, rationals, cyclotomics, unknowns, and finite field elements are smaller than permutations. Everything else is larger. | gap> (1,2,3) < (1,3,2); true # $1^{(1,2,3)} = 2 \<\ 3 = 1^{(1,3,2)}$ gap> (1,3,2,4) < (1,3,4,2); false # $2^{(1,3,2,4)} = 4 > 1 = 2^{(1,3,4,2)}$ | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Operations for Permutations}% '<p1> \*\ <p2>' The operator '\*' evaluates to the product of the two permutations <p1> and <p2>. '<p1> / <p2>' The operator '/' evaluates to the quotient $p1 \* p2^{-1}$ of the two permutations <p1> and <p2>. 'LeftQuotient( <p1>, <p2> )' 'LeftQuotient' returns the left quotient $p1^{-1} \* p2$ of the two permutations <p1> and <p2>. (This can also be written '<p1> mod <p2>'.) ' \^\ ' The operator '\^' evaluates to the -th power of the permutation . '<p1> \^\ <p2>' The operator '\^' evaluates to the conjugate $p2^{-1} \* p1 \* p2$ of the permutation <p1> by the permutation <p2>. 'Comm( <p1>, <p2> )' 'Comm' returns the commutator $p1^{-1} \* p2^{-1} \* p1 \* p2$ of the two permutations <p1> and <p2>. ' \^\ ' The operator '\^' evaluates to the image $i^p$ of the positive integer under the permutation . ' / ' The operator '/' evaluates to the preimage $i^{p^{-1}}$ of the integer under the permutation . '<list> \*\ ' \\ ' \*\ <list>' The operator '\*' evaluates to the list of products of the permutations in <list> with the permutation . That means that the value is a new list <new> such that '<new>[] = <list>[] \*\ ' respectively '<new>[] = \*\ <list>[]'. '<list> / ' The operator '/' evaluates to the list of quotients of the permutations in <list> with the permutation . That means that the value is a new list <new> such that '<new>[] = <list>[] / '. For the precedence of the operators see "Operations". %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsPerm} 'IsPerm( <obj> )' 'IsPerm' returns 'true' if <obj>, which may be an object of arbitrary type, is a permutation and 'false' otherwise. It will signal an error if <obj> is an unbound variable. | gap> IsPerm( (1,2) ); true gap> IsPerm( 1 ); false | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{LargestMovedPointPerm} 'LargestMovedPointPerm( <perm> )' 'LargestMoverPointPerm' returns the largest point moved by the permutation <perm>, i.e., the largest positive integer such that '\^<perm> \<> '. It will signal an error if <perm> is trivial (see also "SmallestMovedPointPerm"). | gap> LargestMovedPointPerm( (2,3,1) ); 3 gap> LargestMovedPointPerm( (1,2)(1000,1001) ); 1001 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SmallestMovedPointPerm} 'SmallestMovedPointPerm( <perm> )' 'SmallestMovedPointPerm' returns the smallest point moved by the permutation <perm>, i.e., the smallest positive integer such that '\^<perm> \<> '. It will signal an error if <perm> is trivial (see also "LargestMovedPointPerm"). | gap> SmallestMovedPointPerm( (4,7,5) ); 4 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SignPerm} 'SignPerm( <perm> )' 'SignPerm' returns the *sign* of the permutation <perm>. The sign $s$ of a permutation $p$ is defined by $s = \prod_{i \< j}{(i^p - j^p)} / \prod_{i \< j}{(i - j)}$, where $n$ is the largest point moved by $p$ and $i,j$ range over $1...n$. One can easily show that *sign* is equivalent to the *determinant* of the *permutation matrix* of <perm>. Thus it is obvious that the function *sign* is a homomorphism. | gap> SignPerm( (1,2,3)(5,6) ); -1 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SmallestGeneratorPerm} 'SmallestGeneratorPerm( <perm> )' 'SmallestGeneratorPerm' returns the smallest permutation that generates the same cyclic group as the permutation <perm>. | gap> SmallestGeneratorPerm( (1,4,3,2) ); (1,2,3,4) | Note that 'SmallestGeneratorPerm' is very efficient, even when <perm> has huge order. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ListPerm} 'ListPerm( <perm> )' 'ListPerm' returns a list <list> that contains the images of the positive integers under the permutation <perm>. That means that '<list>[] = \^<perm>', where lies between 1 and the largest point moved by <perm> (see "LargestMovedPointPerm"). | gap> ListPerm( (1,2,3,4) ); [ 2, 3, 4, 1 ] gap> ListPerm( () ); [ ] | 'PermList' (see "PermList") performs the inverse operation. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{PermList} 'PermList( <list> )' 'PermList' returns the permutation <perm> that moves points as describes by the list <list>. That means that '\^<perm> = <list>[]' if lies between 1 and the length of <list>, and '\^<perm> = ' if is larger than the length of the list <list>. It will signal an error if <list> does not define a permutation, i.e., if <list> is not a list of integers without holes, or if <list> contains an integer twice, or if <list> contains an integer not in the range '[1..Length(<list>)]'. | gap> PermList( [6,2,4,1,5,3] ); (1,6,3,4) gap> PermList( [] ); () | 'ListPerm' (see "ListPerm") performs the inverse operation. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{RestrictedPerm} 'RestrictedPerm( <perm>, <list> )' 'RestrictedPerm' returns the new permutation <new> that operates on the points in the list <list> in the same way as the permutation <perm>, and that fixes those points that are not in <list>. <list> must be a list of positive integers such that for each in <list> the image '\^<perm>' is also in <list>, i.e., it must be the union of cycles of <perm>. | gap> RestrictedPerm( (1,2,3)(4,5), [4,5] ); (4,5) | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{MappingPermListList} 'MappingPermListList( <list1>, <list2> )' 'MappingPermListList' returns a permutation <perm> such that '<list1>[] \^\ <perm> = <list2>[]'. <perm> fixes all points larger then the maximum of the entries in <list1> and <list2>. If there are several such permutations, it is not specified which 'MappingPermListList' returns. <list1> and <list2> must be lists of positive integers of the same length, and neither may contain an element twice. | gap> MappingPermListList( [3,4], [6,9] ); (3,6,4,9,8,7,5) gap> MappingPermListList( [], [] ); () | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables %% %% Local Variables: %% mode: outline %% outline-regexp: "\\\\Chapter\\|\\\\Section" %% fill-column: 73 %% eval: (hide-body) %% End: %%