Permutation Groups (S_n): Cycle Decomposition, Sign, A_n

At a Glance

• Frequency: 2 sub-parts across 1 of 14 years (2013)
• Priority tier: T4
• Marks (count): 23 (2)
• Average solve time: ~12 min
• Difficulty mix: medium 2
• Section: A | Dominant type: computation

Why This Chapter Matters

Permutation groups underpin Cayley’s theorem, Galois theory, and many combinatorial arguments in UPSC Mathematics Paper 2. The two 2013 sub-parts tested cycle decomposition and facts about the alternating group $A_n$ — both are purely computational once the vocabulary is mastered. These are also among the most mechanical questions in the algebra syllabus: with the right template, full marks are achievable in under 15 minutes.

Minimum Theory

The Symmetric Group $S_n$

$S_n$ is the set of all bijections $\sigma : \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\}$, with composition as the group operation. $|S_n| = n!$.

Cycle Notation

A $k$-cycle $(a_1\; a_2\; \cdots\; a_k)$ denotes the permutation $a_1 \mapsto a_2 \mapsto \cdots \mapsto a_k \mapsto a_1, \quad \text{and every other element fixed.}$

Theorem (Cycle Decomposition). Every $\sigma \in S_n$ can be written uniquely (up to the order of the cycles and the starting point within each cycle) as a product of disjoint cycles.

Procedure:

1. Start from the smallest unmoved element $a_1$.
2. Trace $a_1 \to \sigma(a_1) \to \sigma^2(a_1) \to \cdots$ until you return to $a_1$; this gives one cycle.
3. Repeat with the smallest element not yet assigned.
4. Omit fixed-point 1-cycles (or include them if the sign is needed).

Order of a permutation. The order of $\sigma$ equals the lcm of its cycle lengths.

Transpositions and Sign

A transposition is a 2-cycle $(i\; j)$. Every cycle and hence every permutation is expressible as a product of transpositions (not uniquely, but the parity — even or odd number of transpositions — is an invariant).

Sign (parity). For $\sigma \in S_n$ with cycle decomposition having $c$ cycles (including fixed-point 1-cycles): $\mathrm{sgn}(\sigma) = (-1)^{n - c}.$ Equivalently, if $\sigma$ is written as a product of $t$ transpositions (any such product): $\mathrm{sgn}(\sigma) = (-1)^t.$ A $k$-cycle has sign $(-1)^{k-1}$ (it decomposes into $k-1$ transpositions).

Sign is a homomorphism: $\mathrm{sgn}(\sigma\tau) = \mathrm{sgn}(\sigma)\,\mathrm{sgn}(\tau)$.

Alternating Group $A_n$

$A_n = \ker(\mathrm{sgn}) = \{ \sigma \in S_n : \mathrm{sgn}(\sigma) = +1 \}.$

$A_n$ is a normal subgroup of $S_n$ with $|A_n| = n!/2$ for $n \ge 2$.

$A_n$ is simple (no proper normal subgroups) for $n \ge 5$ — a deep result tested occasionally.

Key membership rule: $\sigma \in A_n$ iff in its disjoint cycle decomposition, the number of even-length cycles is even.

Question Archetypes

cycle-decomposition (1 question; 2013)

Recognition Cues

• A permutation is given in two-row notation or as a product of cycles
• Asked to find: disjoint cycle form, order, sign, or powers of the permutation

Solution Template

1. Write the permutation in two-row notation if not already done.
2. Trace cycles: pick smallest unvisited element, follow the map until return.
3. Write down the disjoint cycle product.
4. State the order = $\mathrm{lcm}$ of cycle lengths.
5. Compute sign using $(-1)^{n-c}$ or by counting transpositions.

Worked Example

2013 Paper 2, 2013-P2-Q1a (10 marks)

Let $\sigma \in S_7$ be defined by $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 5 & 1 & 6 & 4 & 7 & 2 \end{pmatrix}.$ Express $\sigma$ as a product of disjoint cycles. Hence find its order and sign.

Solution.

Cycle decomposition.

• Start at 1: $1 \to 3 \to 1$. Cycle: $(1\;3)$.
• Smallest unvisited: 2. $2 \to 5 \to 4 \to 6 \to 7 \to 2$. Cycle: $(2\;5\;4\;6\;7)$.

So $\sigma = (1\;3)(2\;5\;4\;6\;7)$.

(Check: all 7 elements accounted for.)

Order. $\mathrm{ord}(\sigma) = \mathrm{lcm}(2, 5) = 10.$

Sign.

Number of elements $n = 7$. Number of cycles $c = 2$ (the two disjoint cycles above; no fixed points). $\mathrm{sgn}(\sigma) = (-1)^{7-2} = (-1)^5 = -1.$

Alternatively: $(1\;3)$ contributes $(-1)^{2-1} = -1$ and $(2\;5\;4\;6\;7)$ contributes $(-1)^{5-1} = +1$, so $\mathrm{sgn}(\sigma) = (-1)(+1) = -1$.

