Abstract AlgebraPermutation Groups

The Order of a Permutation

Write σ as disjoint cycles: its order is the lcm of the cycle lengths, and its cycle type tells how many permutations share its shape.

Not started Jump to practice

With cycle notation, the order of a permutation can be read off with no multiplying at all.

Why it works

Theorem. The order of a permutation written as a product of disjoint cycles of lengths $k_{1}, \dots, k_{r}$ is $\operatorname{lcm}(k_{1}, \dots, k_{r})$.
Proof. A $k$-cycle has order $k$: each application moves every entry one place around the cycle, and they all come back to the start for the first time after $k$ steps. Disjoint cycles commute, so $$(\gamma_{1}\gamma_{2}\cdots\gamma_{r})^{m} = \gamma_{1}^{m}\gamma_{2}^{m}\cdots\gamma_{r}^{m},$$ and since the cycles move different numbers, this is the identity exactly when each $\gamma_{i}^{m}$ is, that is, when every $k_{i}$ divides $m$. The least such $m$ is the lcm. $\square$
$(1\;2\;3)(4\;5)$: the 3-cycle returns after 3 steps and the 2-cycle after 2, so everything returns together after $\operatorname{lcm}(3, 2) = 6$ steps.

Worked example: Orders from cycle lengths

Find the orders of $(1\;2\;3)(4\;5)$, $(1\;2\;3\;4)(5\;6\;7\;8)$ and $(1\;2\;3\;4\;5)(6\;7\;8)$.
  1. $\operatorname{lcm}(3, 2) = 6$.
  2. $\operatorname{lcm}(4, 4) = 4$, not $8$ or $16$.
  3. $\operatorname{lcm}(5, 3) = 15$.

Answer: $6$, $4$ and $15$.

Worked example: Overlapping cycles first

Find the order of $(1\;2)(2\;3)$.
  1. The cycles overlap, so multiply first: $3 \to 2 \to 1$, $1 \to 1 \to 2$, $2 \to 3 \to 3$, giving $(1\;2\;3)$.
  2. A single 3-cycle has order $3$.
  3. (The lcm of the original lengths, $2$, would be wrong.)

Answer: Order $3$.

Cycle types and counting

The lengths of the disjoint cycles (with fixed points as cycles of length 1) form the cycle type. To count the permutations of a given type in $S_{n}$, fill the pattern with the $n$ numbers and divide out the repeats: each $k$-cycle can be written starting at any of its $k$ entries, and cycles of equal length can be listed in any order. With $m_{k}$ cycles of length $k$ (including $k = 1$): $$\#\{\text{permutations of that type}\} = \frac{n!}{\prod_{k} k^{m_{k}}\, m_{k}!}.$$

Worked example: Counting 3-cycles in $S_{5}$

How many 3-cycles does $S_{5}$ contain?
  1. Fill $(\ast\;\ast\;\ast)$: $5 \cdot 4 \cdot 3 = 60$ ways.
  2. Each 3-cycle is written $3$ ways (start anywhere).
  3. $60/3 = 20$. The formula agrees: $5!/(3^{1} \cdot 1! \cdot 1^{2} \cdot 2!) = 120/6 = 20$.

Answer: $20$.

Worked example: A big power

Compute $\sigma^{100}$ for $\sigma = (1\;2\;3)(4\;5\;6\;7)$.
  1. The order is $\operatorname{lcm}(3, 4) = 12$, so exponents work mod $12$: $100 = 12 \cdot 8 + 4$, and $\sigma^{100} = \sigma^{4}$.
  2. Powers of disjoint cycles can be taken one cycle at a time: $(1\;2\;3)^{4} = (1\;2\;3)$ and $(4\;5\;6\;7)^{4} = e$.

Answer: $\sigma^{100} = (1\;2\;3)$.

Common mistake

Adding or multiplying cycle lengths instead of taking their lcm: $(1\;2\;3\;4)(5\;6)$ has order $\operatorname{lcm}(4, 2) = 4$, not $6$ or $8$. And take the lcm only after rewriting as disjoint cycles; overlapping ones can merge into longer cycles or cancel.

Key idea

For disjoint cycles, the order of the product is the lcm of the cycle lengths. The cycle type also tells how many permutations look alike: $n!/\prod k^{m_{k}} m_{k}!$.

Practice

Pass with 3 right answers, the last 2 in a row. Each right answer earns 2 XP.

Loading practice…

Builds on

Leads to

Sources and further reading

  • Thomas W. Judson, Abstract Algebra: Theory and Applications (open textbook), chapter 5, Permutation Groups (section 5.1)
  • John A. Beachy and William D. Blair, Abstract Algebra, online study guide (Northern Illinois University), section 2.3, Permutations (order of a permutation)
  • MIT OpenCourseWare 18.703 Modern Algebra (Spring 2013), lecture on permutation groups
@teddyrookbook GitHub