$SPAD/src/input perm.input

Johannes Grabmeier, M. Weller, HWG, Timothy Daly

December 3, 2016

Abstract

Contents

2

1 License

— license —

--Copyright The Numerical Algorithms Group Limited 1991.

———-

— * —

)set break resume
)spool perm.output
)set message test on
)set message auto off
)clear all

———-

This file demonstrates some of the new routines for permutations in AXIOM.

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):

— * —

--S 1 of 51
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]]
--R
--R
--R   (1)  [[23,19,7,9,12,11,15],[22,4,14,18,2,5,8],[21,20,10,16,13,6,17]]
--R                                             Type: List(List(PrimeField(29)))
--E 1
--S 2 of 51
px : PERM PrimeField 29 := x
--R
--R
--R   (2)  (2 5 8 22 4 14 18)(6 17 21 20 10 16 13)(7 9 12 11 15 23 19)
--R                                            Type: Permutation(PrimeField(29))
--E 2

———-

If the permutation consists of just one cycle, you can use the function “cycle” instead of “coerce”:

— * —

--S 3 of 51
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]

--R
--R
--R   (3)  [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23]
--R                                                   Type: List(PrimeField(29))
--E 3
--S 4 of 51
pw : PERM PrimeField 29 := cycle w
--R
--R
--R   (4)  (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23)
--R                                            Type: Permutation(PrimeField(29))
--E 4

———-

For a product of cycles there is also the function “cycles”:

— * —

--S 5 of 51
k : List List PrimeField 29 :=
 [[23,24],[22,16],[21,9],[20,19],[18,12],[17,14],[15,7],[10,6]]
--R
--R
--R   (5)  [[23,24],[22,16],[21,9],[20,19],[18,12],[17,14],[15,7],[10,6]]
--R                                             Type: List(List(PrimeField(29)))
--E 5
--S 6 of 51
pk : PERM PrimeField 29 := cycles k
--R
--R
--R   (6)  (6 10)(7 15)(9 21)(12 18)(14 17)(16 22)(19 20)(23 24)
--R                                            Type: Permutation(PrimeField(29))
--E 6

———-

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:

— * —

--S 7 of 51
pw*pk
--R
--R
--R   (7)  (13 14 18)(8 9 22 17 15)(1 2 3 4 5 6 11 12 19 21 10 7 16 23 24)
--R                                            Type: Permutation(PrimeField(29))
--E 7

--S 8 of 51
px**3
--R
--R
--R   (8)  (2 22 18 8 14 5 4)(6 20 13 21 16 17 10)(7 11 19 12 23 9 15)
--R                                            Type: Permutation(PrimeField(29))
--E 8

———-

You can ask for inverses:

— * —

--S 9 of 51
inv px
--R
--R
--R   (9)  (2 18 14 4 22 8 5)(6 13 16 10 20 21 17)(7 19 23 15 11 12 9)
--R                                            Type: Permutation(PrimeField(29))
--E 9

———-

Or for the image of some element under a special permutation:

— * —

--S 10 of 51
eval(px,17::PrimeField(29))
--R
--R
--R   (10)  21
--R                                                         Type: PrimeField(29)
--E 10

———-

You may try to build commutators:

— * —

--S 11 of 51
commutator(pk,pw)
--R
--R
--R   (11)  (5 21 7 15 9)(6 17 11 14 10)(8 19 12 18 20)(13 22 23 24 16)
--R                                            Type: Permutation(PrimeField(29))
--E 11

———-

Which is the same as inv(pk) * inv(pw) * pk * pw You can also ask for the orbit of some element under a permutation:

— * —

--S 12 of 51
orbit(px,11::PrimeField(29))
--R
--R
--R   (12)  {11,15,23,19,7,9,12}
--R                                                    Type: Set(PrimeField(29))
--E 12

———-

Or for the elements of the underlying set, which are permuted by a given permutation: — * —

