**Exercises for the group package**

You must have the group22_v7.mpl file and Maple 7 to do these exercises (group22_v5.mpl might work if you only have Maple 5). It is available from group22_v7.mpl (click on the groups link then find the group2.2 link and download it).

wdj, group_exercises_v7.mws, 8-2001

`> `
**restart;**

`> `
**with(group):**

`> `
**with(combinat):**

Warning, the protected name Chi has been redefined and unprotected

`> `
**read(`c:/maplefiles/groups/group22_v7.mpl`);**

There is a labeling of the 48 non-center facets of the Rubik's cube such that the moves R(ight),L(eft),U(p),D(own),F(ront),B(ack) (given by a clock-wise quarter turn) are described as permutations of {1,2,...,48} by:

`> `
**U:=[[1,3,8,6],[2,5,7,4],[9,33,25,17],
[10,34,26,18],[11,35,27,19]];
DD:=[[41,43,48,46],[42,45,47,44],[14,22,30,38],
[15,23,31,39],[16,24,32,40]];
## note: D is "protected" by MAPLE
R:=[[25,27,32,30],[26,29,31,28],[3,38,43,19],
[5,36,45,21],[8,33,48,24]];
L:=[[9,11,16,14],[10,13,15,12],[1,17,41,40],
[4,20,44,37],[6,22,46,35]];
F:=[[17,19,24,22],[18,21,23,20],[6,25,43,16],
[7,28,42,13],[8,30,41,11]];
B:=[[33,35,40,38],[34,37,39,36],[3,9,46,32],
[2,12,47,29],[1,14,48,27]];**

These permutations will be used to illustrate some of the examples below.

`> `
**disjcyc_to_list([[1, 3, 4], [2, 5]]);
disjcyc_to_list(U);**

`> `
**order_of_element([[1,2,3],[4,5,6,14]]);
order_of_element(U);**

The identity permutation of {1,2,3,4,5} can be written in 3 ways:

(1) as a list [1,2,3,4,5],

(2) as a array (see below),

(3) in disjoint notation [].

The group package has conversion routines between them.

`> `
**id:=[1,2,3,4,5];
list_to_disjcyc(id);**

`> `
**pm:=[3,5,4,1,2];
list_to_disjcyc(pm);
#exercise**

`> `

`> `
**Id:=list_to_array(id);**

`> `
**array_to_list(Id);**

`> `
**ID:=array_to_disjcyc(Id);**

**Exercise 1**
: (a) Convert [3,5,4,1,2] to array notation and to disjoint cycle notation.

(b) Convert [[1,4,3],[2,5]] to array notation and to list notation.

(c) Convert R to array notation and to list notation.

The sign of a permutation can be computed using
**perm_sign**
. More precisely, the swapping number (called the Bruhat length in some references) can be computed using the
**swap**
command. The
**swap(p)**
command determines the swapping number of p in
S_{n}, where the swapping number of a permutation is
the number of inequalities i<j, 1<=i,j<=n, swapped
by p. The sign of a permutation p, sgn(p),
satisfies sgn(p)=(-1)^swap(p). Each has an optional second
argument to specify the degree.

`> `
**p:=[[1,2,5],[3,4]];
swap(p);
perm_sign(p);
swap(L);
perm_sign(L);**

**Exercise 2**
: (a) Find the sign and swapping number of (1,4,7)(2,5).

(b) Same for the Rubik's cube move B.

`> `
**L:=permute(4):
print(`All possible perms of {1,2,3,4} : `);
for x in L do
print(`Array: `,list_to_array(x),`Disjoint cycle: `,list_to_disjcyc(x),` list: `,x);
od;**

**Exercise 3**
: List all permutations in S_5.

The mult_list command multiplies together all the disjoint cycles in a list:

`> `
**mult_list([[[1,2],[3,5]],[[1,2]],[[1,2,3,4,5]]]);
**
multiplies (1,2)(3,5) times (1,2) times (1,2,3,4,5).

**Exercise 4**
: (a) Multiply (1,2,3,4,5,6,7) times (2,5) times (7,6,5,4,3,2,1).

(b) Multiply R*L*U*DD*F*B.

A permutation group in MAPLE is entered using the
permgroup
command in the share
group
package. The permutations in MAPLE are written as lists of lists. For example, the cyclic permutation (1,2,3) is written [[1,2,3]] and the disjoint product (1,2)*(3,4,5) is written [[1,2],[3,4,5]]. The identity element 1 is written []. The subgroup of S_5 generated by (1,2,3) and (1,2)*(3,5) is given in MAPLE by the command
permgroup(5,{[[1,2,3]],[[1,2],[3,5]]});
. This is how we shall enter groups into MAPLE in this worksheet.

The Rubik's cube group, corresponding to the set of all possible "states" of the Rubik's cube, is given in MAPLE by
permgroup(48,{U,DD,L,R,F,B});
However, this group is probably too large for MAPLE to handle (it has about 4.3x10_{19} elements - try GAP of MAGMA instead).

The
**group22_v7.mpl**
program
gp_elements
lists the elements of a group. The degree and generators and be recovered using the degree_permgroup and gens_permgroup commands. The size of the group can be obtained from the
**group**
package's
**grouporder**
command.

