《Discrete Mathematics II教学-华南理工》Section 9 Orbits, Cycles, and the Alternating Groups.pdfVIP

II.9 Orbits, Cycles, Alternating Groups 1 Section II.9. Orbits, Cycles, and the Alternating Groups Note. In this section, we explore permutations more deeply and introduce an important subgroup of S . n Lemma. Let σ be a permutation of set A. For a, b ∈ A, define a ∼ b if and only if b = σn (a) for some n ∈ Z. Then ∼ is an equivalence relation on A. Definition 9.1. Let σ be a permutation of a set A. The equivalence classes described in Lemma are the orbits of σ. Exercise 9.2. Let  1 2 3 4 5 6 7 8  σ =  5 6 2 4 8 3 1 7  . Find the orbits of σ. Solution. We consider the powers of σ as applied to various elements of set A: σ σ σ σ σ σ σ σ 1 → 5 → 8 → 7 → 1, 2 → 6 → 3 → 2, and 4 → 4. So the orbits are {1, 5, 8, 7}, {2, 6, 3}, and {4}. II.9 Orbits, Cycles, Alternating Groups 2 Note. In the previous example, we see that σ can be thought of as a permutation which cycles around the elements of A as follows: We can connect the elements of A and think of the permutation as a combination of rotations that we encountered in the previous section: Definition 9.6. A permutation σ ∈ Sn is a cycle if it has at most one orbit containing more than one element. The length of the cycle is the number of elements in its largest orbit. Example. σ ∈ S8 given above is not a cycle since it contains two orbits which contain more than one point. II.9 Orbits, Cycles, Alternating Groups 3 Note. So a cycle in Sn is either (1) a permutation which fixes all n points—this is a cycle of length 1, or (2) a permutat