--S 13 of 51
movedPoints(pk)
--R
--R
--R   (13)  {16,22,19,20,14,17,6,10,15,7,18,12,21,9,23,24}
--R                                                    Type: Set(PrimeField(29))
--E 13

———-

Now we take a short look on permutation groups. They are represented as a list of generating permutations:

— * —

--S 14 of 51
gp1 : PERMGRP PrimeField 29 := [ px , pk ]
--R
--R
--R   (14)
--R   <
--R       (2 5 8 22 4 14 18)(6 17 21 20 10 16 13)(7 9 12 11 15 23 19)
--R    ,
--R       (6 10)(7 15)(9 21)(12 18)(14 17)(16 22)(19 20)(23 24)
--R     >
--R                                       Type: PermutationGroup(PrimeField(29))
--E 14
--S 15 of 51
gp2 : PERMGRP PrimeField 29 := [ pw , px ]
--R
--R
--R   (15)
--R   <
--R       (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23)
--R    ,

--R       (2 5 8 22 4 14 18)(6 17 21 20 10 16 13)(7 9 12 11 15 23 19)
--R     >
--R                                       Type: PermutationGroup(PrimeField(29))
--E 15
--S 16 of 51
gp3 : PERMGRP PrimeField 29 := [ pw , pk ]
--R
--R
--R   (16)
--R   <
--R       (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23)
--R    ,
--R       (6 10)(7 15)(9 21)(12 18)(14 17)(16 22)(19 20)(23 24)
--R     >
--R                                       Type: PermutationGroup(PrimeField(29))
--E 16

———-

And we can ask for their orders:

— * —

--S 17 of 51
order gp1
--R
--R
--R   (17)  443520
--R                                                        Type: PositiveInteger
--E 17
--S 18 of 51
order gp2
--R
--R
--R   (18)  10200960
--R                                                        Type: PositiveInteger
--E 18
--S 19 of 51
order gp3
--R
--R
--R   (19)  244823040
--R                                                        Type: PositiveInteger
--E 19

———-

In fact these are the Mathieu-groups M_{2}2, M_{2}3 and M_{2}4.

Now a more sophisticated example. The following matrices generate the general linear group GL(3,2):

— * —

--S 20 of 51
(m1,m2,m3,m4): Matrix PrimeField 2
--R
--R                                                                   Type: Void
--E 20
--S 21 of 51
m1 := [[1,1,0],[0,1,0],[0,0,1]]
--R
--R
--R         +1  1  0+
--R         |       |
--R   (21)  |0  1  0|
--R         |       |
--R         +0  0  1+
--R                                                  Type: Matrix(PrimeField(2))
--E 21
--S 22 of 51
m2 := [[1,0,0],[0,1,1],[0,0,1]]
--R
--R
--R         +1  0  0+
--R         |       |
--R   (22)  |0  1  1|
--R         |       |
--R         +0  0  1+
--R                                                  Type: Matrix(PrimeField(2))
--E 22
--S 23 of 51
m3 := [[1,0,0],[1,1,0],[0,0,1]]
--R
--R
--R         +1  0  0+
--R         |       |
--R   (23)  |1  1  0|
--R         |       |
--R         +0  0  1+
--R                                                  Type: Matrix(PrimeField(2))
--E 23
--S 24 of 51
m4 := [[1,0,0],[0,1,0],[0,1,1]]
--R
--R

--R         +1  0  0+
--R         |       |
--R   (24)  |0  1  0|
--R         |       |
--R         +0  1  1+
--R                                                  Type: Matrix(PrimeField(2))
--E 24

———-

And these matrices act on the non-zero vectors of the corresponding vector space — * —

