Permutation Groups

Definition

A permutation of a set is a bijective function from the set to itself. A permutation group is a set of permutations on a given set, together with the operation of function composition, that satisfies the group axioms:

Closure

• : The composition of two permutations is again a permutation.

Associativity

• : Composition of functions is associative.

Identity element

• : The identity permutation leaves every element unchanged.

Inverse element

• : Every permutation has an inverse permutation.

If a set has $n$ elements, then the set of all permutations of that set forms the symmetric group $S_n$, which is the most common example of a permutation group.

For example, if $X = \{1,2,3\}$, then one permutation may send:

• $1 \mapsto 2$
• $2 \mapsto 3$
• $3 \mapsto 1$

This can be written as $(1\,2\,3)$, meaning the elements cycle among themselves.

Main Content

1. Permutations and Symmetric Groups

• A permutation is a one-to-one and onto mapping from a set to itself, meaning every element is rearranged exactly once.
• The set of all permutations of $n$ objects forms the symmetric group $S_n$, whose order is $n!$. For example, $S_3$ has $3! = 6$ elements.

A permutation can be represented in several ways:

Two-line notation $$\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$$ This means $1\to 2$, $2\to 3$, and $3\to 1$.

Cycle notation $$(1\,2\,3)$$ This means 1 goes to 2, 2 goes to 3, and 3 goes back to 1.

Some permutations may fix certain elements. For instance: $$(1\,3)$$ means 1 and 3 are swapped, while 2 stays fixed.

The identity permutation is written as $e$ or sometimes as $()$, and it leaves all elements unchanged.

2. Group Operation: Composition of Permutations

• The operation in a permutation group is composition, meaning we apply one permutation after another.
• Composition is generally not commutative, so in many permutation groups $ab \neq ba$. This makes permutation groups important examples of non-abelian groups.

Suppose: $$\sigma = (1\,2\,3), \quad \tau = (1\,2)$$ Then the product $\sigma \circ \tau$ means apply $\tau$ first and then $\sigma$.

To compute:

• $1 \xrightarrow{\tau} 2 \xrightarrow{\sigma} 3$
• $2 \xrightarrow{\tau} 1 \xrightarrow{\sigma} 2$
• $3 \xrightarrow{\tau} 3 \xrightarrow{\sigma} 1$

So: $$\sigma \circ \tau = (1\,3)$$

But: $$\tau \circ \sigma \neq \sigma \circ \tau$$ which shows the order matters.

This non-commutative behavior is one of the defining features of permutation groups and is crucial in understanding algebraic structure.

3. Cycle Structure, Transpositions, and Subgroups

• Every permutation can be decomposed into disjoint cycles, which makes it easier to study and compute with.
• Any permutation can also be written as a product of transpositions, where a transposition is a swap of exactly two elements.

For example: $$(1\,2\,3\,4) = (1\,4)(1\,3)(1\,2)$$ This means a 4-cycle can be built from simpler swaps.

Important facts:

• Disjoint cycles commute with each other.
• A cycle of length $k$ can be expressed as $k-1$ transpositions.
• The parity of a permutation is determined by whether it is an even or odd number of transpositions.

Permutation groups often contain subgroups, which are smaller groups formed by some of the permutations in the larger group. Examples include:

• The alternating group $A_n$, consisting of all even permutations in $S_n$.
• Cyclic subgroups generated by a single permutation.
• Symmetry groups of geometric figures, such as the rotations of a triangle.

For example, the subgroup generated by $(1\,2\,3)$ is: $$\{e, (1\,2\,3), (1\,3\,2)\}$$ This is a cyclic subgroup of order 3.

Working / Process

1. Identify the underlying set

• Determine the set whose elements are being permuted, such as $\{1,2,3,4\}$ or the vertices of a square.
• Count the number of elements; if there are $n$ elements, the full permutation group is $S_n$.

2. Write the permutations clearly

• Use two-line notation or cycle notation to represent each permutation.
• If composing permutations, remember the rightmost permutation is applied first.

3. Analyze the group structure

• Verify closure, identity, inverse, and associativity.
• Find subgroups, cycle decomposition, order of elements, and whether the group is abelian or non-abelian.

For example, in $S_3$:

• The elements are $e$, $(1\,2)$, $(1\,3)$, $(2\,3)$, $(1\,2\,3)$, and $(1\,3\,2)$.
• You can compute products using composition rules.
• You can identify the subgroup $\{e, (1\,2\,3), (1\,3\,2)\}$, which is closed under composition.

A useful way to visualize a permutation is by tracking how elements move:

1 → 2 → 3 → 1

This helps in understanding cycle notation and repeated application of a permutation.

Advantages / Applications

• Permutation groups are fundamental in studying symmetry in mathematics and science, especially the symmetries of geometric objects such as polygons, polyhedra, and crystals.
• They provide a powerful framework for solving problems in combinatorics, counting arrangements, and analyzing rearrangements of objects.
• They are widely used in advanced mathematics, including Galois theory, where permutations of roots of polynomials help determine solvability by radicals, as well as in cryptography, coding theory, and computer science.

Summary

• Permutation groups consist of bijections from a set to itself under composition.
• The symmetric group $S_n$ is the group of all permutations on $n$ elements.
• Cycle notation and transpositions make permutations easier to represent and analyze.
• Permutation groups are essential for understanding symmetry and structure in algebra and beyond.