Therefore $\sigma \notin A_7$.

$\boxed{\sigma = (1\;3)(2\;5\;4\;6\;7),\quad \mathrm{ord}(\sigma)=10,\quad \mathrm{sgn}(\sigma)=-1}\;\blacksquare$

alternating-group-fact (1 question; 2013)

Recognition Cues

• Question asks about $A_n$: its order, normality, simplicity, or whether a specific permutation lies in $A_n$
• May ask to prove $A_n$ is a normal subgroup of $S_n$

Solution Template

1. Recall $A_n = \ker(\mathrm{sgn})$; since $\mathrm{sgn}$ is a homomorphism, $A_n \trianglelefteq S_n$.
2. $|A_n| = n!/2$ because the map $\mathrm{sgn}$ is surjective onto $\{+1,-1\}$ and the kernel has index 2.
3. For membership: compute the sign of the given permutation.

Worked Example

2013 Paper 2, 2013-P2-Q1b (13 marks)

(i) Show that $A_n$ is a normal subgroup of $S_n$ and determine its order. (ii) For $n \ge 3$, show that $A_n$ is generated by the 3-cycles in $S_n$.

Solution.

(i) $A_n \trianglelefteq S_n$.

Define $\mathrm{sgn} : S_n \to \{+1, -1\}$ by $\mathrm{sgn}(\sigma) = (-1)^t$ where $t$ is the number of transpositions in any decomposition of $\sigma$ (well-defined by invariance of parity). This is a group homomorphism: $\mathrm{sgn}(\sigma\tau) = (-1)^{s+t} = \mathrm{sgn}(\sigma)\,\mathrm{sgn}(\tau).$

Then $A_n = \ker(\mathrm{sgn})$. The kernel of any group homomorphism is a normal subgroup, so $A_n \trianglelefteq S_n$.

Since $\mathrm{sgn}$ is surjective (the transposition $(1\;2)$ maps to $-1$), the first isomorphism theorem gives $S_n / A_n \cong \{+1, -1\}$, so $[S_n : A_n] = 2$ and $|A_n| = \frac{n!}{2}.$

(ii) $A_n$ is generated by 3-cycles.

Every even permutation is a product of an even number of transpositions, so it suffices to show every product of two transpositions $(i\;j)(k\;l)$ is a product of 3-cycles.

• Case 1: Disjoint transpositions ($\{i,j\} \cap \{k,l\} = \emptyset$). $(i\;j)(k\;l) = (i\;j\;k)(j\;k\;l).$ (Verify: $i \mapsto j \mapsto k$, $j \mapsto k \mapsto l$, $k \mapsto l \mapsto l$… check all elements.)

Explicitly: $(i\;j\;k)$ sends $i\mapsto j, j\mapsto k, k\mapsto i$; $(j\;k\;l)$ sends $j\mapsto k, k\mapsto l, l\mapsto j$. Then the product $(i\;j\;k)(j\;k\;l)$: $i\mapsto j\mapsto k$; $j\mapsto k\mapsto l$; $k\mapsto i\mapsto i$; $l\mapsto l\mapsto j$… adjusting for right-to-left composition convention one verifies the product equals $(i\;j)(k\;l)$. $\checkmark$

• Case 2: Overlapping transpositions (share one element, say $j = k$). $(i\;j)(j\;l) = (i\;j\;l).$

Since every element of $A_n$ is a product of such pairs, every element of $A_n$ lies in the subgroup generated by 3-cycles. Conversely, every 3-cycle $(i\;j\;k) = (i\;j)(j\;k)$ is even, so lies in $A_n$.

Hence $A_n$ is generated by the 3-cycles.

$\boxed{A_n \trianglelefteq S_n,\quad |A_n|=n!/2,\quad A_n=\langle\text{3-cycles}\rangle}\;\blacksquare$

Common Traps

• Forgetting that fixed points count as 1-cycles when using the formula $(-1)^{n-c}$.
• Confusing “number of transpositions in a decomposition” (not unique) with “parity” (unique) — always state the invariance of parity explicitly.
• In two-row notation, reading the bottom row as the top row.
• Order of composition: $(1\;2)(2\;3)$ means apply $(2\;3)$ first (right-to-left), or $(1\;2)$ first (left-to-right) depending on convention — state your convention once.

Marks-Aware Writing

Section A, ~10–13 marks each sub-part:

• Cycle decomposition: show every step of the tracing (3–4 marks), state the order (2 marks), compute the sign with formula cited (3–4 marks).
• Alternating group proof: for normality, citing kernel-of-homomorphism is sufficient (3–4 marks); order calculation (2 marks); generators argument (4–5 marks).

Practice Set

Both historical questions on this atom are worked above (2013-P2-Q1a and 2013-P2-Q1b).