Symmetric Group (All Permutations)

The symmetric group $S_n$, also sometimes just called the permutation group, consists of all permutations of $n$ objects. These objects being permuted can be labeled cards, or points, or whatever else you want. In isomorphic ciphers, the $n$ letters of the ciphertext alphabet are the objects being permuted. This group is always (for n > 2) non-commutative.

There are $n!$ elements in $S_n$, consisting of all possible permutations of the numbers {1, 2, ..., n} (or 0-indexed if you prefer, or any other set) with n elements). As permutations, these are (all of the) bijective functions from this set to itself. Each element can be described by a list of numbers which says what the output of the function is for each input index, which can be thought of as where the object goes.

It can also be described, sometimes more compactly, with cycle notation, which shows which elements cycle between each other and does not write anything for the elements which are unchanged by the permutation. In cycle notation, a swap is written as (1 2), a 3-cycle as (1 2 3) (meaning 1 goes to 2, 2 goes to 3, and 3 goes to 1), etc. with the lowest number used in the cycle at the beginning. Cycle notation can make working with permutations a bit more convenient. For example, you can take an nth power of an element by decimating each of the cycles by n. E.g. (1 2 3 4 5)^3 = (1 4 2 5 3).

The group operation in $S_n$ is composition of the permutations as functions, and based on how composition works, this is normally written as a left multiplication action. If you have two permutations $f$ and $g$, then $f * g$ is $f(g(x))$, where $x$ is one of the numbers getting permuted. When multiplying permutations, this means you basically need to read from right to left. For example, if you are working in $S_3$ and want to multiply (1 2) and (2 3), you consider where each number goes for (2 3) and then (1 2):

• 1 stays the same, then goes to 2, so 1 goes to 2 overall.
• 2 goes to 3, then stays the same, so 2 goes to 3 overall.
• 3 goes to 2, then goes to 1, so 3 goes to 1 overall. So the resulting permutation is (1 2) * (2 3) = (1 2 3).

Each permutation has a cycle type, which is the number of cycles of each size, which describes the shape of the permutation. The cycle type stays unchanged under conjugation, meaning that $f$ and $g * f * g^-1$ have the same cycle type for any permutations $f$ and $g$. This makes the conjugacy classes of $S_n$ the set of permutations of each given cycle type. The order of an element (number of times you need to repeat it to end up with the identity) can be found easily as the LCM of the cycle lengths, so all permutations of the same cycle type have the same order. For example, (1 2)(3 4) has order 2, and (1 2)(3 4 5) has order 6.

Permutations have a parity (even/odd or +/- 1), which is the number of swaps required to multiply together to produce them. The subgroup of all even permutations is $A_n$, and has $n!/2$ elements. $A_n$ is notable for being a simple group (meaning no normal subgroups), as long as $n >= 5$.

The subgroup structure of $S_n$ is extremely complicated, and not even really fully known for even somewhat modest values of $n$. All finite groups are subgroups of some permutation group, so in some sense, the subgroup structure of $S_n$ can get arbitrarily complicated. As some basic groups that it contains, though, it has cyclic groups corresponding to the orders possible for any cycle type, dihedral groups up to $D_{2n}$, alternating groups up to $A_n$, and symmetric groups up to $S_{n-1}$, among many others.

$S_n$ is surprisingly easy to generate with only a few permutations. For example, it can be generated by an n-cycle (1 2 ... n) and a single swap (1 2). For large enough $n$, generating $S_n$ is kind of the default given a few random permutations, and generating a subgroup instead often requires specific elements to be chosen for the generators.