Back to the on-screen lesson ·
Bijections of a finite set, written as products of disjoint cycles: how to produce the decomposition, why it is essentially unique, and why cycles sharing a letter refuse to commute.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to read a permutation from cycle notation and say where it sends each letter, convert a list of images into disjoint cycle notation, explain why the decomposition into disjoint cycles always exists and is unique up to rewriting, state the cycle type of a permutation, say why disjoint cycles commute and cycles sharing a letter do not, and count the writings a single cycle has.
Unit 1 worked with groups described by arithmetic: residues, units, symmetries. Permutations are different in kind. They are functions, composed rather than multiplied, and Cayley's theorem — proved at the end of this unit — says every group is a group of permutations in disguise. So learning to compute with them is learning to compute with every finite group at once.
A permutation of $\{1, \ldots, n\}$ is a bijection from that set to itself. The symmetric group $S_n$ is the set of all of them under composition, of order $n!$. A cycle $(a_1\,a_2\,\ldots\,a_k)$ sends each $a_i$ to the next and $a_k$ back to $a_1$, fixing everything else; $k$ is its length, and a cycle of length $k$ is a $k$-cycle. A transposition is a $2$-cycle. Two cycles are disjoint when they share no letter.
A permutation may be written in two-line notation, listing each letter above its image, but the useful form is cycle notation.
To produce it: start at a letter, write it, write its image, write that letter's image, and continue until you return to where you began. Close the bracket. Start again with any letter not yet used. Stop when every letter has been used, and omit any cycle of length one — those are the letters the permutation fixes.
$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 4 & 2 \end{pmatrix} = (1\,3)(2\,5).$$
Three facts make the notation worth the trouble.
Every permutation decomposes into disjoint cycles, and the decomposition is unique up to the order in which the cycles are written and the letter each starts from. The tours always close because the map is a bijection: a letter can never be the image of two different letters, so following images never merges two tours.
Disjoint cycles commute. They move different letters, so neither interferes with the other, and a product of disjoint cycles may be written in any order.
Cycles that share a letter do not commute. $(1\,2)(1\,3) = (1\,3\,2)$ while $(1\,3)(1\,2) = (1\,2\,3)$. That single fact is why $S_n$ is non-abelian for $n \ge 3$, and it is the first genuinely non-commutative computation in this course.
Another way: picture
Put the letters as dots on a page and draw an arrow from each letter to its image. Because the map is a bijection, exactly one arrow leaves each dot and exactly one arrives, so the arrows fall into closed loops — and a dot with an arrow to itself is a fixed letter. The loops are the cycles, and the picture makes the uniqueness obvious: the loops are there whether or not anybody writes brackets round them.
Another way: steps
To write a permutation in cycle notation: 1. Pick the smallest letter not yet used and write it. 2. Write its image, then that letter's image, and so on. 3. Close the bracket when the next image is the letter you started from. 4. Repeat from step 1 until every letter has appeared. 5. Delete every bracket of length one.
$|S_n| = n!$: choose the image of $1$ in $n$ ways, then the image of $2$ in $n - 1$ remaining ways, and so on. So $|S_3| = 6$, $|S_4| = 24$, $|S_5| = 120$ — the symmetric groups grow faster than any other family in this course.
The cycle type of a permutation is the list of its cycle lengths, written in decreasing order, including the fixed letters as ones. It is a way of writing $n$ as a sum of positive parts, and it is the single most useful invariant a permutation has: order, parity and conjugacy are all functions of it alone.
For $S_4$ the five cycle types account for all twenty-four elements:
| Cycle type | How many | Order | Parity |
|---|---|---|---|
| $1+1+1+1$ (the identity) | $1$ | $1$ | even |
| $2+1+1$ (a transposition) | $6$ | $2$ | odd |
| $2+2$ | $3$ | $2$ | even |
| $3+1$ | $8$ | $3$ | even |
| $4$ | $6$ | $4$ | odd |
The counts add to $24$, which is the check worth doing. The count of $3$-cycles, for instance, is $8$: choose the fixed letter in $4$ ways, and there are $2$ distinct three-cycles on the remaining three letters, because $3! = 6$ writings describe $6/3 = 2$ cycles.
That last division — dividing by the length because a cycle can be started anywhere — is the transfer item of this lesson, and it is how every count of this kind is done.
Reading a cycle as a product of numbers. $(1\,3\,5)$ is not $1 \times 3 \times 5$. It is an instruction: $1$ to $3$, $3$ to $5$, $5$ to $1$.
Thinking the notation is unique. $(1\,2\,3) = (2\,3\,1) = (3\,1\,2)$, and disjoint cycles may be written in any order. What is unique is the set of cycles, not the string of symbols.
Writing fixed letters as cycles of length one. Harmless but wrong by convention, and it obscures which symmetric group the permutation is being regarded as living in.
Assuming all cycles commute. Only disjoint ones do. Cycles sharing a letter are exactly where $S_n$ stops being abelian.
Treating a product of non-disjoint cycles as a decomposition. $(1\,2)(2\,3)$ is a perfectly good permutation, but it is not in disjoint form, and the order and parity rules of the next lesson read the disjoint form only.
Images: $1 \mapsto 5$, $2 \mapsto 2$, $3 \mapsto 6$, $4 \mapsto 3$, $5 \mapsto 1$, $6 \mapsto 4$. Start at $1$: $1 \to 5 \to 1$, closing $(1\,5)$.
First tour.
Next unused letter is $2$, which is fixed, so it is omitted. Then $3 \to 6 \to 4 \to 3$, closing $(3\,6\,4)$.
Second tour, and one fixed letter.
So the permutation is $(1\,5)(3\,6\,4)$, of cycle type $3 + 2 + 1$.
Two disjoint cycles.
$(1\,2)(1\,3)$, composed right to left: $1 \to 3 \to 3$; $3 \to 1 \to 2$; $2 \to 2 \to 1$. So the result is $(1\,3\,2)$.
Follow each letter through both brackets.
The other way round, $(1\,3)(1\,2)$: $1 \to 2 \to 2$; $2 \to 1 \to 3$; $3 \to 3 \to 1$. That is $(1\,2\,3)$.
A different permutation.
The two cycles share the letter $1$, so nothing promised they would commute — and they do not. This is the smallest non-abelian group in the course.
$S_3$ is non-abelian, in one line.
Start at $1$: it goes to $2$, and $2$ goes back to $1$. That closes $(1\,2)$.
First tour.
Next unused is $3$: it goes to $5$, and $5$ goes back to $3$, closing $(3\,5)$. The letter $4$ is fixed.
Second tour.
So the permutation is $(1\,2)(3\,5)$, of cycle type $2 + 2 + 1$. The two cycles are disjoint, so they may be written in either order.
The permutation $(1\,3\,4)$ acts on the letters $1, 2, 3, 4$. Write down where it sends each of them.
| Its image | |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 |
Each permutation of $1, 2, 3, 4$ is given by its list of images, in the order $1, 2, 3, 4$. Match it to its cycle notation.
| $(1\,2\,3)$ | $(1\,2)(3\,4)$ | $(2\,3)$ | $(1\,2\,3\,4)$ | $(1\,3)(2\,4)$ | |
|---|---|---|---|---|---|
| $2, 1, 4, 3$ | |||||
| $2, 3, 1, 4$ | |||||
| $2, 3, 4, 1$ | |||||
| $1, 3, 2, 4$ |
A permutation of $1, \ldots, 5$ sends $1 \mapsto 3$, $2 \mapsto 4$, $3 \mapsto 5$, $4 \mapsto 1$, $5 \mapsto 2$. Put the letters in the order the cycle visits them, starting at $1$.
Number the steps in order (write the number in the box):
Select every statement about cycle notation that is true.
This task has no paper form; do it on a device.
A permutation of $1, \ldots, 6$ sends $1 \mapsto 4$, $2 \mapsto 6$, $3 \mapsto 3$, $4 \mapsto 1$, $5 \mapsto 2$, $6 \mapsto 5$. Which is its disjoint cycle decomposition?
A cycle of length $7$ may be written as a single bracket in several ways. How many?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The permutation $(2\,3)$ acts on the letters $1, 2, 3, 4$. Write down where it sends each of them.
| Its image | |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 |
You can convert between a list of images and disjoint cycle notation, and you know what the notation does and does not determine. Say in your own words why following a letter always returns you to the start. Next: composing two permutations, where the order of the factors starts to matter.
9. Your turn: write the permutation sending $1 \mapsto 2, 2 \mapsto 1, 3 \mapsto 5, 4 \mapsto 4, 5 \mapsto 3$ in cycle notation., step 3