<html><head><title>[ref] 52 Transformations</title></head> <body text="#000000" bgcolor="#ffffff"> [<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP051.htm">Previous</a>] [<a href ="CHAP053.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <h1>52 Transformations</h1><p> <p> This chapter describes functions for transformations. <p> A <strong>transformation</strong> in <font face="Gill Sans,Helvetica,Arial">GAP</font> is an endomorphism of a set of integers of the form {1,..., <i>n</i>}. Transformations are taken to act on the right, which defines the composition <i>i</i><sup>(αβ)</sup> = (<i>i</i><sup>α</sup>)<sup>β</sup> for <i>i</i> in {1, ..., <i>n</i>}. <p> For a transformation α on the set {1, …, <i>n</i>}, we define its <strong>degree</strong> to be <i>n</i>, its <strong>image list</strong> to be the list, [1α, …, <i>n</i>α], its <strong>image</strong> to be the image list considered as a set, and its <strong>rank</strong> to be the size of the image. We also define the <strong>kernel</strong> of α to be the equivalence relation containing the pair (<i>i</i>, <i>j</i>) if and only if <i>i</i><sup>α</sup> = <i>j</i><sup>α</sup>. <p> Note that unlike permutations, we do not consider unspecified points to be fixed by a transformation. Therefore multiplication is only defined on two transformations of the same degree. <p> <a name = ""></a> <li><code>IsTransformation( </code><var>obj</var><code> ) C</code> <a name = ""></a> <li><code>IsTransformationCollection( </code><var>obj</var><code> ) C</code> <p> We declare it as <code>IsMultiplicativeElementWithOne</code> since the identity automorphism of {1,…,<i>n</i>} is a multiplicative two sided identity for any transformation on the same set. <p> <a name = ""></a> <li><code>TransformationFamily( n ) F</code> <a name = ""></a> <li><code>TransformationType( n ) F</code> <a name = ""></a> <li><code>TransformationData( n ) F</code> <p> For each <code></code><var>n</var><code> > 0</code> there is a single family and type of transformations on n points. To speed things up, we store these in a database of types. The three functions above a then access functions. If the <var>n</var>th entry isn't yet created, they trigger creation as well. <p> For <code></code><var>n</var><code> > 0</code>, element <var>n</var> of the type database is <code>[TransformationFamily(n), TransformationType(n)]</code> <p> <a name = ""></a> <li><code>Transformation( </code><var>images</var><code> ) F</code> <a name = ""></a> <li><code>TransformationNC( </code><var>images</var><code> ) F</code> <p> both return a transformation with the image list <var>images</var>. The normal version checks that the all the elements of the given list lie within the range {1,...,<i>n</i>} where <var>n</var> is the length of <var>images</var>, but for speed purposes, a non-checking version is also supplied. <p> <a name = ""></a> <li><code>IdentityTransformation( </code><var>n</var><code> ) F</code> <p> return the identity transformation of degree <var>n</var> <p> <a name = ""></a> <li><code>RandomTransformation( </code><var>n</var><code> ) F</code> <p> returns a random transformation of degree <var>n</var> JDM <p> <a name = ""></a> <li><code>DegreeOfTransformation( </code><var>trans</var><code> ) A</code> <p> returns the degree of <var>trans</var>. <p> <pre> gap> t:= Transformation([2, 3, 4, 2, 4]); Transformation( [ 2, 3, 4, 2, 4 ] ) gap> DegreeOfTransformation(t); 5 </pre> <a name = ""></a> <li><code>ImageListOfTransformation( </code><var>trans</var><code> ) A</code> <p> returns the image list of <var>trans</var>. <p> <pre> gap> ImageListOfTransformation(t); [ 2, 3, 4, 2, 4 ] </pre> <a name = ""></a> <li><code>ImageSetOfTransformation( </code><var>trans</var><code> ) A</code> <p> returns the image of <var>trans</var> as a set. <p> <pre> gap> ImageSetOfTransformation(t); [ 2, 3, 4 ] </pre> <a name = ""></a> <li><code>RankOfTransformation( </code><var>trans</var><code> ) A</code> <p> returns the rank of <var>trans</var>. <p> <pre> gap> RankOfTransformation(t); 3 </pre> <a name = ""></a> <li><code>KernelOfTransformation( </code><var>trans</var><code> ) A</code> <p> Returns the kernel of <var>trans</var> as an equivalence relation (See <a href="CHAP032.htm#SECT001">General Binary Relations</a>). <p> <pre> gap> KernelOfTransformation(t); [ [ 1, 4 ], [ 2 ], [ 3, 5 ] ] </pre> <a name = ""></a> <li><code>PreimagesOfTransformation( </code><var>trans</var><code>, </code><var>i</var><code> ) O</code> <p> returns the subset of {1,...,<i>n</i>} which maps to <var>i</var> under <var>trans</var>. <p> <pre> gap> PreimagesOfTransformation(t, 2); [ 1, 4 ] </pre> <a name = ""></a> <li><code>RestrictedTransformation( </code><var>trans</var><code>, </code><var>alpha</var><code> ) O</code> <p> The transformation <var>trans</var> is restricted to only those points of <var>alpha</var>. <p> <a name = ""></a> <li><code>AsTransformation( </code><var>O</var><code> ) O</code> <a name = ""></a> <li><code>AsTransformation( </code><var>O</var><code>, </code><var>n</var><code> ) O</code> <a name = ""></a> <li><code>AsTransformationNC( </code><var>O</var><code>, </code><var>n</var><code> ) O</code> <p> returns the object <var>O</var> as a transformation. Supported objects are permutations and binary relations on points. In the second form, the operation returns a transformation of degree <var>n</var>, signalling an error if such a representation is not possible. <code>AsTransformationNC</code> does not perform this check. <p> <pre> gap> AsTransformation((1, 3)(2, 4)); Transformation( [ 3, 4, 1, 2 ] ) gap> AsTransformation((1, 3)(2, 4), 10); Transformation( [ 3, 4, 1, 2, 5, 6, 7, 8, 9, 10 ] ) </pre> <pre> gap> AsTransformation((1, 3)(2, 4), 3); Error, Permutation moves points over the degree specified called from <function>( <arguments> ) called from read-eval-loop Entering break read-eval-print loop ... you can 'quit;' to quit to outer loop, or you can 'return;' to continue brk> quit; </pre> <p> <a name = ""></a> <li><code>PermLeftQuoTransformation( </code><var>tr1</var><code>, </code><var>tr2</var><code> ) O</code> <p> Given transformations <var>tr1</var> and <var>tr2</var> with equal kernel and image, we compute the permutation induced by (<var>tr1</var>)<sup>−1</sup>*<var>tr2</var> on the set of images of <var>tr1</var>. If the kernels and images are not equal, an error is signaled. <p> <a name = ""></a> <li><code>BinaryRelationTransformation( </code><var>trans</var><code> ) O</code> <p> returns <var>trans</var> when considered as a binary relation. <p> <a name = ""></a> <li><code>TransformationRelation( </code><var>R</var><code> ) O</code> <p> returns the binary relation <var>R</var> when considered as a transformation. Only makes sense for injective binary relations over <code>[1..n]</code>. Returns an error if the relation is not over <code>[1..n]</code>, and <code>fail</code> if it is not injective. <p> <p> [<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP051.htm">Previous</a>] [<a href ="CHAP053.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> <font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008 </font></body></html>