<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>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
194
