Abstract Algebra with Maple
Chapter 3: Groups

3: Groups

Groups U ( n )

Here is the definition of groups formed by relatively prime with n integers mod n . I used the name un for them since is reserved in Maple for Chebyshev polynomials.

> un:=n->select(m->evalb(igcd(m,n)=1),[$1..n]):

> un(12);

> for N to 100 do T[N]:=nops(un(N)) od:

Here are the numbers of elements of groups for n from 1 to 100, written so that 78=24 means that the group has 24 elements.

> op(op(T));

The number theory package has a built in function phi for these numbers:

> with(numtheory):

Warning, the protected name order has been redefined and unprotected

> phi(78);

Cayley tables for groups can be found using the following command:

> CayleyU:=n->Matrix(nops(un(n)),(i,j)->un(n)[i]*un(n)[j] mod n):

> CayleyU(42);

To find inverse elements of groups one can use the following procedure:

> invU:=proc(a,n) local v; igcdex(a,n,'v'); v mod n end:

> invU(23,42);

Matrix Groups mod n

Maple is good for calculations with matrix groups. The following examples are self-explanatory.

> with(LinearAlgebra):

> A:=Matrix([[1,2],[3,4]]);

> B:=Inverse(A) mod 5;

> A.B;

> Map(x->x mod 5,%);

> A^(-1);

Maple operates faster with lists than with matrices or Matrices. That's why it is better to define matrix groups using lists instead of Matrices. Groups and can be defined as follows:

> gl2:=n->select(A->evalb(igcd(A[1,1]*A[2,2]-A[1,2]*A[2,1],n)=1),
[seq(seq(seq(seq([[j,i],[l,k]],l=0..n-1),k=0..n-1),j=0..n-1),i=0..n-1)]):

> sl2:=n->select(A->evalb(A[1,1]*A[2,2]-A[1,2]*A[2,1] mod n=1),
[seq(seq(seq(seq([[j,i],[l,k]],l=0..n-1),k=0..n-1),j=0..n-1),i=0..n-1)]):

Here are the numbers of elements of some of them:

> for N from 2 to 6 do nops(sl2(N)) od;

> for N from 2 to 6 do nops(gl2(N)) od;

Look at some of their elements:

> map(matrix,sl2(2));

> matrix(gl2(6)[256]);

Multiplication in GL ( n ) and SL ( n ) can be defined as follows:

> mm:=(A,B,n)->[[A[1,1]*B[1,1] +A[1,2]*B[2,1] mod n,A[1,1]*B[1,2] +A[1,2]*B[2,2] mod n ],[A[2,1]*B[1,1] +A[2,2]*B[2,1] mod n,A[2,1]*B[1,2] +A[2,2]*B[2,2] mod n]]:

For example,

> matrix(mm([[1,2],[3,4]],[[5,6],[7,8]],11));

Inverse elements also can be determined by a direct calculation. In SL ( n ) it is especially simple:

> invSL:=(A,n)->[[A[2,2],-A[1,2] mod n],[-A[2,1] mod n, A[1,1]]]:

> invGL:=proc(A,n) local d; d:=invU(A[1,1]*A[2,2]-A[1,2]*A[2,1],n);
[[A[2,2]*d mod n,-A[1,2]*d mod n],[-A[2,1]*d mod n, A[1,1]*d mod n]] end:

For example,

> matrix(invSL([[3,4],[5,7]],20));

> matrix(invGL([[1,2],[3,4]],25));

Note.

We need to include mm , invSL , and invGL inside the matrix() , if we want to see the output as a matrix. Otherwise the output would look as a list of matrix rows. To apply the matrix() to every element of a set S , we need to use the command map(matrix, S); .

Group Definition

We'll define a group G in a standard way, as a 2-element list containing a set or a list G [1] with an associative binary operation G [2] having an identity and inverses for all elements. To do that, we need to define a few procedures.

The following procedure is checking if the rows of the Cayley table are permutations of the group elements:

