Permutation groups and parity

The cycle $(1\ 4\ 2)$ sends one to four, four to two, and two back to one, leaving unlisted labels fixed. Starting the written cycle at another point does not change its function: $(4\ 2\ 1)$ describes the same mapping. Reversing its direction usually changes the permutation and gives its inverse. To multiply permutations, follow each label through the rightmost factor first; then collect the resulting mapping into cycles.

Every permutation decomposes into disjoint cycles by following a label until it returns, then starting with a label not yet visited. Disjoint cycles commute because they affect separate labels. The decomposition is unique apart from rearranging its cycles and choosing where each cycle starts. Fixed points are cycles of length one, often omitted from the notation. Record them when the size of the underlying set matters, particularly in counting arguments.

A transposition swaps two labels and fixes the others. A cycle of length $k$ can be expressed using $k-1$ transpositions: exchange its first label with its last, then with the preceding labels in the appropriate right-to-left product. Therefore every permutation can be built from swaps. The expression is not unique, because inserting the same transposition twice changes neither the permutation nor its effect on any label.

Although the number of swaps is not unique, its parity is. One proof assigns a permutation its permutation matrix, whose determinant is either one or minus one. Swapping two labels swaps two columns of the identity matrix and changes the determinant's sign. Multiplicativity of determinants then forces every transposition decomposition of the same permutation to have the same evenness. This is a statement about all decompositions, rather than evidence from a few chosen expressions.

The symmetric group $S_n$ contains all permutations of $n$ labels and has $n!$ elements: choose the image of the first label, then the second, without repeating a destination. The even permutations form the alternating group $A_n$. Products and inverses of even permutations remain even because signs multiply. For $n\ge2$, multiplying by a fixed transposition pairs each even permutation with an odd one, so exactly half the permutations are even.

Cycle length and parity answer different questions. A three-cycle is even, despite containing three labels, because it needs two swaps. A four-cycle is odd but has order four. The identity is even and has order one. Nor does parity determine whether two permutations commute: two even three-cycles can interact nontrivially when they share labels. Use the cycle decomposition to calculate order, and use signs to calculate parity; replacing either task with intuition about the written number of symbols invites errors.