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
|
\documentclass{article}
\usepackage{axiom}
\begin{document}
\title{\$SPAD/src/input perm.input}
\author{The Axiom Team}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{License}
<<license>>=
--Copyright The Numerical Algorithms Group Limited 1991.
@
<<*>>=
<<license>>
)clear all
-- This file demonstrates some of the new routines for permutations
-- in AXIOM. ( Last change: 05/16/89 by HWG )
-- (J. Grabmeier: adjusted to new concept: 08/07/89)
-- (M. Weller : adjusted to 1..: 03/29/90)
-- (J. Grabmeier : adjusted to new algebra 05/14/90)
-- Permutations can act on every set, finite or infinite.
-- Usually permutations are given as a product of cycles,
-- so the following generates a permutation acting on some
-- elements of GF(29):
x : List List PrimeField 29 :=
[[23,19,7,9,12,11,15],[22,4,14,18,2,5,8],[21,20,10,16,13,6,17]]
px : PERM PrimeField 29 := x
-- If the permutation consists of just one cycle, you can use the
-- function "cycle" instead of "coerce":
w : List PrimeField 29 :=
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23]
pw : PERM PrimeField 29 := cycle w
-- For a product of cycles there is also the function "cycles":
k : List List PrimeField 29 :=
[[23,24],[22,16],[21,9],[20,19],[18,12],[17,14],[15,7],[10,6]]
pk : PERM PrimeField 29 := cycles k
-- Since these permutations generate a group, you can
-- perform various operations on px, pw and pk.
-- You may have to be careful, because permutations are viewed
-- as mappings acting on the left, so (pw*pk)(7) = pw(pk(7)).
-- Here are some examples:
pw*pk
px**3
-- You can ask for inverses:
inv px
-- or for the image of some element under a special permutation:
elt(px,17::PrimeField(29))
-- you may try to build commutators:
commutator(pk,pw)
-- which is the same as inv(pk) * inv(pw) * pk * pw
-- You can also ask for the orbit of some element under a permutation:
orbit(px,11::PrimeField(29))
-- or for the elements of the underlying set, which are permuted
-- by a given permutation:
support(pk)
-- Now we take a short look on permutation groups.
-- They are represented as a list of generating permutations:
gp1 : PERMGRP PrimeField 29 := [ px , pk ]
gp2 : PERMGRP PrimeField 29 := [ pw , px ]
gp3 : PERMGRP PrimeField 29 := [ pw , pk ]
-- and we can ask for their orders:
order gp1
order gp2
order gp3
-- In fact these are the Mathieu-groups M_22, M_23 and M_24.
-- now a more sophisticated example
-- The following matrices generate the general linear group GL(3,2):
(m1,m2,m3,m4): Matrix PrimeField 2
m1 := [[1,1,0],[0,1,0],[0,0,1]]
m2 := [[1,0,0],[0,1,1],[0,0,1]]
m3 := [[1,0,0],[1,1,0],[0,0,1]]
m4 := [[1,0,0],[0,1,0],[0,1,1]]
-- and these matrices act on the non-zero vectors of the
-- corresponding vector space
vl : List Vector PrimeField 2
vl := [[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
-- Now we can write down the action of our matrices on this list vl
-- as a list of pairs
ll1 : List List Vector PrimeField 2 :=
[ [ vl.i , m1*(vl.i) ] for i in 1..7 ]
ll2 : List List Vector PrimeField 2 :=
[ [ vl.i , m2*(vl.i) ] for i in 1..7 ]
ll3 : List List Vector PrimeField 2 :=
[ [ vl.i , m3*(vl.i) ] for i in 1..7 ]
ll4 : List List Vector PrimeField 2 :=
[ [ vl.i , m4*(vl.i) ] for i in 1..7 ]
-- and we can coerce these lists to permutations
el1 : PERM Vector PrimeField 2 := coerceListOfPairs ll1
el2 : PERM Vector PrimeField 2 := coerceListOfPairs ll2
el3 : PERM Vector PrimeField 2 := coerceListOfPairs ll3
el4 : PERM Vector PrimeField 2 := coerceListOfPairs ll4
-- Now we can do the same operations as before, e.g.
el3(vl.5)
el2 * el1
support el4
-- Let's built the general linear group now
gl : PERMGRP Vector PrimeField 2 := [ el1 , el2 , el3 , el4 ]
-- and ask for its order
order gl
-- We can also ask for the orbit of the unordered set of vectors
setOfVectors : Set Vector PrimeField 2 := brace [ vl.2 , vl.4 , vl.6 ]
-- under gl
orbit ( gl, setOfVectors )
-- and also for the orbit of the ordered list
listOfVectors : List Vector PrimeField 2 := parts setOfVectors
orbit ( gl, listOfVectors )
-- Now Rubik's cube.
f : PERM INT := cycles [[11,13,15,17],[12,14,16,18],[51,31,21,41],[53,33,23,43],_
[52,32,22,42]]
r : PERM INT := cycles [[21,23,25,27],[22,24,26,28],[13,37,67,43],[15,31,61,45],_
[14,38,68,44]]
-- Some calculation in Rubik's group:
(f**2*r**2)**3
rc := rubiksGroup()
order rc
orbits rc
-- Can we interchange just two pieces with two visible faces on the cube
-- and leave everything else fixed?
member? (cycles([[12,14],[32,22]])$(PERM INT),rc)
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}
|
