Processing math: 76%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

3.1: Symmetric Groups

( \newcommand{\kernel}{\mathrm{null}\,}\)

Definition: Symmetric Group

Let nN. Let X={1,,n}, be a set. Then Sn is the set of all the bijections from X to X (permutations). Note that there are n! permutations. The operation := composition of bijections.  Note that it is a right-to-left composition.

Screen Shot 2023-07-04 at 5.47.23 AM.png
Figure 3.1.1: composition of bijections. (Copyright: Pamini Thangarajah)

Sn with compositions forms a group; this group is called a Symmetric group. Sn is a finite group of order n! and are permutation groups consisting of all possible permutations of n objects.

Identity permutation is denoted as e.

We will denote a permutation by σ=[123nσ(1)σ(2)σ(3)σ(n)]Sn

 

Example 3.1.1

Let σ=[1234524351]S5 and

γ=[1234554123]S5.

Lets find γσ.

Screen Shot 2023-07-04 at 5.45.01 AM.png

Figure 3.1.2: γσ. (Copyright; Pamini Thangarajah via Google draw)

Figure 3.1.2 illustrates the process of moving from one function to another.  Note the system is closed since it is a bijection. Completing the process, we obtain the following: 

Consider γσ=γσ= [1234554123][1234524351]=[1234542135]

Note, if we switch the order of the functions are switched, we obtain: σγ=[1234515243].

Note that σγγσ.  To prove not abelian, we need only show that for at least one element, k, σγ(k)γσ(k).

Note

The inverse of a permutation σ is the inverse of the function σ, and it is denoted by  σ1.

Thus,  σ1σ=σσ1=e.

Example 3.1.2

Let σ=[1234524351]S5. Then  Let σ1=[1234551324]S5.

Cycle Notation

Cycle notation, a simple and straightforward method, is a convenient way to represent permutations in the symmetric group. For example:

Example 3.1.3

Let γ=[1234554123]=(1,5,3)(2,4).

clipboard_ecf749fadb65f4c655fde26b4c0d8766f.png
Figure 3.1.3: γ. (Copyright: Pamini Thangarajah )
(1,5,3) can be read as 1 goes to 5, 5 goes to 3, and 3 goes back to 1, and is called a cycle of  γ of length 3. Then 2 goes to 4, and then 4 goes back to 2, and (2,4) is called a cycle of  γ of length 2.
Note
  •  (1,2,4,5) means that 1 goes to 2, 2 goes to 4, 4 goes to 5 and 5 goes to 1.  Note that 3 is not included, so 3 goes to 3. 
  • There is no cycle notation in the case of the identity, e, and we use e.  
  • The cycles are always listed in a logical and clear order-descending order of their smallest element.

  • If the permutation fixes an element (i.e., it remains unchanged), it is often omitted from the cycle notation.

Definition: Cycle

A cycle γ=(a1,,ak) means clipboard_e90a3b1fc8bea88a5a08987246ea06870.png

 

Definition: disjoint cycles

Disjoint cycles mean that the elements involved in one cycle are distinct from those in another. 

Two cycles in Sn, γ=(a1,,ak) and σ=(b1,,bl) are disjoint if aibj,i,j.

Note that the length of the cycles does not need to be the same. 

Example:  (1,2) and (3,4) are disjoint, but (1,2,3) and (3,4) are not disjoint.

Example 3.1.4

Let σ=[123456789101112122311195106478]

Then, a cycle decomposition of 

  σ=(1,12,8,10,4)(2)(3)(5,11,7)(6,9)=(1,12,8,10,4)(5,11,7)(6,9).

Note that these are disjoint cycles; therefore, they commute.

Theorem 3.1.1

1. Disjoint cycles are commutative.

Let γ and σ be disjoint cycles, then γσ=σγ.

2. Every permutation of a finite set can be written as a cycle or a product of disjoint cycles.

The inverse of a cycle:

Theorem 3.1.2

(a1,a2,,ak)1=(ak,ak1,,a1)

