1.

3 Example of Groups 1 THE DEFINITION OF A GROUP AND EXAMPLES

If f P Sn is of the form ˆ ˙
a1 a2 a3 ¨ ¨ ¨ ak´1 ak
,
a2 a3 a4 ¨ ¨ ¨ ak a1
then we call f a k-cycle, and write it as

pa1 a2 a3 ¨ ¨ ¨ ak q.

Example: ˆ ˙
2 3 4
f“
3 4 2
is written as p234q, and is a 3-cycle. Observe that, as a function from X to X, we have

p234q “ p342q
“ p423q.

So a permutation need not have a unique representation as a cycle. Also, not all elements of Sn
are k-cycles, for n ě 4.

Definition: Two cycles pa1 a2 ¨ ¨ ¨ ak q and pb1 b2 ¨ ¨ ¨ bm q are called disjoint cycles if the two sets
ta1 , a2 , . . . , ak u and tb1 , b2 , . . . , bm u are disjoint.

Example: p134q, p2567q are disjoint, while p134q and p263q are not.
Theorem 1.3.6.1. If pa1 a2 ¨ ¨ ¨ ak q and pb1 b2 ¨ ¨ ¨ bm q are disjoint, then they commute.
Proof. Let f “ pa1 a2 ¨ ¨ ¨ ak q and g “ pb1 b2 ¨ ¨ ¨ bm q. We want to show that f ˝ g “ g ˝ f , i.e.,

f ˝ gplq “ g ˝ f plq @ l P X “ t1, 2, . . . , nu.

We have three cases:

CASE 1: l P ta1 , a2 , . . . , ak u. Then l “ ai for some i, where 1 ď i ď k. Since ta1 , a2 , . . . , ak u

is disjoint from tb1 , b2 , . . . , bm u, we know that l R tb1 , b2 , . . . , bm u, hence gplq “ l. Also, since
f pai q P ta1 , a2 , . . . , ak u and, since ta1 , a2 , . . . , ak u and tb1 , b2 , . . . , bm u are disjoint, we have f pai q R
tb1 , b2 , . . . , bm u, hence gpf pai qq “ f pai q. Thus

f ˝ gplq “ f pgplqq “ f plq “ f pai q and g ˝ f plq “ gpf plqq “ gpf pai qq “ f pai q

and therefore g ˝ f plq “ f ˝ gplq.

CASE 2: l P tb1 , b2 , . . . , bm u. Then l “ bj for some j, where 1 ď j ď m. Just as in CASE 1

above, we can show that f ˝ gplq “ gpbj q and g ˝ f plq “ gpbj q hence g ˝ f plq “ f ˝ gplq.

CASE 3: l R ta1 , a2 , . . . , ak u and l R tb1 , b2 , . . . , bm u. Then f plq “ l “ gplq and

f ˝ gplq “ l “ g ˝ f plq.

Whatever the case, g ˝ f plq “ f ˝ gplq, hence g ˝ f “ f ˝ g. l

Page: 28 of 114
1.3 Example of Groups 1 THE DEFINITION OF A GROUP AND EXAMPLES

Theorem 1.3.6.2. Any non-identity permutation f P Sn is either already a cycle, or can be written
as a product of disjoint cycles.
We will simply illustrate how this is done: first consider the circle p1f p1qf 2 p1qf 3 p1q ¨ ¨ ¨q. This
will be the first circle. Now take the smallest k not in the set t1, f p1q, f 2 p1q, f 3 p1q, . . .u. The second
circle is pkf pkqf 2 pkqf 3 pkq ¨ ¨ ¨q, etc.

Example: Consider f P S8 given by

ˆ ˙
1 2 3 4 5 6 7 8
f“ .
2 5 1 8 3 7 6 4
Then f “ p1253qp48qp67q, using the procedure described above.

Definition: A 2-cycle is called a transposition.

Theorem 1.3.6.3. Any cycle can be expressed as a product of (not necessarily disjoint) transposi-
tions.
Proof. pa1 a2 ¨ ¨ ¨ ak q “ pa1 ak qpa1 ak´1 q ¨ ¨ ¨ pa1 a2 q. l

Example: p2354q “ p24qp25qp23q.

Theorem 1.3.6.4. For n ě 2, any permutation in Sn can be written as a product of (not necessarily
disjoint) transpositions.
Proof. Let f P Sn . If f “ e, then f “ p12qp12q, a product of transpositions. If f ­“ e then,
by Theorem 1.3.6.2, f is a product of cycles, hence by Theorem 1.3.6.3, f can be expressed as a
product of transpositions. l

Example: Let ˆ ˙
1 2 3 4 5 6 7 8
f“ P S8 .
2 5 1 8 3 7 6 4
Then f “ p1253qp48qp67q “ p13qp15qp12qp48qp67q. (So we first express f as a product of cycles using
Theorem 1.3.6.2, and then we express each cycle as a product of transpositions using Theorem
1.3.6.3.)
Theorem 1.3.6.5 (Parity). Let n ě 2 and let f P Sn . Suppose f can be written as a product of r
transpositions, and also as a product of s transpositions. Then either r and s are both even integers,
or are both odd integers
(We will assume this result without proof.)

