Past exam of the mathematics course of the University of Cambridge / 2017 / ia / Paper 3 / 8E (Groups)

With rightmost-first composition, a permutation cycle satisfiesTracing each $a_j$ verifies the equality, and every other letter is fixed. Thus every cycle is a product of transpositions; decomposing a permutation into disjoint permutation cycles proves that every element of $S_n$ is such a product. The identity is the empty product.

To establish that parity is well defined, use the permutation matrix $P_{\sigma }$ defined by $P_{\sigma }{e}_i=e_{\sigma (i)}$. Its determinant is $\pm 1$, and $P_{\sigma \tau }=P_{\sigma }{P}_{\tau }$. A transposition swaps two columns of the identity matrix and has determinant $-1$. Therefore if $\sigma$ is expressed as a product of $r$ transpositions,The left side depends only on $\sigma$, so any two decompositions have the same parity. DefineMultiplicativity of the determinant makes this the sign homomorphism. Its kernel of a group homomorphism is the alternating groupIt is a normal subgroup consisting of the even permutations. For $n\ge 2$ the sign map is surjective because a transposition has sign $-1$, so $[S_n:A_n]=2$. For $n=1$ both groups are trivial.

Write $c=(12\cdots n)$, with $n\ge 2$. Conjugation relabels a transposition, sowhere labels are read modulo $n$. In particular the subgroup contains $(12),(23),\dots ,(n-1n)$. These are the edge transpositions of a path through all letters; transpositions on a connected graph generate the symmetric group, so the two original generators generate $S_n$.

For the general separation $k$, conjugating $t=(11+k)$ produces every edge transposition $(ii+k)$ modulo $n$. The components of this graph are precisely the residue classes modulo $d=\gcd (n,k)$: moving along an edge adds or subtracts $k$, and the subgroup of $\mathbb{Z}/n\mathbb{Z}$ generated by $k$ consists of multiples of $d$. Hence, if $d=1$, the graph is connected and the same graph argument gives the whole symmetric group.

For completeness, the graph argument can be proved without assuming a generating-set theorem. On a simple path $v_0,\dots ,v_{\ell }$, put $t_j=(v_{j-1}{v}_j)$. ThenThis is a conjugate of the last edge transposition; connectivity therefore supplies every transposition, and part (a) supplies every permutation.

If $d>1$, there are $d$ residue blocks of size $n/d>1$, since $1\le k<n$. The cycle $c$ permutes these blocks, and $t$ swaps two letters in the same block. Both preserve this block system, so their generated subgroup does too. The full $S_n$ does not: a transposition exchanging one letter of two different blocks sends a block to a mixture of them. Thus the subgroup is proper. This provesThus a cycle and a transposition generate the symmetric group exactly at coprime separation. The obstruction is preservation of a partition, not failure of transitivity: the $n$-cycle already acts transitively even when $d>1$.