Cycle Composition

MA441: Algebraic Structures I

Lecture 12 15 October 2003

1

Review from Lecture 11: We showed how to organize a list of the subgroups of a group into a diagram called the lattice of subgroups. We reviewed the definition of a permutation. We defined the group of permutations of degree n, denoted Sn, and showed that it has order n!.

2

Theorem 5.1: Products of Disjoint Cycles Every permutation of a finite set can be written as a cycle or as a product of disjoint cycles. Theorem 5.2: Disjoint Cycles Commute If the pair of cycles α = (a1a2 . . . am) and β = (b1b2 . . . bn) have no entries in common, then αβ = βα.

3

Theorem 5.3: The Order of a Permutation The order of a permutation of a finite set written in disjoint cycle form is the least common multiple of the lengths of the cycles. Idea of Proof: The disjoint cycles commute with each other. Therefore if we have a permutation α written as α = (a1a2 . . . am)(b1b2 . . . bk ) · · · (c1c2 . . . cs), then αn = (a1a2 . . . am)n(b1b2 . . . bk )n · · · (c1c2 . . . cs)n. When n is the LCM of m, k, s, and the other cycle lengths, that is the lowest power of α that equals the identity.

4

Proof: First, observe that a cycle of length n has order n. (Exercise 5.2) Next, suppose that α and β are disjoint cycles of lengths m and n, respectively. Let k be the LCM of m and n. Then (αβ)k = αk β k = e. Let t be the order of αβ, that is, t = |αβ|. By Corollary 2 to Theorem 4.1, we know that t divides k.

5

By definition of t, (αβ)t = e = αtβ t, so αt = β −t. Since α and β are assumed to be disjoint cycles, it is also true that αt and β t are disjoint cycles. Therefore αt and β t must both be the identity, since they are inverses, yet any element is fixed by either αt or β t since they are disjoint. αt = e implies m|t. β t = e implies n|t. So t equals the LCM of m and n.

6

We can extend the argument to more than two disjoint cycles by similar reasoning. We can prove this by induction, treating the above...