> isCP:=proc(g,m) local i,j;
i:=1; while (i<=nops(g) and {seq(m(g[i],g[j]),j=1..nops(g))}={op(g)}) do i:=i+1 od; evalb(i=nops(g)+1) end:

The following procedure is checking associativity:

> isAssociative:=proc(g,m) local i,j,k;
i:=1; j:=1; k:=1; while(i<=nops(g) and
m(m(g[i],g[j]),g[k])=m(g[i],m(g[j],g[k]))) do if k=nops(g) then if j=nops(g) then i:=i+1; j:=1; k:= 1 else j:=j+1 fi else k:=k+1 fi od; evalb(i=nops(g)+1) end:

The following example shows that these two procedures are not enough to define a group.

Example 1.

Let g be an arbitrary set containing more than 1 element, and m ( a,b ) = b for all pairs ( a,b ) of elements of g . It is not a group, because ab = bb would imply a = b in a group. However, m is associative and every row of the Cayley table is the trivial permutation of the elements of g :

> isCP({0,1},(a,b)->b);

> isAssociative({0,1},(a,b)->b);

The following Theorem shows that an additional property of the existence of a right identity is enough for defining a group.

Theorem 1.

Let m be a binary associative operation on a set G so that

• i ) for every g in G the left multiplication by g is one-to-one and onto G , i.e. for every element f of G there is a unique element h of G so that f = gh ;
• ii ) there exists a right identity e , so that ge=g for every element g of G .

Then the set G with the operation m is a group.

Proof.

Pick an element g in G . By associativity, gh = ( ge)h = g ( eh ) , so h =eh for every h (by the one-to-one property of the left multiplication by g ). That means that e is a left identity as well. By i ), there exists unique elements h and x of G so that gh = e and hx = e . Then, x = ( gh ) x = g ( hx ) = g , in other words, gh = hg = e , so h is an inverse element of g . Since the operation is associative and there exists an identity and inverses of all elements, the set G with the operation m is a group.

The following procedure is checking if a set g with an operation m (satisfying isCP ) has a right identity:

> hasRightId:=proc(g,m) local i,k;
member(g[1],[seq(m(g[1],g[i]), i=1..nops(g))],'k'); i:=1;
while (i<=nops(g) and m(g[i],g[k])=g[i]) do i:=i+1 od;
evalb(i=nops(g)+1) end:

Here is a negative example:

> hasRightId([0,1],(a,b)->b);

Finally, we can introduce a new Maple type - a group:

> `type/group`:=proc(g)
type(g,list) and nops(g)=2 and (type(g[1],list) or type(g[1],set)) and type(g[2],procedure) and isCP(op(g)) and isAssociative(op(g)) and hasRightId(op(g)) end:

Let's check a few examples of the groups we know:

> type([un(42),(i,j)->i*j mod 42],group);

> cyclic:=n->[seq([$i..n,$1..i-1],i=1..n)]:

> dihedral:=n->[op(cyclic(n)),seq([n+1-j$j=i..n,n+1-j$j=1..i-1],i=1..n)]:

> mult:=proc(a,b,g) local i,v; member([seq(g[a][g[b][i]],i=1..nops(g[a]))],g,'v');v end:

> type([[$1..8],(a,b)->mult(a,b,dihedral(4))],group);

> type([sl2(3),(A,B)->mm(A,B,3)],group);

> type([[$0..9],(a,b)->a+b mod 10],group);

If we know that the set or list g with the operation m is a group, the identity and the inverses can be found as follows:

> Id:=proc(g,m) local i,k; member(g[1],[seq(m(g[1],g[k]),k=1..nops(g))],'i');g[i] end:

> Inv:=proc(a,g,m) local i,k; member(Id(g,m),[seq(m(a,g[k]),k=1..nops(g))],'i');g[i] end:

For example,

> matrix(Id(gl2(5),(a,b)->mm(a,b,5)));

> matrix(Inv([[1,2],[3,4]],gl2(5),(a,b)->mm(a,b,5)));

The Cayley table can be displayed as follows:

> cayleyTable:=(g,m)->Matrix(nops(g),(i,j)->m(g[i],g[j])):

