Tuesday, August 12, 2008

Groups

The theory of group arose from the theory of equations, later on the group of transformations was extended and generalized as
an abstract group. Group theory has played a major role in finding new connections between various branches of mathematics
especially in the studies of geometric problems. Group theory has tremendous applications in physics and new types of
interesting and significant applications of group theory are being explored in biological sciences and theoretical computer
science too.

A group (G, *) is a non-empty set G, together with a binary operation * satisfying the following axioms.
For all a, b, c Î G,
1. a * (b * c)=(a * b) * c.
2. There exists an element e in G such that a * e = a = e * a.
3. For each a Î G, there exists an element a¢ Î G such that a * a¢ = e = a¢ * a.

Examples:
1. (Z, +), (Q, +), (R, +) and (C, +) are all groups, where Z is the set of integers, Q is the set of rational numbers, R is the
set of real numbers and C is the set of complex numbers, and ‘+’ is the usual addition.
2. (Z\{0}, ·), where . is the usual multiplication, is not a group, since inverse does not exist for every element of Z\{0}.
3. (Q\{0}, ·), (R\{0}, ·), (C\{0}, ·) are all groups, where . is the usual multiplication.
4. Let Mn denote the set of all non-singular matrices over R, then (Mn ,*) is a group, where * is the matrix multiplication
(Prove !).
5. Let S be any non-empty set. Then the set of all bijective mappings from S into itself together with the binary operation the
composition of mappings form a group.
6. Let Zm be the set of distinct equivalence classes of integer modulo m, then (Zm, +) is a group, where
[a] + [b] = [(a + b)(mod m)].

From the definition of group it is clear that group always has identity element and each element in a group has inverse. In fact we
can show that identity element in a group is unique and inverse for an element in a group is unique.

Suppose a group has two identity elements, say e and e¢, then by taking an element a = e¢ in axiom(2) of group we have,
e¢ * e = e¢ = e * e¢ ……… ( i )

Similarly by taking a=e in axiom(2) of the group, we have
e * e¢ = e = e¢ * e ……… ( ii )

Thus, we have from ( i ) and ( ii ) ,
e¢ = e * e¢ = e.

Thus, in a group identity element is unique.

Similarly, if an element ‘a’ has two inverses, say a¢ and a¢¢,
then we have a * a¢ = e = a¢ * a and a * a¢¢ = e = a¢¢ * a.
Now, a¢ = a¢ * e
= a¢ * (a * a¢¢ )
= (a¢ * a) * a¢¢
= e * a¢¢
= a¢¢

Thus, in a group inverse of an element is unique.

A group (G ,*) is called a finite group if the cardinality of G is finite. The number of elements in a finite group,
i.e. |G| , is called the order of the group and is denoted by the symbol o(G). A group which is not finite is called an
infinite group.

If a group is finite, then definition of its binary operation can be expressed in the form of a table. For example, let
G = {e, a, b, c}, then the binary operation * on G can be expressed by the following table:

Table 1

Observe that the element x * y obtained by operating the elements x and y by using the operation * is the element in the row
containing x and the column containing y. For instance, a * b = c, a * a = e, etc.

A group (G, * ) is called an abelian group if a * b = b * a, for all a, b Î G.

Abelian groups are sometimes called commutative groups.

Examples 1, 3, 6 and 7 are commutative groups, while Example 4 is not an abelian group.

In fact it is interesting to observe that all finite groups with order £ 5 are all commutative.

In the next section we discuss about permutation groups. This is an important example of class of groups that are non-abelian.

3.1.1 Permutation Groups

In this subsection we discuss about a popular class of groups called permutation groups. In particular, we discuss about two
interesting permutation groups, the symmetric groups (Sn, à) and the dihedral group (Dn, à). The permutation groups play an
important role in the studies of finite combinatorial and geometrical structures.

3.1.1.1 Symmetric Groups

Any one-to-one mapping of a set S onto S is called permutation of S.

Let S = {a, b, c} be a set and p denote a permutation of elements of S, that is, p : S ® S , is a bijective mapping.
Suppose p(a) = c, p(b) = a and p(c) = b, then the classical way of representing p is

, where the image of any element of S is entered below the element.

Consider now a set S={a, b} consisting of only two elements and let the permutations on the elements of this set be denoted
by p1 and p2, where

.

It is clear that p1 and p2 are the only possible permutations on the set S.