`> `
**G:=permgroup(5,{[[1,2,3]],[[1,2],[3,5]]}); **

`> `
**degree_permgroup(G);**

`> `
**gens_permgroup(G);**

`> `
**gp_elements(G);**

`> `
**grouporder(G);**

**Exercise 5**
: (a) List all the elements in the group G generated by (1,2,3) and (1,2)*(3,4).

(b) List all the elements in the group S_4 generated by (1,2) and (1,2,3,4).

(c) How many positions of the Rubik's cube can be obtained by only using the moves R and F? (Hint: Consider the "two faces subgroup" of the Rubik's cube group generated by F and R.)

`> `
**D4:=permgroup(4,{[[1,2],[3,4]],[[1,2,3,4]]});**

The group table of a permgroup, as a group of permutations, can be displayed using the
**gp_table**
command. It can be messy, as the example of D4 shows:

`> `
**gp_table(D4);**

**Exercise 6**
: Find the group table of the group S_{3}
generated by (1,2) and (1,2,3).

The mulperm_power command returns the k-th power of a disjoint cycle:

`> `
**mulperm_power([[1,2,3]],2);**

The elements of a given order can be determined
using the **elements_order**
command. For example:

`> `
**elements_order0(3,{[[1,2]],[[2,3]]},2);**

`> `
**G:=permgroup(3,{[[1,2]],[[2,3]]}):
elements_order(G,3);**

**Exercise 7**
: Find all elements of order 2 in D4.

The program conjugacy_class lists the conjugacy class of an element of a group. For example, the conjugacy class of [[2,4]] in the symmetric group D4 is:

`> `
**conjugacy_class([[2,4]],D4);**

**Exercise 8**
: Find the conjugacy class
of [[2,4]] in the group D4.

The function
**conjugacy_classes**
lists all the conjugacy classes of a group.
For example, the conjugacy classes of S_{3}, S_{4},
and D4 are:

`> `
**conjugacy_classes(D4);**

To find a complete set of representatives
of each conjugacy class of a permutation group G, use the command
**conjugacy_classes_reps**. For example to find one element in each
class of D4, type

`> `
**conjugacy_classes_reps(D4);**

**Exercise 9**
: (a) Find the conjugacy classes of the group
S_{3}.

(b) Find a complete set of representatives
of each conjugacy class of S_{5}.

Using **Symm** you can enter the symmetric
group S_{m} as a subgroup of S_{n}, for m<n.
Below, G is the symmetric group S_{4} and H is
S_{3} regarded as the subgroup which leaves 4 fixed.

`> `

`> `
**G:=Symm(4,4); H:=Symm(3,4);
grouporder(G);grouporder(H);**

To obtain a set of right coset representatives of S_{3}
in S_{4}, type

`> `
**Cr:=right_coset_reps(G,H);**

To obtain a set of left coset
representatives of S_{3} in S_{4}, type

`> `
**Cl:=left_coset_reps(G,H);**

**Exercise 10**
: Obtain both left and right coset representatives of D4 in S4.

The **perm_matrix**
command computes the associated permutation matrix of a
permutation of {1,2,...,n} in disjoint cycle notation.
It has an optional second argument to specify the
degree (the maximum of the entries in the disjoint cycle
notation is the default degree):

`> `
**L:=[[1,2,4],[3,6]];
perm_matrix(L);
perm_matrix(L,7);**

**Exercise 11**: Find the permutation matrix
of a=[[1,2,3]], b=[[1,3]], and ab. Verify that the
permutation matrix of ab is the
product of the permutation matrices of a and of b.

The action of the permutation
group G on {1,2,...,degree(G)} can be determined using the
**perm_value**
command. The **perm_value**
command determines the value (i)p of a
permutation p at an element i.

`> `
**g:=[[1,2,3]];
h:=[[1,2],[3,4]];
perm_value(g,2);
perm_value(g,4);
perm_value(g,3);
perm_value(h,2);
perm_value(h,4);**

**Exercise 12**
: Compute the effect of the
Rubik's cube permutation F on each of the numbers i=1,2,...,10.

`> `

Application: The rotation game

On some cell phones, in particular the Nokia 7160 (tm),
there is a game called ``Rotation''. It is a 3x3 grid, of the form

a1 a2 a3

a4 a5 a6

a7 a8 a9

The letters could be scrambled randomly in an actual game.
The allowed moves are rotations of the following form, or
combinations thereof:

In cycle notation, r1=(a1,a2 ,a5 ,a4), which sends the
above grid to the rotation

a4 a1 a3

a5 a2 a6

a7 a8 a9 ,

r2=(a2 ,a3 ,a6 ,a5), r3=(a4 ,a5 ,a8 ,a9 ), r4=(a5 ,a6 ,a9 ,a8 ).

In other words, a legal move in the Rotation game is any permutation of the form

r{i_1}r{i_2}...r{i_k}, where 1 <= i_j <= 4 for all 1 <= j <= N.

**Question**
: Can each permutation of {1,2,...,9} be
expressed in the form

r{i_1}r{i_2}...r{i_k}, where 1 <= i_j <= 4 for
all 1 <= j <= N?

This question is actually easy to answer using group theory.

**Exercise 13**
: Use the
**permgroup**
and
**grouporder**
command to answer this.

Last modified 11-16-2001.