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`);

`   Basic group theory commands:   `

`gp_elements, conjugation, conjugacy_class, conjuga...

`conjugacy_classes_reps, gp_table, abs_gp_table, mu...

`perm_value, perm_sign, permute_vector_left, permut...

`mult_sets, is_subset, is_sublist, left_coset_reps,...

`cartesian_product, cartesian_power, conj_type, con...

`order_of_element, inverse_of_element, elements_ord...

`innerprod, is_reducible, array_to_disjcyc, list_to...

`disjcyc_to_list, list_to_array ... loaded.  group2...

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]];

U := [[1, 3, 8, 6], [2, 5, 7, 4], [9, 33, 25, 17], ...

DD := [[41, 43, 48, 46], [42, 45, 47, 44], [14, 22,...

R := [[25, 27, 32, 30], [26, 29, 31, 28], [3, 38, 4...

L := [[9, 11, 16, 14], [10, 13, 15, 12], [1, 17, 41...

F := [[17, 19, 24, 22], [18, 21, 23, 20], [6, 25, 4...

B := [[33, 35, 40, 38], [34, 37, 39, 36], [3, 9, 46...

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

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

[3, 5, 4, 1, 2]

[3, 5, 8, 2, 7, 1, 4, 6, 33, 34, 35, 12, 13, 14, 15...

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

12

4

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

id := [1, 2, 3, 4, 5]

[]

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

pm := [3, 5, 4, 1, 2]

[[1, 3, 4], [2, 5]]

>

> Id:=list_to_array(id);

Id := matrix([[1, 2, 3, 4, 5], [1, 2, 3, 4, 5]])

> array_to_list(Id);

[1, 2, 3, 4, 5]

> ID:=array_to_disjcyc(Id);

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 Sn, 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);

p := [[1, 2, 5], [3, 4]]

7

-1

233

-1

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;

`All possible perms of {1,2,3,4} : `

`Array: `, matrix([[1, 2, 3, 4], [1, 2, 3, 4]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [1, 2, 4, 3]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [1, 3, 2, 4]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [1, 3, 4, 2]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [1, 4, 2, 3]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [1, 4, 3, 2]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [2, 1, 3, 4]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [2, 1, 4, 3]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [2, 3, 1, 4]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [2, 3, 4, 1]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [2, 4, 1, 3]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [2, 4, 3, 1]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [3, 1, 2, 4]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [3, 1, 4, 2]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [3, 2, 1, 4]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [3, 2, 4, 1]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [3, 4, 1, 2]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [3, 4, 2, 1]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [4, 1, 2, 3]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [4, 1, 3, 2]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [4, 2, 1, 3]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [4, 2, 3, 1]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [4, 3, 1, 2]]), `D...

`Array: `, matrix([[1, 2, 3, 4], [4, 3, 2, 1]]), `D...

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

[[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.3x1019 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]]});

G := permgroup(5,{[[1, 2], [3, 5]], [[1, 2, 3]]})

> degree_permgroup(G);

5

> gens_permgroup(G);

{[[1, 2], [3, 5]], [[1, 2, 3]]}

> gp_elements(G);

[[], [[2, 3, 5]], [[2, 5, 3]], [[1, 2], [3, 5]], [[...

> grouporder(G);

12

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]]});

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

matrix([[[], [[2, 4]], [[1, 2], [3, 4]], [[1, 2, 3,...

Exercise 6 : Find the group table of the group S3 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);

[[1, 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);

[4, [[], [[2, 3]], [[1, 2]], [[1, 3]]]]

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

[9, [[], [[2, 3, 4]], [[2, 4, 3]], [[1, 2, 3]], [[1...

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

{[[2, 4]], [[1, 3]]}

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 S3, S4, and D4 are:

> conjugacy_classes(D4);

{{[[1, 2], [3, 4]], [[1, 4], [2, 3]]}, {[[1, 2, 3, ...

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

{[], [[1, 3], [2, 4]], [[1, 2, 3, 4]], [[2, 4]], [[...

Exercise 9 : (a) Find the conjugacy classes of the group S3.

(b) Find a complete set of representatives of each conjugacy class of S5.

Using Symm you can enter the symmetric group Sm as a subgroup of Sn, for m<n. Below, G is the symmetric group S4 and H is S3 regarded as the subgroup which leaves 4 fixed.

>

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

G := permgroup(4,{[[1, 2]], [[1, 2, 3, 4]]})

H := permgroup(4,{[[1, 2, 3]], [[1, 2]]})

24

6

To obtain a set of right coset representatives of S3 in S4, type

> Cr:=right_coset_reps(G,H);

C := {[], [[3, 4]], [[2, 4, 3]], [[1, 4, 3, 2]]}

To obtain a set of left coset representatives of S3 in S4, type

> Cl:=left_coset_reps(G,H);

Cl := {[], [[1, 2, 3, 4]], [[3, 4]], [[2, 3, 4]]}

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

L := [[1, 2, 4], [3, 6]]

matrix([[0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0,...

matrix([[0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0...

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

g := [[1, 2, 3]]

h := [[1, 2], [3, 4]]

3

4

1

1

3

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. wdj@usna.edu