Let à denote a binary operation on S representing the (right) composition of permutation. By pi à pj ,
for i, j =1, 2, we mean the permutation obtained by permuting the elements of S by an application of pi followed by an
application of the permutation pj.

For example, pi à pj (a) = pj ( pi(a) ).

That is, in the above example, we have p2 à p1(a) = p1( p2(a)) = p1(b) = b.
p2 à p1(b) = p1(p2(b)) = p1(a) = a.
Thus p2 à p1 = p2 .

So, we have the following composition table.

Table 2

It follows from the above table that (S2, à) is a group of order 2.

Observe that (S2, à) is independent of the elements of the set S (= {a, b}) but depends upon the number of elements in the set.
Any other set of two elements will generate the same permutation group (S2, à).

Next consider 3!(= 6) permutations of the elements of the set {1, 2, 3}. Let us denote the set of all permutations by
S3 = {p1, p2, …, p6}, where

, , , , and

.

The following composition table shows that (S3, à) is a group.

Table 3 : Composition Table of (S3 , à )

 à p1 p2 p3 p4 p5 p6 p1 p1 p2 p3 p4 p5 p6 p2 p2 p1 p5 p6 p3 p4 p3 p3 p6 p1 p5 p4 p2 p4 p4 p5 p6 p1 p2 p3 p5 p5 p4 p2 p3 p6 p1 p6 p6 p3 p4 p2 p1 p5

It is clear from the table that (S3, à) is not abelian. In fact S3 is the smallest non-abelian group.

In general the set Sn of all permutations of n elements is a permutation group
(Sn, à), also called symmetric group.

It is interesting to observe that the symmetric groups (Sn, à), n ³ 3, are all non-abelian.

In the permutation group, the number elements on which the permutations are defined is called the degree of the permutation
group

Thus in the symmetric group Sn, degree is n and the order is n!.

3.1.1.2 Dihedral Group

By considering the symmetries of regular polygon we obtain another interesting permutation groups called dihedral groups.

First we discuss the permutation group obtained from an equilateral triangle.

Consider an equilateral triangle with vertices 1, 2 and 3 as shown in Figure 3.1. Consider the following transformation of the
triangle itself

Figure 3.1

1. Three rotations through the center through 0° , 120° , 240° (in counter clockwise).
2. Three reflections along the three bisectors. We call any one of the above six transformations as symmetry.

On the six transformations (the symmetries), we consider the composition of transformation as a binary operation. The
symmetries form a group which has its identity element, the identity transformation (corresponding to 0° rotation). Rotations
through 120° and through 240° are mutual inverse of each other. For every other reflection the inverse is itself.

Thus the symmetries form a group.

The product (composition) of rotation through 120o with reflection along the bisector through vertex 1 is the reflection along the
bisector through 2. But the product in the reverse order, that is, the product of reflection along the bisector through vertex 1 and
the rotation through 120° is the reflection along the bisector through 3. Hence, this group is non-abelian.

The above example can also be interpreted as follows:

Each symmetry permutes the vertices of the triangle and each permutation of the vertices of the triangle defines a symmetry. The
three rotations correspond respectively, to the permutations

and the three reflections along the bisectors through 1, 2 and 3 respectively corresponding to the permutations

.

The product of the symmetries corresponds to the product of the permutations. Thus, the six permutations form a group. This
group is denoted by D3. It is very clear that D3 coincides with S3, that is, S3 and D3 are one and the same.

Now we consider the symmetries of the square. Consider a square with vertices 1, 2, 3 and 4.

Consider the following transformation of square into itself.
1. The four rotation about the center through 90°, 180°, 270°, 0° respectively (in the counter clockwise direction) about O.
These four rotations can be interpreted as the following permutation of the vertices

, , and .
1. The two reflections about the lines AA¢ and BB¢ and two more reflections about the diagonals 13 and 24. These reflections
can be interpreted as the following permutations of the vertices

, , and .

Let D4 = {r1, r2, r3,…, r8}. The compositions of the rotations and the reflections of D4 is given in the table.

Table 4: Composition table of (D4 , à )
 à r1 r2 r3 r4 r5 r6 r7 r8 r1 r2 r3 r7 r1 r8 r7 r5 r6 r2 r3 r4 r1 r2 r6 r5 r8 r7 r3 r4 r1 r2 r3 r7 r8 r6 r5 r4 r1 r2 r3 r4 r5 r6 r7 r8 r5 r7 r6 r8 r5 r4 r2 r1 r3 r6 r8 r5 r7 r6 r2 r4 r3 r1 r7 r6 r8 r5 r7 r3 r1 r4 r2 r8 r5 r7 r6 r8 r1 r3 r2 r4

