Two students decompose the 4-cycle (1 2 3 4) into transpositions differently. Student A writes (1 2)(1 3)(1 4) — three transpositions. Student B writes (1 4)(2 4)(3 4)(1 4)(2 4) — five transpositions. Which student, if either, is correct?
AStudent A only — the unique decomposition into transpositions uses exactly three
BStudent B only — a 4-cycle requires exactly five transpositions by the cycle-length rule
CBoth are correct — the decomposition into transpositions is not unique, but both use an odd number, preserving the correct parity
DNeither is correct — a 4-cycle must be written as a product of exactly two transpositions
The decomposition of a permutation into transpositions is never unique — there are infinitely many ways to do it. What is invariant is the parity: a given permutation always decomposes into either an even or odd number of transpositions. A 4-cycle is an odd permutation (it takes k−1 = 3 transpositions in the standard formula, and 3 is odd). Both 3 and 5 are odd, so both students have correct, valid decompositions with consistent parity. Students often assume the decomposition must be unique — this question targets that misconception directly.
Question 2 Multiple Choice
Is the permutation (1 2 3) in S₃ even or odd?
AOdd — it moves three elements, one for each transposition needed
BEven — it decomposes into two transpositions: (1 2)(1 3), which is an even number
CNeither — a 3-cycle is its own inverse, so parity is undefined
DOdd — any single cycle is an odd permutation by definition
A k-cycle decomposes as (a₁ a₂ ... aₖ) = (a₁ a₂)(a₁ a₃)···(a₁ aₖ), which requires k−1 transpositions. For a 3-cycle, that is 2 transpositions — an even number — making (1 2 3) an even permutation. The confusion in option A is a natural one: 'it moves three elements' sounds like it should take three transpositions, but the formula gives k−1, not k. Option D is incorrect: 2-cycles (transpositions) are odd; 3-cycles are even.
Question 3 True / False
The decomposition of a permutation into transpositions is not unique, so a given permutation can sometimes be expressed using an even number of transpositions and sometimes an odd number of transpositions.
TTrue
FFalse
Answer: False
This is the parity invariance theorem, and it is the key fact about transposition decompositions. While the specific transpositions used, their number, and their order are all non-unique, the *parity* — whether the total count is even or odd — is always the same for a given permutation. No permutation is simultaneously even and odd. This invariance is not obvious and requires proof; it is the foundation for the sign function sgn: Sₙ → {+1, −1} and the alternating group Aₙ.
Question 4 True / False
Disjoint cycles in a permutation can be applied in any order without changing the result, because they act on completely separate sets of elements.
TTrue
FFalse
Answer: True
Two cycles are disjoint if they involve no common elements. Since they act on entirely separate elements, the operations do not interact — applying one cycle has no effect on the elements the other cycle moves. Formally, disjoint cycles commute: (a b)(c d) = (c d)(a b) when {a,b} ∩ {c,d} = ∅. This is why the disjoint cycle decomposition of a permutation is so useful for computation: you can trace each element independently through its own cycle.
Question 5 Short Answer
Why is the parity of a permutation well-defined, even though there are infinitely many ways to write the same permutation as a product of transpositions?
Think about your answer, then reveal below.
Model answer: Parity is well-defined because of a topological or algebraic invariant that is preserved by every transposition: for instance, the sign of a permutation can be defined as the sign of the Vandermonde polynomial ∏(xᵢ − xⱼ) under the action of the permutation. Each transposition flips exactly one pair (xᵢ − xⱼ) to −(xᵢ − xⱼ), changing the sign. So every transposition toggles the sign exactly once. No matter how you factor a permutation into transpositions, each factor flips the sign once — so an even-count decomposition always leaves the sign unchanged (even permutation) and an odd-count decomposition always flips it (odd permutation). Because the final sign is determined by the permutation itself, not by the decomposition, parity is invariant.