Permutations of Finite Sets

Part 15, Chapter 15: Mappings and Permutations

Learning objectives

Define a permutation as a bijection from a set to itself
Write permutations in two-line and cycle notation
Compute the composition of permutations

A permutation is a bijection from a finite set to itself, nothing more, nothing less. Yet from that one definition flows an enormous part of modern mathematics: group theory, combinatorics, the resolution of polynomial equations, the symmetries of a Rubik's cube. The reason permutations matter so much is that any time you shuffle a finite collection of objects, the rule that says "where each object went" is a permutation, and the algebra of these shuffles has surprising structure.

Definition and the symmetric group

A permutation of a set $A$ is a bijection $\sigma : A \to A$ . When $A = \{1, 2, \ldots, n\}$ , the set of all permutations of $A$ is denoted $S_n$ n and contains exactly $n!$ elements. With composition as the operation, $S_n$ n becomes the symmetric group on $n$ letters, the most-studied finite group in mathematics.

Two-line and cycle notation

The two-line notation stacks input above output:

$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{pmatrix}$

means $\sigma(1) = 3$ , $\sigma(2) = 1$ , $\sigma(3) = 4$ , $\sigma(4) = 2$ . The cycle notation traces orbits: starting from $1$ , follow the arrows: $1 \to 3 \to 4 \to 2 \to 1$ . That orbit is the cycle $(1\;3\;4\;2)$ . Each permutation decomposes uniquely into disjoint cycles.

A 2-cycle like $(1\;2)$ is called a transposition, it swaps two elements and fixes the rest. Every permutation is a product of transpositions; the parity of the number of transpositions needed is a permanent property called the sign of the permutation. Permutations with an even number of transpositions are called even; odd ones are called odd.

Where this shows up

Cryptography: Symmetric ciphers (AES, ChaCha20) are essentially permutations of a 128-bit block; the cycle structure of these permutations is what cryptanalysts probe to find weaknesses.
Algorithms: Sorting algorithms are permutations: the output is a re-ordering of the input. Big-O analysis of sorting counts the number of permutations the algorithm explores before stopping.
Statistics: Permutation tests in statistics randomly relabel data points to estimate $p$ -values without assuming a parametric distribution; the test draws random permutations from a finite group.

(Drag the numbered tiles in the top row to swap wires. The widget shows the cycle notation and parity update live. Switch to compose mode to see two permutations stacked, tau wires first, then sigma wires below, with the resulting composition cycle notation at the bottom.)

Composition

Permutations compose like any other mappings: $(\sigma \circ \tau)(x) = \sigma(\tau(x))$ . Apply $\tau$ first, then $\sigma$ . So if $\sigma = (1\;2\;3)$ and $\tau = (1\;2)$ :

$1 \xrightarrow{\tau} 2 \xrightarrow{\sigma} 3, \qquad 2 \xrightarrow{\tau} 1 \xrightarrow{\sigma} 2, \qquad 3 \xrightarrow{\tau} 3 \xrightarrow{\sigma} 1.$

So $\sigma \circ \tau = (1\;3)$ . Disjoint cycles commute (they touch different elements, so their order does not matter), but non-disjoint cycles generally do not.

Inverses and the identity

The identity permutation $e$ fixes every element. Every permutation $\sigma$ has an inverse $\sigma^{-1}$ with $\sigma \circ \sigma^{-1} = \sigma^{-1} \circ \sigma = e$ . The inverse of a cycle reverses its order: $(1\;2\;3)^{-1} = (3\;2\;1) = (1\;3\;2)$ . Inverting a product of disjoint cycles inverts each cycle separately.

Try it

In single mode, drag the input tiles until the wiring shows the cycle $(1\;3)(2\;4)$ . What is the parity?
Predict first: compute $\sigma \circ \tau$ and $\tau \circ \sigma$ by hand for $\tau = (1\;2)$ , $\sigma = (1\;3)$ , should they be equal? Switch to compose mode, set both, and verify order matters.
How many permutations of $\{1, 2, 3, 4\}$ are odd? Count by hand and check against the widget by listing.

Pause: a single transposition is odd. The composition of two transpositions is even. What does that say about the composition of three transpositions?

A trap to watch for

Composition of permutations reads right-to-left. Beginners compute $(1\;2\;3) \circ (1\;2)$ by applying $(1\;2\;3)$ first because it is written on the left. That is backwards. The convention $(\sigma \circ \tau)(x) = \sigma(\tau(x))$ feeds the input $x$ to $\tau$ first, $\tau$ is the function closest to $x$ in the formula. So $\tau$ acts first. This is the same right-to-left rule from 14.2, and the same trap. Whenever you compose permutations, trace the path: where does $1$ go under $\tau$ ? Now where does that go under $\sigma$ ? The result is $(\sigma \circ \tau)(1)$ . Some textbooks (notably some abstract algebra books) use the opposite convention, left-to-right, for permutations specifically. Always check the convention of the source.

What you now know

You can read a permutation in either two-line or cycle notation, decompose it into disjoint cycles, compute its inverse, compose two permutations correctly (right-to-left), and decide whether it is even or odd by counting transpositions. The next chapter introduces an entirely new number system, the complex numbers, built to give every polynomial a root and to provide the cleanest possible algebra of rotations and scalings in the plane.

Quick check

Mark section complete →

References

Lang, S. (1971). Basic Mathematics. Springer. Chapter 14 §3, permutations of a finite set.
Herstein, I. N. (1996). Topics in Algebra, 2nd ed. Wiley. Section 2.5: the symmetric group $S_n$ n, cycle decomposition, parity.
Dummit, D. S. & Foote, R. M. (2003). Abstract Algebra, 3rd ed. Wiley. Section 1.3: permutations, cycle notation, and the sign homomorphism.