Symmetric Group \(S_n\)

The symmetric group \(S_n\) is the group of all permutations of the set

\[ \{1,2,\ldots,n\}. \]

The group operation is the composition of permutations. Since there are \(n!\) permutations of \(n\) objects,

\[ |S_n|=n!. \]

Permutation composition is normally performed from right to left. Thus, in \(\sigma\tau\), we apply \(\tau\) first and then apply \(\sigma\).

The Symmetric Group \(S_2\)

The group \(S_2\) contains all permutations of the set \(\{1,2\}\):

\[ S_2=\{e,(12)\}, \]

where \(e\) is the identity permutation. Therefore,

\[ |S_2|=2. \]

Since

\[ (12)^2=e, \]

we have

\[ S_2\cong\mathbb Z_2. \]

• The identity \(e\) has order \(1\).
• The transposition \((12)\) has order \(2\).
• The group \(S_2\) is abelian.

The Symmetric Group \(S_3\)

The group \(S_3\) consists of all permutations of the set \(\{1,2,3\}\):

\[ S_3=\{e,(12),(13),(23),(123),(132)\}. \]

Therefore,

\[ |S_3|=3!=6. \]

The elements of \(S_3\) can be classified as follows:

• The identity \(e\), which has order \(1\).
• The transpositions \((12),(13),(23)\), each of which has order \(2\).
• The \(3\)-cycles \((123),(132)\), each of which has order \(3\).

For example, using right-to-left composition,

\[ (12)(23)=(123). \]

However,

\[ (23)(12)=(132). \]

Consequently,

\[ (12)(23)\neq(23)(12). \]

Therefore, \(S_3\) is a nonabelian group.

A presentation of \(S_3\) is

\[ S_3=\left\langle r,s\mid r^3=e,\ s^2=e,\ srs=r^{-1}\right\rangle, \]

where we may take

\[ r=(123),\qquad s=(12). \]

Dihedral Group \(D_n\)

The dihedral group \(D_n\) is the group of all symmetries of a regular \(n\)-gon.

It contains:

• \(n\) rotations;
• \(n\) reflections.

Therefore,

\[ |D_n|=2n. \]

A standard presentation of \(D_n\) is

\[ D_n=\left\langle r,s\mid r^n=e,\ s^2=e,\ srs=r^{-1}\right\rangle, \]

where \(r\) represents a rotation through the angle \(\frac{2\pi}{n}\), and \(s\) represents a reflection.

Every element of \(D_n\) has one of the forms

\[ r^k\qquad\text{or}\qquad sr^k, \]

