Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works

Recipe

Compute the composition of two permutations

Use when: you're given two permutations \sigma and \tau, in two-line or cycle notation, and need \sigma\circ\tau

Goal: the resulting permutation \sigma\circ\tau, written out in cycle notation

Taught in Composing permutations

Quick recipe

  1. Decide whether to trace via two-line notation or directly through cycles
  2. For each element x, apply tau first, then sigma, and record the result
  3. Collect the results into two-line notation, then read off the cycles
  4. When composing a permutation with itself, trace each element through the same cycle twice
  1. 1

    Look at how \sigma and \tau are given, and how used to tracing cycles directly you are.

    Example

    Given \sigma=(1\ 2\ 4) and \tau=(2\ 3) on \{1,2,3,4\}, both are already cycles, so direct tracing applies.

    • unsure, or more comfortable building the full array first — use Step 2's general method.
    • both permutations are already given in cycle notation — trace each element directly through the right cycle then the left cycle, Step 2's shortcut.

    Why: cycle notation can be composed by direct tracing, which is faster once you're used to it, but the two-line array is the safer default when unsure.

  2. 2

    Compute \tau(x), then feed that output into \sigma: (\sigma\circ\tau)(x)=\sigma(\tau(x)). Repeat for every x in the domain.

    Example

    (\sigma\circ\tau)(1)=\sigma(\tau(1))=\sigma(1)=2. (\sigma\circ\tau)(2)=\sigma(\tau(2))=\sigma(3)=3. (\sigma\circ\tau)(3)=\sigma(\tau(3))=\sigma(2)=4. (\sigma\circ\tau)(4)=\sigma(\tau(4))=\sigma(4)=1.

    ⚡ Shortcut

    Composing two products of disjoint transpositions works entirely by tracing, no array needed. For \alpha=(1\ 4)(2\ 5), \beta=(1\ 5)(2\ 4) on \{1,\ldots,5\}: trace 1 through \beta then \alpha, \beta(1)=5, \alpha(5)=2, so (\alpha\circ\beta)(1)=2. The same two-hop trace on every element gives \alpha\circ\beta=(1\ 2)(4\ 5).

    Why: composition is defined right to left, (\sigma\circ\tau)(x)=\sigma(\tau(x)), the same convention as ordinary function composition f(g(x)).

  3. 3

    Line up every input above the output computed in Step 2, then follow each element forward until it returns to its start to identify each cycle.

    Example

    1\mapsto2,\ 2\mapsto3,\ 3\mapsto4,\ 4\mapsto1 closes a single 4-cycle.

    Why: cycle notation is the compact, standard form, so the composition isn't finished until it's written that way, with every fixed point either shown or stated.

  4. 4

    Apply \sigma once, then apply \sigma again to that result, using the identical rule both times.

    Example

    \sigma=(1\ 2\ 4): \sigma^2(1)=\sigma(\sigma(1))=\sigma(2)=4; \sigma^2(2)=\sigma(4)=1; \sigma^2(4)=\sigma(1)=2; 3 stays fixed. So \sigma^2=(1\ 4\ 2).

    Why: \sigma\circ\sigma applies the identical rule twice in a row, so no new tracing method is needed beyond running Step 2's rule again on its own output.

Common mistakes

  • Applying \sigma first instead of \tau first, reversing the order composition is actually defined in.
  • Assuming \sigma\circ\tau and \tau\circ\sigma agree, since disjoint cycles commute but most pairs of permutations don't.
  • Dropping a fixed point from the final cycle notation instead of stating or implying it stayed put.
  • Losing track of a hop while tracing directly through cycles, sending an element to the wrong place.