Skip to content
Symmetric Groups, Cycles, and Transpositions
A companion webpage for the lecture on permutations, cycle notation, disjoint cycles, and the structure of the symmetric group. This page is designed to help students move from the language of functions to the algebra of symmetry.
Lecture video
Watch the lecture first, then use the notes below to consolidate the main definitions, examples, and structural results.
Dropbox video link.
Learning goals
By the end of this lesson, you should be able to:
- Define the symmetric group \(S_n\).
- Interpret a permutation as a bijection \(\{1,2,\dots,n\}\to\{1,2,\dots,n\}\).
- Convert between two-line notation and cycle notation.
- Recognize fixed points, cycles, transpositions, and disjoint cycles.
Conceptual goals
- Understand that symmetry can be encoded algebraically.
- See that complicated permutations break into simpler pieces.
- Understand why order matters when composing permutations.
- Connect cycle structure to partitions of \(n\).
1. What is the symmetric group \(S_n\)?
Let \(S\) be a finite set. The set of all bijections from \(S\) to itself forms a group under composition. When
\(S=\{1,2,\dots,n\}\), this group is denoted by \(S_n\) and is called the symmetric group of degree \(n\).
S_n=\{f:\{1,2,\dots,n\}\to\{1,2,\dots,n\}\mid f \text{ is bijective}\}.
\]
The group operation is composition of functions. The identity element is the map sending every element to itself, and each permutation has an inverse because every bijection is reversible.
The number of elements in \(S_n\) is
|S_n|=n!=n(n-1)(n-2)\cdots 2\cdot 1.
\]
Indeed, there are \(n\) choices for the image of \(1\), then \(n-1\) choices for the image of \(2\), and so on.
2. Ways to write a permutation
A permutation can be written in more than one way. Consider \(\gamma\in S_6\) defined by
\gamma(1)=2,\quad \gamma(2)=1,\quad \gamma(3)=3,\quad \gamma(4)=5,\quad \gamma(5)=6,\quad \gamma(6)=4.
\]
| Notation | How it appears | What it emphasizes |
|---|---|---|
| Explicit listing | \(\gamma(1)=2,\gamma(2)=1,\gamma(3)=3,\gamma(4)=5,\gamma(5)=6,\gamma(6)=4\) | The exact image of each element. |
| Two-line notation |
\[ \gamma= \begin{pmatrix} 1&2&3&4&5&6\\ 2&1&3&5&6&4 \end{pmatrix} \] |
A compact visual record of the map. |
| Cycle notation | \(\gamma=(1\,2)(4\,5\,6)\) | The moving pieces and their internal structure. |
3. Cycle notation
If \(i_1,i_2,\dots,i_k\) are distinct elements of \(\{1,2,\dots,n\}\), then the cycle
\((i_1\,i_2\,\dots\,i_k)\) sends
i_1\mapsto i_2,\quad i_2\mapsto i_3,\quad \dots,\quad i_{k-1}\mapsto i_k,\quad i_k\mapsto i_1,
\]
and fixes every element not appearing in the cycle.
Example
Let \(\sigma\in S_7\) be given by
\sigma=
\begin{pmatrix}
1&2&3&4&5&6&7\\
3&5&2&4&7&6&1
\end{pmatrix}.
\]
Start with \(1\). We have \(1\mapsto 3\), then \(3\mapsto 2\), then \(2\mapsto 5\), then \(5\mapsto 7\), and finally \(7\mapsto 1\). Therefore
\sigma=(1\,3\,2\,5\,7).
\]
Since \(4\) and \(6\) are fixed, they are omitted.
Important note: cycle notation is not unique
The cycle
\((1\,3\,2\,5\,7)\) can also be written as
\((3\,2\,5\,7\,1)\),
\((2\,5\,7\,1\,3)\),
\((5\,7\,1\,3\,2)\), or
\((7\,1\,3\,2\,5)\).
These all describe the same cycle, merely starting at different points.
4. Transpositions
A transposition is a cycle of length two. Thus
\((\ell\,k)\) is the permutation that swaps \(\ell\) and \(k\) and fixes every other element.
(\ell\,k)(\ell)=k,
\qquad
(\ell\,k)(k)=\ell,
\qquad
(\ell\,k)(j)=j\text{ for }j\notin\{\ell,k\}.
\]
Transpositions are the basic building blocks of permutations. One of the key results of the lesson is that every permutation can be written as a product of transpositions.
5. Composition, order, and disjoint cycles
Composition is read from right to left
If \(\alpha\beta\) is written as a product of permutations, the permutation \(\beta\) is applied first and then \(\alpha\).
Permutations do not usually commute
In general,
\(\alpha\beta\neq\beta\alpha\).
For example, in \(S_3\), if
\(\alpha=(1\,2\,3)\) and \(\beta=(2\,3)\),
then a direct computation shows that the two products are different.
Disjoint cycles
Two cycles are disjoint if they do not move any common element. For example,
\((1\,2)\) and \((3\,4\,5)\) are disjoint.
Disjoint cycles do commute:
(1\,2)(3\,4\,5)=(3\,4\,5)(1\,2).
\]
This is because each cycle acts independently of the other.
6. Two fundamental theorems
Theorem A: decomposition into disjoint cycles
Every permutation in \(S_n\) can be written as a product of pairwise disjoint cycles. This decomposition is unique up to the order of the cycles and the omission of 1-cycles.
The idea is to begin with some element \(i_1\), follow its orbit under repeated application of \(\sigma\), and record the resulting cycle. Then restrict \(\sigma\) to the remaining elements and continue.
Theorem B: decomposition into transpositions
Every permutation in \(S_n\) can be written as a product of transpositions.
Since every permutation is a product of disjoint cycles, it suffices to write a cycle as a product of transpositions:
(a_1\,a_2\,\dots\,a_m)=(a_1\,a_m)(a_1\,a_{m-1})\cdots(a_1\,a_2).
\]
Why the disjoint cycle decomposition is unique
Pick any element \(x\in\{1,2,\dots,n\}\). The repeated images
\(x,\sigma(x),\sigma^2(x),\dots\)
determine exactly one orbit, and hence exactly one cycle containing \(x\). Therefore the cycle containing \(x\) is forced by the action of \(\sigma\). Repeating this for each orbit determines the full disjoint cycle decomposition.
7. Cycle structure and partitions
Suppose a permutation \(\sigma\in S_n\) is written as a product of disjoint cycles, including 1-cycles, with lengths
\(n_1,n_2,\dots,n_k\). Then
n_1+n_2+\cdots+n_k=n.
\]
The list \((n_1,n_2,\dots,n_k)\), usually written in nondecreasing order, is called the cycle structure of \(\sigma\). It gives a partition of \(n\).
For example, if
\sigma=(2\,3)(1\,5\,4)\in S_5,
\]
then the cycle lengths are \(2\) and \(3\), so the cycle structure is the partition \((2,3)\) of \(5\).
8. Worked examples
Example 1: convert from two-line notation to cycles
Let
\[
\sigma=
\begin{pmatrix}
1&2&3&4&5\\
2&1&4&5&3
\end{pmatrix}.
\]
Then \(1\leftrightarrow 2\), and separately \(3\mapsto 4\mapsto 5\mapsto 3\). Hence
\[
\sigma=(1\,2)(3\,4\,5).
\]
Example 2: write a cycle as transpositions
A 5-cycle can be written as
\[
(1\,2\,3\,4\,5)=(1\,5)(1\,4)(1\,3)(1\,2).
\]
This shows concretely how long cycles are built out of swaps.
Example 3: identify fixed points
If \(\gamma=(1\,2)(4\,5\,6)\in S_6\), then the element \(3\) is fixed because it does not appear in the cycle notation.
Example 4: cycle structure
The permutation \((1\,4)(2\,5\,3)\in S_5\) has cycle lengths \(2\) and \(3\). Its cycle structure is therefore \((2,3)\).
9. Check your understanding
- Write the permutation
\[
\begin{pmatrix}
1&2&3&4&5&6\\
4&2&6&1&5&3
\end{pmatrix}
\]
in cycle notation. - Express the cycle \((1\,3\,5\,2)\) as a product of transpositions.
- Determine whether \((1\,2\,3)\) and \((3\,4)\) are disjoint.
- Find the cycle structure of \((1\,2)(3\,5\,4)\in S_5\).
- Explain why fixed points are usually omitted in cycle notation.
Teaching lens
A useful classroom emphasis is that permutations can be read in at least three complementary ways: as functions, as motion, and as algebraic factors. Students often understand a cycle better once they imagine the listed elements moving around a circle.
10. Summary
The symmetric group \(S_n\) is the group of all bijections of \(\{1,2,\dots,n\}\). Its elements are permutations, and cycle notation is the most efficient way to describe how those permutations move elements.
The two structural ideas to remember are these:
- Every permutation decomposes uniquely into disjoint cycles.
- Every permutation can be expressed as a product of transpositions.
These results make permutations manageable. Instead of viewing a permutation as a long list of values, we can read it as a collection of simple motions, each of which reveals part of the underlying symmetry.
Permutation
Cycle notation
Transposition
Disjoint cycles
Cycle structure