Thus, from the above table it is clear that (D4, à ) is a permutation group of order 8 and degree 4 and it is called as dihedral
group of degree 4
. Also, from the table it is clear that D4 is not abelian.

In general, the set of all rigid rotations of a regular polygon of n sides under the composition à is a group (Dn, à), where Dn is
of order 2n and degree n . The group (Dn, à ) is called dihedral group of degree n.

Remark:

It is evident from the definition of (Sn, à) that (Dn, à) is a subgroup of (Sn, à) and it is non-abelian.

3.1.2 Cyclic Groups

Here we define and discuss another important class of groups called cyclic groups.
Let (G , *) be a group and a Î G.
Define a0 = e, an+1 = an * a, for n Î N. and (a-1)n = a-n, for n Î N, so that we have defined ar, for r Î Z, where Z is the set of
integers.

Furthermore, am * an = am+n, for m, n Î Z.

Let (a) denote the set { an / nÎ Z}.
A group G is called a cyclic group if for some a Î G such that G = (a) and the element ‘a’ is called the generator of G.

Note :

A cyclic group can have several generators.

Examples:

1. The group Z of integers is cyclic.
Since Z = (1) = (-1).
Thus, 1 and –1 are the generators of Z.
2. The group G = {1, -1, i, -i} with multiplication as its operation is a cyclic group with i and – i as its
generators.
3. The group G ={ …, , , ¼, ½, 1, 2, 4, 8,16, …} is cyclic with multiplication as its operation with
generator ½ .
4. The trivial group G = {e} is cyclic with generator e.
5. The group (Zn , +) of residue classes modulo n is cyclic with generator 1.

Theorem:

If G is a cyclic group then G is abelian.

Proof:

Let G be cyclic. Then G = (a), for some a Î G. If x Î G and y Î G, x = am and y = an for some m, n Î Z.
Then xy = aman = am+n = an+m = anam = xy.
Hence, G is abelian.

Theorem:

Let (G , *) be a finite cyclic group generated by an element a Î G. If G is of order n,

that is, |G| = n, then, an = e so that G = {a, a2, a3, …, an = e}. Furthermore, n is the least positive integer for which an = e.

Proof:

Let us assume that for some positive integer m <>m = e.

Since G is a cyclic group, any element of G can be written as ak, for some k Î Z.

Now by Euclid’s Algorithm, we can write

k = mq + r, where q is some integer and 0 £ r £ m - 1.
This means that ak = amq + r = (am)q * ar = ar.
That is, every element of G can be expressed as ar, for some r, 0 £ r £ m - 1.

Thus, implying that G has atmost m distinct elements, i.e. |G| = m < n, which is a contradiction.

Hence, am = e, for m < n is not possible.

Claim:
The elements a, a2, a3, …, an are all distinct, where an = e.

Suppose ai = aj, for i < face="Symbol">£ n.
Then aj - i = e, where j - i < n, which is again a contradiction.
Hence the claim.
Hence the theorem.

Let (G , *) be a group. Order of an element a Î G is the least positive integer m such that am = e.

For example, in the group (Z7 \ [0], •), the order of [2] is 3.

For, [2]1 = [2], [2]2 = [2]•[2] = [4], [2]3 = [2]•[2]•[2] = [8] = [1].

1. Is it true that (Zm\{0), •) is a group, for all m Î Z+ where [a]•[b] = [ab (mod m)]. If the answer is no then what are the
m Î Z+ such that (Zm\{0}, •) is a group.
2. Prove that in a group (G , *)
1. ab = ac implies b = c (left cancellation law).
2. ba = ca implies b = c (right cancellation law).
3. (ab)-1 = b-1a-1.
1. Show that in a group identity element is the only idempotent element.
2. Construct the multiplication table for (Z7 , +) and (Z7 , • ). If (G , *) is an abelian group, then for all a, b Î G show that
(a * b)n = an * bn.
3. Find all those elements in S3 such that (a * b)2 ¹ a2 * b2.
4. Show that in a group (G , *) if for any a, b Î G, (a * b)2 = a2 * b2 , then (G , *) must be abelian . Is the converse true?
5. Show that if G is a group such that a2 = e, for every a Î G, then G is abelian.
6. Find a solution of the equation ax = b in S3, where
.
1. Prove that if G is non-abelian then G is not cyclic.