% This file was created automatically from trans.msk.
% DO NOT EDIT!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  trans.msk                GAP documentation                Isabel Araujo
%%
%A  @(#)$Id: trans.msk,v 1.13 2002/09/03 16:03:33 gap Exp $
%%
%Y  (C) 1999 School Math and Comp. Sci., University of St.  Andrews, Scotland
%Y  Copyright (C) 2002 The GAP Group
%%
\Chapter{Transformations}

This chapter describes functions for transformations. 

A *transformation* in {\GAP} is an endomorphism of a set of integers
of the form $\{1,\dots, n\}$.  Transformations are taken to act on the 
right, which defines the composition $i^{(\alpha\beta)} = (i^\alpha)^\beta$
for $i$ in $\{1, \dots, n\}$.

For a transformation $\alpha$ on the set $\{1, \ldots, n\}$, we define
its *degree* to be $n$, its *image list* to be the list,
$[1\alpha, \ldots, n\alpha]$, its *image* to be the image 
list considered as a set,
and its *rank* to be the size of the image.
We also define the *kernel* of $\alpha$ to be the equivalence relation
containing the pair $(i, j)$ if and only if $i^\alpha = j^\alpha$.

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.


\>IsTransformation( <obj> ) C
\>IsTransformationCollection( <obj> ) C

We declare it as `IsMultiplicativeElementWithOne' since
the identity automorphism of  $\{1,\ldots,n\}$ is a multiplicative
two sided identity for any transformation on the same set.

\>TransformationFamily( n ) F
\>TransformationType( n ) F
\>TransformationData( n ) F

For each `<n> > 0' 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 <n>th entry isn't yet created, they trigger
creation as well.

For `<n> > 0', element <n>  of the type database is
`[TransformationFamily(n), TransformationType(n)]'

\>Transformation( <images> ) F
\>TransformationNC( <images> ) F

both return a transformation with the image list <images>.   The
normal version checks that the all the elements of the given list
lie within the range $\{1,\dots,n\}$ where <n> is the length of <images>,
but for speed purposes, a non-checking version is also supplied.


\>IdentityTransformation( <n> ) F

return the identity transformation of degree <n>  


\>RandomTransformation( <n> ) F

returns a random transformation of degree <n>


\>DegreeOfTransformation( <trans> ) A

returns the degree of <trans>.


\beginexample
gap> t:= Transformation([2, 3, 4, 2, 4]);
Transformation( [ 2, 3, 4, 2, 4 ] )
gap> DegreeOfTransformation(t);
5
\endexample
\>ImageListOfTransformation( <trans> ) A

returns the image list of <trans>.


\beginexample
gap> ImageListOfTransformation(t);
[ 2, 3, 4, 2, 4 ]
\endexample
\>ImageSetOfTransformation( <trans> ) A

returns the image of <trans> as a set.


\beginexample
gap> ImageSetOfTransformation(t);
[ 2, 3, 4 ]
\endexample
\>RankOfTransformation( <trans> ) A

returns the rank of <trans>.


\beginexample
gap> RankOfTransformation(t);
3
\endexample
\>KernelOfTransformation( <trans> ) A

Returns the kernel of <trans> as an equivalence relation (See
"General Binary Relations").


\beginexample
gap> KernelOfTransformation(t);
<equivalence relation on <object> >
gap> EquivalenceRelationPartition(last);
[ [ 1, 4 ], [ 3, 5 ] ]
\endexample
\>PreimagesOfTransformation( <trans>, <i> ) O

returns the subset of $\{1,\dots,n\}$  which maps to <i> under <trans>.


\beginexample
gap> PreimagesOfTransformation(t, 2);
[ 1, 4 ]
\endexample
\>RestrictedTransformation( <trans>, <alpha> ) O

The transformation <trans> is restricted to only those points of <alpha>.


\>AsTransformation( <O> ) O
\>AsTransformation( <O>, <n> ) O
\>AsTransformationNC( <O>, <n> ) O

returns the object <O> as a transformation. Supported objects are
permutations and binary relations on points. In the
second form, the operation  returns a 
transformation of degree <n>, signalling
an error if such a representation is not possible.  `AsTransformationNC'
does not perform this check.


\beginexample
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 ] )
\endexample
%notest
\beginexample
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;
\endexample

\>PermLeftQuoTransformation( <tr1>, <tr2> ) O

Given transformations <tr1> and <tr2> with equal kernel and image, 
we compute the permutation induced by (<tr1>)$^{-1}*$<tr2> on the set of 
images of <tr1>. If the kernels and images are not equal, an error 
is signaled.


\>BinaryRelationTransformation( <trans> ) O

returns <trans> when considered as a binary relation.


\>TransformationRelation( <R> ) O

returns the binary relation <R> when considered as a transformation.
Only makes sense for injective binary relations over `[1..n]'.  Returns 
an error if the relation is not over `[1..n]', and `fail' if it is not
injective.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E
