Lecture Notes on Permutation Groups

5. Permutation groups Definition 5.1. Let S be a set. A permutation of S is simply a bijection f : S −→ S. Lemma 5.2. Let S be a set. (1) Let f and g be two permutations of S. Then the composition of f and g is a permutation of S. (2) Let f be a permutation of S. Then the inverse of f is a permu­ tation of S. Proof. Well-known. D Lemma 5.3. Let S be a set. The set of all permutations, under the operation of composition of permutations, forms a group A(S). Proof. (5.2) implies that the set of permutations is closed under com­ position of functions. We check the three axioms for a group. We already proved that composition of functions is associative. Let i : S −→ S be the identity function from S to S. Let f be a permutation of S. Clearly f ◦ i = i ◦ f = f . Thus i acts as an identity. Let f be a permutation of S. Then the inverse g of f is a permutation of S by (5.2) and f ◦ g = g ◦ f = i, by definition. Thus inverses exist and G is a group. D Lemma 5.4. Let S be a finite set with n elements. Then A(S) has n! elements. Proof. Well-known. D Definition 5.5. The group Sn is the set of permutations of the first n natural numbers. We want a convenient way to represent an element of Sn . The first way, is to write an element σ of Sn as a matrix. 1 2 3 4 5 3 1 5 4 2 ∈ S5 . Thus, for example, σ(3) = 5. With this notation it is easy to write down products and inverses. For example suppose that σ= 1 2 3 4 5 3 1 5 4 2 τ= 1 2 3 4 5 . 4 3 1 2 5 Then τσ = 1 2 3 4 5 . 1 4 5 2 3 1 MIT OCW: 18.703 Modern Algebra Prof. James McKernan On the other hand   1 2 3 4 5 στ = . 4 5 3 1 2 In particular S5 is not abelian. The problem with this way of representing elements of Sn is that we don’t see much of the structure of τ this way. For example, it is very hard to figure out the order of τ from this representation. Definition 5.6. Let τ be an element of Sn . We say that τ is a k-cycle if there are integers a1 , a2 , . . . , ak such that τ (a1 ) = a2 , τ (a2 ) = a3 , . . . , and τ (ak ) = a1 and τ fixes every other integer. More compactly ⎧ ⎪ ⎨ai+1 i < k τ (ai ) = a1 i=k ⎪ ⎩ otherwise. ai For example   1 2 3 4 2 3 4 1 is a 4-cycle in S4 and   1 2 3 4 5 . 1 5 3 2 4 is a 3-cycle in S5 . Now given a k-cycle τ , there is an obvious way to represent it, which is much more compact than the first notation. τ = (a1 , a2 , a3 , . . . , ak ). Thus the two examples above become, (1, 2, 3, 4) and (2, 5, 4). Note that there is some redundancy. For example, obviously (2, 5, 4) = (5, 4, 2) = (4, 2, 5). Note that a k-cycle has order k. Definition-Lemma 5.7. Let σ be any element of Sn . Then σ may be expressed as a product of disjoint cycles. This fac­ torisation is unique, ignoring 1-cycles, up to order. The cycle type of σ is the lengths of the corresponding cycles. 2 MIT OCW: 18.703 Modern Algebra Prof. James McKernan Proof. We first prove the existence of such a decomposition. Let a1 = 1 and define ak recursively by the formula ai+1 = σ(ai ). Consider the set { ai | i ∈ N }. As there are only finitely many integers between 1 and n, we must have some repetitions, so that ai = aj , for some i < j. Pick the 6 1. Then smallest i and j for which this happens. Suppose that i = σ(ai−1 ) = ai = σ(aj−1 ). As σ is injective, ai−1 = aj−1 . But this contradicts our choice of i and j. Let τ be the k-cycle (a1 , a2 , . . . , aj ). Then ρ = στ −1 fixes each element of the set { ai | i ≤ j }. Thus by an obvious induction, we may assume that ρ is a product of k − 1 disjoint cycles τ1 , τ2 , . . . , τk−1 which fix this set. But then σ = ρτ = τ1 τ2 . . . τk , where τ = τk . Now we prove uniqueness. Suppose that σ = σ1 σ2 . . . σk and σ = τ1 τ2 . . . τl are two factorisations of σ into disjoint cycles. Suppose that 6 i. By disjointness, in fact τp (i) = j. σ1 (i) = j. Then for some p, τp (i) = Now consider σ1 (j). By the same reasoning, τp (j) = σ1 (j). Continuing in this way, we get σ1 = τp . But then just cancel these terms from both sides and continue by induction. D Example 5.8. Let   1 2 3 4 5 σ= . 3 4 1 5 2 Look at 1. 1 is sent to 3. But 3 is sent back to 1. Thus part of the cycle decomposition is given by the transposition (1, 3). Now look at what is left {2, 4, 5}. Look at 2. Then 2 is sent to 4. Now 4 is sent to 5. Finally 5 is sent to 2. So another part of the cycle type is given by the 3-cycle (2, 4, 5). I claim then that σ = (1, 3)(2, 4, 5) = (2, 4, 5)(1, 3). This is easy to check. The cycle type is (2, 3). As promised, it is easy to compute the order of a permutation, given its cycle type. Lemma 5.9. Let σ ∈ Sn be a permutation, with cycle type (k1 , k2 , . . . , kl ). The the order of σ is the least common multiple of k1 , k2 , . . . , kl . 3 MIT OCW: 18.703 Modern Algebra Prof. James McKernan Proof. Let k be the order of σ and let σ = τ1 τ2 . . . τl be the decompo­ sition of σ into disjoint cycles of lengths k1 , k2 , . . . , kl . Pick any integer h. As τ1 , τ2 , . . . , τl are disjoint, it follows that σ h = τ1h τ2h . . . τlh . Moreover the RHS is equal to the identity, iff each individual term is equal to the identity. It follows that τik = e. In particular ki divides k. Thus the least common multiple, m of k1 , k2 , . . . , kl divides k. But σ m = τ1m τ2m τ3m . . . τlm = e. Thus m divides k and so k = m. D Note that (5.7) implies that the cycles generate Sn . It is a natural question to ask if there is a smaller subset which generates Sn . In fact the 2-cycles generate. Lemma 5.10. The transpositions generate Sn . Proof. It suffices to prove that every permutation is a product of trans­ positions. We give two proofs of this fact. Here is the first proof. As every permutation σ is a product of cycles, it suffices to check that every cycle is a product of transpositions. Consider the k-cycle σ = (a1 , a2 , . . . , ak ). I claim that this is equal to σ = (a1 , ak )(a1 , ak−1 )(a1 , ak−2 ) · · · (a1 , a2 ). It suffices to check that they have the same effect on every integer j between 1 and n. Now if j is not equal to any of the ai , there is nothing to check as both sides fix j. Suppose that j = ai . Then σ(j) = ai+1 . On the other hand the transposition (a1 , ai ) sends j to a1 , the ones befores this do nothing to j, and the next transposition then sends a1 to ai+1 . No other of the remaining transpositions have any effect on ai+1 . Therefore the RHS also sends j = ai to ai+1 . As both sides have the same effect on j, they are equal. This completes the first proof. To see how the second proof goes, think of a permutation as just be­ ing a rearrangement of the n numbers (like a deck of cards). If we can find a product of transpositions, that sends this rearrangement back to the trivial one, then we have shown that the inverse of the correspond­ ing permutation is a product of transpositions. Since a transposition is its own inverse, it follows that the original permutation is a product of transpositions (in fact the same product, but in the opposite order). In other words if τk · · · · · τ3 · τ2 · τ1 · σ = e, 4 MIT OCW: 18.703 Modern Algebra Prof. James McKernan then multiplying on the right by τi , in the opposite order, we get σ = τ1 · τ2 · τ3 · · · · · τk . The idea is to put back the cards into the right position, one at a time. Suppose that the first i − 1 cards are in the right position. Suppose that the ith card is in position j. As the first i − 1 cards are in the right position, j ≥ i. We may assume that j > i, otherwise there is nothing to do. Now look at the transposition (i, j). This puts the ith card into the right position. Thus we are done by induction on i. D 5 MIT OCW: 18.703 Modern Algebra Prof. James McKernan