Back to the on-screen lesson ·
The order as the lowest common multiple of the cycle lengths, the factorisation into transpositions, and why the number of swaps is not determined while its parity is.
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 compute the order of a permutation as the lowest common multiple of its cycle lengths, factor a cycle into transpositions and count them, decide whether a permutation is even or odd, explain why a cycle of even length is an odd permutation, say what is and is not determined about a factorisation, and prove that the even permutations form a subgroup.
A permutation has been written as disjoint cycles and composed with another. Now two questions get asked of it, and both are answered by the list of cycle lengths alone: how many times must it be applied to return to doing nothing, and is it built from an even or an odd number of swaps.
A transposition swaps two letters and fixes the rest. A permutation is even when it is a product of an even number of transpositions and odd when the number is odd; the sign or signature is $+1$ for an even permutation and $-1$ for an odd one. The alternating group $A_n$ is the set of even permutations, of order $n!/2$ for $n \ge 2$.
Order. Disjoint cycles commute, so raising a product of them to the power $t$ raises each separately. A cycle of length $\ell$ is the identity exactly when $\ell \mid t$, so the whole permutation is the identity exactly when $t$ is a common multiple of every cycle length. Hence
$$|\sigma| = \operatorname{lcm}(\ell_1, \ell_2, \ldots).$$
Not the product. $(1\,2)(3\,4)$ has order $2$, not $4$.
Parity. Every cycle is a product of transpositions:
$$(a_1\,a_2\,\ldots\,a_k) = (a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2),$$
which is $k - 1$ of them. So every permutation is a product of transpositions, and the natural count is the sum of $(\ell_i - 1)$ over the cycles.
That count is not unique — the identity is both the empty product and $(1\,2)(1\,2)$ — but its parity is. A permutation is even when the number is even and odd when it is odd, and no factorisation can disagree. Notice the reversal that catches everybody: a cycle of length $k$ is even exactly when $k$ is odd, because $k - 1$ is what counts.
Parities add: $\operatorname{sgn}(\sigma\tau) = \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)$. So the sign is a homomorphism onto $\{1, -1\}$, and the even permutations are its kernel — which is the first kernel in this course, met before homomorphisms are defined.
Another way: picture
Picture each cycle as a wheel turning one notch per application, with $\ell$ notches. The permutation is back to doing nothing when every wheel is simultaneously back at its start, and wheels of $3$ and $2$ notches line up again after $6$ turns, not after $5$ and not after $1$. That is the lowest common multiple, and it is why the answer is not the product unless the wheels share no factor.
Another way: steps
Given a permutation in disjoint cycle notation: 1. List the cycle lengths. 2. Order: take their lowest common multiple. 3. Parity: add up each length less one; even total means an even permutation. 4. Sanity check: a cycle of even length is an odd permutation. 5. For a product not in disjoint form, compose first.
The claim that needs proof is that no permutation is both a product of an even number of transpositions and of an odd number. Several proofs exist; the shortest uses the polynomial
$$\Delta = \prod_{i < j} (x_i - x_j).$$
A permutation $\sigma$ acts on it by permuting the subscripts, and a single transposition changes the sign of $\Delta$ exactly once. So a product of $r$ transpositions multiplies $\Delta$ by $(-1)^{r}$, and since the effect of $\sigma$ on $\Delta$ does not depend on how $\sigma$ was written, neither does $(-1)^{r}$. That is parity, well defined.
A permutation matrix gives the same result in a different language: a transposition swaps two rows of the identity matrix, which multiplies the determinant by $-1$, so the sign of a permutation is the determinant of its matrix. Anyone who has met determinants has already met this theorem.
What it buys is a homomorphism $S_n \to \{1, -1\}$, and with it the alternating group $A_n$ of even permutations. Multiplying by a single transposition is a bijection between the even and the odd permutations, so exactly half of $S_n$ is even and
$$|A_n| = \frac{n!}{2} \quad (n \ge 2).$$
A subgroup of index $2$, and every subgroup of index $2$ is normal — which is why $A_n$ is the example that unit 3 keeps returning to.
Taking the product of the cycle lengths for the order. $(1\,2)(3\,4)$ has order $2$. The lowest common multiple and the product agree only when the lengths are coprime.
Thinking a cycle of even length is an even permutation. It is odd. A $k$-cycle takes $k - 1$ transpositions, and the parities are opposite.
Applying the lowest common multiple rule to cycles that are not disjoint. $(1\,2)(2\,3)$ has order $3$, not $2$: it is a three-cycle in disguise. Compose into disjoint form first.
Believing the number of transpositions is determined. Only its parity is. A permutation can always be written with two more swaps than necessary.
Forgetting the fixed letters when reading a cycle type. They are cycles of length one and contribute nothing to either the order or the parity, which is why omitting them is safe — but they must be counted when the cycle type is being used to count elements.
$\sigma = (1\,5\,3)(2\,6)(4\,7\,8\,9)$: cycle lengths $3$, $2$ and $4$.
List the lengths first.
Order: $\operatorname{lcm}(3, 2, 4) = 12$. Applying $\sigma$ twelve times is the first return to the identity.
Lowest common multiple.
Parity: $2 + 1 + 3 = 6$ transpositions, so $\sigma$ is even and lies in $A_9$.
Each length less one, added.
$(1\,2)(2\,3)$ is not in disjoint form, so no rule applies to it yet. Compose, right factor first: $1 \to 1 \to 2$, $2 \to 3 \to 3$, $3 \to 2 \to 1$.
Trace the letters.
So the product is $(1\,2\,3)$: one cycle of length $3$, order $3$, and even.
Now the rules apply.
Reading the original form as two cycles of length two would have given order $2$ and even — right about the parity by luck, wrong about the order.
Disjoint form first, always.
Lengths $5$ and $2$, disjoint. Order $\operatorname{lcm}(5, 2) = 10$.
Lowest common multiple.
Transpositions: $4 + 1 = 5$.
Each length less one.
Five is odd, so the permutation is odd and is not in $A_7$. Note the five-cycle alone would have been even — the transposition is what flips it.
For the permutation $(1\,2\,3)(4\,5)$, write down its order and the number of transpositions it factors into.
| Value | |
|---|---|
| Its order | |
| Transpositions it factors into |
A permutation is a product of two disjoint cycles, of lengths $4$ and $2$. What is its order?
Answer:
Match each kind of permutation to its order.
| order $2$ | order $3$ | order $4$ | order $6$ | order $5$ | |
|---|---|---|---|---|---|
| A transposition | |||||
| A cycle of length three | |||||
| A cycle of length four | |||||
| A cycle of length three times a disjoint transposition |
Select every statement about the parity of a permutation that is true.
This task has no paper form; do it on a device.
Is $(1\,2\,3)$ even or odd?
Build the proof that the even permutations of $\{1, \ldots, n\}$ form a subgroup.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
For the permutation $(1\,2)(3\,4)$, write down its order and the number of transpositions it factors into.
| Value | |
|---|---|
| Its order | |
| Transpositions it factors into |
You can compute the order and the parity of a permutation from its cycle lengths alone. Say in your own words why the order is a lowest common multiple rather than a product, and why a four-cycle is odd. Next: the alternating group itself, and the theorem that every group is a group of permutations.
9. Your turn: what are the order and parity of $(1\,2\,3\,4\,5)(6\,7)$?, step 3