Example: p145q “ p15qp14q

looomooon “ p41qp45qp12qp12q.
looooooooomooooooooon
a product of 2 transpositions a product of 4 transpositions
Although 2 ­“ 4, both 2 and 4 are even. According to Theorem 1.3.6.5, there is no way one can
write p145q as a product of 3 transpositions (why?).

Definition: Assume n ě 2 and let f P Sn . Then f is called an even permutation if f can be

written as a product of an even number of transpositions; otherwise f is called an odd permutation.

Page: 29 of 114
1.3 Exercise Set 1 THE DEFINITION OF A GROUP AND EXAMPLES

Theorem 1.3.6.6. Let pa1 a2 ¨ ¨ ¨ ak q be a k-cycle. Then it is an even permutation if and only if k
is odd; and it is an odd permutation if and only if k is even.
Proof. Observe that pa1 a2 ¨ ¨ ¨ ak q “ pa1 ak qpa1 ak´1 q ¨ ¨ ¨ pa1 a2 q, i.e., a product of k ´ 1 transposi-
tions. Thus the k-cycle is an even permutation if and only if k ´ 1 is even, and this is true if and
only if k is odd. Similarly, the k-cycle is an odd permutation if and only if k is even. l.

Caution: The above theorem only works for cycles. As was earlier pointed out, not every
permutation is a single cycle!

1.3.7 The Alternating Group of Degree n, An

Definition: For n ě 2, let An be the set of all even permutations of Sn .

Theorem 1.3.7.1. For n ě 2, pAn , ˚q is a group, where f ˚ g “ f ˝ g, as before.

Proof. Observe that e “ p12qp12q P An , hence An is not empty. The product of two even per-
mutations is again an even permutation, hence ˚ is indeed a binary operation on An . It is obviously
associative. If f P An , then f ˝ f ´1 “ e, an even permutation. Since f is an even permutation,
f ´1 has to be an even permutation (why?), hence f ´1 P An . All this says pAn , ˚q is indeed a group. l

pAn , ˚q is called the alternating group of degree n.

Theorem 1.3.7.2. |An | “ n! 2 pn ě 2q.
Proof. Let B be the set of all odd permutations of Sn . We claim that, for each even permutation,
there corresponds exactly one odd permutation and visa-versa (thus Sn is divided into two “equal
halfs”, An and B).
So let f be an even permutation. Then f ˚ p12q is an odd permutation (why?). Further, if g is
an odd permutation, then g ˚ p12q is an even permutation corresponding to g, since

pg ˚ p12qq ˚ p12q “ g ˚ pp12q ˚ p12qq “ g ˚ e “ g.

Thus the function from An to B mapping f to f ˚ p12q is a bijection. Therefore the number of
even permutation of Sn is exactly the same as the number of odd permutations. Since a permutation
is either odd or even, we see that |Sn | “ |B| ` |An | “ 2|An | since |An | “ |B|, hence

|Sn | n!
|An | “ “ .l
2 2

1.3 Exercise Set

1. Let pG, ˚q be a finite group. Then one can completely describe the binary operation ˚ by
means of a multiplication table, also called Cayley table. For example,

Page: 30 of 114
1.3 Exercise Set 1 THE DEFINITION OF A GROUP AND EXAMPLES

˚ a b c
a c b a

b a a a

c b b b

means a ˚ b “ b, b ˚ a “ a, etc, that is, the elements in the left-most column of the table are
always placed on the LHS during multiplication.

Write Cayley tables for A3 , S3 , D4 , Q8 , and Z4 .

2. List all elements of A4 .

3. (a) Prove that a product of two even permutations of Sn is also an even permutation.
(b) Prove that a product of an even permutation and an odd permutation is an odd permu-
tation.
(c) Prove that a product of two odd permutations is an even permutation.

4. Find an element of S4 which is not a cycle.

5. Let ˆ ˙
1 2 3 4 5
f“ .
4 5 1 2 3
(a) Write f as a product of disjoint cycles.
(b) Write f as a product of transpositions.

6. Let g P Sn be a transposition. Show that g ´1 “ g.

7. Let f “ pa 1a 2¨ ¨ ¨ a kq be a k-cycle in S n. Write f ´1as a k-cycle, and also in the two-row

notation.

8. Express e P Sn in the two-row notation.

9. What is the inverse of k in Q8 ?

10. What are the inverses of v, h, r90 in D4 ?

11. Show that D4 , Q8 , S3 are not commutative.

12. Show that |Sn | “ n!.

13. Show that Sn is not commutative for n ě 3.

14. Show that S2 is commutative.

15. Show that A3 is commutative.

Page: 31 of 114