The symmetric group 𝓢_n

We have introduced the group 𝓢(X, ∘) of all bijections from X to itself. When the number of elements of X is finite the group 𝓢(X) is indicated by 𝓢_n, with n representing the cardinality of of X = {x₁, x₂, ..., x_n}, and is known as symmetric group of degree n.

Let X = {1, 2, ..., n}. Every element σ of 𝓢_n is a bijections from X to itself, represent a permutation of {1, 2, ..., n}. Thus the cardinality of 𝓢_n is

You may be familiar with the notion of a permutation of a set as a rearrangement of the elements of the set. Thus for the set {1, 2, 3, 4, 5}, a rearrangement of the elements that could be for example the new arrangement {5, 2, 4, 3, 1}.

Informally, a permutation of a finite set of objects, arranged in a given arbitrary order, consists of a rearrangement of those objects into another order. Given such an arrangement, two equivalent formal definitions of permutations can be give, depending on whether one considers them form a combinatorial of from an algebraic perspective.

Let n = 6, X = {1,2,3,4,5,6} and let σ the bijective mapping the act in the following way:

A permutation is thus a function mapping of each element listed in the left column into a single (not necessarily different) element from the same set listed at the right. Thus 1 is carried into 5, 2 is mapped into 1, and so on. Furthermore, to be a permutation of the set, this mapping must be such that each element appears in the right column once and only once.

We shall write σ as 2 x 6 matrix

since the σ is bijective in the bottom row, which contains the images of the elements of X we have all the elements of the first row in a different order. This means that

In general an element of 𝓢_n is indicated by a 2 x n matrix

The composition of two permutations σ ◦ τ, or στ where for example σ is the permutation above and τ is the following permutation

is the permutation obtained applying first τ on X then σ: Remember that the action of στ on X must be read in right-to-left order: first apply τ and then σ that is

if we reverse the order the result is

The group 𝓢_n is thus not Abelian. Now permutation multiplication is defined as function composition, we showed that function composition is associative. The identity element indicated by id of 𝓢_n is the permutation

The inverse of a permutation is the permutation that reverses the direction of the mapping σ, that is, σ⁻¹(a) is the element a' of X such that a = σ (a'), thus swapping the two rows and then reordering the first row. The inverse of the permutation

is the permutation

Starting from a permutation σ we can obtain its powers σ^k with k ∈ ℤ. Let r the least positive integer such that σ^r = id. Such an integer surely exists and it is the order of the permutation.

7.4.1 Example. Calculate the order of the permutation

The powers of τ are:

Thus the order of τ is 5.  ■

Let X be a set and let σ ∈ 𝓢_n. We define in X the following relation:

it can be easily proved it is an equivalence relation, thus X is parted into equivalence classes.

7.4.2 Definition. For a fixed x ∈ X, the set

is the orbit of x under σ.

Since X is finite, given a x ∈ X, there must exist given the invertibility of the permutation, a least positive integer m = m(x) such that σ^m(x) = x: indeed, there must exist two distinct integers h and k (h > k) such that σ^h(x) = σ^k(x), from which applying σ^−k(x) to both sides, we obtain

7.4.3 Proposition. Let σ ∈ 𝓢_n. Given m = m(x) the least positive integer such that σ^m(x) = x, the orbit of the element x under σ is the subset of X.

Proof. We have to prove that each σⁱ(x), with i ∈ ℤ, coincides to one of the m elements x = σ⁰(x), σ(x), σ²(x), ..., σ^m−1(x) of X. From i = mq + r, 0 ≤ r < m, we obtain

7.4.4 Definition. A cycle of σ is the ordered set

The integer m is said length of the permutation.

7.4.5 Example. Let σ ∈ 𝓢₆, the permutation

starting from 1 ∈ X, the orbit of 1 under σ is the subset X

Notice that the same orbit could be represented as the subset {1,2,3} since the order of the elements does not matter. If we order the elements of 𝓞_σ in a way that every element is the transformed of the previous element, we obtain a cycle of the permutation σ. In this case the cycle obtained starting from element 1 is

We use () when we are referring to a cycle. Also (3,2,1) represents the same cycle as well as (2,1,3), but it's not the case for the cycle (1,2,3) as the element 2, since σ(1) = 3.

Not every permutation is a cycle, e.g.

but as we shall we it can always be written as product of two cycle (1 4)(2 3).

If we pick an element not contained in the orbit 𝓞_σ(1), say 5, its orbit under σ is

The correspondent cycle is

There no more elements of X that are not already contained in the two cycles above, thus the cycle of the permutation σ are (1,3,2) and (5,6,4).

