MATH14 – ABSTRACT ALGEBRA

Lecture Note

Lesson No. 3: Permutation & Symmetry Groups

Learning Objectives:
At the end of the lesson, you will be able to:
1. define permutation, permutation groups and symmetry groups, and related terms
2. solve problems permutation groups and symmetry groups

Definition
A permutation of a set A is a function, S A , from A to A that is bijective. A permutation
group (symmetry group) of a set A is a set of permutations of A that forms a group under
function composition.

Notations

 Standard notation: (12 23 45 6

31 5 6 4 )
 Cyclic Notation:( 1 ,2 , 3 ) ( 4 ,5 , 6 )

Theorem
 |Sn|=n !
 Every permutation of a finite set can be written as a cycle or as a product of disjoint
cycles.
 Disjoint cycles (not same content) in Sn commute. If the pair of cycle α =( a1 ,a 2 , ⋯ ,a m )
and β=( b1 ,b 2 , ⋯ ,b n ) have no entries in common then, then αβ =βα
 The group Snis nonabelian for all n ≥ 3.
 The order of a permutation of a finite set written in disjoint cycle form is the least
common multiple of the length of the cycles.

Example: Show that f ( x )=x +1 is a permutation of ℝ.

Proof:
To show that f ( x )=x +1 is a permutation of ℝ, we have to show that f ( x ) is bijective.
f ( x ) is one-to-one, because

f ( x 1 ) =f ( x 2 )
x 1+ 1=x 2+1
 x 1=x 2

and it is onto, since

f ( x )=x +1
y=x +1
x= y −1

Example: Convert the ( 14 23 45 6

32 5 1 6 )
to disjoint cyclic notation.

Solution:

Since 1 σ 4 σ 5 σ 1 σ 4 σ 5 ⋯ and 2 σ 3 σ 2 σ 3 ⋯, then

→ → → → → → → → ( 14 23 45 6
32 5 1 6 )
=( 1 , 4 , 5 )( 2 , 3 )

Example: Convert ( 1 , 6 , 4 ) ( 2 ,5 , 7 ) in S7 to standard notation.

Solution:

Working backwards, we have (16 23 45 67

53 17 4 2
. )
Example: Compute the following product (function composition) involving permutations in S6 .

( ) (
α = 1 2 3 4 5 6 , β= 1 2 3 4 5 6
2 13 5 4 6 6 12 4 3 5 )
a. αβ
b. β 2
c. β 2 α
d. β−1
e. ⟨α⟩
f. ¿ ⟨ β 2 ⟩∨¿

Solution:
a. Function composition must be read from right-to-left order. For instance, in αβ , we first
apply α and then α .

(
αβ = 1 2 3 4 5 6
6 21 53 4 )
2
b. β =ββ= (15 23 45 6
6 1 42 3 )
 2
c. β α= (16 23 45 6
51 24 3 )
d. The inverse β−1 is determined in reverse order. β =
−1
(12 23 4 5 6
35 4 6 1 )
e. The following are the elements generated by ⟨ α ⟩

(
α= 1 2 3 4 5 6
2 13 5 4 6 )
(
α 2= 1 2 3 4 5 6 =e
1 23 45 6 )
Hence, ⟨ α ⟩ =\{ e , α \}

g. To determine the order, ¿ ⟨ β 2 ⟩∨¿, we have to determine the group generated by β 2

β= (16 23 4 5 6
12 4 3 5 )
β =(
3)
2 1 23 4 5 6
5 61 4 2
3
β =β β =β β=
2 2
( 13 23 4 5 6
56 4 1 2 )
4 2 2
β =β β =β β=β β =
3 3
( 12 23 45 6
35 46 1 )
5 4
β =β β=β β =β β =β β =
4 2 3 3 2
( 11 23 45 6
23 45 6
=e )
Since ⟨ β 2 ⟩ =\{ β , β 2 , β 3 , β 4 , β 5=e \}, then ¿ ⟨ β 2 ⟩∨¿5

Definition
A cycle of length 2 is a transposition. That is,
(a 1 , a2 , ⋯ , a n)=(a1 , an )¿

A permutation of a finite set is even or odd according to whether it can be expressed as

a product of an even number of transpositions or the product of an odd number of
transpositions, respectively.

Theorem
  Any permutation of a finite set containing at least two elements is a product of
transposition.
 No permutation in S6 can be expressed both as a product of an even number of
transpositions and as a product of an odd number of transpositions.
 The set of even permutations in Snforms a subgroup of Sn .

Definition
The subgroup of Sn consisting of the even permutations of n letters is the alternating
group An on n letters.

Example: Express α = (13 23 45 67 8

8 6 7 4 15 2 )
as a product of disjoint cycles and transpositions.

Solution:

(
α= 1 23 4 5 67 8
3 8 6 7 4 15 2 )
¿ ( 1 ,3 , 6 )( 2 , 8 ) ( 4 , 7 , 5 )
¿ ( 1 ,6 )( 1 , 3 ) ( 2, 8 ) ( 4 ,5 )( 4 , 7 )

Note that it can be expressed as a product of 5 transposition; hence, it is an odd permutation.

Dihedral Groups (congruent)