Example 3.1.5

(1,2,3)1=(3,2,1), and (1,2)1=(2,1)=(1,2). 

Let σ=[123456789101112122311195106478]=(1,12,8,10,4)(5,11,7)(6,9).

In a cycle decomposition, to find the inverse, just reverse the order of the cycles and find the inverse of each cycle. Hence, 

 σ1=(6,9)1(5,11,7)1(1,12,8,10,4)1=(9,6)(7,11,5)(4,10,8,12,1)

Note that disjoint cycles are commutative!

Caution

(2,3)(1,2)=(1,3,2)=(3,2,1)=(2,1,3) Note:  1 goes to 2 first, then to 2 and then gets to  3.

(1,2)(2,3)=(1,2,3)=(2,3,1)=(3,1,2)  Note: Since there is no 1 in the inner function, it goes to itself and then goes to 2.

Type of a permutation (cycle structure of a permutation)

The type of a permutation (or cycle structure of a permutation) is the integer partition formed from the cycle lengths in decreasing order. We will denote it by type(σ), where σ is a permutation in Sn.

Example 3.1.6

Let γ=[1234554123]=(1,5,3)(2,4)S5.

The type of γ is,  type (γ)=3 2.

 

Example 3.1.7

Let σ=[12344123]=(1,4,3,2)S4.

The type σ is, type (σ)=4.

Note

A partition of a positive integer n   is a sum of nonnegative integers n=k1++ks,kiN, where the order of the summand is not important. For example: 

The partitions of 6 are 6,5+1,4+2,4+1+1,3+3,3+2+1,3+1+1+1,2+2+2,2+2+1+1,2+1+1+1+1,1+1+1+1+1+1.

Example 3.1.8

How many permutations in S6 have type 321?

Type (321) permutation is of the form \boldsymbol{(_,_,_)(_,_)(_)}. There are 6! ways of filling the blanks. Note that each cycle can be restarted anywhere.

Hence, the number of permutations in S6 have type (321) is 6!(3)(2)(1).

Example 3.1.9

How many permutations in S6 have  3 cycles of length 2?

The  permutation is of the form \boldsymbol{(_,_)(_,_)(_,_)}. There are 6! ways of filling the blanks.  Since each cycle has two representations matching this format (by restarting at any two places), so divided by 23.

The order of the whole cycle can be changed while keeping the pattern. Divide by 3! ways to reorder the cycles.

Hence, the number of permutations in S6 have  3 cycles of length 2 is 6!(23)(3!).

Theorem 3.1.3

Suppose the number of cycles of length i is mi, for i=1,,k. and n=m1+2m2++(k1)m(k1)+kmk.

The number of  permutations in Sn of the type (mkm(k1)m1)  is 

n!1m12m2kmkm1!m2!mk!.

Example 3.1.10

 |S3|=3!=23=6.

Table 3.1.1: Cycle type for S3
Cycle type

111

 21

3

Number of permutations

3!133!=1

3!11211!1!=3

3!311!1!=2

Notation: 

         1(123123) the identity matrix.

   (1,2)(123213).  Note that 3 points to itself.

(1,2,3)(123231).

(1,3,2)(132321).

Hence, S3={e,(1,2),(1,3),(2,3),(1,2,3),(1,3,2)}.   

 

Table 3.1.2: Cayley table for S3

 

 

e

(1,2,3)

(1,3)

(1,2)

(2,3)

(1,3,2)

e

e

(1,2,3)

(1,3)

(1,2)

(2,3)

(1,3,2)

(1,2,3)

(1,2,3)

(1,3,2)

(2,3)

(1,3)

(1,2)

e

(1,3)

(1,3)

(1,2)

e

(1,2,3)

(1,3,2)

(2,3)

(1,2)

(1,2)

(2,3)

(1,3,2)

e

(1,2,3)

(1,3)

(2,3)

(2,3)

(1,3)

(1,2,3)

(1,3,2)

