Applications of Abstract Algebra with Solved Questions step by step

1.1 Permutation Groups Suppose a set G is closed under an operation ∗. That is, suppose a ∗ b ∈ G for all a, b ∈ G. Then ∗ is called a binary operation on G. We will use the notation (G, ∗) to represent the set G with this operation. Suppose (G, ∗) also satisfies the following three properties. 1. (a ∗ b) ∗ c = a ∗ (b ∗ c) for all a, b, c ∈ G. 2. There exists an identity element e ∈ G for which e ∗ a = a ∗ e = a for all a ∈ G. 3. For each a ∈ G, there exists an inverse element b ∈ G for which a ∗ b = b ∗ a = e. The inverse of a is usually denoted a−1 or −a. Then (G, ∗) is called a group. For example, it can easily be verified that for the set Z of integers, (Z, +) is a group with identity element 0. c 1999 by CRC Press LLC Let S be a set, and let A(S) be the set of bijections on S. Then an element α ∈ A(S) can be uniquely expressed by its action (s)α on the elements s ∈ S. Example 1.1 If S = {1, 2, 3}, then A(S) contains six elements. One of the α in A(S) can be expressed as (1)α = 2, (2)α = 3, and (3)α = 1. Let ◦ represent the composition operation on A(S). Specifically, if α, β ∈ A(S), then define α ◦ β by the action (s)(α ◦ β) = ((s)α)β for s ∈ S. Since the composition of two bijections on S is also a bijection on S, then α ◦ β ∈ A(S). Hence, ◦ is a binary operation on A(S). It can easily be verified that (A(S), ◦) is a group (see Written Exercise 1). A group (G, ∗) is said to be abelian or commutative if a∗b = b∗a for all a, b ∈ G. For example, since m + n = n + m for all m, n ∈ Z, then (Z, +) is abelian. However, for a set S with more than two elements, α◦β = β ◦α for some α, β ∈ A(S). Therefore, if a set S contains more than two elements, then (A(S), ◦) is not abelian. We will represent the number of elements in a set S by |S|. Suppose S is a set with |S| = n. Then (A(S), ◦) is denoted by Sn and called the symmetric group on n letters. It can easily be shown that |Sn| = n! (see Written Exercise 2). Suppose α ∈ Sn. Then α can be viewed as a bijection on the set {1, 2,...,n}. This bijection can be represented by listing the elements in the set {1, 2,...,n} in a row with their images under α listed immediately below. α : 1 2 ··· n (1)α (2)α ··· (n)α Example 1.2 Let S = {1, 2, 3}, and let α ∈ S3 be given by (1)α = 2, (2)α = 3, and (3)α = 1. Then α can be represented as follows. α : 123 231 An element α ∈ Sn is called a permutation. Note that for permutations α, β ∈ Sn, we can represent α ◦ β as follows. 1 ··· n (1)α ··· (n)α 1 ··· n (1)β ··· (n)β = 1 ··· n (1α)β ··· (nα)β For example, let α ∈ S4 be given by (1)α = 2, (2)α = 4, (3)α = 3, and (4)α = 1, and let β ∈ S4 be given by (1)β = 4, (2)β = 3, (3)β = 2, and c 1999 by CRC Press LLC (4)β = 1. Then we can express α ◦ β as follows. = We now discuss another way to express elements in Sn. Let i1, i2,...,is be distinct elements in the set S = {1, 2,...,n}. Then (i1 i2 i3 ··· is−1 is) is called a cycle of length s or an s-cycle, and represents the permutation α ∈ Sn that maps i1 → i2, i2 → i3,...,is−1 → is, is → i1, and every other element in S to itself. For example, the permutation α : in S6 can be expressed as the 6-cycle (). Note that this expression of α as a cycle is not unique, for α can also be expressed as () and (), among others. Next, consider the permutation β : in S6. To express β using cycle notation, we must use more than one cycle. For example, we can express β as the following “product” of two 3-cycles: (135)(246). Since these cycles contain no elements in common they are said to be disjoint. And because they are disjoint, the order in which they are listed does not matter. The permutation β can also be expressed as (246)(135). Every permutation in Sn can be expressed as either a single cycle or a product of disjoint cycles. When a permutation is expressed as a product of disjoint cycles, cycles of length one are not usually included. For example, consider the permutation γ : in S6. Even though the fact that γ maps 6 to itself would be expressed as the 1-cycle (6), this cycle would not usually be included in the expression of γ as a product of disjoint cycles. That is, γ would usually be expressed as (135)(24) or (24)(135). In an expression of a permutation as a product of cycles, the cycles need not be disjoint. For example, the permutation α = () defined above can also be expressed as the product (13)(15)(16)(12)(14) of 2-cycles. c 1999 by CRC Press LLC Because these 2-cycles are not disjoint, the order in which they are listed matters. A 2-cycle is also called a transposition. Any permutation can be ex pressed as a product of transpositions in the way illustrated above for α. Specifically, the cycle (i1 i2 i3 ··· is−1 is) can be expressed as the product (i1 i2)(i1 i3) ··· (i1 is−1)(i1 is) of transpositions. If a permutation can be expressed as a product of more than one disjoint cycle, then each cycle can be considered separately when expressing the permutation as a product of transpositions. For example, the permutation β = (135)(246) defined above can be expressed as (13)(15)(24)(26), and the permutation γ = (135)(24) defined above can be expressed as (13)(15)(24). There are many ways to express a permutation as a product of trans positions, and the number of transpositions in these expressions may vary. However, the number of transpositions in the expression of a permutation as a product of transpositions is either always even or always odd. A per mutation is said to be even if it can be expressed as a product of an even number of transpositions, and odd if it can be expressed as a product of an odd number of transpositions. Thus, the product of two even permutations is even, and the product of two odd permutations is also even. The inverse of the cycle (i1 i2 i3 ··· is−1 is) is (is is−1 ··· i3 i2 i1). Suppose α = α1α2 ··· αk ∈ Sn, where each αi is a transposition. Then α−1 = α−1 k ··· α−1 2 α−1 1 = αk ··· α2α1 since α−1 i = αi for each transposition αi. Hence, the inverse of an even permutation is even. And because the identity permutation is even, the subset of even permutations in Sn forms a group. This group is denoted by An and called the alternating group on n letters. Since An is a subset of Sn and forms a group, we call An a subgroup of Sn. Definition 1.1 Let (G, ∗) be a group, and suppose H is a nonempty subset of G. If (H, ∗) is a group, then H is called a subgroup of G. Consider a regular polygon P, such as, for example, an equilateral triangle or a square. Any movement of P that preserves the general shape of P is called a rigid motion. There are two types of rigid motions – rotations and reflections. For a regular polygon P with n sides, there are 2n distinct rigid motions. These include the n rotations of P through 360j/n degrees for j = 1,...,n. The remaining n rigid motions are reflections. If n is even, these are the reflections of P across the lines that connect opposite vertices or bisect opposite sides of P. If n is odd, these are the reflections of P across the lines that are perpendicular bisectors of the sides of P. Since the rigid motions of P preserve the general shape of P, they can be viewed c 1999 by CRC Press LLC as permutations of the vertices or sides of P. The set of rigid motions of a regular polygon P forms a group called the symmetries of P. Example 1.3 Consider the group of symmetries of a square. To express these symmetries as permutations of the vertices of a square, consider the following general figure. 1 2 4 3 The 8 symmetries of a square can be expressed as permutations of the vertices of this general figure as follows (rotations are counterclockwise). Rigid Motion Permutation 90◦ rotation (1234) 180◦ rotation (13)(24) 270◦ rotation (1432) 360◦ rotation identity reflection across horizontal (12)(34) reflection across vertical (14)(23) reflection across 1–3 diagonal (24) reflection across 2–4 diagonal (13) Note that expressing these rigid motions as permutations on the vertices of the preceding general figure yields a subgroup of S4. When the symmetries of an n-sided regular polygon are expressed as permutations on the set {1, 2,...,n}, the resulting subgroup of Sn is de noted by Dn and called the dihedral group on n letters. The subgroup of S4 in Example 1.3 is the dihedral group D4. A group (G, ·), or just G for short, is called cyclic if there is an element a ∈ G for which G = {ai | i ∈ Z}. In this case, a is called a cyclic generator for G. More generally, suppose a is an element in a group G, and let H = {ai | i ∈ Z}. Then H is a subgroup of G called the cyclic group generated by a. Let ai = aj for some 0 <i<j. Then aj−i = aja−i = e, where e is the identity element in G. Thus, there is a smallest positive integer m for which am = e. Now, suppose at = e. Since t = mq + r for some 0 ≤ r<m, and at = amq+r = (am)qar = ar, it follows that r = 0. Hence, m divides t. Since ai = aj for i<j forces aj−i = e, a contradiction if 0 < j − i<m, the set {ai | 0 ≤ i<m} consists of m c 1999 by CRC Press LLC distinct elements. Furthermore, for any integer k we can write k = mq + r for some 0 ≤ r<m with ak = ar. Therefore, H = {ai | 0 ≤ i<m}, and H contains m elements. We summarize this discussion as the following theorem. Theorem 1.2 Suppose a is an element in a group G. If m is the smallest positive integer for which am = e, where e is the identity element in G, then the cyclic group generated by a contains m elements. The value of m in Theorem 1.2 is called the order of a. Also, a set S with |S| = n is said to have order n. Hence, the order of an element a in a group G is the order of the cyclic subgroup of G generated by a. We will show in Theorem 1.4 that for an element of order m in a group G of order n, m must divide n. Therefore, in a group G of order n, an = e for all a ∈ G where e is the identity element in G. We summarize this as the following corollary. Corollary 1.3 Suppose a is an element in a group G of order n. Then an = e where e is the identity element in G. Example 1.4 Consider the dihedral group Dn of order 2n. Recall that the elements in Dn can be viewed as the symmetries of an n-sided regular polygon P. Each of the n reflections of P has order 2. Also, the rotations of P through 360/n and 360(n−1)/n degrees have order n (as do, possibly, some other rotations). Note that these orders divide |Dn|. 1.2 Cosets and Quotient Groups Let H be a subgroup of a group G. For an element g ∈ G, we define gH = {gh | h ∈ H}, called a left coset of H in G. Since gh1 = gh2 implies h1 = h2 for all h1, h2 ∈ H, then there is a one-to-one correspondence between the elements in gH and H. Thus, if H is finite, |gH| = |H|. Suppose g1, g2 ∈ G. If x ∈ g1H ∩ g2H for some x ∈ G, then x = g1h1 = g2h2 for some h1, h2 ∈ H. Hence, g1 = g2h2h−1 y ∈ g1H, it follows that y = g1h3 = g2h2h−1 1 ∈ g2H. Then for any 1 h3 ∈ g2H for some h3 ∈ H. Therefore, g1H ⊆ g2H. Similarly, g2H ⊆ g1H, so g1H = g2H. The preceding arguments imply that if g1, g2 ∈ G, then either g1H = g2H, or g1H and g2H are disjoint. Hence, G is the union of pairwise disjoint left cosets of H in G. c 1999 by CRC Press LLC Example 1.5 Consider the subgroup An of Sn. If α is an odd permutation in Sn, then αAn and An are disjoint. If β is any other odd permutation in Sn, then β−1α will be even. Therefore, β−1α ∈ An, and αAn = βAn. Hence, there are two left cosets of An in Sn, one consisting of the even permutations in Sn, and the other consisting of the odd permutations. For a finite group G with subgroup H, the following theorem is a fundamental algebraic result regarding the number of left cosets of H in G. This theorem is called Lagrange’s Theorem. Theorem 1.4 Let G be a group of order n with subgroup H of order k, and suppose there are t distinct left cosets of H in G. Then n = kt. Proof. Each of the t distinct left cosets of H in G contains k elements. Since G is the union of these left cosets, then n = kt. As a consequence of Lagrange’s Theorem, the order of a subgroup H in a finite group G must divide the order of G. For example, the dihedral group D4 of permutations in Example 1.3 has order 8, which divides |S4| = 24. We began this section by defining the left cosets gH of a subgroup H in a group G. Results analogous to those discussed so far in this section also hold for the sets Hg = {hg | h ∈ H}, called right cosets of H in G. Next, we discuss how cosets can be used to construct new groups from known ones. Suppose H is a subgroup of a group G. Then for x ∈ G, let x−1Hx = {x−1hx | h ∈ H}. If x−1Hx ⊆ H for all x ∈ G, then H is called a normal subgroup of G. As we will show, if H is a normal subgroup of a group G, then the set of left cosets of H i