Let n ≥ 3. Then Dn is the set of all one-to-one functions ϕ :Z n × Z n that map onto Z n with
the property that the line segment between vertices i and j is an edge in Pn iff the line segment
between ϕ ( i ) and ϕ ( j ) is an edge of Pn. The nth dihedral group is the set D n with binary
operation function composition.

Theorem
 For any n ≥ 3, ⟨ D n ,∘ ⟩ is a group.
 For any n ≥ 3, the order of the dihedral group D n is 2 n.

Symmetries of D 3 (Equilateral Triangle)

There are 2(3) = 6 elements for D 3.

No movement (identity)
 ρ0 = (11 22 33) elements

Rotations

ρ1= (12 32 31)

120 degree

(
ρ2= 1 2 3
3 12 )

Mirror Images

μ1 = (11 23 32)

μ2= (13 22 31)

μ3= (12 12 33)

The Cayley’s table below shows the multiplication table for D 3.

ρ0 ρ1 ρ2 μ1 μ2 μ3
ρ0 ρ0 ρ1 ρ2 μ1 μ2 μ3
ρ1 ρ1 ρ2 ρ0 μ3 μ1 μ2
ρ2 ρ2 ρ0 ρ1 μ2 μ3 μ1
μ1 μ1 μ2 μ3 ρ0 ρ1 ρ2
μ2 μ2 μ3 μ1 ρ2 ρ0 ρ1
μ3 μ3 μ1 μ2 ρ1 ρ2 ρ0

The subgroups are:

 Improper Subgroup – \{ ρ0 , ρ1 , ρ1 , μ1 , μ 2 , μ3 \} (order 6)
 Proper Subgroup – \{ ρ0 , ρ1 , ρ2 \} (order 3), \{ ρ0 , μ1 \} (order 2), \{ ρ0 , μ2 \} (order 2),
\{ ρ0 , μ3 \} (order 2)
 Trivial Subgroup – \{ ρ0 \} (order 1)

Lattice diagram:

Symmetries of D 4 (Square): Octic Group

There are 2(4) = 8 elements for D 4 .

No movement

(
ρ0 = 1 2 3 4
1 23 4 )
Rotations

ρ1= (12 23 4
34 1 )

(
ρ2= 1 2 3 4
3 41 2 )

(
ρ3= 1 2 3 4
4 12 3 )

Mirror Images

(
μ1= 1 2 3
2 14
4
3 )

(
μ2= 1 2 3 4
4 32 1 )

Diagonal Flips

( 13
δ 1=
23 4
21 4 )
 δ 2= ( 11 23 4
43 2 )

The Cayley’s table below shows the multiplication table for D 4 .

ρ0 ρ1 ρ2 ρ3 μ1 μ2 δ 1 δ 2
ρ 0 ρ 0 ρ 1 ρ 2 ρ 3 μ1 μ 2 δ 1 δ 2
ρ1 ρ1 ρ2 ρ3 ρ0 δ 1 δ 2 μ2 μ1
ρ 2 ρ 2 ρ 3 ρ 0 ρ 1 μ2 μ 1 δ 2 δ 1
ρ 3 ρ3 ρ0 ρ1 ρ2 δ 2 δ 1 μ1 μ2
μ 1 μ 1 δ 2 μ2 δ 1 ρ 0 ρ 2 ρ 3 ρ 1
μ 2 μ2 δ 1 μ 1 δ 2 ρ 2 ρ 0 ρ 1 ρ 3
δ 1 δ 1 μ1 δ 2 μ 2 ρ 1 ρ 3 ρ 0 ρ 2
δ 2 δ 2 μ 2 δ 1 μ1 ρ 3 ρ 1 ρ 2 ρ 0

The subgroups are:

 Improper Subgroup – \{ ρ0 , ρ1 , ρ1 , ρ3 , μ1 , μ2 , δ 1 , δ 2 \} (order 8)
 Proper Subgroup – \{ ρ0 , ρ1 , ρ2 , ρ3 \} (order 4), \{ ρ0 , ρ2 , μ1 , μ2 \} (order 4),
\{ ρ0 , ρ2 , δ1 , δ 2 \} (order 4), \{ ρ0 , ρ2 \} (order 2), \{ ρ0 , μ1 \} (order 2), \{ ρ0 , μ2 \} (order 2),
\{ ρ0 , δ 1 \} (order 2), \{ ρ0 , δ 2 \} (order 2)
 Trivial Subgroup – \{ ρ0 \} (order 1)

Lattice diagram:
 WRITTEN WORK (Reflection Log)

Directions:
1. Read the following articles.
a. That strikes a chord! An illustration of permutation groups in music theory.
https://www.msudenver.edu/media/content/rowdyjournal/documents/Roonaccepteda
sis.pdf
b. Plane and Frieze symmetry group determination for educational purposes.
https://pubs.acs.org/doi/pdf/10.1021/acs.jchemed.0c00093
c. Optimal check digit systems based on modular arithmetic.
https://www.scielo.br/scielo.php?script=sci_arttext&pid=S2179-84512017000100105

2. Choose one article and make a 2-paragraph summary. Include the learning and insights
you gained from the article.

3. Recreate the study by applying the concepts you gained.