Mathematics with Maple

S.Duzhin

Lesson 10: Groups

Mathematics: Groups, subgroups, cosets, generators.

Maple: with(group).

Key words:

group, subgroup, coset

permutation group

associativity, commutativity, unit (of a group).

generators and relations

order of an element

cyclic group

In this lesson, we will review some important notions related to finite groups, especially to permutation groups.

A finite group is a finite set of arbitrary elements G={a1,a2,...,an} with an operation * : G x G -> G such that

1) (x*y)*z = x*(y*z) for any three elements x,y,z of G

(associativity)

2) among a1,a2,...,an there is an element with the property

e*x = x*e = x for any element x of G

(unit element)

3) for every x in G there is an element y in G such that x*y = y*x = e

(existence of the inverse element; usually y is denoted by 1/x)

The operation denoted here by * may be of arbitrary nature, e.g. addition of numbers, multiplication of numbers or matrices, composition of functions or permutations or some weird operation given by a formula or an algorithm.

Example 1. Let A be the set of 4 complex numbers {1,-1,i,-i}, where i is the square root of -1 (in Maple, you have to denote it by the capital letter I).

Check that A is a group with respect to ordinary multiplication.

Solution. Before going to the three properties 1), 2), 3), one has to check that the product of any two out of the given 4 numbers is always one if these numbers.

The most transparent way to do this with Maple is to define two matrices, 1x4 and 4x1, consisting of these numbers, and multiply them:

> with(linalg):

> row:=matrix([[1,I,-1,-I]]);

[Maple Math]

> col:=matrix([[1],[I],[-1],[-I]]);

[Maple Math]

> multiply(row,col);

[Maple Math]

You see that all products x*y belong to A.

Associativity holds because it is a general property of the multiplicaiton of numbers. Unit element is 1. And every element of A has an inverse in A, because 1/-1 = -1, 1/I = -I, 1/-I = I.

Exercise 1. Check that the set B that consists of the six different roots of 1 of degree 6 (i.e. all complex numbers x such that x^6=1) makes a group.

If the nature of the operation is well explained and we are given several elements of that group, we can try and see what are the other elements of that group, by performing the group operation on the given elements, then on the elements that we obtain in this way, and so on.

Example 2. (Group of functions generated by 1-x and 1/x).

Prove that there is a finite group that contains the two functions, f(x) = 1-x and g(x) = 1/x, where the operation is the composition of functions.

Solution. Here are our two functions in Maple's functional notation (this notation is convenient when you want to evaluate the function on any argument):

> f:= x -> 1-x;

[Maple Math]

> g:= x -> 1/x;

[Maple Math]

Now, since the operation is the composition of functions, the group must also contain the functions f(f(x)), f(g(x)), f(g(g(f(x))), ... (all the possible combinations). Let us try some of them:

> f(f(x));

[Maple Math]

Aha, this is the identity function x -> x. It plays the role of the unit element with respect to teh functional composition, so let us denote it by

> e:= x -> x;

[Maple Math]

Let us do the same with the second given function:

> g(g(x));

[Maple Math]

This is also e, the identity function.

Using the vocabulary of group theory, we can state these equalities as

f*f = e,

g*g = e.

So far, we have only 3 elements in our set: {e,f,g}. Let us try other compositions:

> p:= x -> f(g(x));

[Maple Math]

> p(x);

[Maple Math]

That's something new!

We get {e,f,g,p}.

> q:=x -> g(f(x));

[Maple Math]

> q(x);

[Maple Math]

This is again different from e,f,g,p.

Thus, we obtain 5 elements {e,f,g,p,q}.

> r:=normal(g(p(x)));

[Maple Math]

Something new again!

6 elements: {e,f,g,p,q,r}

Will we always obtain new elements?

> normal(f(q(x)));

[Maple Math]

This is the element r which is not new.

Try to find some more compositions between the elements {e,f,g,p,q,r}

and you will see that you not get anything new!

Thus, the group generated by f and g, has order 6.

Exercise 2.

How many different functions can you obtain from

f(x) = 1/x and g(x) = (x-1)/(x+1) using the composition of functions?

Remark. In Lesson 7 (exercise 2 and before it) we have already tried the similar procedure of group generation. The group we talked about there was the group of all integer matrices with determinant 1 ("modular group").

Now let us load the special Maple package designed for the study of finite groups, especially permutation groups.

> with(group);

Warning, new definition for center

[Maple Math]
[Maple Math]

The command "permgroup" is used to construct a group of permutations generated by several given permutations.

This command takes two arguments: a number (the degree of permutations, i.e. the number of symbols that are permuted) and the set of generators.

Example 3. Define the group of all permutations of degree 3, find its order (the number of elements) and the list of elements.

Solution. The complete group of permutations S3 is generated by tranpositions of neighbours:

> matrix([[1,2,3],[2,1,3]]);

[Maple Math]

> matrix([[1,2,3],[1,3,2]]);

[Maple Math]

The first one (transposition of 1 and 2 ) is denoted in Maple-group as [1,2], the second one as [2,3].

Now the group S3 can be defined as:

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

[Maple Math]

Now we can do some computations.

First of all, let us find the order of the group (how many elements does it have?)

> grouporder(S3);

[Maple Math]

Remember that 6 = 3!

Now let us obtain the list of all elements in the group.

There is no such direct command in "group" package, but there is a much more powerful command for the coset decomposition.

Note that the coset decomposition with respect to the unit subgroup {e} gives you the list of all elements of a group.

Let us try it on our example.

> ?cosets;

So, the command cosets takes two arguments: the group itself and the subgroup.

Let us define the unit subgroup as generated by the unit permutation []

(the empty list inside the brackets means that nothing is permuted).

> U:= permgroup(3, {[ ]});

[Maple Math]

> cosets(S3,U);

[Maple Math]

This is the list of all permutations of degree 3.

You can multiply them using the function mulperms.

Exercise 3. Get help about mulperms (?mulperms;) and compute the product of the permutations [1,3,2] and [1,3] using it. Then make the same computation by hand and compare.

Exercise 4. Define the group of all permutations of degree 4, find its order and th list of elements.

Exercise 5. How many different permutations of degree 7 can be obtained taking the products of the two permutations [1,2,3,4] and [4,5,6,7]?

Now we will try another way to define finite groups -- through generators and relations.

Unfortunately, the list of commands displayed after with(group); does not contain two very important commands which are present in the "group" package: grelgroup and subgrel.

Let us see their meaning using Maple help.

> ?grelgroup;

This is a very convenient way to define a finite group -- by generators and relations. The first argument of this command is a set {} of some identifiers (names of the generators), and the second argument is a set of lists (every list is enclosed in brackets []). Each list in this set denotes a relation between generators (the product of generators equal to 1.

The simplest class of groups are the groups with 1 generator, also called cyclic groups.

Example 4. Cyclic group of order 3 (generated by one element a that satisfies one relation aaa=1, or a^3=1).

> C3:=grelgroup({a}, {[a,a,a]});

[Maple Math]

You can find the order of this group:

> grouporder(C3);

[Maple Math]

And the list of its elements expressed through the generators:

> cosets(subgrel({e=[ ]},C3));

[Maple Math]

Here and everywhere [ ] stands for the empty list, which corresponds to the unit element of the group.

Exercise 6. Define the group with two generators, s and v, and three relations:

s^3=e, v^7=e, s*v*1/s = v^2. Find the number of elements in this group.

Hint. The relations should be written as lists of symbols s,v,1/s and 1/v whose product equals e.