--S 25 of 51
vl : List Vector PrimeField 2
--R
--R                                                                   Type: Void
--E 25
--S 26 of 51
vl := [[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
--R
--R
--R   (26)  [[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
--R                                            Type: List(Vector(PrimeField(2)))
--E 26

———-

Now we can write down the action of our matrices on this list vl as a list of pairs — * —

--S 28 of 51
ll1 : List List Vector PrimeField 2 :=
   [ [ vl.i , m1*(vl.i) ] for i in 1..7 ]
--R
--R
--R   (27)
--R   [[[0,0,1],[0,0,1]], [[0,1,0],[1,1,0]], [[0,1,1],[1,1,1]], [[1,0,0],[1,0,0]],
--R    [[1,0,1],[1,0,1]], [[1,1,0],[0,1,0]], [[1,1,1],[0,1,1]]]
--R                                      Type: List(List(Vector(PrimeField(2))))
--E 28
--S 29 of 51
ll2 : List List Vector PrimeField 2 :=
   [ [ vl.i , m2*(vl.i) ] for i in 1..7 ]
--R
--R
--R   (28)
--R   [[[0,0,1],[0,1,1]], [[0,1,0],[0,1,0]], [[0,1,1],[0,0,1]], [[1,0,0],[1,0,0]],
--R    [[1,0,1],[1,1,1]], [[1,1,0],[1,1,0]], [[1,1,1],[1,0,1]]]

--R                                      Type: List(List(Vector(PrimeField(2))))
--E 29
--S 30 of 51
ll3 : List List Vector PrimeField 2 :=
   [ [ vl.i , m3*(vl.i) ] for i in 1..7 ]
--R
--R
--R   (29)
--R   [[[0,0,1],[0,0,1]], [[0,1,0],[0,1,0]], [[0,1,1],[0,1,1]], [[1,0,0],[1,1,0]],
--R    [[1,0,1],[1,1,1]], [[1,1,0],[1,0,0]], [[1,1,1],[1,0,1]]]
--R                                      Type: List(List(Vector(PrimeField(2))))
--E 30
--S 31 of 51
ll4 : List List Vector PrimeField 2 :=
   [ [ vl.i , m4*(vl.i) ] for i in 1..7 ]
--R
--R
--R   (30)
--R   [[[0,0,1],[0,0,1]], [[0,1,0],[0,1,1]], [[0,1,1],[0,1,0]], [[1,0,0],[1,0,0]],
--R    [[1,0,1],[1,0,1]], [[1,1,0],[1,1,1]], [[1,1,1],[1,1,0]]]
--R                                      Type: List(List(Vector(PrimeField(2))))
--E 31

———-

And we can coerce these lists to permutations — * —

--S 32 of 51
el1 : PERM Vector PrimeField 2 := coerceListOfPairs ll1
--R
--R
--R   (31)  ([1,1,0] [0,1,0])([1,1,1] [0,1,1])
--R                                     Type: Permutation(Vector(PrimeField(2)))
--E 32
--S 33 of 51
el2 : PERM Vector PrimeField 2 := coerceListOfPairs ll2
--R
--R
--R   (32)  ([0,1,1] [0,0,1])([1,1,1] [1,0,1])
--R                                     Type: Permutation(Vector(PrimeField(2)))
--E 33
--S 34 of 51
el3 : PERM Vector PrimeField 2 := coerceListOfPairs ll3
--R
--R

--R   (33)  ([1,1,0] [1,0,0])([1,1,1] [1,0,1])
--R                                     Type: Permutation(Vector(PrimeField(2)))
--E 34
--S 35 of 51
el4 : PERM Vector PrimeField 2 := coerceListOfPairs ll4
--R
--R
--R   (34)  ([0,1,1] [0,1,0])([1,1,1] [1,1,0])
--R                                     Type: Permutation(Vector(PrimeField(2)))
--E 35

———-

Now we can do the same operations as before, e.g.

— * —

--S 36 of 51
eval ( el3 , vl.5 )
--R
--R
--R   (35)  [1,1,1]
--R                                                  Type: Vector(PrimeField(2))
--E 36
--S 37 of 51
el2 * el1
--R
--R
--R   (36)  ([0,1,0] [1,1,0])([0,1,1] [1,0,1] [1,1,1] [0,0,1])
--R                                     Type: Permutation(Vector(PrimeField(2)))
--E 37
--S 38 of 51
movedPoints el4
--R
--R
--R   (37)  {[1,1,1],[1,1,0],[0,1,1],[0,1,0]}
--R                                             Type: Set(Vector(PrimeField(2)))
--E 38

———-

Let’s built the general linear group now — * —

--S 39 of 51
gl : PERMGRP Vector PrimeField 2 := [ el1 , el2 , el3 , el4 ]
--R
--R
--R   (38)

--R   <
--R       ([1,1,0] [0,1,0])([1,1,1] [0,1,1]),([0,1,1] [0,0,1])([1,1,1] [1,0,1])
--R    ,
--R       ([1,1,0] [1,0,0])([1,1,1] [1,0,1]),([0,1,1] [0,1,0])([1,1,1] [1,1,0])
--R     >
--R                                Type: PermutationGroup(Vector(PrimeField(2)))
--E 39

———-

And ask for its order — * —

--S 40 of 51
order gl
--R
--R
--R   (39)  168
--R                                                        Type: PositiveInteger
--E 40

———-

We can also ask for the orbit of the unordered set of vectors — * —

--S 41 of 51
setOfVectors : Set Vector PrimeField 2 := brace [ vl.2 , vl.4 , vl.6 ]
--R
--R
--R   (40)  {[0,1,0],[1,0,0],[1,1,0]}
--R                                             Type: Set(Vector(PrimeField(2)))
--E 41

———-

Under gl — * —

--S 42 of 51
orbit ( gl, setOfVectors )
--R
--R
--R   (41)
--R   {{[0,1,0],[1,0,0],[1,1,0]}, {[0,1,1],[1,0,0],[1,1,1]},
--R    {[0,0,1],[1,0,0],[1,0,1]}, {[0,1,1],[1,1,0],[1,0,1]},
--R    {[0,0,1],[1,1,0],[1,1,1]}, {[1,1,1],[0,1,0],[1,0,1]},
--R    {[0,0,1],[0,1,0],[0,1,1]}}
--R                                        Type: Set(Set(Vector(PrimeField(2))))
--E 42

———-

And also for the orbit of the ordered list — * —

--S 43 of 51
listOfVectors : List Vector PrimeField 2 := parts setOfVectors
--R
--R
--R   (42)  [[0,1,0],[1,0,0],[1,1,0]]
--R                                            Type: List(Vector(PrimeField(2)))
--E 43
--S 44 of 51
orbit ( gl, listOfVectors )
--R
--R
--R   (43)
--R   {[[0,1,0],[1,0,0],[1,1,0]], [[1,1,0],[1,0,0],[0,1,0]],
--R    [[0,1,0],[1,1,0],[1,0,0]], [[0,1,1],[1,0,0],[1,1,1]],
--R    [[1,0,0],[1,1,0],[0,1,0]], [[1,1,1],[1,0,0],[0,1,1]],
--R    [[1,1,0],[0,1,0],[1,0,0]], [[0,1,1],[1,1,1],[1,0,0]],
--R    [[0,0,1],[1,0,0],[1,0,1]], [[0,1,1],[1,1,0],[1,0,1]],
--R    [[1,0,0],[0,1,0],[1,1,0]], [[1,0,0],[1,1,1],[0,1,1]],
--R    [[1,0,1],[1,0,0],[0,0,1]], [[1,0,1],[1,1,0],[0,1,1]],
--R    [[1,1,1],[0,1,1],[1,0,0]], [[0,0,1],[1,0,1],[1,0,0]],
--R    [[0,1,1],[1,0,1],[1,1,0]], [[0,0,1],[1,1,0],[1,1,1]],
--R    [[1,1,1],[0,1,0],[1,0,1]], [[0,1,0],[1,1,1],[1,0,1]],
--R    [[1,0,0],[0,1,1],[1,1,1]], [[1,0,0],[1,0,1],[0,0,1]],
--R    [[1,1,0],[1,0,1],[0,1,1]], [[1,1,1],[1,1,0],[0,0,1]],
--R    [[1,0,1],[0,1,0],[1,1,1]], [[1,0,1],[1,1,1],[0,1,0]],
--R    [[1,0,1],[0,0,1],[1,0,0]], [[1,0,1],[0,1,1],[1,1,0]],
--R    [[0,0,1],[1,1,1],[1,1,0]], [[1,1,1],[1,0,1],[0,1,0]],
--R    [[0,1,0],[1,0,1],[1,1,1]], [[0,0,1],[0,1,0],[0,1,1]],
--R    [[1,1,0],[0,1,1],[1,0,1]], [[1,0,0],[0,0,1],[1,0,1]],
--R    [[1,1,0],[1,1,1],[0,0,1]], [[0,1,1],[0,1,0],[0,0,1]],
--R    [[1,1,1],[0,0,1],[1,1,0]], [[0,0,1],[0,1,1],[0,1,0]],
--R    [[1,1,0],[0,0,1],[1,1,1]], [[0,1,0],[0,1,1],[0,0,1]],
--R    [[0,1,1],[0,0,1],[0,1,0]], [[0,1,0],[0,0,1],[0,1,1]]}
--R                                       Type: Set(List(Vector(PrimeField(2))))
--E 44

———-

Now Rubik’s cube.

— * —

--S 45 of 51
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

--R
--R   (44)  (11 13 15 17)(12 14 16 18)(21 41 51 31)(22 42 52 32)(23 43 53 33)
--R                                                   Type: Permutation(Integer)
--E 45
--S 46 of 51
r : PERM INT := cycles [[21,23,25,27],[22,24,26,28],[13,37,67,43],[15,31,61,45],_
             [14,38,68,44]]
--R
--R
--R   (45)  (13 37 67 43)(14 38 68 44)(15 31 61 45)(21 23 25 27)(22 24 26 28)
--R                                                   Type: Permutation(Integer)
--E 46

———-

Some calculation in Rubik’s group:

— * —

--S 47 of 51
(f**2*r**2)**3
--R
--R
--R   (46)  (12 16)(24 28)(32 42)(38 44)
--R                                                   Type: Permutation(Integer)
--E 47
--S 48 of 51
rc := rubiksGroup()
--R
--R
--R   (47)
--R   <
--R       (11 13 15 17)(12 14 16 18)(21 41 51 31)(22 42 52 32)(23 43 53 33)
--R    ,
--R       (13 37 67 43)(14 38 68 44)(15 31 61 45)(21 23 25 27)(22 24 26 28)
--R    ,
--R       (11 57 61 23)(12 58 62 24)(13 51 63 25)(31 33 35 37)(32 34 36 38)
--R    ,
--R       (15 27 65 53)(16 28 66 54)(17 21 67 55)(41 43 45 47)(42 44 46 48)
--R    ,
--R       (11 41 65 35)(17 47 63 33)(18 48 64 34)(51 53 55 57)(52 54 56 58)
--R    ,
--R       (25 35 55 45)(26 36 56 46)(27 37 57 47)(61 63 65 67)(62 64 66 68)
--R     >
--R                                              Type: PermutationGroup(Integer)
--E 48
--S 49 of 51
order rc

--R
--R
--R   (48)  43252003274489856000
--R                                                        Type: PositiveInteger
--E 49
--S 50 of 51
orbits rc
--R
--R
--R   (49)
--R   {{11,13,15,17,21,23,25,27,31,33,35,37,41,43,45,47,51,53,55,57,61,63,65,67},
--R    {12,14,16,18,22,24,26,28,32,34,36,38,42,44,46,48,52,54,56,58,62,64,66,68}}
--R                                                      Type: Set(Set(Integer))
--E 50

———-

Can we interchange just two pieces with two visible faces on the cube and leave everything else fixed?

— * —

--S 51 of 51
member? (cycles([[12,14],[32,22]])$(PERM INT),rc)
--R
--R
--R   (50)  false
--R                                                                Type: Boolean
--E 51
)spool
)lisp (bye)

———-

References^{[1] nothing}

16