Not as each cycle represents a permutation : the one that sends every element in the next one, and the last one in the first element, while leaving all the other elements fixed. Thus

and

What is remarkable is that the original permutation σ can be obtained as a product of the two disjoint cycle γ₁ and γ₂

we could write directly

What we presented can be generalized in the following proposition.

7.4.6 Proposition. Every permutation σ ∈ 𝓢_n is the product of its cycles (which are disjoint).

Proof. Let γ₁, γ₂, ⋅⋅⋅, γ_k the disjoint cycles of σ, to prove that σ = γ₁ γ₂ ⋅⋅⋅ γ_k we have to prove that for each x ∈ X = {1, 2, ..., n} we have

Every x ∈ X is contained only in one cycle γ_i = (x, σ(x), σ²(x) ⋅⋅⋅ σ^m−1(x)). Moreover, for every j ≠ i and every y = σ^h(x) (i.e. for every y ∈ γ_i)

Then for every x ∈ X

Thus σ = γ₁γ₂ ⋅⋅⋅ γ_k.   □

Transpositions and the sign of a permutation

A 2-cycles (i, j) is a permutation that interchanges the two elements i and j while leaving all the other elements fixed. Thus, a 2-cycle is also called a transposition.

7.4.7 Example. The order of permutation τ = (1,2) (3,4,5,6) is 4. To see this let us calculate

7.4.8 Proposition. Every cycle can be written as product of transpositions i.e.

Proof. We use the method of induction on m.

Basic step. When m = 2, then the cycle becomes (1,2) which is in required form.

Induction step. Let the result true for k, Let as assume that (x₁, x₂, x₃, x_h, x_k+1) is a cycle of length k + 1. Then we have

as can be verified by computing the composition.

Now by the induction composition

Substituting (ii) into (i), we have

7.4.9 Example. Write the cycle (a, b, c, d, e, f) on the set A = {a,b,c,d,e,f) as a product of transpositions.

Solutions. The cycle (a, b, c, d, e, f) = (a,f) ∘ (a, e) ∘ (a, d) ∘ (a, c) ∘ (a,b)

Notice how a cycle of length m has order m.

7.4.10 Proposition. The order of a permutation σ ∈ 𝓢_n is the least common multiple of the length of its cycles.

Proof. Let σ = γ₁, γ₂ ⋅⋅⋅ γ_k, be the decomposition into a product of disjoint cycles. Let m_i the order of the i^th cycle and let M = lcm (m₁, m₂ ⋅⋅⋅ m_k), we have to prove that M is equal to the order N of σ. Indeed

hence N|M, furthermore

Then m_i | N ∀i = 1, ..., k, from which M|N, thus N = M.  □

7.4.11 Example- The order of

After checking that the cycles are disjoint with calcualate the order as lcm(4,3,2,3,5) = 60.  ■

7.4.12 Corollary. Every permutation is the product of 2-cycles (or transpositions).

Proof. Every cycle can be written as product of transpositions; For example

Since every permutation is the product of its cycles, and every cycle is a product of transpositions, the corollary is proved.   □

The writing of a permutation as the product of transpositions is not unique. For example

(1, 3, 2, 4) (1, 7, 6, 2) = (1, 4)(1, 2)(1, 3)(1, 2)(1, 6)(1, 7)

and also as

(1, 3, 2, 4) (1, 7, 6, 2) = (1, 7, 6, 4)(2, 3)
= (1, 4)(1, 6)(1, 7)(2, 3).

7.4.13 Definition. A permutation is said even if product of an even number of transposition, odd if product of an odd number of transpositions.

Remark. Although the expression of a permutation as a product of transpositions is not unique, the number of transpositions used for a certain permutation is either always odd or else always even.

7.4.14 Proposition. (Always Even or Always Odd) If a permutation can be written as product of an even number (odd) of transpositions, every other expression of the permutation contain an even (odd) number of transpositions.

Proof. We prove the theorem taking in consideration a polynomial P defined as follows

with 1 ≤ i < j ≤ n.

Let σ ∈ 𝓢_n, then σ is applied to p by the rule

For example, if n = 4 and σ = (2,3,4), then

and

we are going to prove that starting from a transposition, τ, then

To illustrate the underlying reasoning let us apply the transposition τ = (2, 4) to the polynomial (7.4.1), we have

since 2 and 4 are interchanged by τ. Analyzing this result, we observe the following:

1. The factor (x₂ − x₄) in p is changed to (x₄ − x₂) in τ(p), so this factor changes sign.

2. The factor (x₁ − x₃) is unchanged.