e

(1,2)

(1,3,2)

(1,3,2)

e

(1,2)

(2,3)

(1,3)

(1,2,3)

 

Example 3.1.11

Let's explore S4. Note S4 has  4!=24 elements.

 
Table 3.1.3: Cycle type for S4
 Cycle type

 1111

211

22

31

4

 

Number of permutations

4!144!=1

4!12212!1!=6

4!222!=3

4!11311!1!=8

4!411!=6

 

Hence, S4={e,(1,2),(1,3),(1,4),(2,3),(2,4),(3,4),(1,2)(3,4),(1,3)(2,4),(1,4)(2,3),(1,2,3),(1,3,2),(2,3,4),(2,4,3),(3,4,1),(3,1,4),(4,1,2),(4,2,1),(1,2,3,4),(1,2,4,3),(1,3,4,2),(1,3,2,4),(1,4,2,3),(1,4,3,2)}.

Note

Notice that all the elements in S3 in S4.

 

The following theorem proves that Sn are non-Abelian for integer n ≥ 3, which means that the order in which we compose permutations matters. 

Theorem 3.1.4

Sn is non-Abelian for all integers n ≥ 3.

Proof

Let a,bS3.

We will show that there exists  a,bSn,s.t.abba, n3.

Note S3={e,(1,2),(1,3),(2,3),(1,2,3),(1,3,2)}.

Let a=(1,2) and b=(2,3) both elements of S3.

Consider ab=(1,2)(1,3)=(1,3,2) and ba=(1,3)(1,2)=(1,2,3).

Since (1,3,2)(1,2,3), abbaa,bS3, thus S3 is non-abelian.

Since a,bSn,n3, Sn in non-abelian for n3.◻

 

Example 3.1.12

Given α,βS4 with αβ=(1,4,3,2),βα=(1,2,4,3), and α(1)=4, determine α and β.

Solution:

Let α=(1,4,c,d) and β=(w,x,y,z).

Since α(1)=4 and βα(1)=2, implies β(4)=2.

Since β(4)=2 and αβ(4)=3, implies α(2)=3.

Since α(2)=3 and βα(2)=4, implies β(3)=4.

Since β(3)=4 and αβ(3)=2, implies α(4)=2.Screen Shot 2023-07-04 at 6.19.05 AM.png

Since α(4)=2 and βα(4)=3, implies β(2)=3.

Since β(2)=3 and αβ(2)=1, implies α(3)=1.

Since α(3)=1 and βα(3)=1, implies β(1)=1.

α=(1,4,2,3) and β=(2,3,4).

Then βα=(2,3,4)(1,4,2,3)=(2,4,3,1)=(1,2,4,3).

And αβ=(1,4,2,3)(2,3,4)=(4,3,2,1)=(1,4,3,2).

Figure 3.1.4: Thinking out Loud (Copyright: Pamini Thangarajah)

 

 

Note that every permutation of a finite set can be written as a cycle or a product of disjoint cycles.

2 Cycle (Transposition)

 

Definition: Transposition

(i,j),ij,jn,ij.

(i,j)1=(j,i)=(i,j).

Example 3.1.1

(1, 3, 2) = (1, 2) (1, 3)  1 goes to 3, 3 goes to itself, then to 1 then to 2.

(1, 2, 3) = (1, 3) (1, 2).

(2, 4, 1, 3, 5) = (2, 5) (2, 3) (2, 1) (2, 4)

Note:  Any cycle can be written as a composition of two cycles.

Theorem 3.1.5

A kcycle (i1,i2,ik) can be decomposed into a product of k1 transpositions. That is,

(i1,i2,ik)=(i1,ik)(i1,ik1)(i1,i2). 

Theorem 3.1.6

Every permutation in Sn can be expressed as a product of 2-cycles (Transpositions). The number of transpositions will either always be even or odd.

If a permutation α can be expressed as a product of an even number of 2-cycles, then every decomposition of α into a product of 2-cycles has an even number of 2-cycles.  A similar statement holds for odd.
 

