2.2. Subgroups and Cyclic Groups
i
“bookmt” — 2006/8/8 — 12:58 — page 92 — #104
i
i
92
2. BASIC THEORY OF GROUPS 2.1.16. Let M be a set with a not necessarily associative operation. Show that there are 14 ways of grouping five elements for multiplication. Try to find a method to show that there are 42 ways to group six elements for multiplication without listing the 42 ways.
2.1.17. Let M be a set with an associative operation and let N be a subset which is closed under the operation. Show that N is also closed for the product of an arbitrary number of elements; i.e., if n 1 and a1; a2; : : : ; an 2 N , then a1a2 an 2 N .
2.2. Subgroups and Cyclic Groups Definition 2.2.1. A nonempty subset H of a group G is called a subgroup if H is itself a group with the group operation inherited from G. We write H G to indicate that H is a subgroup of G.
For a nonempty subset H of G to be a subgroup of G, it is necessary that
1. For all elements h1 and h2 of H , the product h1h2 is also an element of H .
2. For all h 2 H , the inverse h 1 is an element of H .
These conditions also suffice for H to be a subgroup. Associativity of the product is inherited from G, so it need not be checked. Also, if conditions (1) and (2) are satisfied, then e is automatically in H ; indeed, H is nonempty, so contains some element h; according to (2), h 1 2 H as well, and then according to (1), e D hh 1 2 H .
These observations are a great labor–saving device. Very often when we need to check that some set H with an operation is a group, H is already contained in some known group, so we need only check points (1) and (2).
We say that a subset H of a group G is closed under multiplication if condition (1) is satisfied. We say that H is closed under inverses if condition (2) is satisfied.
Example 2.2.2. An n-by-n matrix A is said to be orthogonal if At A D E.
Show that the set O.n; R/ of n-by-n real–valued orthogonal matrices is a group.
Proof. If A 2 O.n; R/, then A has a left inverse At , so A is invertible with inverse At . Thus O.n; R/ GL.n; R/. Therefore, it suffices to check that the product of orthogonal matrices is orthogonal and that the inverse of an orthogonal matrix is orthogonal. But if A and B are orthogonal, then
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 93 — #105
i
i
2.2. SUBGROUPS AND CYCLIC GROUPS
93
.AB/t D Bt At D B 1A 1 D .AB/ 1; hence AB is orthogonal. If A 2 O.n; R/, then .A 1/t D .At /t D A D .A 1/ 1, so A 1 2 O.n; R/.
n
Here are some additional examples of subgroups:
Example 2.2.3. In any group G, G itself and feg are subgroups.
Example 2.2.4. The set of all complex numbers of modulus (absolute value) equal to 1 is a subgroup of the group of all nonzero complex numbers, with multiplication as the group operation. See Appendix D.
Proof. For any nonzero complex numbers a and b, jabj D jajjbj, and ja 1j D jaj 1. It follows that the set of complex number of modulus 1 is closed under multiplication and under inverses.
n
Example 2.2.5. In the group of symmetries of the square, the subset fe; r; r2; r3g is a subgroup. Also, the subset fe; r2; a; bg is a subgroup; the latter subgroup is isomorphic to the symmetry group of the rectangle, since each nonidentity element has square equal to the identity, and the product of any two nonidentity elements is the third.
Example 2.2.6. In the permutation group S4, the set of permutations satisfying .4/ D 4 is a subgroup. This subgroup, since it permutes the numbers f1; 2; 3g and leaves 4 fixed, is isomorphic to S3.
Example 2.2.7. In S4, there are eight 3–cycles. There are three elements that are products of disjoint 2–cycles, namely .12/.34/, .13/.24/, and .14/.23/. These eleven elements, together with the identity, form a subgroup of S4.
Proof. At the moment we have no theory to explain this fact, so we have to verify by computation that the set is closed under multiplication. The amount of computation required can be reduced substantially by observing some patterns in products of cycles, as in Exercise 2.2.4. The set is clearly closed under inverses.
Eventually we will have a theory that will make this result transparent.
n
We conclude this subsection with some very general observations about subgroups.
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 94 — #106
i
i
94
2. BASIC THEORY OF GROUPS Proposition 2.2.8. Let G be a group and let H1, H2; : : : ; Hn be subgroups of G. Then H1 \ H2 \ \ Hn is a subgroup of G. More generally, if fH˛g is any collection of subgroups, then \˛H˛ is a subgroup.
Proof. Exercise 2.2.7.
n
For any group G and any subset S G, there is a smallest subgroup of G that contains S , which is called the subgroup generated by S and denoted hSi. When S D fag is a singleton, the subgroup generated by S is denoted by hai. We say that G is generated by S or that S generates G if G D hSi.
A “constructive” view of hSi is that it consists of all possible prod ucts g1g2 gn, where gi 2 S or g 1
i
2 S. Another view of hSi, which is sometimes useful, is that it is the intersection of the family of all subgroups of G that contain S ; this family is nonempty since G itself is such a subgroup.
The family of subgroups of a group G are partially ordered by set inclusion.1 In fact, the family of subgroups forms what is called a latticeThis means that, given two subgroups A and B of G there is a unique smallest subgroup C such that C A and C B. In fact, the subgroup C is hA [ Bi. Furthermore, there is a unique largest subgroup D such that D A and D B; in fact, D D A \ B.
Example 2.2.9. Determine all subgroups of S3 and all containment relations between these subgroups. The smallest subgroup of S3 is feg. The next smallest subgroups are those generated by single element. There are three distinct subgroups of order 2 generated by the 2–cycles, and there is one subgroup of order 3 generated by either of the 3–cycles. Now we can compute that if a subgroup contains two distinct 2–cycles, or a 2–cycle and a 3–cycle, then it is equal to S3. Therefore, the only subgroups of S3 are h.12/i, h.13/i, h.23/i, h.123/i, feg, and S3. The inclusion relations among these subgroups are shown in Figure 2.2.1 on the facing page.
Cyclic Groups and Cyclic Subgroups
I now discuss a certain type of subgroup that appears in all groups.
Take any group G and any element a 2 G. Consider all powers of a: 1A partial order on a set X is a relation satisfying transitivity (x y and y z implies x z) and asymmetry (x y and y x implies x D y). Evidently, the family of subgroups of a group, with the relation , is a partially ordered set.
2The word lattice is used in several completely different senses in mathematics. Here we mean a lattice in the context of partially ordered sets.
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 95 — #107
i
i
2.2. SUBGROUPS AND CYCLIC GROUPS
95
S3
@
@
@
@
@
h.12/i
h.13/i
h.23/i
h.123/i
HHH
@
HH
@ HH @ HH@
@
H feg
Figure 2.2.1. Lattice of subgroups of S3.
Define a0 D e; a1 D a, and for k > 1, define ak to be the product of k factors of a. (This makes sense because of the general associative law, Proposition 2.1.19) For k > 1 define a k D .a 1/k.
We now have ak defined for all integers k, and it is a fact that akal D akCl for all integers k and l. Likewise, we can show that for all integers k, .ak/ 1 D a k. Finally, akl D .ak/l for all integers k and l. All of these assertions can be proved by induction, and you are asked to write the proofs in Exercise 2.2.8.
Proposition 2.2.10. Let a be an element of a group G. The subgroup hai generated by a is fak W k 2 Zg.
Proof. The formulas akal D akCl and .ak/ 1 D a k show that fak W k 2 Zg is a subgroup of G containing a D a1. Therefore, hai fak W k 2 Zg. On the other hand, a subgroup is always is closed under taking integer powers, so hai fak W k 2 Zg.
n
Definition 2.2.11. Let a be an element of a group G. The set hai D fak W k 2 Zg of powers of a is called the cyclic subgroup generated by a. If there is an element a 2 G such that hai D G, we say that G is a cyclic group. We say that a is a generator of the cyclic group.
Example 2.2.12. Take G D Z, with addition as the group operation, and take any element d 2 Z. Because the group operation is addition, the set of powers of d with respect to this operation is the set of integer multiples of
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 96 — #108
i
i
96
2. BASIC THEORY OF GROUPS d , in the ordinary sense. For example, the third power of d is d Cd Cd D 3d .
Thus, hd i D d Z D fnd W n 2 Zg is a cyclic subgroup of Z. Note that hd i D h d i.
Z itself is cyclic, h1i D h 1i D Z.
Example 2.2.13. In Zn, the cyclic subgroup generated by an element Œd is hŒd i D fŒkd W k 2 Zg D fŒkŒd W Œk 2 Zng.
Zn itself is cyclic, since hŒ1i D Zn.
Example 2.2.14. Let Cn denote the set of nth roots of unity in the complex numbers.
(a) Cn D fe2ik=n W 0 k n 1g.
(b) Cn is a cyclic group of order n with generator D e2i=n.
Proof. Cn is a subgroup of the multiplicative group of nonzero complex numbers, as the product of two nth roots of unity is again an nth root of unity, and the inverse of an nth root is also an nth root or unity.
If z is an nth root of unity in C, then jzjn D jznj D 1; thus jzj is a positive nth root of 1, so jzj D 1. Therefore, z has the form z D ei , where 2 R. Then 1 D zn D ein . Hence n is an integer multiple of 2, and z D e2ik=n for some k 2 Z. These numbers are exactly the powers of D e2i=n, which has order n.
n
Example 2.2.15. The set of all powers of r in the symmetries of the square is fe; r; r2; r3g.
There are two possibilities for a cyclic group hai, as we are reminded by these examples. One possibility is that all the powers ak are distinct, in which case, of course, the subgroup hai is infinite; if this is so, we say that a has infinite order.
The other possibility is that two powers of a coincide. Suppose k