1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
|
% 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.2.1 2006/03/03 17:30:59 jamesm 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>
JDM
\>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);
[ [ 1, 4 ], [ 2 ], [ 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
|