Permutation parity 

Definition: Parity

Let σSn.  (i.e. a permutation)

Then 

(1) σ is an even permutation if σ can be expressed as a product of an even number of two cycles (transpositions).

(2) σ is an odd permutation if σ can be expressed as a product of an odd number of two cycles (transpositions).

Theorem 3.1.7

1. A cycle of even length is odd.

2. A cycle of odd length is even.

 

Example 3.1.13

1. let’s explore S4. Note S4 has  4!=24 elements.

Consider S4={e,(1,2),(1,3),(1,4),(2,3),(2,4),(3,4),(1,2)(3,4),(1,3)(2,4),(1,4)(2,3),(1,2,3),(1,3,2),(2,3,4),(2,4,3),(3,4,1),(3,1,4),(4,1,2),(4,2,1),(1,2,3,4),(1,2,4,3),(1,3,4,2),(1,3,2,4),(1,4,2,3),(1,4,3,2)} 

 

2. Find the center of S4.

Since all symmetrical groups, Snn3, are non-abelian, the centre of S4 is trivial, being the identity e, or (1)(2)(3)(4). (what do you think of this proof? Is this a valid argument?)

Alternatively, proof by exhaustion:  Having tried all x \in S_4, the only x \in S_4 that satisfies xg=gx, \; \forall g \in S_4 is the identity.

 

3. Find the cyclic subgroup of S_4 that has an order of 4.  

The subgroup of S_4, C4 =\{e, (1,2,3,4),(1,3)(2,4),(1,4,3,2) \}, has an order 4 and is generated by (1,2,3,4)

(1,2,3,4)^2=(1,3)(2,4), (1,2,3,4)^3=(1,4,3,2), and (1,2,3,4)^4=e.

 

4. Find a non-cyclic subgroup of S_4 that has order 4.

The 2-2 cycles together will form an order 4 group. 

\{e, (1,2)(3,4),(1,3)(2,4),(1,4)(2,3)\} is a subgroup of S_4 and has order 4.  Note the inverse of (1,2)(3,4) is (4,3)(2,1), which is (1,2)(3,4).  Since a similar argument can be made for the other 2-2 cycles, the inverses of each element exist.  In addition, the set is closed under composition.

Theorem \PageIndex{8}

The center of S_4, Z(S_4)=\{e\}.

Proof

Proof by contradiction

Let \gamma (\ne e) \in Z(S_n).  We shall find an \alpha \in S_n such that \gamma \alpha \ne \alpha \gamma. Since \gamma (\ne e), there exist l,m \in \{1,2,3,\cdots, n\} such that  \gamma (l) =m \ne l. Now we can choose an element k \in \{1,2,3,\cdots, n\} such that k\ne l and k\ne m. Choose \alpha=(l,k). Then \gamma \alpha(l)=\gamma(k) and \alpha \gamma (l)= \alpha(m)=m. Since \gamma is a bijection and  \gamma (l) =m \ne l, \gamma(k) \ne m.  This is a contradiction. Hence, Z(S_n) = \{e\}.

 

Order of a permutation

Let \sigma=(1, 2, 3).

Then \sigma^2=(1, 2, 3)(1, 2, 3)=(1, 3, 2)=\sigma^{-1}.

Further \sigma ^3=(1, 2, 3)(1, 3, 2)=(1)(2)(3)=e.  We shall refer to e as 1.

Thus the order of \sigma, |\sigma |=3.

Theorem \PageIndex{9}

If \sigma=(a_1, \ldots, a_k), then the |\sigma |=k