3. The remaining factors in τ(p) may be grouped in pairs as

   (x₁ − x₄) (x₁ − x₂) and (x₄ − x₃)(x₃ − x₂) = (x₃ − x₄)(x₂ − x₃)

   The products of these pairs are unchanged by τ.

Thusτ(p) = −p, in this particular case, and we are going to show it valid in general.

The factors of τ(p) may be analyzed as follows:

1. The factor (x_r − x_s) in p is changed to (x_s − x_r) in τ(p) so this factor changes sign.

2. The factors (x_i − x_j) in p with both subscripts different from r and s are unchanged by τ.

3. The remaining factors in p have exactly one subscript k different from r and s and may be grouped into pairs according to the following plan.

   1. If k < r < s, the pair (x_k − x_r) (x_k − x_s) becomes (x_k − x_s) (x_k − x_r), and their product is unchanged by the transposition τ.

   2. Similarly, if r < s < k, the product (x_r − x_k) (x_k − x_s) is also unchanged by τ.

   3. Finally, if r < k < s, then the pair (x_r − x_k) (x_k − x_s) is unchanged by τ since

      (x_s − x_k) (x_k − x_r) = [−(x_k − x_s)] [−(x_r − x_k)]
      = (x_k − x_s) (x_r − x_k)

Thusτ(p) = −p, and the proof is complete. With this fact it's clear that a permutation σ ∈ 𝓢_n, we have

depending on whether the permutation can be expressed as a product of an even or odd number of transpositions. Thus a permutation σ cannot be written both as product of even and odd number of transpositions.   □

7.4.15 Definition. The alternating group A_n is the subgroup of 𝓢_n that consists of all even permutations in 𝓢_n.

A_n is a subgroup of 𝓢_n. Let determine the number of elements in A_n.

Let

the k permutations even (all distinct) we want to count. Let τ an arbitrary transposition. Then the following permutations

are all odd and distinct. Suppose by contradiction that

Then

which is the cancellation law for groups. Since the group is not Abelian, it is important that τ is always on the same side.

Let us consider now odd permutations

the h odd permutations. Then

are h even permutations. By comparing with the previous relations we have k = h; We use this fact to prove the following

7.4.16 Proposition. The order of the subgroup A_n (its cardinality) of 𝓢_n is

Proof. For each odd permutation α, the permutation (12)α is even and, by the cancellation property in groups, (12)α ≠ (12)β when α ≠ β. Thus, there are at least as many even permutations as there are odd ones. On the other hand, for each even permutation α, the permutation (12)α is odd and (12)α ≠ (12)β when α ≠ β. Thus, there are at least as many odd permutations as there are even ones. It follows that there are equal numbers of even and odd permutations. Since |𝓢_n| = n!, we have |A_n| = n! /2.   □

7.4.17 Example. The group 𝓢₃ has six elements that we write in the cycle notation

The group multiplicative table is the following

The alternating subgroup A₃ is

Other groups of 𝓢₃ are the following

The first and last in list are the trivial subgroups.

Lemma 7.4.18 If n ≥ 5, then all 3–cycles are conjugate in A_n.

Proof. Let σ and θ = (123) be two 3-cycles in A_n for n ≥ 5. Let π a permutation in S_n such that πσπ⁻¹ = θ. If π is an even permutation we are done. Otherwise we choose k and l ∉ {1,2,3}. Since the 3-cycle θ and the transposition τ = (k l) are disjoint they commute and πτ is even. In view of this τθτ⁻¹ = θ. Hence (πτ)θ(πτ)⁻¹ = π(τθτ⁻¹)π⁻¹ = πθπ⁻¹ = σ. The permutation πτ is an even permutation and it conjugates σ and θ. This completes the proof. □

For the treatment of the following lemma notice these simple facts about transpositions:

• If two transposition are equal, they cancel each other (ab)(ab) = id.

• If two transpositions have one letter in common their product is a 3-cycle (ab)(ac) = (acb).

• If two transposition have no letter in common, their product can be expressed as the product of two 3-cycles, (ab)(cd) = (cad)(abc).

Lemma 7.4.19 For n ≥ 3, the alternating group A_n is generated by 3-cycles.

Proof. Since every even permutation is a product of an even number of 2-cycles, it suffices to show that every product of two 2-cycles may be written as product of 3-cycles. Therefore, consider a product

with a ≠ b, c ≠ d. If (ab) = (cd), then this product is the identity, and there is nothing to prove. If {a, b}, {c, d} have exactly one element in common, then we may assume c = a and observe

If {a, b}, {c, d} are disjoint, then

and the proof is complete.  □