III.68 Permutation Groups

Martin W. Liebeck

Let S be a set. A permutation of S is a function from S to S that is both injective and surjective—in other words, a function that “rearranges” the elements of S. For example, if S = {1, 2, 3}, then the function a : S → S that sends 1 to 3, 2 to 1, and 3 to 2 is a permutation of S; so is the function b that sends 1 to 3, 2 to 2, and 3 to 1; whereas the function c that sends 1 to 3, 2 to 1, and 3 to 1 is not a permutation. An example of a permutation of the set of real numbers is the function x 8 - 2x.

From the point of view of finite group theory, the most important permutations to study are those of the set I_n = {1, 2, . . . , n}, where n is a positive integer. Let S_n denote the set of all permutations of I_n. So, for example, the permutations a and b defined in the previous paragraph lie in S₃. To count how many permutations there are altogether in S_n, observe that, for a permutation f : I_n ∀ I_n, there are n choices for f(1), then n - 1 choices for f(2) (we can choose anything different from f(1), then n - 2 for f(3), and so on, until we have just 1 choice for f(n). Therefore the total number of permutations in S_n is n(n - 1) (n - 2) ··· 1 = n!.

If f and g are permutations of a set S, their composition f g is defined by f g(s) = f(g(s)) for all s ∈ S, and it is quite easy to see that f g is also a permutation of S. It is usual to drop the “” symbol and write just fg instead of f g. For example, if a, b ∈ S₃ are as in the first paragraph, then ab ∈ S₃ sends 1 to 2, 2 to 1, and 3 to 3, while ba sends 1 to 1, 2 to 3, and 3 to 2. Notice that ab ≠ ba.

For any set S, the identity function ι : S ∀ S, defined by ι(s) = s for all s ∈ S, is a permutation of S; and if f is a permutation of S, then there is an inverse permutation f^-1 that sends everything back to where it came from and therefore satisfies ff^-1 = f^-1f = ι. For example, the inverse of the above permutation a ∈ S₃ is the permutation that sends 1 to 2, 2 to 3, and 3 to 1. Also, for any permutations f, g, h of S, we have f(gh) = (fg)h, since both sides send any s ∈ S to f(g(h(s))).

Thus, the set of all permutations of S, together with the BINARY OPERATION [I.2 §2.4] of composition, satisfies the axioms for a GROUP [I.3 §2.1]. In particular, S_n is a finite group of size n!, known as the symmetric group of degree n.

There is a neat way of representing permutations succinctly, known as the cycle notation. It is best explained with an example. Let d ∈ S₆ be the permutation 1 3, 2 5, 3 6, 4 4, 5 2, 6 1. We can represent this more economically by writing 1 3 6 1, 2 5 2, and 4 4. We say the symbols 1, 3, 6 form a cycle of d (of length 3); similarly, 2, 5 form a cycle of length 2, and 4 a cycle of length 1. We then compress our notation even further and write d = (136) (25) (4), indicating that each number 1, 3, 6 in the first cycle is sent to the next one, except for the last which is sent back to the first, and likewise for the second and third cycles. This is the cycle notation for d; notice that the cycles have no symbols in common—they are called disjoint cycles. It is not too hard to see that every permutation in S_n can be expressed as a product of disjoint cycles; this is what we mean by the cycle notation for a permutation. For example, in cycle notation, the six permutations of S₃ are σ, (12) (3), (13) (2), (23) (1), (123), and (132). (The permutations a and b in the first paragraph are (132) and (13) (2), respectively.) You might like to while away a few minutes by working out the multiplication table of S₃.

The cycle-shape of a permutation g is the sequence of numbers we get by writing down the lengths of the disjoint cycles in the cycle notation for g, in decreasing order. For example, the cycle-shape of the permutation (163) (24) (58) (7) (9) in S_g is (3,2,2,1,1), or more succinctly (3, 2², 1²).

One can define the powers of a permutation f ∈ S_n in a natural way—namely, f¹ = f f² = ff, f³ = f²f, and so on. For example, if e = (1234) ∈ S₄, then e² = (13) (24), e³ = (1432), and e⁴ = ι. The order of a permutation f ∈ S_n is defined to be the smallest positive integer r such that f^r = ι: that is, the smallest number of times we have to do f to send everything back to where it came from. So the order of the r-cycle e above is 4. In general, the order of an r-cycle (i.e., a cycle of length r) is equal to r, and the order of a permutation in cycle notation is equal to the least common multiple of the lengths of the (disjoint) cycles.

It is often useful to be able to work out the order of a permutation. Here is one such instance. Suppose we shuffle a pack of eight cards in the following way: the pack is divided into two equal parts and then “interlaced,” so that if the original order was 1, 2, 3, 4, . . . , the new order is 1,5,2,6, . . . . How many times must this shuffle be repeated before the cards are again in the original order? Well, the shuffle gives the permutation of the eight card positions sending 1 to 1, 2 to 5, 3 to 2, 4 to 6, and so on, which in cycle notation is (1) (253) (467) (8). This has order 3, so the cards return to their original order after three shuffles. Things get quite interesting if we consider the same problem for different numbers of cards—you might like to try it yourself with fifty-two cards, for instance.

There is one slightly more subtle aspect of permutations which is important for group theory: namely, the theory of even and odd permutations. Again, this is best illustrated by example. Take n = 3, and let x_l, x₂, x₃ be three variables. Let us think of the permutations in S₃ as moving these variables around rather than the numbers 1, 2, and 3. So, for instance, we shall take the permutation (132) to send x₁ to x₃, x₂ to x₁, and x₃ to x₂. Now let Δ be the expression Δ (x₁ - x₂) (x₁ - x₃) (x₂ - x₃). We can apply permutations in S₃ to Δ in an obvious way: for example, (123) sends Δ to (x₂ - x₃) (x₂ - x₁) (x₃ - x₁). Notice that this is just the expression for Δ with two of the brackets, (x₁ - x₂) and (x₁ - x₃), reversed. So (123) sends Δ to Δ. However, if we apply (12) (3) to Δ, we get (x₂ - x_l)(x₂ - x₃)(x_l - x₃) = -Δ. You can see that each permutation in S₃ sends Δ to either +Δ or -Δ. Call those permutations that send Δ to +Δ even permutations and those that send Δ to -Δ odd permutations. Check that ι, (123), and (132) are even, while (12) (3), (13) (2), and (23) (1) are odd.

The definition of even and odd permutations for general n is very similar to this example. Let x_l, . . . , x_n be variables, and regard the permutations in S_n as moving these variables around rather than the symbols 1, 2, . . . , n. Define Δ to be the product of all x_i - x_j for i < j. Just as in the example, we can apply any permutation g ∈ S_n to Δ, and the result will be either +Δ or -Δ. Define the signature of g to be the number sgn(g) ∈ {+1, -1} such that g(Δ) = sgn(g)Δ. This defines the signature function sgn : S_n ∀ {+1, -1}. Then a permutation g ∈ S_n is even if sgn(g) = +1, and is odd if sgn(g) = -1.

It follows easily from the definition that

sgn(gh) = sgn(g) sgn(h)

for any g, h ∈ S_n, and also that the signature of any 2-cycle is -1. Since an r-cycle (a₁ a₂ ··· a_r) can be expressed as a product (a₁ a_r) (a₁ a_r-1)···(a₁ a₂) of 2-cycles, the signature of the r-cycle is (-1)^r-1. Hence, if g ∈ S_n has cycle-shape (r₁, r₂, . . . , r_k), then

sgn(g) = (-1)^r1-1(-1)^r2-1. . .(-1)^r_k^-1.

This makes it easy to work out the signature of any permutation. For example, the even permutations in S₅ are those that have cycle-shape (1⁵), (2², 1), (3, 1²), or (5). If you count these, you will find that there are sixty even permutations in S₅ altogether, which is exactly half of the total of 5! = 120 permutations in S₅. In general, the number of even permutations in S_n is n!.

So what is the point of this complicated definition? The answer is that the set of all even permutations in S_n forms a subgroup of size n!, known as the alternating group of degree n, and written as A_n. The alternating groups are very important examples of finite groups, because of the fact that, for n ≥ 5, A_n is a simple group—that is, its Only NORMAL SUBGROUPS [I.3 §3.3] are the identity subgroup and A_n itself (see THE CLASSIFICATION OF FINITE SIMPLE GROUPS [V.7]). For example, A₅ is a simple group of size 60, and in fact is the smallest non-Abelian finite simple group.