where \(0\leq k

An important relation in \(D_n\) is

\[ sr=r^{-1}s. \]

For \(n\geq3\), the group \(D_n\) is nonabelian.

Notation warning: Some books use \(D_{2n}\) for the dihedral group of order \(2n\). Here, \(D_n\) denotes the symmetry group of a regular \(n\)-gon and has order \(2n\).

The Dihedral Group \(D_3\)

The group \(D_3\) is the symmetry group of an equilateral triangle. It contains six elements:

\[ D_3=\{e,r,r^2,s,sr,sr^2\}. \]

The defining relations are

\[ r^3=e,\qquad s^2=e,\qquad srs=r^{-1}. \]

Thus,

\[ |D_3|=6. \]

Every symmetry of an equilateral triangle permutes its three vertices. Conversely, every permutation of its three vertices is produced by a symmetry. Hence,

\[ \boxed{D_3\cong S_3}. \]

One possible correspondence is

\[ r\longleftrightarrow(123),\qquad s\longleftrightarrow(12). \]

The Dihedral Group \(D_4\)

The group \(D_4\) is the symmetry group of a square. It contains eight elements:

\[ D_4=\{e,r,r^2,r^3,s,sr,sr^2,sr^3\}. \]

The defining relations are

\[ r^4=e,\qquad s^2=e,\qquad srs=r^{-1}. \]

Therefore,

\[ |D_4|=8. \]

The elements \(e,r,r^2,r^3\) represent rotations, while \(s,sr,sr^2,sr^3\) represent reflections.

• The identity \(e\) has order \(1\).
• The rotations \(r\) and \(r^3\) have order \(4\).
• The rotation \(r^2\) has order \(2\).
• Every reflection has order \(2\).

Unlike \(D_3\),

\[ D_4\not\cong S_4, \]

because

\[ |D_4|=8,\qquad |S_4|=24. \]

However, \(D_4\) can be represented as a subgroup of \(S_4\) by labeling the four vertices of the square. For example, we may take

\[ r=(1234),\qquad s=(24). \]

Then

\[ D_4=\langle(1234),(24)\rangle\leq S_4. \]

Cycle Notation

A cycle

\[ (a_1\,a_2\,\ldots\,a_k) \]

represents the permutation

\[ a_1\mapsto a_2,\quad a_2\mapsto a_3,\quad\ldots,\quad a_k\mapsto a_1. \]

All elements not appearing in the cycle remain fixed.

For example, the cycle \((135)\) means

\[ 1\mapsto3,\qquad3\mapsto5,\qquad5\mapsto1. \]

A cycle containing \(k\) symbols is called a \(k\)-cycle.

Disjoint Cycles

Two cycles are called disjoint if they have no common symbols. For example, \((12)\) and \((345)\) are disjoint.

Disjoint cycles commute:

\[ (12)(345)=(345)(12). \]

Every permutation can be expressed as a product of disjoint cycles. This expression is unique except for:

• the order in which the disjoint cycles are written;
• cyclic rearrangement of the symbols within a cycle.

For example,

\[ (135)=(351)=(513). \]

Transpositions

A cycle of length \(2\) is called a transposition. Examples include

\[ (12),\qquad(15),\qquad(34). \]

Every permutation can be expressed as a product of transpositions. For example,

\[ (123)=(13)(12). \]

More generally,

\[ (a_1a_2\ldots a_k) = (a_1a_k)(a_1a_{k-1})\cdots(a_1a_2). \]

Therefore, a \(k\)-cycle can be expressed as a product of \(k-1\) transpositions.

Even Permutations

A permutation is called even if it can be expressed as a product of an even number of transpositions.

The identity permutation is even because it is a product of zero transpositions.

The cycle \((123)\) is also even because

\[ (123)=(13)(12). \]

It is expressed as a product of two transpositions.

Odd Permutations

A permutation is called odd if it can be expressed as a product of an odd number of transpositions.

For example, \((12)\) is odd because it is one transposition.

The cycle \((1234)\) is also odd because

\[ (1234)=(14)(13)(12). \]

It is expressed as a product of three transpositions.

Although a permutation may have several different expressions as a product of transpositions, the parity of the number of transpositions is always the same. Therefore, a permutation cannot be both even and odd.

Parity of a Cycle

A \(k\)-cycle can be expressed as a product of \(k-1\) transpositions. Therefore,

\[ \boxed{\text{A \(k\)-cycle is even if and only if \(k\) is odd.}} \]

• A \(2\)-cycle is odd because it requires \(1\) transposition.
• A \(3\)-cycle is even because it requires \(2\) transpositions.
• A \(4\)-cycle is odd because it requires \(3\) transpositions.
• A \(5\)-cycle is even because it requires \(4\) transpositions.

Sign of a Permutation

The sign of a permutation \(\sigma\) is defined by

\[ \operatorname{sgn}(\sigma)= \begin{cases} 1,&\text{if \(\sigma\) is even},\\ -1,&\text{if \(\sigma\) is odd}. \end{cases} \]

The sign map

\[ \operatorname{sgn}:S_n\longrightarrow\{1,-1\} \]

is a group homomorphism. Hence,

\[ \operatorname{sgn}(\sigma\tau) = \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau). \]

• The product of two even permutations is even.
• The product of two odd permutations is even.
• The product of an even permutation and an odd permutation is odd.
• A permutation and its inverse have the same parity.

In particular,

\[ \operatorname{sgn}(\sigma^{-1}) = \operatorname{sgn}(\sigma). \]

Alternating Group \(A_n\)

The set of all even permutations in \(S_n\) is called the alternating group \(A_n\):

\[ A_n=\{\sigma\in S_n:\sigma\text{ is even}\}. \]

Since

\[ A_n=\ker(\operatorname{sgn}), \]

the alternating group is a normal subgroup of \(S_n\):

\[ A_n\trianglelefteq S_n. \]

For \(n\geq2\), exactly half of the permutations in \(S_n\) are even. Therefore,

\[ |A_n|=\frac{n!}{2}. \]

Moreover,

\[ [S_n:A_n]=2. \]

For example,

\[ A_3=\{e,(123),(132)\}. \]

Therefore,

\[ A_3\cong\mathbb Z_3. \]

Length of a Permutation

The phrase length of a permutation can have different meanings depending on the context.

Cycle length: The length of the cycle