Proof

 Since \sigma^k(a_i)=a_i, \forall i=1, cdots, n, \sigma^=(a_1, \ldots, a_k)^k=e.  We shall show that k the smallest positive integer such that \sigma^k=e. Suppose  m is a positive integer such that 0 < m<k.) Then \(\sigma^m(a_i)=a_{i+m} \ne a_i\, \forall i=1, cdots, n). Hence \(k the smallest positive integer such that \sigma^k=e.

Example \PageIndex{14}

 Let \gamma = (1, 2, 4). Then

\gamma^2=(1, 2, 4)(1,2, 4)=(1, 4, 2).

\gamma^3=(1, 2, 4)(1, 4, 2)=(1)(2)(4)=e.

 
Theorem \PageIndex{10}

The order of a permutation of a finite set, written in disjoint cycle form, is the least common multiple of the lengths of the cycles.

Screen Shot 2023-07-06 at 9.57.45 AM.png

Example \PageIndex{15}

Find the orders of the 5040 elements of S_7.

Solution

The longest cycle in S_7 is the one that includes all the elements -- 7. We will show cycle lengths as \underline{7}.  Note the underlining.  The possible cycles are shown in the table below.  Note that the leading term is the longest cycle in the permutation.

Cycle type

Order

Cycle type

Order

Cycle type

Order

7

7

4 2 1

4

3 1 1 1 1

3

6 1

6

4 1 1 1

4

2 2 2 1

2

5 2

10

3 3 1

3

2 2 1 1 1

2

5 1 1

5

3 2 2

6

2 1 1 1 1 1

2

4 3

12

3 2 1 1

6

1 1 1 1 1 1 1

1

Conjugacy classes of S_n

Recall:

Two elements x,y in a group G are conjugate if y=gxg^{-1} for some g\in G.

Theorem \PageIndex{11}

For \alpha , \beta \in S_n\text{,} define \alpha \sim \beta if there exists a \sigma \in S_n such that \sigma \alpha \sigma^{-1} = \beta\text{.} Then \sim is an equivalence relation on S_n\text{.}

Proof

Reflexive: Let \alpha \in S_n. Then e\in S_n and e \alpha e^{-1} = \alpha\text{.} Hence  \alpha \sim \alpha. Thus \sim is reflexive on S_n\text{.}

Symmetric: Let \alpha , \beta \in S_n such that \alpha \sim \beta. Then there exists a \sigma \in S_n such that \sigma \alpha \sigma^{-1} = \beta\text{.}  Therefore,  \sigma^{-1} \beta \sigma= \alpha\text{,}  and \sigma^{-1} \in S_n.  Hence, \beta \sim \alpha. Thus \sim is symmetric on S_n\text{.}

Transitive: Let \alpha , \beta , \gamma \in S_n such that \alpha \sim \beta and  \beta \sim \gamma. Then there exist \sigma_1, \sigma_2 \in S_n such that \sigma_1 \alpha \sigma_1^{-1} = \beta\text{,} and  \sigma_2\beta \sigma_2^{-1}= \gamma\text{.} Consider, \begin{align*} \gamma &= \sigma_2\beta \sigma_2^{-1}\\ &= \sigma_2 \left( \sigma_1 \alpha \sigma_1^{-1}  \right) \sigma_2^{-1}\\ &=\left( \sigma_2 \sigma_1\right) \alpha \left( \sigma_1^{-1}   \sigma_2^{-1}\right)\\  &= \left( \sigma_2 \sigma_1\right) \alpha \left( \sigma_2  \sigma_1\right)^{-1} .\end{align*} Hence,  \alpha \sim \gamma.  Thus \sim is transitive on S_n\text{.}

Since \sim is reflexive, symmetric and transitive, \sim is an equivalence relation on S_n\text{.}

The equivalence classes are called conjugacy classes of G, subsets of G in which elements are conjugate to each other.

Theorem \PageIndex{12}

Two permutations in S_n are conjugate if and only if they have the same cycle structure, i.e. they have the same cycle type.

Example \PageIndex{16}

Conjugacy classes of S_3.

Solution

There are three conjugacy classes. Those are \{(1,2),(2,3),(1,3)\},\{e\},\{(1,2,3),(3,2,1)\}.


This page titled 3.1: Symmetric Groups is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.

Support Center

How can we help?