For example, for :

> cayleyTable([$0..9],(a,b)->a+b mod 10);

We can check if the group is Abelian by checking if the Cayley table is symmetric:

> isAbelianGroup:=(g,m)->IsMatrixShape(cayleyTable(g,m),symmetric):
#type(cayleyTable(g,m),'Matrix'(symmetric)):

For example,

> isAbelianGroup([$0..9],(a,b)->a+b mod 10);

> isAbelianGroup(sl2(2),(a,b)->mm(a,b,2));

Redefining of Groups

If we knew the group identity and the inverses, we can save time in many calculations. That's why it is convenient to add the identity and the procedure finding the inverse elements to the group definition. We define an extended group as a list G containing four elements, a set G [1], a binary operation (multiplication) G [2], the identity G [3], and the unary operation (inverse) G [4]:

> `type/extendedGroup`:=proc(g) local i;
if type(g,list) and nops(g)=4 and type([g[1],g[2]],group) and g[2](g[1][1],g[3])=g[1][1]
then i:=1; while not i=nops(g[1])+1 and g[2](g[1][i],g[4](g[1][i]))=g[3] do i:=i+1 od;
evalb(i=nops(g[1])+1) else false fi end:

It might be annoying to enter the same operations repeatedly many times for the groups we know. So we can redefine the groups, including the operations, the identities, and the inverses in their definitions. I'll do that in the order they have appeared in this manual, starting their names with capital letters:

> Cyclic:=n->[[$1..n], (a,b)->`if`(a+b-1<=n,a+b-1,(a+b-1)-n), 1, a->`if`(a=1,1,n-a+2)]:

> Dihedral:=n->[[$1..2*n], (a,b)->mult(a,b,dihedral(n)), 1, a->`if`(a=1 or a>n,a,n-a+2)]:

> Un:=n->[un(n),(a,b)->a*b mod n, 1, a->invU(a,n)]:

> GL2:=n->[gl2(n),(a,b)->mm(a,b,n),[[1,0],[0,1]],a->invGL(a,n)]:

> SL2:=n->[sl2(n),(a,b)->mm(a,b,n),[[1,0],[0,1]],a->invSL(a,n)]:

> Z:=n->[[$0..n-1],(a,b)->a+b mod n, 0, a->-a mod n]:

Now we can test the correctness of the new definitions:

> type(Cyclic(10),extendedGroup);

> type(Dihedral(5),extendedGroup);

> type(Un(12),extendedGroup);

> type(GL2(2),extendedGroup);

> type(SL2(3),extendedGroup);

> type(Z(20),extendedGroup);

Cayley tables for the extended Groups can be defined as follows:

> Cayley:=g->cayleyTable(g[1],g[2]):

For example,

> Map(matrix,Cayley(SL2(2)));

The same as we did before, we can check if the group is Abelian by checking if the Cayley table is symmetric:

> IsAbelian:=g->isAbelianGroup(g[1],g[2]):

For example,

> IsAbelian(Z(100));

> IsAbelian(Un(15));

> IsAbelian(GL2(3));

Every group G , defined as a 2-element list, containing a set G [1] and a binary operation G [2], can be easily converted to the extended group by adding the identity and inverse element:

> `convert/extendedGroup`:=proc(g) local a, i;
i:=a->Inv(a,(op(g))); [op(g),Id(op(g)),i] end:

For example,

> convert([[$0..10],(a,b)->a+b mod 11],extendedGroup):

> type(%,extendedGroup);

>

>

Exercises

• 1 . Find the numbers of elements of groups U (5), U (25), U (125), and U (625).
• 2 . Display the Cayley table of U (40).
• 3 . Find the inverse of 151 in U (212).
• 4 . Find the inverse matrix of mod 321.
• 5 . Find the product of and mod 125.
• 6 . Find the numbers of elements of and .
• 7 . Check if the set {5, 15, 25, 45, 55, 65} is a group under multiplication mod 90. If it is, find the identity element and inverses of every element. Display the Cayley table.