\[ (a_1a_2\ldots a_k) \]

is \(k\). For example, the cycle \((1532)\) has length \(4\).

Transposition length: The transposition length of a permutation is the minimum number of transpositions needed to express it.

If \(\sigma\in S_n\) has \(c\) disjoint cycles, including fixed points, then

\[ \boxed{\ell_T(\sigma)=n-c}. \]

For example, let

\[ \sigma=(123)(45)\in S_5. \]

This permutation has two disjoint cycles. Therefore,

\[ \ell_T(\sigma)=5-2=3. \]

Indeed,

\[ (123)(45)=(13)(12)(45). \]

Inversions and Inversion Length

Write a permutation in one-line notation as

\[ \sigma=[\sigma(1),\sigma(2),\ldots,\sigma(n)]. \]

An inversion is a pair \((i,j)\) satisfying

\[ i<j \]

but

\[ \sigma(i)>\sigma(j). \]

The total number of inversions is called the inversion length of the permutation. It is also the minimum number of adjacent transpositions

\[ (12),(23),\ldots,(n-1\;\;n) \]

needed to express the permutation.

For example, consider

\[ \sigma=[3,1,2]. \]

Its inversions are \((1,2)\) and \((1,3)\). Therefore, its inversion length is \(2\). Since \(2\) is even, \(\sigma\) is even.

In general,

\[ \boxed{\sigma\text{ is even}\iff\sigma\text{ has an even number of inversions}.} \]

Similarly,

\[ \boxed{\sigma\text{ is odd}\iff\sigma\text{ has an odd number of inversions}.} \]

Order of a Permutation

Suppose that a permutation \(\sigma\) is expressed as a product of disjoint cycles of lengths

\[ m_1,m_2,\ldots,m_k. \]

Then the order of \(\sigma\) is

\[ \boxed{|\sigma|=\operatorname{lcm}(m_1,m_2,\ldots,m_k)}. \]

For example, let

\[ \sigma=(123)(45)(6789). \]

The cycle lengths are \(3\), \(2\), and \(4\). Therefore,

\[ |\sigma|=\operatorname{lcm}(3,2,4)=12. \]

Inverse of a Permutation

The inverse of a cycle is obtained by reversing its direction:

\[ (a_1a_2\ldots a_k)^{-1} = (a_k\ldots a_2a_1). \]

For example,

\[ (1234)^{-1}=(1432) \]

and

\[ (123)^{-1}=(132). \]

For a product of permutations,

\[ (\sigma\tau)^{-1} = \tau^{-1}\sigma^{-1}. \]

Basic Properties and Important Results

• The order of the symmetric group is \(|S_n|=n!\).
• Every permutation can be expressed as a product of disjoint cycles.
• Every permutation can be expressed as a product of transpositions.
• Disjoint cycles commute.
• A \(k\)-cycle has order \(k\).
• A \(k\)-cycle is a product of \(k-1\) transpositions.
• A \(k\)-cycle is even if and only if \(k\) is odd.
• The inverse of a cycle is obtained by reversing its direction.
• The order of a product of disjoint cycles is the least common multiple of their lengths.
• The product of two even permutations is even.
• The product of two odd permutations is even.
• The product of an even permutation and an odd permutation is odd.
• Exactly half of the permutations in \(S_n\) are even for \(n\geq2\).
• The set of even permutations forms the normal subgroup \(A_n\).
• For \(n\geq2\), \(|A_n|=\frac{n!}{2}\).
• The symmetric group \(S_n\) is nonabelian for every \(n\geq3\).
• For \(n\geq3\), the center of \(S_n\) is trivial: \(Z(S_n)=\{e\}\).
• The alternating group \(A_n\) is generated by \(3\)-cycles.
• Two permutations in \(S_n\) are conjugate if and only if they have the same cycle type.
• The groups \(D_3\) and \(S_3\) are isomorphic.
• The group \(D_4\) is isomorphic to a subgroup of \(S_4\), but \(D_4\not\cong S_4\).
• By Cayley’s theorem, every finite group is isomorphic to a subgroup of some symmetric group.

Conjugation of Cycles

Conjugation of a cycle by a permutation simply relabels the entries of the cycle:

\[ \sigma(a_1a_2\ldots a_k)\sigma^{-1} = \bigl(\sigma(a_1)\sigma(a_2)\ldots\sigma(a_k)\bigr). \]

Consequently, two permutations in \(S_n\) are conjugate if and only if they have the same cycle type.