MAPLE V in Introductory
Group Theory:
Exploring Permutation Groups
1. Introduction
A
computer algebra software such as Maple V, a very powerful tool for doing
mathematics, can be effectively used in the undergraduate abstract algebra
course to encourage the discovery of mathematical ideas through guided
experiments. The main focus of the paper is to show how to
introduce discovery learning into abstract algebra class and how to use
a laboratory approach to teach basic concepts of group theory. We
will present some elementary group theory commands in MAPLE V's packages
group and combinat which may be useful in a first
abstract algebra course or introductory group theory.
Focusing
on the notion that "One cannot teach a computer how to do something
without learning it better oneself,' several of our exercises require
the students to write functions or procedures to implement abstract mathematical
ideas in a concrete way, such as "listing elements of a permutation
group", or "constructing an abstract group's table." Those
exercises really require the students to think about what the computer
is doing when it is performing the instructions given it. As a result,
they will begin to form a mental image of the ideas they are learning,
and come to truly understand these ideas.
Another
type of assignments requires students to identify a group by means of a
set of generators and a set of relations between those generators. The
students then verify their answer by constructing the group using grelgroup
and subgrel commands of Maple V. Such construction
is useful in distinguishing finite groups from infinite groups.
Another useful
command of Maple V is the permrep command. The paper will present
an example illustrating the use of Maple V's permrep command in
the study of Cayley's Regular Representation Theorem.
2. Listing elements of
a permutation group using MAPLE's functions.
2.1. permgroup(degree, {generators})
This routine constructs a permutation group of
specified degree and generators.
Note: All permutations in MAPLE V must
be written as disjoint cycles.
Example: The symmetric group S_3. >with(group):
>
S_3 := permgroup(3,{[[1,2]],[[1,2,3]]});
S_3
:= permgroup(3, {[[1, 2]], [[1, 2, 3]]})
2.2. grouporder
(group)
This routine gives the order (or number of elements)
of a group.
Example : To verify S_3 above has 6 elements:
> grouporder(S_3);
6
2.3. cosets(PG,SG)
This routine gives a complete list of right coset
representatives for a subgroup SG of a permutation group PG. A set of permutations
in disjoint cycle notation is returned.
- 2.3.1 Note:
- PG and SG must be permutation groups of the same
degree.
- This routine can be used to list elements of
a permutation group when SG is the trivial subgroup, { }, of the same degree.
- 2.3.2 Example
- > ident := permgroup
(3, {[]} ):
- > cosets(S_3, ident);
- {[],
[[1, 2]], [[1, 2, 3]], [[1, 3, 2]], [[1, 3]], [[2, 3]]}
3. Listing elements of permutation groups
without the cosets command.
The following MAPLE V' s functions will be required.
- (i) permute(n)
- This
function (found in MAPLE V's combinat package) constructs a list of all
permutations
of n objects.
- (ii) convert(permlist, 'disjcyc')
- This
function converts permutations in a list into disjoint cycles.
- (iii) groupmember(element, PG)
- This
function tests if a given element is a member of the permutaion group PG.
3.1 Outline of Procedure (for listing elements
of a permutation group )
- (i) Create a list L0 of all
permutations on n letters using combinat[permute](n)
- (ii) Convert all elements in
L0 to disjoint cycles with convert(L0, 'disjcyc').
- (iii) Create the permutation group
G of degree n generated by generators in the set L using
permgroup(n, L).
- (iv) Test each elements in L0 for membership
in G using groupmember(element, G)
- (v) Put those that are members
of G in a set L1. Display L1.
- 3.2 Procedure gpElements (n, L)
- (lists all elements of a permutation
group of degree n generted by a list of generators L)
- > gpElements := proc(n::integer,G)
- > local i,j,L0,L1;
- > L0 := combinat[permute](n);
- > for i from
1 to nops(L0) do
- > g.i
:= convert(L0[i],'disjcyc');
- > od;
- > L1 := []:
for i from 1 to nops(L0) do
- > if
groupmember(g.i,G) then
- > L1
:= [op(L1),g.i];
- > fi;
- > od;
- > RETURN(L1);
- > end;
3.3 Example
- > S_3 := permgroup(3,{[[1,2]],[[1,2,3]]});
- S_3
:= permgroup(3, {[[1, 2]], [[1, 2, 3]]})
- > gpElements(3, S_3);
- [[],
[[2, 3]], [[1, 2]], [[1, 2, 3]], [[1, 3, 2]], [[1, 3]]]
- > S_4 := permgroup(4,{[[1,2]],[[1,2,3,4]]});
- S_4
:= permgroup(4, {[[1, 2]], [[1, 2, 3, 4]]})
- > gpElements(4, S_4);
- [[], [[3, 4]], [[2, 3]], [[2, 3, 4]], [[2, 4,
3]], [[2, 4]], [[1, 2]], [[1, 2], [3, 4]],
- [[1, 2, 3]], [[1, 2, 3, 4]], [[1, 2, 4, 3]],
[[1, 2, 4]], [[1, 3, 2]], [[1, 3, 4, 2]],
- [[1, 3]], [[1, 3, 4]], [[1, 3],[2, 4]], [[1,
3, 2, 4]], [[1, 4, 3, 2]], [[1, 4, 2]],
- [[1, 4, 3]], [[1, 4]], [[1, 4, 2, 3]], [[1,
4], [2, 3]]]
4. Embedded Subgroups of a Symmetric Group
and Cayley's Theorem
By
comparing an embedded subgroup of a symmetric group with a symmetric group
of lower degree having exactly the same elements (in disjoint cycle notations),
the students will see the distinction between subgroup of a symmetric group
and a subset which is also a group but not a subgroup of that symmetric
group. In particular, this experiment will illustrate the following
points
(i) S_3 is not a subgroup of S_4. Although, written
as disjoint cycle, every element of S_3 is in S_4 and S_3 is a group. However,
a subgroup of a permutation group must have the same degree. I.e.
they must act on the same set of letters.
(ii) S_3 is isomorphic to an embedded subgroups of S_4.
(iii) Any
group is isomorphic to a subgroup of a symmetric group. (Cayley's Theorem)
4.1 Procedure
Symm (n, degree)
- (creates an embedded
subgroup S_n of a symmetric group S_degree)
- > Symm := proc (n::integer,degree::integer)
- > local i, S:
- > if degree < n
then ERROR (`argument 2 must be > argument 1`); fi;
- > S := permgroup(degree,{[[1,2]],[[seq
(i, i = 1..n)]]});
- > RETURN(S);
- > end;
4.2 Example.
- > S3 := Symm(3,4):
- > S_4 := permgroup(4,{[[1,2]],[[1,2,3,4]]}):
- > issubgroup(S3,S_4);
- true
- > S_3:=permgroup(3,{[[1,2]],[[1,2,3]]}):
- > issubgroup(S_3,S_4);
- false
- > gpElements(3,S3);
- [[],
[[2, 3]], [[1, 2]], [[1, 2, 3]], [[1, 3, 2]], [[1, 3]]]
- > gpElements(3,S_3);
- [[],
[[2, 3]], [[1, 2]], [[1, 2, 3]], [[1, 3, 2]], [[1, 3]]]
5. Cayley's Group Table
A useful tool for studying properties of a finite group is its abstract
group table. So one of our projects is to have the students write
a procedure to construct a table for a permutation group G. The procedure
calls the already defined function gpElements to create a list of
all elements of G then it constructs a two dimensional array of size o(G) x o(G).
The product of two elements of G is computed by the MAPLE V's function:
group[mulperms](L0[i],L0[j]), where L0 = ordered list of elements
of G and L0[i] = ith entry in the list. All entries in the list are
in disjoint cycle notations
5.1 Procedure for constructing Abstract
Group Table
- > abs_gp_table:=proc(n::integer,G)
- > local i, j, L0, S_table, g, k ;
- > L0:=gpElements(n,G);
- > S_table:=array(1..(nops(L0)+1),1..(nops(L0)+1));
- > for i from 1 to nops(L0) do
- > for j from 1 to
nops(L0) do
- > for
k from 1 to nops(L0) do
- > if
L0[k]=group[mulperms](L0[i],L0[j]) then
- >
S_table[i+1,j+1]:=a.k; fi;
- > od; od; od;
- > S_table[1,1] := `*` ;
- > for j from 1 to nops(L0) do
- > S_table[1,j+1]:=a.j;
- > S_table[j+1,1]:=a.j;
- > od;
- > print(convert(S_table, matrix));
- > print(seq(a.i=L0[i],i=1..nops(L0)));
- > end;
6. Regular Permutation Representations.
This section
will introduce MAPLE V's function: group[permrep] for finding
a permutation representation of a group. The calling Sequence
is permrep(sbgrl) , where sbgrl is a subgroup of a group described
by generators and relations (i.e. a subgrel)
6.1 Description of group[permrep]
This function
finds all the right cosets of the given subgroup in a given group then
assigns integers consecutively to these cosets and constructs a permutation
on these coset numbers for each group generator. It returns
the permutation group generated by these permutations. Thus the permutation
group will be a homomorphic image of (but not necessarily isomorphic to)
the original group. A permgroup is returned whose generators are
named the same as the original group generators.
Trick: To find a regular representation of elements
of finite group G, we let the subgr to be the trivial subgroup
{ }.
6.2 Example.
Suppose G is generated
by the relations: y^2 = 1 and yxy = x^2. We let SG to be the trivial subgroup
of G generated by {[]}.
- > G := grelgroup({x,y}, {[y,x,y,1/x,1/x],[y,y]}):
- > SG := subgrel({y=[]},G):
- > PG:= permrep(SG);
- PG := permgroup(6,{x
= [[1, 5, 4], [2, 3, 6]], y = [[1, 2], [3, 4],[5, 6]]})
- > grouporder(PG);
- 6
- > gpElements(6,PG);
- [[],
[[1, 2], [3, 4], [5, 6]], [[1, 3], [2, 5], [4, 6]], [[1, 4, 5],
- [2,
6, 3]], [[1, 5, 4], [2, 3, 6]], [[1, 6], [2, 4], [3, 5]]]
Since
the abstract group Table for G, will be the same as the abstract group
table for PG we can use our procedure abs_gp_table(n,PG) to construct
an abstract group table for G.
6.3 Cayley's Table: an application
of the procedure abs_gp_table
- > abs_gp_table(6,PG);
- [* a1 a2 a3 a4 a5 a6]
- [a1 a1 a2 a3 a4 a5 a6]
- [a2 a2 a1 a5 a6 a3 a4]
- [a3 a3 a4 a1 a2 a6 a5]
- [a4 a4 a3 a6 a5 a1 a2]
- [a5 a5 a6 a2 a1 a4 a3]
- [a6 a6 a5 a4 a3 a2 a1]
- a1 = [], a2 = [[1, 2], [3, 4], [5, 6]],
- a3 = [[1, 3], [2, 5], [4, 6]], a4 = [[1, 4, 5],
[2, 6, 3]],
- a5 = [[1, 5, 4], [2, 3, 6]], a6 = [[1,
6], [2, 4], [3, 5]]
6.4. A Conway's Problem: An
application of permrep.
- Problem. Suppose Gis generated
by the relations: ab = c, bc =a, ca = b.
- Find the order of G
and construct its Cayley's table.
Solution,
- > C := grelgroup({a,b,c},{[a,b,1/c],[b,c,1/a],[c,a,1/b]});
- C := grelgroup({a, b, c}, {[b, c,
1/a], [c, a, 1/b], [a, b, 1/c]})
- > grouporder(C);
- 8
- > sc := subgrel({y=[]},C):
- > PC:=permrep(sc);
- PC
:= permgroup(8, {a = [[1, 3, 5, 8], [2, 6, 7, 4]],
- c = [[1, 4, 5, 6], [2, 3, 7, 8]], b = [[1,
2, 5, 7], [3, 4, 8, 6]]})
- > grouporder(PC);
- 8
- > gpElements(8,PC);
- [ [],
[[1, 2, 5, 7], [3, 4, 8, 6]], [[1, 3, 5, 8], [2, 6, 7, 4]], [[1, 4, 5,
6],
- [2,
3, 7, 8]], [[1, 5], [2, 7], [3, 8], [4, 6]], [[1, 6, 5, 4], [2, 8,
7, 3]], [[1, 7, 5, 2],
- [3,
6, 8, 4]], [[1, 8, 5, 3], [2, 4, 7, 6]] ]
- > abs_gp_table(8,PC);
- [* a1 a2 a3 a4 a5 a6 a7 a8]
- [a1 a1 a2 a3 a4 a5 a6 a7 a8]
- [a2 a2 a5 a6 a3 a7 a8 a1 a4]
- [a3 a3 a4 a5 a7 a8 a2 a6 a1]
- [a4 a4 a8 a2 a5 a6 a1 a3 a7]
- [a5 a5 a7 a8 a6 a1 a4 a2 a3]
- [a6 a6 a3 a7 a1 a4 a5 a8 a2]
- [a7 a7 a1 a4 a8 a2 a3 a5 a6]
- [a8 a8 a6 a1 a2 a3 a7 a4 a5]
-
The abstract elements of PC correspond to the
following permutations
- a1 = [], a2 = [[1, 2, 5, 7], [3, 4, 8, 6]], a3
= [[1, 3, 5, 8], [2, 6, 7, 4]],
- a4 = [[1, 4, 5, 6], [2, 3, 7, 8]], a5 = [[1,
5], [2, 7], [3, 8], [4, 6]],
- a6 = [[1, 6, 5, 4], [2, 8, 7, 3]], a7 = [[1,
7, 5, 2], [3, 6, 8, 4]],
- a8 = [[1, 8, 5, 3], [2, 4, 7, 6]]
7. Conclusion
A
computer algebra system, such as MAPLE V, can and should be used to
help students learn abstract mathematical ideas by getting them involved
in constructing the ideas. We strongly believe that students' active
involvement with constructing mathematics for themselves is essential to
understanding concepts. When students write a procedure, such as
gpElements, that makes use of several other related concepts, they
will learn those concepts through the action of having to describe them
precisely to the computer. The mathemaical ideas they are able to put together
for themselves with the help of MAPLE V will tend to be rich and meaningful
to them.
8. References
1. Baxter, Nancy, Dubinsky,
Ed, & Levin, Gary, Learning Discrete Mathematics with ISETL, Springer-Verlag, New
York, 1988.
2. Redfem, D., The Maple
Handbook, Springer-Verlag, New York, 1993.
Suda
Kunyosying
Shepherd
College
Shepherdstown, WV 25443
skunyosy@shepherd.wvnet.edu