76 Chapter 1. Groups I ∗ 1.107. If G is a group of order n, prove that G is isomorphic to a subgroup of GL(n, Q). Hint. If σ ∈ Sn, then the n×n permutation matrix Pσ is the matrix obtained from the n × n identity matrix by permuting its columns via σ. Show that σ → Pσ is an injective homomorphism Sn → GL(n, Q). ∗ 1.108. Let G be a group with |G| = mp, where p is prime and 1 m p. Prove that G is not simple. Hint. Show that G has a subgroup H of order p, and use the representation of G on the cosets of H. Remark. We can now show that all but 11 of the numbers smaller than 60 are not orders of nonabelian simple groups (namely, 12, 18, 24, 30, 36, 40, 45, 48, 50, 54, 56). Theorem 1.113 eliminates all prime powers (for the center is always a normal subgroup), and this exercise eliminates all numbers of the form mp, where p is prime and m p. ∗ 1.109. (i) Let a group G act on a set X, and suppose that x, y ∈ X lie in the same orbit: y = gx for some g ∈ G. Prove that Gy = gGxg−1. (ii) Let G be a finite group acting on a set X prove that if x, y ∈ X lie in the same orbit, then |Gx| = |Gy|. Section 1.8. Counting We now use groups to solve some diﬃcult counting problems. Theorem 1.124 (Burnside’s Lemma).32 Let G be a finite group acting on a finite set X. If N is the number of orbits, then N = 1 |G| τ∈G Fix(τ), where Fix(τ) is the number of x ∈ X fixed by τ. Proof. List the elements of X as follows: choose x1 ∈ X, and then list all the elements x1,x2,...,xr in the orbit O(x1) then choose xr+1 / ∈ O(x1), and list the elements xr+1,xr+2,... in O(xr+1) continue this procedure until all the elements of X are listed. Now list the elements τ1,τ2,...,τn of G, and form Figure 1.10, where fi,j = 1 if τi fixes xj 0 if τi moves xj. 32Burnside himself attributed this lemma to Frobenius. To avoid the confusion that would be caused by changing a popular name, P. M. Neumann has suggested that it be called “not- Burnside’s Lemma.” Burnside was a fine mathematician, and there do exist theorems properly attributed to him. For example, Burnside proved Theorem 7.62, which implies that there are no simple groups of order pmqn, where p and q are primes.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2010 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.