{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "

\n", "Abstract Algebra: An Interactive Approach, 2e\n", "

\n", "\n", "

\n", "©2015 This notebook is provided with the textbook, "Abstract Algebra: An Interactive Approach, 2nd Ed." by William Paulsen. Users of this notebook are encouraged to buy the textbook.\n", "

\n", "\n", "\n", "\n", "

\n", "Chapter 6
\n", "Building Larger Groups from Smaller Groups\n", "

\n", "\n", "\n", "

Initialization: This cell MUST be evaluated first:

" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "%display latex\n", "try:\n", " load('absalgtext.sage')\n", "except IOError:\n", " load('/media/sf_sage/absalgtext.sage')" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The Direct Product
\r\n", "The Fundemental Theorem of Finite Abelian Groups
\r\n", "Automorphisms
\r\n", "Semi-Direct Products
\r\n", "Sage Interactive Problems
\r\n", "\r\n", "\r\n", "

The Direct Product

\r\n", "\r\n", "
\r\n", "In this chapter, we will focus on forming larger groups using the smaller groups previously studied as building blocks. In this way, many important groups can be \r\n", "constructed. In fact, we will be able to construct all finite abelian groups using only the groups that we have already studied.

\r\n", " \r\n", "The first step in building larger groups is to understand how two groups can be combined. Let H and K be two groups, and let G be the set of \r\n", "all ordered pairs (h, k) such that h ∈ H and k ∈ K.

\r\n", "\r\n", "We need to describe how to multiply two ordered pairs together. If (h1, k1) and (h2, k2) \r\n", "are two ordered pairs in G, the product could be defined in the natural way:\r\n", "

(h1, k1)·(h2, k2) = \r\n", "(h1·h2, k1·k2).

\r\n", "It is clear that the associate law would hold. If e1 is the identity element for H and e2 the identity element for \r\n", "K, then (e1, e2) would be the identity element of G.

\r\n", "\r\n", "Finally we can define the inverse of an ordered pair (h, k) to be (h-1, k-1). This is so\r\n", "

(h, k)·(h-1, k-1) = \r\n", "(h-1, k-1)·(h, k) = (e1, e2).

\r\n", "Since the four properties of groups hold for the set G of ordered pairs (h, k), G forms a group.

\r\n", "\r\n", "DEFINITION 6.1
\r\n", "Given two groups H and K, the direct product of H and K, denoted H × K, is the group of ordered pairs \r\n", "(h, k) such that h ∈ H and k ∈ K, with multiplication defined by\r\n", "

(h1, k1)·(h2, k2) = \r\n", "(h1·h2, k1·k2).

\r\n", "
\r\n", "\r\n", "EXAMPLE:
\r\n", "Let H = Z4, and K = Z2. Consider the direct product \r\n", "G = Z4 × Z2. Since Z4 consists of the elements {0,1,2,3} and Z2 consists \r\n", "of {0, 1}, the set of all ordered pairs (h, k) with h in Z4 and k in Z2 is \r\n", "

{(0,0), (0,1), (1,0), (1,1), (2,0), (2,1), (3,0), (3,1)}.

\r\n", "Thus, we will have a group of order 8. Multiplication is performed component-wise in the two groups. In order to define this group in Sage, we first define \r\n", "the groups Z4 and Z2.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z4 = ZGroup(4)\r\n", "Z2 = ZGroup(2)\r\n", "G = DirectProduct(Z4, Z2); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can now look at the Cayley table.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Recall that in Chapter 4, we found that there were only 5 non-isomorphic groups of order 8: Z8, Z15*, \r\n", "Z24*, D4, and Q. Hence, this group must be isomorphic to one of these groups. Notice that this group is\r\n", "commutative, so it is neither Q nor D4. There is an element of order 4, namely (1,0), but there are no elements of order 8. Hence this group \r\n", "cannot be either Z8 nor Z24*. Since Z15* is the only remaining possibility, this group \r\n", "must be isomorphic to Z15*.
\r\n", "
\r\n", "\r\n", "EXPERIMENT:
\r\n", "Compare the group Z4 × Z2 given by the table
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "with the table for Z15*, generated by the commands
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "M = ZStar(15); M" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable([M[0], M[1], M[2], M[3], M[4], M[5], M[6], M[7]])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Can you, by rearranging the elements in the last MultTable command, get the color pattern of this table to resemble the pattern for \r\n", "Z4 × Z2?

\r\n", " \r\n", "Hint: Which element of Z15* corresponds to (2,0)? What are the other elements of order 2?

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "In this example, we saw that the direct product of two commutative groups turned out to be commutative. This is, in fact, what generally happens.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 6.1
\r\n", "Let H and K be two groups. Then H × K is commutative if, and only if, both H and K \r\n", "are commutative.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "It is easy to find the number of elements in a direct product. If H has order n, and K has order m, then the number of ordered pairs \r\n", "(h, k) would be n·m.

\r\n", " \r\n", "We can generalize the direct product to a set of more than two groups. Let\r\n", "

G1, G2, G3, …, Gn

\r\n", "be a collection of n groups. Then we define\r\n", "

G1 × G2 × G3 × ··· × \r\n", "Gn

\r\n", "to be the set of ordered n-tuples (g1, g2, g3, …, gn) with \r\n", "multiplication defined by\r\n", "

(g1, g2, …, gn)·(h1, h2, \r\n", "…, hn) = (g1·h1, g2·h2, …, \r\n", "gn·hn).

\r\n", "\r\n", "
\r\n", "The direct product of more than two groups can also be defined by taking the direct product of direct products. That is, given three groups G, H, and \r\n", "K, we can define\r\n", "

(G × H) × K and G × (H × K)

\r\n", "using only the definition for the direct product of two groups. But it is trivial to see that the mappings\r\n", "

ƒ: (G × H) × K → G × H × K
\r\n", "ϕ : G × (H × K) → G × H × K

\r\n", "given by\r\n", "

ƒ(((g, h), k)) = (g, h, k) and \r\n", "ϕ((g, (h, k))) = (g, h, k)

\r\n", "are both surjective isomorphisms. Thus, \r\n", "

(G × H) × K ≈ G × H × K ≈ G × \r\n", "(H × K).

\r\n", "\r\n", "
\r\n", "It also should be noted that we have the natural mapping\r\n", "

ϕ : H × K → K × H

\r\n", " given by \r\n", "

ϕ((h, k)) = (k, h).

\r\n", "This is clearly one-to one and onto, and is a homomorphism. Thus,\r\n", "

H × K ≈ K × H.

\r\n", "This shows that the direct product between groups is a commutative operation, as well as associative. This suggests that some groups may be able to be expressed as a \r\n", "direct product of two or more smaller groups. If this is the case, then the order in which the smaller groups are combined would be irrelevant.

\r\n", "\r\n", "DEFINITION 6.2
\r\n", "Let G be a group. We say that G has a decomposition if\r\n", "

G ≈ H × K,

\r\n", "where neither H nor K is the trivial group.

\r\n", "\r\n", "For example, we saw above that Z15* had a decomposition, namely Z4 × Z2.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Does the group S3 have a decomposition into a direct product? Why or why not?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We would like to find a way of testing whether a general group can be decomposed into smaller groups. In the case of S3, we could use the fact that \r\n", "all smaller groups are abelian, along with Proposition 6.1 to show that S3 cannot have a decomposition. But for other groups, the\r\n", "problem is more difficult. The following theorem gives us a way to determine whether a given group has a decomposition.\r\n", "\r\n", "

\r\n", "\r\n", "THEOREM 6.1:The Direct Product Theorem
\r\n", "Let G be a group with identity e, and let H and K be two subgroups of G. Suppose the following two statements are true:\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
1)  H ∩ K = {e}.
2)  h·k = k·h for all h ∈ H and k ∈ K.
\r\n", "
\r\n", "Then H · K ≈ H × K.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "We can use this theorem to find the direct product of two groups in Sage.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Generate the direct product S3 × Z8* in Sage.

\r\n", "\r\n", "We first must define the two groups in Sage using the same identity and different letters for the generators. This way, the identity will be the \r\n", "only element in common between the two groups.

\r\n", " \r\n", "Let us define S3 in Sage:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\",\"b\")\r\n", "Define(a^3, e)\r\n", "Define(b^2, e)\r\n", "Define(b*a, a^2*b)\r\n", "H = Group(a, b); H" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Now let us define Z8*, using c and d for the two generators.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "AddGroupVar(\"c\",\"d\")\r\n", "Define(c^2, e)\r\n", "Define(d^2, e)\r\n", "Define(d*c, c*d)\r\n", "H = Group(a, b)\r\n", "K = Group(c, d); K" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Of course we did not use the InitGroup command before defining the second group because we want to define a single group involving all four \r\n", "generators. By using e as the identity for both groups, we have that the intersection of H and K is
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Intersection(H, K)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "so the first condition of the direct product theorem is satisfied.

\r\n", "\r\n", "In order for the second condition of the direct product theorem to be satisfied, every element of H must commute with every element of K. This will be \r\n", "true as long as all of the generators of H commute with all of the generators of K. Since there are 2 generators of H and 2 \r\n", "of K, we can tell Sage that the generators commute using 2·2 = 4 definitions:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(c*a, a*c)\r\n", "Define(c*b, b*c)\r\n", "Define(d*a, a*d)\r\n", "Define(d*b, b*d)\r\n", "H = Group(a, b); H" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "K = Group(c, d); K" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "According to the direct product theorem H·K is now the same as H × K. Here, then, is \r\n", "the direct product:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "H * K" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Alternatively, we could find the smallest group that contains all of the generators:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = Group(a, b, c, d); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can check that the order of this direct product is
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "len(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "as expected, since S3 is of order 6, and Z8* is of order 4. The multiplication table of this new group is given as
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We saw two other groups of order 24, namely S4 and the octahedronal group. Yet these turned out to be isomorphic. Is this new group of order 24 \r\n", "possibly the same group?

\r\n", "\r\n", "Recall that the main tool we used for finding the isomorphism between the octahedronal group and S4 was determining the orders of the elements in \r\n", "the groups. We defined S4 to be:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S4 = Group(P(2,1), P(2,3,1), P(2,3,4,1)); S4" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "To determine how many elements are of order 2, we can use the RootCount function
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RootCount(S4, 2)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "and see that there are 10 solutions to x2 = e, with one being the identity, so there are 9 elements of order 2. Now let us try this with G = S3 × Z8*:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RootCount(G, 2)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So there are 15 elements of G which are of order 2, as opposed to 9 elements in S4. Hence, these two groups are not isomorphic.

\r\n", "\r\n", "\r\n", "This example shows it would be helpful to know the number of elements of order n of the direct product H×K. Then we could determine \r\n", "whether or not two groups expressed as direct products were isomorphic.

\r\n", "\r\n", "Recall in §2.3 we denoted the number of solutions to xn = e by Rn(G). In particular, \r\n", "if G is cyclic, Rn(G) = gcd(|G|, n). It is also rather easy to calculate Rn(G) for \r\n", "direct products.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 6.2
\r\n", "Let H and K be finite groups, and let n be a positive integer. Then\r\n", "

Rn(H × K) = Rn(H)·Rn(K).

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "Let us use this proposition on the example S3 × Z8*. The number of elements of this group solve \r\n", "x2 = e is the product of the number of elements solving the equation in S3 and the number of such elements in \r\n", "Z8*. Note that four of the six elements of S3 satisfy x2 = e, while all four elements \r\n", "of Z8* satisfy the equation. Thus, there are 4·4 = 16 elements of the product \r\n", "S3 × Z8* whose square is the identity. One of these is the identity element, but the other 15 elements are of \r\n", "order 2. Thus, we can find the number of elements of a direct product of given order without having to use Sage.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Use Proposition 6.2 to predict the number of elements of S3 × Z8* which are of order 3 and of order 6. Then \r\n", "use Sage to verify your predictions.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We will end this section by showing another way to test whether a group is a direct product of two of its subgroups.\r\n", "\r\n", "

\r\n", "\r\n", "COROLLARY 6.1
\r\n", "Let G be a group with identity e, and let H and K be two normal subgroups of G. Then \r\n", "

if H ∩ K = {e}, then H·K ≈ H × K.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "This corollary is sometimes more useful than the direct product theorem, even though for abelian groups the two are equivalent, since all subgroups of abelian groups \r\n", "are normal. In the next section we will continue to study the decomposition of abelian groups, and find that all finite abelian groups can be decomposed uniquely \r\n", "into a certain form.

\r\n", "\r\n", "\r\n", "

Fundamental Theorem of Finite Abelian Groups

\r\n", "\r\n", "
\r\n", "In the last section we promised that we will be able to construct any finite abelian group using as building blocks the groups that we have already learned. \r\n", "In this section, we will show how that can be done by considering the direct products of the cyclic groups Zn. We will even be able to find the \r\n", "number of abelian groups of a given order. Let us begin with a simple example.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Consider the group Z6 = {0, 1, 2, 3, 4, 5}. Can we express this as the direct product of two smaller groups?

\r\n", "\r\n", "Note that for abelian groups, the second condition of the direct product theorem is automatically satisfied, so we merely have to find two subgroups of \r\n", "Z6 whose intersection is just the identity {0}, and whose product gives us the whole group. With a group this small, it is easy to find \r\n", "all of the subgroups:\r\n", "

{0},  {0, 3},  {0, 2, 4},  and  {0, 1, 2, 3, 4, 5}.

\r\n", "Thus, the only two candidates are the subgroups \r\n", "

H = {0, 3} ≈ Z2 and K = {0, 2, 4} ≈ Z3.

\r\n", "\r\n", "\r\n", "
\r\n", "Since the intersection of these two subgroups is the identity, we have by the direct product theorem that H·K ≈ H × K.\r\n", "Since H × K is of order 6, we have that H · K is of order 6, and hence is Z6. Therefore,\r\n", "

Z6 ≈ Z2 × Z3.

\r\n", "\r\n", "\r\n", "
\r\n", " Let us check this using Sage: Z2 and Z3 are easy to define.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z2 = ZGroup(2); Z2" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z3 = ZGroup(3); Z3" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can form the direct product
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = DirectProduct(Z2, Z3); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Here is the multiplication table:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We want to see if this group is isomorphic to Z6. Thus, we want to find an element of order 6. By computing
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RootCount(G, 2)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RootCount(G, 3)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we see that there is only one element of order 2, and 2 elements of order 3, so there must be two elements of order 6. In fact, it is not hard to see that \r\n", "(1, 1) and (1, 2) are these elements. From this information we can create an isomorphism. We let F\r\n", "be the homomorphism between Z6 and Z2 × Z3.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z6 = ZGroup(6); Z6" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F = Homomorph(Z6, G)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoDef(F, Z6[1], G[5])" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FinishHomo(F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So this in a homomorphism. The image is
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Image(F, Z6)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "so F is surjective. The kernel is
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Kernel(F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So F is also injective. Therefore, we have found the isomorphism from Z6 to Z2 × Z3.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "GraphHomo(F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "

\r\n", "EXPERIMENT:
\r\n", "Using the same technique as above, see if you can find a decomposition of Z10 into a direct product of smaller groups. Define the homomorphism \r\n", "between Z10 and the direct product, and show that the homomorphism is surjective and injective.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", " By observing the patterns in the decomposition of Z6 and Z10, let us see if we can find a decomposition of any commutative \r\n", " group.

\r\n", " \r\n", "Observe the groups H = {0, 3} and K = {0, 2, 4} in the example of the decomposition of Z6. Notice that H consists of all \r\n", "of the elements of Z6 such that h2 = 0. Also, K consists of all the elements such \r\n", "that k3 = 0. \r\n", "The fact that these two subgroups have only the identity in common is not a coincidence, as the next lemma shows:\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 6.1
\r\n", "Let G be an abelian group of order m n, where m and n are coprime. Then\r\n", "

H = {h ∈ G | hm = e}

\r\n", "and\r\n", "

K = {k ∈ G | kn = e}

\r\n", "are both subgroups of G, and G ≈ H × K.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "This lemma tells us that if an abelian group has an order that is a product of two coprime numbers, this group can be written as a direct product of two groups. \r\n", "Unfortunately, the lemma does not tell us that neither H nor K are trivial groups. As a result, we still have to ask whether this is a \r\n", "decomposition.

\r\n", "\r\n", "Here is an example to illustrate the possible problem that could occur. Suppose we know G is an abelian group of order 24. Since 24 = 8·3, we could \r\n", "let m = 8, and n = 3 in Lemma 6.1. Then H would consist of all elements of order 1, 2, 4, or 8, while K would consist of the elements \r\n", "of order 1 or 3. Then we would have\r\n", "

G ≈ H × K.

\r\n", "\r\n", "
\r\n", "But what if G had no elements of order 3? Then K would be just the identity element, and H would have to be all of G. Lemma 6.1 would \r\n", "hold, but since H and K are not proper subgroups, this would not give a decomposition of G. The next lemma will show that, in fact, \r\n", "G must have an element of order 3.\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 6.2
\r\n", "If G is a finite abelian group and p is a prime that divides the order of G, then G has an element of order p.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "This lemma is known as Cauchy's theorem for abelian groups. In fact we will see that Cauchy's theorem is true for all groups, not just abelian groups. However, the result for abelian groups is good enough for us to \r\n", "proceed.

\r\n", " \r\n", "EXPERIMENT:
\r\n", "Since the Euler totient function of 35 is
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "EulerPhi(35)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "the group
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = ZStar(35); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "is an abelian group with 24 elements. Lemma 6.2 then tells us that there are elements of order 2 and of order 3. \r\n", "We can find the set of elements H such that h3 = 1, with the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "[x^3 for x in G]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "and the set of elements K such that k8 = 1 with
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "[x^8 for x in G]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "and comparing this list with G.\r\n", "Show that H·K = Z35*, and hence Z35* has the decomposition \r\n", "H × K.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This experiment demonstrates how Lemma 6.2 guarantees that the subgroups H and K generated by Lemma 6.1 must be proper subgroups. Notice that in \r\n", "this experiment, H contained 3 elements while K contained 8 elements. There seems to be a pattern: the number of elements of G satisfying\r\n", "

x(pⁿ) = e,

\r\n", "is pn whenever p divides the order of G exactly n times. This apparent pattern can be shown to exist for all abelian groups. \r\n", "We thus have the following lemma:\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 6.3
\r\n", "Let G be an abelian group of order pn·k where p is prime, k is not divisible by p, and \r\n", "n > 0. Then there are subgroups P and K of G such that\r\n", "

G ≈ P × K,

\r\n", "where |P| = pn and |K| = k.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "Lemma 6.3 is a tremendous help in finding the structure of abelian groups. For example, suppose we have an abelian group G of order 24. \r\n", "Since 24 = 23·3, Lemma 6.3 states that G is isomorphic to a direct product of a group of order 8 and a group of order 3. Since \r\n", "Z3 is the only group of order 3, and there are 3 abelian groups of order 8, namely \r\n", "

Z8, Z15*, and Z24*,

\r\n", "we have that G must be isomorphic to one of the three groups \r\n", "

Z8 × Z3, Z15* × Z3, \r\n", "and Z24* × Z3,

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Since Z35* is an abelian group with 24 elements, this must be isomorphic to one of the three groups mentioned above. \r\n", "Which of the three is it?
\r\n", "(Hint: first use Sage to find Z35*, and to determine the number of elements of order 2. Then use Proposition 6.2 to find the \r\n", "number of elements of order 2 for the three groups listed above.)
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We have seen that if we can find all abelian groups of order pn for p a prime number, then we will be able to find all finite abelian groups. \r\n", "The next lemma is the key to finding all abelian groups whose order is a power of a prime.\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 6.4
\r\n", "Suppose P is an abelian group of order pn, where p is a prime. Let x be an element in P that has the maximal order \r\n", "of all of the elements of P. Then\r\n", "

P ≈ X × T,

\r\n", "where X is the cyclic group generated by x, and T is a subgroup of P.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "To give an illustration of how Lemma 6.4 is applied, consider the groups of order 8. Lemma 6.4 states that these can be decomposed into cyclic groups. \r\n", "We have already seen that Z15* was isomorphic to Z4 × Z2, and Z8 is already \r\n", "a cyclic group. Let's use Lemma 6.4 on the group Z24*.

\r\n", "\r\n", "All non-identity elements of Z24* are of order 2, so this is the maximal order. Thus, Lemma 6.4 states that \r\n", "Z24* can be decomposed into Z2 and a group of order 4. Since \r\n", "Z2 × Z4 is isomorphic to Z15*, the only other choice is \r\n", "Z24* ≈ Z2 × Z8*.

\r\n", "\r\n", "Now we can apply Lemma 6.4 again to Z8*. This is of order 4, and all elements besides the identity are of order 2, so \r\n", "Z8* can be decomposed into Z2 and a group of order 2, which must be Z2. Thus, \r\n", "

Z8* ≈ Z2 × Z2,

\r\n", "and so\r\n", "

Z24* ≈ Z2 × Z2 × Z2.

\r\n", "\r\n", "
\r\n", "It is clear how repeated use of Lemma 6.4 can decompose any abelian group into cyclic groups. But now we want to address the issue as to whether a decomposition is \r\n", "unique. Is it possible for a group to be represented as a direct product of cyclic groups in two different ways?
\r\n", "
\r\n", "\r\n", "In one sence, the answer is yes, for \r\n", "

Z12 × Z2 ≈ Z6 × Z4.

\r\n", "Yet this doesn't give the whole story, since both of these can futher decomposed:\r\n", "

Z12 × Z2 ≈ Z6 × Z4 ≈ \r\n", "Z2 × Z3 × Z4.

\r\n", "So the question that we should ask is whether an abelian group can be decomposed in two different ways into groups which can not be decomposed further, that is, to the point where each factor is a cyclic group whose order is a power of a prime. A way to reword \r\n", "this question is to ask whether two different decompositions are isomorphic.
\r\n", "
\r\n", "\r\n", "The main tool for testing whether two groups are\r\n", "isomorphic is to count elements of a given order. \r\n", "This can be accomplished by computing Rn(G) for various values of n. It \r\n", "is natural to compute Rn(G) for a decomposition of cyclic groups.\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 6.5
\r\n", "Let p be a prime number, and G be the direct product of cyclic groups\r\n", "

G = Z(pₕ¹) × \r\n", "Z(pₕ²) × Z(pₕ³) × ⋯ × \r\n", "Z(pₕⁿ ) × Z ₖ₁ × \r\n", "Z ₖ₂ × ⋯ × \r\n", "Z ₖₘ

\r\n", "where h1, h2, …, hn are positive integers, and k1, k2, …,\r\n", "km are coprime to p. Then if q = px,\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
⎛∑n Min(hi, x)⎞
⎝i=1⎠
Rq(G) = p ,
\r\n", "
\r\n", "where Min(hi , x) denotes the smaller of the two numbers hi and x.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "An example here would help to illustrate the power of Lemma 6.5. Suppose we are given the group\r\n", "

G = Z3 × Z9 × Z9 × Z27.

\r\n", "How many elements are there of order 9? Note that we can rewrite G as \r\n", "

G = Z3¹ × Z3² × Z3² × \r\n", "Z3³.

\r\n", "Thus, h1 = 1, h2 = 2, h3 = 2, and h4 = 3. Since we want the elements of order 9 = 32, we let x = 2. Then\r\n", "

∑ i  Min(hi , \r\n", "x) = 1 + 2 + 2 + 2 = 7,

\r\n", "so R9(G) = 37, meaning there are 2187 solutions to g9 = e. However, not all of these elements will be of order 9, since this count also includes elements of order 3. In order for g to be of order 9, it must \r\n", "satisfy g9 = e and g3 ≠ e. Thus, we will apply the formula \r\n", "again with x = 1 to get\r\n", "

∑ i  Min(hi , \r\n", "x) = 1 + 1 + 1 + 1 = 4.

\r\n", "So R3(G) = 34, and the total number of elements of G of order 9 is 37 − 34 = 2106.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "How many elements of G have order 27? (Use x = 3 instead of x = 2.)
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We are now ready to show that all finite abelian groups can be represented as the direct product of cyclic groups. However, we would like to show at the same time that \r\n", "such a representation is unique. To this end we will use the previous lemma in conjunction with the following.\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 6.6
\r\n", "Let h1, h2, h3, … hn be a set of positive integers, and define \r\n", "ƒ(x) as\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
n
ƒ(x) = ∑Min(hi, x)
i = 1
\r\n", "
\r\n", "where Min(hi, x) denotes the minimum of hi and x. Then the number of times that the integer x appears \r\n", "in the set of integers h1, h2, h3, … hn is given by\r\n", "

2 ƒ(x) − ƒ(x − 1) − ƒ(x + 1).

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "We can now use Lemmas 6.3 through 6.6 to show that not only can a finite abelian group be decomposed into a direct product of cyclic groups, but that it can be \r\n", "decomposed into a standard form in a unique way, much as a positive integer can be uniquely decomposed into a product of prime numbers.\r\n", "\r\n", "

\r\n", "\r\n", "THEOREM 6.2:The Fundamental Theorem of Finite Abelian Groups
\r\n", "A nontrivial finite abelian group is isomorphic to\r\n", "

Z(p₁ₕ¹) × \r\n", "Z(p₂ₕ²) × Z(p₃ₕ³) × \r\n", "⋯ × Z(pₙₕⁿ ),

\r\n", "where p1, p2, p3, … pn are prime numbers (not necessarily distinct). Furthermore, \r\n", "this decomposition is unique up to the rearrangement of the factors.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "From this theorem, we can easily find all non-isomorphic abelian groups of a given order. For example, to find all non-isomorphic abelian groups of order 16, we note that \r\n", "all such groups are direct products of the cyclic groups of orders 2, 4, 8, or 16. We want to find all possible combinations of 2, 4, 8, and 16 which will multiply to \r\n", "give 16. With a little experimenting, we find that there are five such combinations: \r\n", "

2·2·2·2,  2·2·4,  4·4,  2·8,  and 16.

\r\n", "Thus, there are 5 possible abelian groups of order 16:\r\n", "

Z2 × Z2 × Z2 × \r\n", "Z2,  Z2 × Z2 × Z4,  Z4 \r\n", "× Z4,  Z2 × Z8,   and Z16.

\r\n", "Since the fundamental theorem (6.2) also states that the representation is unique, these five groups must be non-isomorphic to each other. Notice that there is a correlation between these five groups, and the five ways we can express the number 4 as a sum of positive integers:\r\n", "

1 + 1 + 1 + 1 = 4
1 + 1 + 2 = 4
2 + 2 = 4
1 + 3 = 4
4 = 4

\r\n", "This leads us to a way of finding the number of non-isomorphic groups of order pm for any m.\r\n", "\r\n", "

\r\n", "\r\n", "COROLLARY 6.2
\r\n", "Let P(m) denote the number of ways in which m can be expressed as a sum of positive integers, without regard to order. Then if p is \r\n", "a prime number, there are exactly P(m) non-isomorphic abelian groups of order pm.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "We call P(m) the number of partitions of m. We can have Sage count the number of partitions for us, using the command \r\n", "PartitionsP(m). Thus, to find the number of partitions of the number 4, we can enter
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "PartitionsP(4)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can even have Sage list all of the paritions for us
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "[i for i in Partitions(4)]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Note that in the last command, we used Partitions instead of PartitionsP.

\r\n", "\r\n", "According to Corollary 6.2, the number of non-isomorphic abelian groups of order 3100 is
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "PartitionsP(100)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We won't ask for the list of all of them here! As we can see, the number of partitions of m grows very rapidly as m gets large. How rapidly? We can make \r\n", "a logarithmic plot of the first 100 values of P(m) with the following command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "list_plot([ln(PartitionsP(m)) for m in range(100)])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This looks like a sideways parabola, indicating that P(m) grows in about the same rate as \r\n", "e√m.

\r\n", "\r\n", "We can now find the number of non-isomorphic abelian groups of any order, as the following corollary shows.\r\n", "\r\n", "

\r\n", "\r\n", "COROLLARY 6.3
\r\n", "Let m > 1 be an integer with prime factorization\r\n", "

\r\n", "p1h¹·p2h²·p3h³ \r\n", "⋯ pnhⁿ

\r\n", "where p1, p2, p3, …, pn are distinct primes. Then the number of non-isomorphic \r\n", "abelian groups of order m is given by\r\n", "

P(h1)·P(h2)·P(h3) ⋯ \r\n", "P(hn).

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "\r\n", "EXAMPLE:
\r\n", "Suppose we want to find the number of non-isomorphic abelian groups of order 180 billion. Since 180,000,000,000 = \r\n", "211·32·510, we have that the number of groups is
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "PartitionsP(11)*PartitionsP(2)*PartitionsP(10)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So there are 4704 abelian groups of order 180 billion.

\r\n", "\r\n", "From these two corollaries, we see that all finite abelian groups have been classified. One of the outstanding problems in group theory is to classify all \r\n", "finite groups. This is as yet an unsolved problem although much progress has been made through the use of computers. In the next two sections we will show some other ways \r\n", "of generating larger groups which have become a key to some of the recent work that has been done in group theory.

\r\n", "\r\n", "\r\n", "

Automorphisms

\r\n", "\r\n", "
\r\n", "We have already studied several examples of homomorphisms and isomorphisms between two groups, but suppose we considered a mapping from a \r\n", "group to itself.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Find an isomorphsm from Z8 onto itself.

\r\n", "\r\n", "We could consider the following mapping:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z8 = ZGroup(8)\r\n", "CircleGraph(Z8, Pow(3))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that this mapping is one-to-one and onto, so in fact we could consider this as a permutation of the numbers 0 through 7, namely (1 3)(2 6)(5 7). However, to\r\n", "make this into a homomorphism in Sage, we have to define a mapping that sends Z8[1] to Z8[3].
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F = Homomorph(Z8, Z8)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "HomoDef(F, Z8[1], Z8[3])" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FinishHomo(F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This shows that we have a homomorphism. Now we can see that F is the same mapping as Pow(3)
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Z8, F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We see that F is a homomorphism from Z8 onto itself. We give such a homomorphism a special name.

\r\n", "\r\n", "DEFINITION 6.3
\r\n", "An automorphism of the group G is a homomorphism from G to G which is one-to-one and onto.

\r\n", "\r\n", "If we study the above automorphism ƒ on Z8, we discover why this works. Recall that the operation of this group is addition modulo \r\n", "8. Hence the mapping x → x3 in Z8 will send each number x to (3 x) mod 8. Therefore,\r\n", "

ƒ(x·y) = ƒ((x + y) mod 8) = \r\n", "(3(x + y) mod 8 = \r\n", "(3x + 3y) mod 8 = ƒ(x)·ƒ(y).

\r\n", "\r\n", "
\r\n", "By observing this pattern, we find another automorphism G of Z8 by letting G send x into x5 = \r\n", "(5 x) mod 8. The graph of \r\n", "G would be given by
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = Homomorph(Z8, Z8)\r\n", "HomoDef(G, Z8[1], Z8[5])\r\n", "FinishHomo(G)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Z8, G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So we have found 2 automorphisms on Z8, one which acts like the permutation P(3,6,1,4,7,2,5) and the other acting like P(5,2,7,4,1,6,3). But we \r\n", "can multiply these permutations together to form a third permutation.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Is the permutation
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "P(3,6,1,4,7,2,5)*P(5,2,7,4,1,6,3)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "represent a homomorphism of Z8? Define H to be the new function sending Z8[1] to Z8[7].
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This experiment suggests that the product of two automorphisms is again an automorphism. We can formally define\r\n", "the product of two automorphisms ƒ(x) and ϕ(x) as \r\n", "(ƒ·ϕ)(x) = ƒ(ϕ(x)). \r\n", "

\r\n", "But there are some other patterns of the automorphisms that we can \r\n", "observe. Because an automorphism ƒ(x) on G is a one-to-one and onto mapping, we can consider the inverse \r\n", "mapping ƒ−1(x). \r\n", "For example, the inverse to the automorphism F is denoted by the permutation
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "P(3,6,1,4,7,2,5)^(-1)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "In this case, the inverse of F is again F, which is an automorphism.

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Are the inverses of G and H again automorphisms? Which automorphisms are they?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Since we seem to be able to multiply two automorphisms together and take inverses, the natural question comes up, which is answered in the next proposition.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 6.3
\r\n", "Given a group G, the set of all automorphisms on G forms a group, denoted Aut(G). In fact, Aut(G) is a subgroup of the group \r\n", "of permutations on the elements of G.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "\r\n", "EXAMPLE:
\r\n", "Find the automorphism group for Z8.

\r\n", "\r\n", "We have two elements already, which we can express in terms of permutations. Let's find \r\n", "the group generated by these two permutations:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "A = Group(P(3,6,1,4,7,2,5),P(5,2,7,4,1,6,3)); A" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So Aut(Z8) has at least four elements. Is this the maximum number of automorphisms? Notice that 1 is of order 8 in Z8, so it must \r\n", "be mapped to an element of order 8, namely 1, 3, 5, or 7. But since 1 is a generator of the group, any automorphism is determined by where the generator is mapped to.\r\n", "Hence, there are at most four automorphisms of Z8. Since we have already found four, we must have found all of them!

\r\n", "\r\n", "Since we have Aut(Z8) is a group of order 4, the natural question is which group is this isomorphic to? Here is a multiplication table for A:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(A)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "From this, we see that all elements of A besides the identity are of order 2. So\r\n", "

Aut(Z8) ≈ Z2 × Z2 ≈ Z8*.

\r\n", "We can use a similar argument to find the automorphism group for any cyclic group.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 6.4\r\n", "

Aut(Zn) ≈ Zn*.

\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "So far, the automorphism group is smaller than the original group, but the goal of this chapter is to form larger groups. Let us\r\n", "consider a non-cyclic group.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Find the set of automorphisms on the group Z8*.

\r\n", "\r\n", "First define this group in Sage, using two generators:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\",\"b\")\r\n", "Define(a^2, e)\r\n", "Define(b^2, e)\r\n", "Define(b*a, a*b)\r\n", "G = Group(a, b); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "A good strategy for finding all of the automorphisms is to first determine an upper bound for the number of automorphisms. \r\n", "Suppose ƒ is an automorphism. Then ƒ(e) = e, but all other elements are of order 2. Hence, any of the other elements \r\n", "might map to each other in any way. For example, ƒ(a) might be a, b, or a·b. \r\n", "Once we know where a is mapped, ƒ(b) might be either of the other two elements. However, once we know \r\n", "ƒ(a) and ƒ(b), then ƒ(a·b) must be \r\n", "ƒ(a)·ƒ(b). Thus, there are at most 3·2 = 6 elements of Aut(Z8*). \r\n", "If we find that there are indeed this many automorphisms, then Aut(Z8*) would be larger than Z8*.

\r\n", "\r\n", "Here would be a possible automorphism:\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
ƒ(e)=e
ƒ(a)=b
ƒ(b)=a
ƒ(a·b)=a·b
\r\n", "We can define this as a homomorphism is Sage.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F = Homomorph(G, G)\r\n", "HomoDef(F, a, b)\r\n", "HomoDef(F, b, a)\r\n", "FinishHomo(F)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(G, F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Let us represent this automorphism as a permutation on the elements of Z8*. There is not a natural numbering of the elements, so it would \r\n", "be difficult to use the P[ ] notation. However, we still can use the notation of cycles, and say that ƒ is the \r\n", "2-cycle (a b). Note that we are using the cycle notation with elements instead of numbers. We are allowed to do this in Sage, and so \r\n", "we can enter this function as follows:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "f = C(a, b); f" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "In fact, we can still use the CircleGraph command to graph this function:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(G, f)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Let us consider another automorphism having ƒ(a) = a, but having ƒ(b) = a·b.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "H = Homomorph(G, G)\r\n", "HomoDef(H, a, a)\r\n", "HomoDef(H, b, a*b)\r\n", "FinishHomo(H)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(G, H)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We see from the circle graph that this is indeed an automorphism, and can be represented by the cycle (b a·b).
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "h = C(b, a*b)\r\n", "CircleGraph(G, h)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The advantage of using cycles instead of functions is that we can now form the group generated by these two automorphisms
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "A = Group(f, h); A" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This gives us six elements, which is the maximum number of automorphisms we can have. Thus, A is Aut(Z8*). Therefore, we have \r\n", "found that the automorphism group is sometimes larger than the original group.

\r\n", " \r\n", "Which group is this? It is not hard to recognize A as the permutation group on the elements a, b, and a·b. Thus, \r\n", "Aut(Z8*) is isomorphic to S3.

\r\n", "\r\n", "For non-commutative groups, there is a quick way to find many of the automorphisms.\r\n", "Let G be a non-commutative group, and let x be any element in G. The mapping fx : G → G defined by\r\n", "

fx(y) = x·y·x-1

\r\n", "will always be an automorphism, for\r\n", "

fx(y·z) = x·y·z·x-1 =\r\n", " (x·y·x-1)·(x·z·x-1) = fx(y)·fx(z).

\r\n", "So fx(y) is a homomorphism. Since the inverse homomorphism can easily be found,\r\n", "

y ∈ fx-1(v) ⟺ x·y·x-1 = \r\n", "v ⟺ y = x-1·v·x ⟺ y = fx₋₁(v),

\r\n", "we have that fx(y) is one-to-one and onto, therefore fx(y) is an automorphism.

\r\n", "\r\n", "DEFINITION 6.4
\r\n", "An automorphism ϕ(y) of a group G is called an inner automorphism if there is an element x in G such that \r\n", "

ϕ(y) = x·y·x-1 for all  y ∈ G.

\r\n", "The set of inner automorphisms of G is denoted Inn(G).

\r\n", "\r\n", "EXAMPLE:
\r\n", "Find the inner automorphisms of the quaternion group Q.

\r\n", "\r\n", "First, we load Q into Sage:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Q = InitQuaternions(); Q" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Let us begin by determining an upper bound for the number of automorphisms. \r\n", "Suppose ƒ is an automorphism of Q. Then ƒ(1) = 1, as always, but ƒ(−1) must be −1, since −1 is the \r\n", "only element of Q of order 2. All of the other elements are of order 4, so ƒ(i) could be any one of the remaining six elements. Once \r\n", "ƒ(i) is determined, though, ƒ(−i) = ƒ(i)3, so this will be determined. \r\n", "Then ƒ(j) could be any one of the remaining four elements. Since i and j generate Q, once \r\n", "ƒ(i) and ƒ(j) is determined, ƒ will be determined for all of Q. Thus, there is a maximum \r\n", "of 6·4 = 24 possible automorphisms.

\r\n", "\r\n", "Let us try to find some inner automorphisms on Q. If we choose x = i, then ƒi(y) is the \r\n", "following mapping:\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
ƒi(1)=i·1·(−i)=1
ƒi(i)=i·i·(−i)=i
ƒi(j)=i·j·(−i)=−j
ƒi(−1)=i·(−1)·(−i)=−1
ƒi(−i)=i·(−i)·(−i)=−i
ƒi(k)=i·k·(−i)=−k
ƒi(−j)=i·(−j)·(−i)=j
ƒi(−k)=i·(−k)·(−i)=k
\r\n", "
\r\n", "So ƒi exchanges j and −j, and exchanges k and −k, leaving all other elements alone. \r\n", "Thus, we can express this automorphism as
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F = C(j, -j)*C(k, -k); F" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Here is the graph of this automorphism:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Q, F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "From the above descussion. we know that this is a homomorphism. If we use x = j instead of x = i, we get a different automorphism:\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
ƒj(1)=j·1·(−j)=1
ƒj(i)=j·i·(−j)=−i
ƒj(j)=j·j·(−j)=j
ƒj(−1)=j·(−1)·(−j)=−1
ƒj(−i)=j·(−i)·(−j)=i
ƒj(k)=j·k·(−j)=−k
ƒj(−j)=j·(−j)·(−j)=−j
ƒj(−k)=j·(−k)·(−j)=k
\r\n", "
\r\n", "We can represent this automorphism in Sage by
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = C(i, -i)*C(k, -k); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Here is the graph:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Q, G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Since F and G are both automorphisms, we can find the group generated by these two:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(F, G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Therefore, we have found 4 automorphisms on Q. But is this all of the automorphisms?

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Find the automorphism ƒx(y) with x = k. Find the corresponding permutation on Q, and have Sage draw \r\n", "a circle graph of this automorphism. Is this automorphism one that we have seen before?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "If we try the above procedure with x equaling any of the eight elements of Q, we will always get one of the four automorphisms. \r\n", "Hence, we have found all of the inner automorphisms of Q, which we can express in terms of cycles as\r\n", "

{( ), (i, −i)(j, −j), (j, −j)(k, −k), (i, −i)(k, −k)}.

\r\n", "\r\n", "EXAMPLE:\r\n", "Find all of the automorphisms of Q.

\r\n", "\r\n", "We found 4 inner automorphisms, but there certainly could \r\n", "be more. Suppose ƒ(i) = i, and ƒ(j) = k? Since i, j, and k are all of order 4, \r\n", "it is conceivable that this would produce an automorphism. This time, we will use Sage's Homomorph function to define the mapping.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "X = Homomorph(Q, Q)\r\n", "HomoDef(X, i, i)\r\n", "HomoDef(X, j, k)\r\n", "FinishHomo(X)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So X is a homomorphism, but is X an automorphism? By finding
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Image(X, Q)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we see that X is onto, and by finding
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Kernel(X)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we see that X is one-to-one. Therefore, X is an automorphism. By looking at the circle graph:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Q, X)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we see that the automorphism can be represented by the 4-cycle
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "H = C(j, k, -j, -k); H" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Let us add this to our group of automorphisms:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Group(F, G, H)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "len(_)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So far, we have 8 automorphisms. Could there be any others?

\r\n", "\r\n", "Notice that all 8 of the automorphisms that we have come up with so far send i either to i or −i. What if we sent i to, say, \r\n", "k? We could let j be sent to j for simplicity. Let's try it.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Y = Homomorph(Q, Q)\r\n", "HomoDef(Y, i, k)\r\n", "HomoDef(Y, j, j)\r\n", "FinishHomo(Y)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can check that this is one-to-one and onto by looking at the circle graph.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Q, Y)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So Y is an automorphism of Q. It can be represented by the 4-cycle
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "J = C(i, k, -i, -k); J" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So here is an updated list of automorphisms:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "A = Group(F,G,H,J); A" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This is a long list. Let's see how many automorphisms we have.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "len(A)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So we have 24 automorphisms of Q. Since we began by observing that there could be at most 24 automorphisms, we finally must have them all. Is this group \r\n", "isomorphic to one of the groups of order 24 that we have studied before?

\r\n", "\r\n", "Rather than proving an isomorphism directly as we have done in the past, in this case there is a geometrical correlation between this automorphism group and the \r\n", "octahedronal group. Note that any automorphism of Q must fix 1 and −1, but the other six elements can go to any other of the six elements. Suppose we were \r\n", "to label the six vertices of the octahedron with the six remaining elements of Q, as follows:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "ShowOctahedronWithQuaternions()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The vertex in the back is labeled −j. Now notice that each rotation of the octahedron gives an automorphism of Q, and vice versa. For \r\n", "example, rotating the red face 120° clockwise corresponds to the automorphism\r\n", "

(i j k)(−i −j −k).

\r\n", "So the automorphism group is isomorphic to the octahedronal group, which we saw was isomorphic to S4. Thus, Aut(Q) is isomorphic to \r\n", "S4.

\r\n", "\r\n", "Although the inner automorphisms did not produce the full automorphism group, this set of inner automorphisms turns out to be a very important subgroup of the automorphism \r\n", "group. Notice that we found that the product of the two inner automorphism was an inner automorphism. This suggests that Inn(G) is a subgroup of Aut(G). \r\n", "In fact we can even say more!\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 6.5
\r\n", "Let G be a group. Then Inn(G) is a normal subgroup of Aut(G).

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "We found two inner-automorphisms of Q, namely F and G. We found one more inner automorphism by considering
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Inn = Group(F, G); Inn" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "If we examine the automorphism ƒx(y) = x·y·x-1 for different elements x, \r\n", "we will find that we will always get one of these four automorphisms. Thus, this group is the group of inner automorphisms on Q. Here is the multiplication \r\n", "table:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(Inn)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Since the square of every element is the identity, we recognize Inn(Q) as isomorphic to Z8*.

\r\n", "\r\n", "Because the inner automorphism group is always a normal subgroup, we could consider the quotient group.

\r\n", "\r\n", "DEFINITION 6.5
\r\n", "We define the outer automorphism group to be the group \r\n", "

Out(G)= Aut(G)/Inn(G).

\r\n", "\r\n", "For example, the outer automorphism group of Q is given by
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z = LftCoset(A, Inn); Z" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This gives a group of order 6.

\r\n", "\r\n", "As complicated as the elements of Z are, we can form a multiplication table.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(Z)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Since this group is non-abelian, we see that the group is isomorphic to S3.

\r\n", "\r\n", "If G is an abelian group, then the only inner automorphism is the identity automorphism. Thus, for abelian groups, \r\n", "

Inn(G) ≈ {e} and Out(G) ≈ Aut(G).

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Load S3 into Sage with the following commands:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^2, e)\r\n", "Define(b^3, e)\r\n", "Define(b*a, a*b^2)\r\n", "G = Group(a, b); G" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Note that for any automorphism, the element a must map to one of the three elements of order 2, and b must map to one of the two elements of order 3. \r\n", "Since the elements a and b generate the group, there can be at most six automorphisms. By finding a few of the inner automorphisms, and having \r\n", "Sage create a multiplication table, identify Inn(S3). What is Aut(S3)?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Let us look at one last example where the automorphism group turns out to be much larger than the original group.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Find the automorphism group of Z24*.

\r\n", "\r\n", "The following loads the group into Sage:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\", \"c\")\r\n", "Define(a^2, e)\r\n", "Define(b^2, e)\r\n", "Define(c^2, e)\r\n", "Define(b*a, a*b)\r\n", "Define(c*a, a*c)\r\n", "Define(c*b, b*c)\r\n", "Y = ListGroup(); Y" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Once again, we will begin by determining an upper bound for the number of automorphisms. \r\n", "Suppose ϕ(x) is an automorphism of Z24*. Naturally, ϕ(e) = e, but the other 7 \r\n", "elements are of order 2. Thus, ϕ(a) could be any of the 7 remaining elements. Now ϕ(a) and ϕ(b) \r\n", "are unrelated so ϕ(b) could be any of the 6 elements besides e and ϕ(a). We then would have \r\n", "ϕ(a·b) = ϕ(a)·ϕ(b), so four elements will be accouted for. But \r\n", "ϕ(c) could be any of the 4 elements left over. Once ϕ(a), ϕ(b), and ϕ(c) are \r\n", "known, the entire automorphism is determined. Therefore, there are at most 7·6·4 = 168 possible automorphisms.

\r\n", "\r\n", "Now let us try to find an automorphism. Since a, b, and c are interchangeable in the definition of the group, we could consider a mapping \r\n", "ƒ that maps a to b, b to c, and c back to a.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "F = Homomorph(Y, Y)\r\n", "HomoDef(F, a, b)\r\n", "HomoDef(F, b, c)\r\n", "HomoDef(F, c, a)\r\n", "FinishHomo(F)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Y, F)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We see that this produces an automorphism, and that a·b maps to \r\n", "b·c, which maps to c·a, which maps back to a·b. The \r\n", "element a·b·c is fixed by this mapping. Thus, this mapping would be the permutation
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "f = C(a, b, c)*C(a*b, b*c, a*c); f" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Can we find other automorphisms? Our success should indicate that there are many of them! Suppose we consider ϕ(a) = a, \r\n", "ϕ(c) = c, but let ϕ(b) = a·b?
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = Homomorph(Y, Y)\r\n", "HomoDef(G, a, a)\r\n", "HomoDef(G, b, a*b)\r\n", "HomoDef(G, c, c)\r\n", "FinishHomo(G)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Y, G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "This automorphism works, and would be represented by the permutation
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "g = C(b, a*b)* C(b*c, a*b*c); g" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can now use Sage to find other automorphisms generated by these two.

\r\n", "\r\n", "Because of the large number of possible elements in Aut(Z24*), we will be better off if we number the elements in the \r\n", "group Z24*. This will allow us to use the P[ ] notation. (Sage works much faster using \r\n", "the P[ ] notation than using cycles.) Since all automorphisms fix the element e this element need not be numbered. The other 7 elements can \r\n", "be numbered as follows, using the same order as the elements appear in ListGroup:\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
1) a
2) b
3) a·b
4) c
5) a·c
6) b·c
7) a·b·c
\r\n", "
\r\n", "Let us convert f and g to permutations using the numbering scheme we gave to the elements.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "f = CycleToPerm(C(1,2,4)*C(3,6,5)); f" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "g = CycleToPerm(C(2,3)*C(6,7)); g" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "That is, f maps element 1 (a) to element 2 (b), which is mapped to element 4 (c), etc.

Likewise, \r\n", "g exchanges the 2nd and 3rd elements, and exchanges the 6th and 7th elements of Z24*. The circle graphs will still looks \r\n", "the same:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph([0,1,2,3,4,5,6,7], f)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph([0,1,2,3,4,5,6,7], g)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Since f and g both represent automorphisms of Z24*, we can find other automorphisms be considering the \r\n", "group generated by f and g.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "A = Group(f, g); A" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Sage came up with quite a few automorphisms. Let's see how many we have.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "len(A)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Therefore, we have found 168 different automorphisms of Z24*. We saw that this was the maximum number of automorphisms we could have, so \r\n", "we must have all of them. However, this is a difficult way to see the elements of the group! It is a challenge just to see if a given permutation is somewhere in this \r\n", "list. Is there an easier way of viewing this group?

\r\n", "\r\n", "One way to tidy up this long list is to convert the permutations to numbers. Recall that in Chapter 5 we ordered all of the permutations, thereby converting every \r\n", "permutation to a number. Setting DisplayPermInt to true causes the permutations to be displayed as integers.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "DisplayPermInt = true" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "A" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This looks much more manageable. By displaying the permutations f and g,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "f" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "g" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "we see that f and g represent the 187th and the 723rd permutations.

\r\n", "\r\n", "This is the largest group with which we will work using Sage. In fact we will discover in the next chapter that this group has some very special \r\n", "properties. We will explore this group in detail using Sage in the next chapter.

\r\n", "\r\n", "We have now seen several examples where the group of automorphisms is larger than the original group. But this group of automorphisms can also be used as a tool for \r\n", "connecting two groups to form an even larger group, in much the same way that two groups formed the direct product. The next section will explore this methodology.

\r\n", "\r\n", "\r\n", "

Semi-Direct Products

\r\n", "\r\n", "
\r\n", "So far in this chapter we have seen how we can combine two groups H and K together to form a larger group H × K using the direct\r\n", "product. We then saw that H × K had isomorphic copies of H and K as normal subgroups.

\r\n", "\r\n", "In this section we will see another way to combine two groups H and K. Once again the larger group will have isomorphic copies of H and \r\n", "K as subgroups, but only one of the two subgroups will be a normal subgroup. For this reason, the combination of groups is called a \r\n", "semi-direct product.

\r\n", "\r\n", "Suppose that H and K are any two groups, and suppose that we have a homomorphism\r\n", "

ϕ: H → Aut(K).

\r\n", "That is, for every h in H, ϕ(h) will be a mapping from K into K. Because the output of the function \r\n", "ϕ is again a function, we will write ϕh instead of ϕ(h). This way we can write \r\n", "ϕh(k) to express the function ϕh evaluated at k. That is, if h1 and \r\n", "h2 are two elements of H, then ϕh₁(k) and \r\n", "ϕh₂(k) will be two automorphisms of K, and also \r\n", "

ϕh₁·h₂(k) = \r\n", "(ϕh₁·ϕh₂)(k) = \r\n", "ϕh₁(ϕh₂(k)).

\r\n", "(Recall that ϕh₁·ϕh₂ means we do ϕh₂ \r\n", "first, then do ϕh₁.)

\r\n", "\r\n", "There will always be at least one possible homomorphism from H to Aut(K) since we could let ϕh be the identity automorphism \r\n", "for all h. However, there will usually be several other possible homomorphisms from H to Aut(K). For each such homomorphism, we can define \r\n", "a product of K and H.

\r\n", "\r\n", "DEFINITION 6.6
\r\n", "Let K and H be two groups, and let G to be the set of all ordered pairs (k, h), where k is in K and \r\n", "h is in H. Let ϕ be a nontrivial homomorphism from H to Aut(K). Then the \r\n", "semi-direct product of K with H through ϕ, \r\n", "denoted\r\n", "

K ⋊ϕH,

\r\n", "is the set G with multiplication defined by\r\n", "

(k1, h1)·(k2, h2) = \r\n", "(k1·ϕh₁(k2), h1·h2).

\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 6.6
\r\n", "The semi-direct product of K with H through ϕ is a group.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "A semi-product of two groups acts in many ways like the direct product. One property that is in common is that there are copies of the two original groups within the \r\n", "product. In fact, we have the following:\r\n", "\r\n", "

\r\n", "\r\n", "LEMMA 6.7
\r\n", "Let G = K ⋊ϕH be the semi-direct product of K with H through the homomorphism \r\n", "ϕ. Suppose that e1 is the identity element of K, and e2 is the identity element of H. Then \r\n", "

H = { (e1, h) | h ∈ H }

\r\n", "is a subgroup of G, and\r\n", "

K = { (k, e2) | k ∈ K }

\r\n", "is a normal subgroup of G. Furthermore, \r\n", "

H ≈ H,   \r\n", "K ≈ K,

\r\n", "and H ∩ K is the identity element of G.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "Since the semi-direct product contains copies of the two smaller groups within itself, the natural question is whether an arbitrary group G can be expressed as \r\n", "a semi-direct product of two of its subgroups. The conditions for when this will happen is set forth in the following theorem.\r\n", "\r\n", "

\r\n", "\r\n", "THEOREM 6.3: The Semi-Direct Product Theorem
\r\n", "Suppose that a group G has two subgroups N and H whose intersection is the identity element. If N is a normal subgroup of G \r\n", "and H is not a normal subgroup of N·H, then there exists a nontrivial homomorphism ϕ from H to \r\n", "Aut(N) such that\r\n", "

N·H ≈ N ⋊ϕH.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "Enough of the technical proofs, let us learn how to define a semi-direct product with Sage. We will use this result to define the semi-direct product of two \r\n", "groups in Sage. We first must define the two groups in Sage using the same identity as we did for the direct product, using different letters for \r\n", "the generators. We must also know the homomorphism ϕ from H to Aut(N).

\r\n", "\r\n", "We will want to express every element into the form k·h, where k is in N, and h is in H.

\r\n", "\r\n", "From the definition, we see that \r\n", "

(k, e2)·(e1, h) = (k·ϕe₂(e1), e2·h) = (k, h).

\r\n", "Thus, we see that k·h can represent the ordered pair (k, h). We need to tell Sage how to handle expressions \r\n", "of the form h·k.

\r\n", "For each generator a of N, and each generator b of H, we can calculate how b·a should be defined by \r\n", "evaluating\r\n", "

(e1, b)·(a, e2) = (e1·ϕb(a), b·e2) = (ϕb(a), b).

\r\n", "So for each generator a of H, and each generator b of N, we make a definition of the form

\r\n", "Define(b * a, ϕb(a) * b )

\r\n", "where we replace the expression ϕb(a) with its element of N.

\r\n", "\r\n", "EXAMPLE:
\r\n", "\r\n", "Use Sage to find a semi-direct product of Z5 with Z2.

\r\n", "\r\n", "We first must define Z5 and \r\n", "Z2 into Sage using the same identity but different generators.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^5, e)\r\n", "Define(b^2, e)\r\n", "Z5 = Group(a); Z5" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z2 = Group(b); Z2" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Next, we must find a nontrivial homomorphism ϕ from Z2 to Aut(Z5). But\r\n", "

Aut(Z5) ≈ Z5* ≈ Z4.

\r\n", "Since the element b is of order 2, ϕ(b)2 = ϕ(b2) = e, so \r\n", "ϕ(b) must be of order 2 to keep the homomorphism from being trivial. We need ϕ(b) to map to the only element of \r\n", "Aut(Z5) which is of order 2.

\r\n", "\r\n", "Which element is this? With a moment's reflection, we can see that\r\n", "

ƒ: N → N, ƒ(k) = k-1

\r\n", "will always be an automorphism of whenever N is an abelian group. As long as N has an element that is not its own inverse, this automorphism will be \r\n", "of order 2.

\r\n", "\r\n", "Therefore, to find a semi-direct product of Z5 by Z2, we must let ϕb be the automorphism \r\n", "ƒ(k) = k-1. Then ϕb(a) = a-1 = a4. \r\n", "So the definition
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Define(b*a, a^4*b)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "completes the definition of the semi-direct product. We now have the group along with the multiplication table:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = ListGroup(); G" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This is the semi-direct product Z5 ⋊ Z2, a non-abelian group of order 10. Note that when there is only one possible \r\n", "semi-direct product between two groups, we can leave out the ϕ in the notation.

\r\n", "\r\n", "We can ask Sage what this group is, using the command StructureDescription(). This command analyzes the last group defined using \r\n", "the InitGroup and Define commands." ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "StructureDescription()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "Sage says that this group is D5, which introduces a new class of groups, known as the dihedral groups.\r\n", "

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Find a semi-direct product Z6 ⋊ Z2. Then ask Sage what the group is using \r\n", "the StructureDescription() command.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can easily generalize these examples to form an important class of groups.

\r\n", "\r\n", "DEFINITION 6.7:
\r\n", "Let n > 2, and let ϕ be the homomorphism from Z2 = {e, b} to Aut(Zn) given by\r\n", "

ϕe(k) = k, ϕb(k) = k-1.

\r\n", "Then the semi-direct product Zn ⋊ϕZ2 is called the dihedral group \r\n", "of order 2n. It is denoted Dn, and is a non-abelian group of order 2n.

\r\n", "\r\n", "Following this example, we see that the dihedral group can be defined in Sage by the commands

\r\n", "\r\n", "InitGroup(\"e\")
\r\n", "AddGroupVar(\"a\", \"b\")
\r\n", "Define(a^n, e)
\r\n", "Define(b^2, e)
\r\n", "Define(b*a, a^-1*b)
\r\n", "Dn = Group(a, b)

\r\n", "\r\n", "The symbol n must be replaced with an integer before executing these commands. When n = 3, we get a non-abelian group of order 6, so we must have that \r\n", "D3 is isomorphic to S3. We also have already seen D4, since this was one of the 5 groups of order 8 that we \r\n", "found in chapter 4.

\r\n", "\r\n", "It should be noted that the semi-direct product may greatly depend on the choice of the homomorphism ϕ.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Consider finding the semi-direct products \r\n", "of Z8 with Z2. The dihedral group D8 is certainly one such product, but there could be others. The homomorphism \r\n", "ϕ would have to map the element b of order 2 in Z2 to an element of order 2 in Aut(Z8). But since\r\n", "

Aut(Z8) ≈ Z8* ≈ Z2 × Z2

\r\n", "has three elements of order 2, we have three choices of what ϕb could be. Do these produce different groups?

\r\n", "\r\n", "To explore this possibility, let us first load in the dihedral group D8.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^8, e)\r\n", "Define(b^2, e)\r\n", "Define(b*a, a^7*b)\r\n", "D8 = ListGroup(); D8" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(D8)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can check that we have defined D8:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "StructureDescription()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that the main diagonal contains 10 e's. This means that there are 9 elements of D8 which are of order 2. This will be useful for \r\n", "later comparisons.

\r\n", "\r\n", "What are the other automorphisms on Z8? Since Z8* = {1, 3, 5, 7}, we have the automorphisms\r\n", "

ϕ(a) = a,   ϕ(a) = a3,   ϕ(a) = \r\n", "a5,   and   ϕ(a) = a7 = a-1.

\r\n", "The first automorphism is the trivial automorphism, and the last is the one we just considered. Suppose we let \r\n", "ϕb(a) = a3. Then b·a = a3·b, so we can enter this \r\n", "into Sage with the commands
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^8, e)\r\n", "Define(b^2, e)\r\n", "Define(b*a, a^3*b)\r\n", "G = ListGroup(); G" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Is this the same group as the dihedral group? Look along the main diagonal. We can count six occurances of the identity elenent, so only five elements of this group are \r\n", "of order 2. Therefore this cannot be isomorphic to D8. What does Sage call this group?
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "StructureDescription()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Sage calls this group \"QD16\", since this is the quasidihedral group of order 16.

\r\n", "\r\n", "What if we let ϕb(a) = a5? We would have b·a = a5·b, \r\n", "and so we would use the following commands to enter this group into Sage:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "AddGroupVar(\"a\", \"b\")\r\n", "Define(a^8, e)\r\n", "Define(b^2, e)\r\n", "Define(b*a, a^5*b)\r\n", "M = ListGroup(); M" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(M)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "How many elements of this group are of order 2? This time there are only four occurances of the identity along the main diagonal, so there are only three elements of \r\n", "order 2. Thus we have yet another non-isomorphic group. Sage's name for this group:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "StructureDescription()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The colon denotes the semi-direct product symbol, ⋊. Sage is identifying this as a semi-direct product, but not telling us which one. In fact, two non-isomorphic groups can sometimes produce the same StructureDescription() result.

\r\n", "\r\n", "We see in these three examples that the semi-direct product N ⋊ϕH depends on the choice of the homomorphism \r\n", "ϕ form H into Aut(N). In fact, even though the three non-identity elements of Z8* are essentially \r\n", "equivalent (The automorphism group of Z8* included all permutations of these three elements), we see that the three elements produced \r\n", "three different semi-direct products of Z8 with Z2.

\r\n", "\r\n", "This example is really more of an exception rather than a rule. Part of what makes this example unusual is that the automorphism group Z8* \r\n", "is abelian, and hence does not have any nontrivial inner automorphisms. We will see in the next proposition that if two homomorphisms ϕ and \r\n", "ƒ from H to Aut(N) are related through an inner automorphism of Aut(N), then the corresponding semi-direct products will \r\n", "be isomorphic.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 6.7
\r\n", "Let ϕ be a homomorphism from a group H to the group Aut(N). Suppose that ƒ is another homomorphism such that\r\n", "

ƒh(k) = w(ϕh(w-1(k))),

\r\n", "where w(k) is an automorphism of N. Then \r\n", "

N ⋊ƒ H ≈ N ⋊ϕH

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "It is also clear that two homomorphisms ϕ and ƒ are related through an automorphism of H, the semi-direct products must be \r\n", "isomorphic since we are merely relabeling the elements of H. As a result there will be many instances in which there will be only one non-isomorphic \r\n", "semi-direct product of N by H. Whenever this happens, we can denote the semi-direct product as\r\n", "

N ⋊ H

\r\n", "without having to specify the homomorphism ϕ.

\r\n", "\r\n", "We will find that we can describe many groups in terms of semi-direct products that would be hard to describe in any other way. With Sage, the structure of \r\n", "these semi-direct products can easily be studied.\r\n", "\r\n", "









































\r\n", "\r\n", "

Proofs:

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Proposition 6.1:

\r\n", "\r\n", "First, suppose that H and K are both abelian. Then for two elements (h1, k1) and (h2, \r\n", "k2) in H × K, we have\r\n", "

(h1, k1)·(h2, k2) \r\n", "= (h1·h2, k1·k2)\r\n", "= (h2·h1, k2·k1)\r\n", "= (h2, k2)·(h1, k1).

\r\n", "So the two elements in H × K commute. Hence, H × K is abelian.

\r\n", "\r\n", "Now suppose that H × K is commutative. We then have\r\n", "

(h1·h2, k1·k2)\r\n", "= (h1, k1)·(h2, k2) \r\n", "= (h2, k2)·(h1, k1)\r\n", "= (h2·h1, k2·k1).

\r\n", "Comparing components, we see that h1·h2 = \r\n", "h2·h1 and k1·k2 = \r\n", "k2·k1. Since this is true for all h1 and h2 in H, and all \r\n", "k1 and k2 in K, both H and K are abelian.

\r\n", "\r\n", "Return to text\r\n", "\r\n", "









































\r\n", "\r\n", "\r\n", "\r\n", "Proof of Theorem 6.1:

\r\n", "\r\n", "First, let us show that every element in H·K can be uniquely written in the form h·k, where \r\n", "h ∈ H and k ∈ K. Suppose that \r\n", "

h1·k1 = h2·k2.

\r\n", "Then h2-1·h1 = k2·k1-1. Since this element \r\n", "must be in both H and K, and the intersection of H and K is the identity element, we have that \r\n", "

h2-1·h1 = k2·k1-1 = \r\n", "e.

\r\n", "Thus, h1 = h2 and k1 = k2. Therefore, every element of H·K can \r\n", "be written uniquely as h·k, where h is in H, and k is in K.

\r\n", "\r\n", "Next, we need to show that H·K is a group. Since h·k = k·h for all h ∈ H\r\n", "and k ∈ K, we have that H·K = K·H. Thus, by Lemma 4.2, H·K is a \r\n", "subgroup of G.

\r\n", "\r\n", "We can now define a mapping\r\n", "

ϕ : H·K → H × K

\r\n", "by ϕ(x) = (h, k), where h and k are the unique elements such that h ∈ H, \r\n", "k ∈ K, and x = h·k. It is clear that ϕ; is one-to-one, since the element (h, k) \r\n", "can only have come from h·k. Also, ϕ is onto, for the element h·k maps to (h, k). \r\n", "All that remains to show is that \r\n", "ϕ(x·y) = ϕ(x)·ϕ(y). \r\n", "Let x = h1·k1 and y = h2·k2. Then\r\n", "

ϕ(x·y) = \r\n", "ϕ(h1·k1·h2·k2) \r\n", "= ϕ(h1·h2·k1·k2) \r\n", "= (h1·h2, k1·k2)\r\n", "= (h1, k1)·(h2, k2)\r\n", "= ϕ(x)·ϕ(y).

\r\n", "Thus, ϕ is an isomorphism, and so H·K ≈ H × K.

\r\n", " \r\n", "Return to text\r\n", "\r\n", "









































\r\n", "\r\n", "\r\n", "\r\n", "Proof of Proposition 6.2:

\r\n", "\r\n", "Let e1 denote the identity element of H, and e2 denote the identity element of K. An element \r\n", "x = (h, k) in H × K solves the equation xn = (e1, e2) \r\n", "if and only if\r\n", "

hn = e1 and kn = e2.

\r\n", "Since there are Rn(H) solutions to the former, and Rn(K) solutions to the latter, \r\n", "there are Rn(H)·Rn(K) ordered pairs (h, k) \r\n", "that solve both of these equations. Thus, there are Rn(H)·Rn(K) elements \r\n", "of H × K for which \r\n", "xn = (e1, e2).

\r\n", " \r\n", "Return to text\r\n", " \r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Corollary 6.1:

\r\n", " \r\n", "The first condition of the direct product theorem (6.1) is given, so we only need to show that the second condition holds. That is, we need to show that \r\n", "h·k = k·h for all h in H, and k in K. Let h ∈ H \r\n", "and k ∈ K.

\r\n", "\r\n", "Since K is a normal subgroup of G, h·k·h-1 is in K. Thus, \r\n", "h·k·h-1·k-1 is also in K.

\r\n", "\r\n", "But H is also a normal subgroup of G, so k·h-1·k-1 is in H. Hence,\r\n", "h·k·h-1·k-1 is also in H.

\r\n", "\r\n", "We now use the fact that the only element in both H and K is e. Thus, \r\n", "h·k·h-1·k-1 = e, which implies \r\n", "h·k = k·h.

\r\n", "\r\n", "Therefore, the second condition of the direct product theorem (6.1) holds, and so by this \r\n", "theorem, H·K ≈ H × K.

\r\n", " \r\n", "Return to text\r\n", " \r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Lemma 6.1:

\r\n", " \r\n", "To check that H and K are indeed subgroups simply observe that since G is commutative the functions \r\n", "ϕ(x) = xm and ƒ(x) = xn are both homomorphisms of G. \r\n", "Then H and K are the kernels of the mappings ϕ and ƒ.

\r\n", "\r\n", "To show that H and K have only the identity element in common, we consider an element x in the intersection. By the Chinese remainder \r\n", "theorem (0.7), there exists a non-negative number k < m·n such that\r\n", "

k mod m = 1  and  k mod n = 0.

\r\n", "Then k = 1 + m b for some number b. Thus,\r\n", "

xk = x(1+m b) = x·(xm)b \r\n", "= x·eb = x

\r\n", "since x is in H. Yet k = n c for some number c, so\r\n", "

xk = xn c = (xn)c = ec = e

\r\n", "since x is in K. Thus, x = e, and so H ∩ K = {e}. Since G is abelian, the direct product \r\n", "theorem (6.1) proves that\r\n", "

H·K ≈ H × K.

\r\n", "All that is left to prove is that G = H·K. Let g be an element in G. Since m and n are coprime, \r\n", "by the greatest common divisor theorem (0.4) there exists a and b such that\r\n", "

a n + b m = gcd(m, n) = 1.

\r\n", "Then \r\n", "

g = g1 = g(a n+b m) = \r\n", "ga n·gb m.

\r\n", "Now, (ga n)m = (ga)n m = e, so ga n is in H.\r\n", "Likewise, gb m is in K. Thus, every element of G is in H·K, and so\r\n", "

G ≈ H × K.

\r\n", " \r\n", "Return to text \r\n", "\r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Lemma 6.2:

\r\n", " \r\n", "We will proceed using induction on the order of G. If |G| is a prime number, then p must be |G|, \r\n", "and G must be isomorphic to Zp. So there \r\n", "would be an element of order p in G.

\r\n", "\r\n", "Suppose that the assumption is true for all groups of order less than |G|. If G does not have any proper subgroups, then G would be a cyclic \r\n", "group of prime order (which we have already covered.) Thus, we may assume that G has a subgroup N that is neither G nor {e}.

\r\n", "\r\n", "Since G is abelian all subgroups are normal. Thus we could consider the quotient group G/N. Since |G| = \r\n", "|N| · |G/N|, p must divide either |N| or |G/N|. If p divides N, then because \r\n", "N is a smaller group than G, by induction N must have an element of order p, which would be in G.

\r\n", "\r\n", "If p does not divide |N| it must divide |G/N|. Since G/N is a smaller group than G, by induction \r\n", "G/N must have an element of order p. This element can be written a N for some a in G.

\r\n", "\r\n", "Since a N is of order p, a cannot be in N, yet ap must be in N. If |N| = q, \r\n", "we would have by Corollary 3.2 that (ap)q = e.

\r\n", "\r\n", "If b = aq is not the identity, then bp = e, and so b would be the required element. \r\n", "But if b = e, then (a N)q = N. But a N was of order p, and \r\n", "so p \r\n", "must divide q. But we assumed that p did not divide q = |N|. Hence, b is not the identity, and so G has an element \r\n", "of order p.

\r\n", " \r\n", "Return to text \r\n", "\r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Lemma 6.3:

\r\n", " \r\n", "Since pn and k are coprime, we can use Lemma 6.1 to form the subgroups\r\n", "

P = { x ∈ G | x(pⁿ) = e }

\r\n", "and \r\n", "

K = { x ∈ G | xk = e }.

\r\n", "By Lemma 6.1 these two subgroups have only the identity in common, and G ≈ P × K. If p divided |K|, then by \r\n", "Lemma 6.2, K would contain an element of order p. But this element would then be in P as well, which contradicts the fact that only the \r\n", "identity element is in common between P and K. So p does not divide the order of K.

\r\n", "\r\n", "Also note that the order of every element of P is a power of p. Thus, Lemma 6.2 tells us that no other prime other than p \r\n", "divides |P|.

\r\n", "\r\n", "Finally, note that |G| = pn·k = |P|·|K|. Since p does not divide |K|, we have \r\n", "that pn must divide |P|. But no other primes can divide |P|, and so |P| = pn. \r\n", "Hence, |K| = k.

\r\n", " \r\n", "Return to text\r\n", "\r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Lemma 6.4:

\r\n", " \r\n", "We will use induction on n. If n = 1, then P is a cyclic group of order p, and hence is generated by non-identity element x \r\n", "in P. We then have X = P, so we can let T = {e}, and hence P ≈ X × T.

\r\n", "\r\n", "Now suppose that the assertion is true for all powers of p less than n. Notice that the order of every element of P is a power \r\n", "of p. Thus, if we let x be an element with the largest order, say m, then the order of all elements in P must divide m. \r\n", "Hence, gm = e for all elements g in P.

\r\n", "\r\n", "We now let X be the subgroup generated by x. If X = P, then we can again let T = {e} and we are done. \r\n", "If X is not P, we let y be an element of P not in X which has the smallest possible order. \r\n", "Then since the order of yp is less than the order of y, yp must be in X. This means that \r\n", "yp = xq for some 0 ≤ q < m.

\r\n", "\r\n", "Since y is in P, ym = e. But\r\n", "

e = ym = (yp)(m/p) = \r\n", "(xq)(m/p) = x(m q/p)

\r\n", "Because x is of order m, this can be the identity only if m q/p is a multiple of m. Hence, q is a multiple of \r\n", "p.

\r\n", "\r\n", "If we let k = x−(q/p)·y then k is not in X because y isn't, and \r\n", "

kp = (x−(q/p))p·yp = \r\n", "x−q·yp = x−q·xq = e.

\r\n", "Therefore, we have found an element k of order p that is not in X. If we let K be the group generated by the element k, \r\n", "then X ∩ K = {e}.

\r\n", "\r\n", "Consider the quotient group P/K. What is the order of x K in P/K? We see that\r\n", "

(x K)n = K ⟺ xn ∈ \r\n", "K ⟺ xn ∈ X ∩ K ⟺ xn = e.

\r\n", "Therefore, the order of x K is the same as the order of x, which is m. Also note that no element of P/K can have an element \r\n", "of higher order since gn = e for all elements g in P.

\r\n", "\r\n", "Now we use the induction. Since the order of P/K is less than the order of P, and x K is an element of maximal order, we have \r\n", "by induction that\r\n", "

P/K ≈ Y × B,

\r\n", "where Y is the subgroup of P/K generated by x K, and B is a subgroup of P/K such that only the \r\n", "identity element K is in the intersection of Y and B.

\r\n", "\r\n", "Let ϕ be the canonical homomorphism from P to P/K given by ϕ(g) = g K. Let \r\n", "T = ϕ-1(B). Then T is a subgroup of P.

\r\n", "\r\n", "If g is in both X and T, then ϕ(g) is in both Y and B. Since the intersection of Y and \r\n", "B is the identity element, we have ϕ(g) = g K = K. Thus, g is in the subgroup K. But \r\n", "X ∩ K = {e}, so we have \r\n", "

X ∩ T = {e}.

\r\n", "Thus, by the direct product theorem (6.1), we find that X·T ≈ X × T.

\r\n", "\r\n", "We finally need to show that P = X·T. Let u be an element in P, and since \r\n", "P/K ≈ Y × B, we can write ϕ(u) as (xc·K)·(k K) \r\n", "for some number c, and some k K in B. Then\r\n", "

u ∈ xc·k·K ⊆ X·T.

\r\n", "Thus, P = X·T, and so P ≈ X × T.

\r\n", " \r\n", "Return to text \r\n", "\r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Lemma 6.5:

\r\n", " \r\n", "Since G is expressed as a direct product we can use Proposition 6.2 and find Rq(H) for each factor H in \r\n", "the product, and multiply these numbers together. Since each factor is cyclic, we can use Corollary 2.1. For all of the factors \r\n", "Z ₖ₁, Z ₖ₂, … Z ₖₘ, since gcd(ki, q) = gcd(ki, px) = 1, Rq(H) would be 1. On the other hand, Rq(Z(pₕⁱ)) is \r\n", "

gcd(phⁱ, q) = gcd(phⁱ, px) = \r\n", "pMin(hⁱ, x).

\r\n", "Thus, Rq(G) is the product of the above for factors 1 through n of \r\n", "G, which gives us a grand total of\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
⎛∑n Min(hi, x)⎞
⎝i=1⎠
p .
\r\n", "Return to text \r\n", " \r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Lemma 6.6:

\r\n", " \r\n", "Let us begin by observing the value of the expression\r\n", "

2 Min(hi, x) − Min(hi, x − 1) − \r\n", "Min(hi, x + 1).

\r\n", "When hi < x, then Min(hi, x) = Min(hi, x−1) = \r\n", "Min(hi, x+1) = hi, and so the above evaluates to 0. On the other hand, if hi > x, then the \r\n", "above expression simplifies to \r\n", "

2 x − (x − 1) − (x + 1) = 0.

\r\n", "However, if hi = x, then Min(hi, x) = x, \r\n", "Min(hi, x − 1) = x − 1, and Min(hi, x + 1) = x. Hence, we have \r\n", "

2 Min(hi, x) − Min(hi, x − 1) − \r\n", "Min(hi, x + 1) = 2 x − (x − 1) − x = 1.

\r\n", "Thus, we see that\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
2 Min(hi, x) − Min(hi, x − 1) − Min(hi, x + 1) = ⎧ 1 if hi = x,
⎨
⎩ 0 if hi ≠ x.
\r\n", "
\r\n", "Thus, if we sum the above expression for i going from 1 to n, we will count the number of terms hi that are equal to \r\n", "x. Hence this count will be\r\n", "

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
n
∑2 Min(hi, x) − Min(hi, x − 1) − \r\n", " Min(hi, x + 1) = 2 ƒ(x) − ƒ(x − 1) − ƒ(x + 1).
i = 1
\r\n", "\r\n", "Return to text \r\n", "\r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Theorem 6.2:

\r\n", " \r\n", "We will proceed on induction on the order of the group. If the order of the group is 2, then the theorem is true since the group would be isomorphic \r\n", "to Z2. Let G be a finite abelian group and suppose the theorem is true for all groups of order less than G. Let p be a \r\n", "prime that divides the order of G. By Lemma 6.3, G ≈ P × K, where P is the subgroup of G containing \r\n", "the elements of order pm for some m.
\r\n", "
\r\n", " \r\n", "Furthermore, if x is an element of maximal order in P, and X is the group generated by x, then by Lemma 6.4, \r\n", "G ≈ X × T × K. Since X will be a nontrivial cyclic group, the orders of T and K will be \r\n", "less than |G|. Thus, by induction, T and K can be written as a direct product of cyclic groups whose orders are powers of primes. Since \r\n", "X is also a cyclic group of order pr for some r, G can be written as a direct product of cyclic groups whose orders are \r\n", "powers of \r\n", "primes.

\r\n", "\r\n", "We next have to show that this decomposition is unique. We will do this by showing that the number of times \r\n", "Z(pₓ) appears in the decomposition, where p is a prime, is completely determined by the order of the \r\n", "elements in the group G. From Lemma 6.5,\r\n", "

Rpₓ(G) = p(∑ Min(hⁱ, x) )

\r\n", "where the sum is taken over all i such that pi = p. Thus, we see that

\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "
ƒp(x) = ∑ Min(hi, x) = \r\n", "logp(Rpₓ(G))
pi = p
\r\n", "
\r\n", "will be completely determined by the orders of the elements of G. But then by Lemma 6.6 the number of times that \r\n", "Z(pₓ) appears in the decomposition is given by\r\n", "

2 ƒp(x) − ƒp(x − 1) − \r\n", "ƒp(x + 1).

\r\n", "Hence, the decomposition of G as a direct product of cyclic groups of the form Z(pₓ) is unique.

\r\n", " \r\n", "Return to text \r\n", " \r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Corollary 6.2:

\r\n", " \r\n", "By the fundamental theorem of abelian groups (6.2), every abelian group of order pm must \r\n", "be isomorphic to\r\n", "

Z(pₕ¹) × \r\n", "Z(pₕ²) × Z(pₕ³) × ⋯ × \r\n", "Z(pₕⁿ )

\r\n", "Also,\r\n", "

ph¹·ph²·ph³ ⋯ \r\n", "phⁿ = pm

\r\n", "Hence h1 + h2 + h3 + ⋯ + hn = m. Furthermore, the decomposition of the \r\n", "abelian group is unique up to rearrangement of the factors. Thus, there is a one-to-one correspondence between non-isomorphic abelian groups of \r\n", "order pm and ways m can be written as a sum of positive integers without regard to order.

\r\n", " \r\n", "Return to text \r\n", "\r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Corollary 6.3:

\r\n", " \r\n", "We know from the fundamental theorem of abelian groups (6.2) that each such group is isomorphic to a direct product of cyclic groups whose order is a power of a prime. \r\n", "If we collect all factors involving the same primes together, we find that such a group is isomorphic to a direct product of a series of groups of orders\r\n", "

p1h¹, p2h², \r\n", "p3h³, …, and pnhⁿ.

\r\n", "We know from Corollary 6.2 that there are exactly P(x) non-isomorphic abelian groups of order px. Thus, there are \r\n", "P(hi) possible groups for the ith factor in this decomposition. Therefore, there are\r\n", "

P(h1)·P(h2)·P(h3) ⋯ \r\n", "P(hn)

\r\n", "possible ways of forming a product of groups with orders p1h¹, p2h², \r\n", "p3h³, …, and pnhⁿ.

\r\n", "\r\n", "Since the fundamental theorem of abelian groups (6.2) also states that the decomposition is unique up to the rearrangement of the factors, every group thus formed \r\n", "is isomorphically different. So we have exactly P(h1)·P(h2)·P(h3) \r\n", "⋯ P(hn) non-isomorphic abelian groups of order m.

\r\n", " \r\n", "Return to text \r\n", "\r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 6.3:

\r\n", "\r\n", "The mapping i(x) = x for all x in G is obviously an automorphism on G, so the set of all automorphisms on G \r\n", "is non-empty. Also, each automorphism is a permutation on the elements of G. Suppose ϕ and ƒ are two automorphisms on G. \r\n", "Then ϕ(ƒ(x)) is a one-to-one and onto mapping from G to G.

\r\n", "\r\n", "Furthermore, \r\n", "

ϕ(ƒ(x·y)) = \r\n", "ϕ(ƒ(x)·ƒ(y)) = \r\n", "ϕ(ƒ(x))·ϕ(ƒ(y)).

\r\n", "So ϕ(ƒ(x)) is a homomorphism on G, hence ϕ·ƒ is an automorphism of G.

\r\n", "\r\n", "Also, since ƒ is one-to-one and onto, ƒ−1 exists on G, and \r\n", "

ƒ(ƒ−1(x)·ƒ−1(y)) = \r\n", "ƒ(ƒ−1(x))·ƒ(ƒ−1(y)) = x·y.

\r\n", "Taking ƒ−1 of both sides of the equation gives us\r\n", "

ƒ−1(x)·ƒ−1(y) = \r\n", "ƒ−1(x·y)

\r\n", "So ƒ−1 is a homomorphism. Hence both ƒ−1 and ϕ·ƒ−1 \r\n", "are automorphisms of G. Therefore by Proposition 2.2, Aut(G) is a subgroup of the group of permutations on the elements of G.

\r\n", " \r\n", "Return to text \r\n", "\r\n", "









































\r\n", "\r\n", "\r\n", "\r\n", "Proof of Proposition 6.4:

\r\n", "\r\n", "Consider the mapping\r\n", "

ψ: Zn* → Aut(Zn)

\r\n", "given by ψ(j) = ƒj, where ƒj(x) = \r\n", "(j·x) mod n.\r\n", "Then given two elements j and k in Zn*, we have that\r\n", "

ƒj(ƒk(x)) = \r\n", "j·(k·x) mod n = \r\n", "(j·k)·x mod n = ƒ(j·k)(x).

\r\n", "So\r\n", "

ψ(j)·ψ(k) = ƒj(ƒk) = \r\n", "ƒ(j·k) = ψ(j·k).

\r\n", "Hence, ψ is a homomorphism from Zn* to Aut(Zn). To see that ψ is one-to-one, note that \r\n", "ƒj(1) = j, and so ƒj = ƒk only if j = k.

\r\n", "\r\n", "To see that ψ is onto, we can use the pigeon-hole principle. If we consider a general automorphism f of Zn, then \r\n", "f(1) must be a generator of Zn, since 1 is a generator. But f will be completely determined by knowing f(1). Thus,\r\n", "the number of automorphisms is at most the number of generators of Zn, which is ϕ(n). Since \r\n", "|Zn*| = ϕ(n), we know the function is one-to-one, so it must also be onto.

\r\n", " \r\n", "Return to text \r\n", "\r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 6.5:

\r\n", " \r\n", "First we need to show that Inn(G) is a subgroup. Let ƒx(y) = x·y·x-1 \r\n", "be an inner automorphism. The inverse can be easily found by observing\r\n", "

y ∈ ƒx-1(v) ⟺ x·y·x-1 \r\n", "= v ⟺ y = x-1·v·x ⟺ y = \r\n", "ƒ(x₋₁)(v),

\r\n", "so the inverse of ƒx is also an inner automorphism.

\r\n", "\r\n", "If we consider two inner automorphisms ƒx and ƒy, then \r\n", "

(ƒx·ƒy)(v) = \r\n", "ƒx(ƒy(v)) = \r\n", "x·(y·v·y-1)·x-1 = \r\n", "(x·y)·v·(x·y)-1 = \r\n", "ƒ(x·y)(v).

\r\n", "Thus the product of two inner automorphisms is also an inner automorphism. So by Proposition 2.2, Inn(G) is a subgroup of Aut(G).

\r\n", "\r\n", "Finally, we need to show that Inn(G) is normal in Aut(G). Let ϕ be any automorphism and let ƒx(y) = \r\n", "x·y·x-1 be an inner automorphism. Then\r\n", "

(ϕ·ƒx·ϕ-1)(v) = \r\n", "ϕ(ƒx(ϕ-1(v))) = \r\n", "ϕ(x·ϕ-1(v)·x-1).

\r\n", "Since ϕ is a homomorphism, this will simplify.\r\n", "

ϕ(x·ϕ-1(v)·x-1) = \r\n", "ϕ(x)·ϕ(ϕ-1(v))·ϕ(x-1) = \r\n", "ϕ(x)·v·[ϕ(x)]-1 =\r\n", "ƒϕ(x)(v).

\r\n", "So ϕ·ƒx·ϕ-1 is an inner automorphism of G. Therefore, by Proposition 3.4, \r\n", "Inn(G) is a normal subgroup of Aut(G).

\r\n", " \r\n", "Return to text \r\n", "\r\n", "









































\r\n", "\r\n", "\r\n", "\r\n", "Proof of Proposition 6.6:

\r\n", "\r\n", "It is clear that the product of two ordered pairs in G is an ordered pair in G. If we let e1 denote the identity element of \r\n", "K, and e2 denote the indentity element of H, then \r\n", "

ϕe₂(k) = k

\r\n", "since ϕ must map e2 to the identity automorphism of K. Thus\r\n", "

(k1, h1)·(e1, e2) = \r\n", "(k1·ϕh₁(e1), h1·e2) = \r\n", "(k1, h1) and (e1, e2)·(k2, h2) =\r\n", "(e1·ϕe₂(k2), e2·h2) =\r\n", "(k2, h2).

\r\n", "So (e1, e2) acts as the identity element of G.

\r\n", "\r\n", "Next we note that the element (k, h) has an inverse (ϕh₋₁(k-1), h-1), since\r\n", "

(ϕh₋₁(k-1), h-1)·(k, h) =\r\n", "(ϕh₋₁(k-1)·ϕh₋₁(k), \r\n", "h-1·h) =\r\n", "(ϕh₋₁(k-1·k), e2) = \r\n", "(ϕh₋₁(e1), e2) = (e1, e2),

\r\n", "and\r\n", "

(k, h)·(ϕh₋₁(k-1), h-1) = \r\n", "(k·ϕh(ϕh₋₁(k-1)), h·h-1) =\r\n", "(k·ϕe₂(k-1), e2) = \r\n", "(k·k-1, e2) = (e1, e2).

\r\n", "The final thing we need to check is that the multiplication on G is associative. Note that\r\n", "

[(k1, \r\n", "h1)·(k2, h2)]·(k3, h3) = \r\n", "(k1·ϕh₁(k2), h1·h2)·(k3, h3) = \r\n", "(k1·ϕh₁(k2)·ϕh₁·h₂(k3), (h1·h2)·h3),

\r\n", "while\r\n", "

(k1, \r\n", "h1)·[(k2, h2)·(k3, h3)] = \r\n", "(k1, h1)·(k2·ϕh₂(k3), h2·h3) =\r\n", "(k1·ϕh₁(k2·ϕh₂(k3)), h1·(h2·h3)) \r\n", "= (k1·ϕh₁(k2)·ϕh₁(ϕh₂(k3)), (h1·h2)·h3)\r\n", "= (k1·ϕh₁(k2)·ϕh₁·h₂(k3), (h1·h2)·h3).

\r\n", "Hence the multiplication on G is associative and so G forms a group.

\r\n", "\r\n", "Return to text \r\n", " \r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Lemma 6.7:

\r\n", " \r\n", "We will use Proposition 2.2 and observe that \r\n", "

(e1, h)-1 = \r\n", "(ϕh₋₁(e1-1), h-1) = (e1, h-1),

\r\n", "so\r\n", "

(e1, h1)·(e1, h2)-1 =\r\n", "(e1, h1)·(e1, h2-1) =\r\n", "(e1·ϕh₁(e1), h1·h2-1) = \r\n", "(e1, h1·h2-1).

\r\n", "Thus, whenever a and b are in H, a·b-1 is in \r\n", "H. So H is a subgroup.

\r\n", "\r\n", "The mapping ƒ : G → H given by \r\n", "

ƒ( (k, h) ) = h

\r\n", "is a homomorphism, since\r\n", "

ƒ( (k1, h1)·(k2, h2) ) = \r\n", "ƒ( (k1·ϕh₁(k2), h1·h2) ) =\r\n", "h1·h2 = \r\n", "ƒ( (k1, h1) )·ƒ( (k2, h2) ).

\r\n", "The kernel of this homomorphism is K, so K\r\n", "is a normal subgroup of G. By restricting the function ƒ to the set H, we find that \r\n", "it is one-to-one and onto. Thus, H ≈ H.\r\n", "\r\n", "A similar function g : K → K, given by\r\n", "

g(k) = (k, e2)

\r\n", "can show that K ≈ K. This function is clearly one-to-one and onto, and\r\n", "

g(k1)·g(k2) = \r\n", "(k1, e2)·(k2, e2) =\r\n", "(k1·ϕe₂(k2), e2) =\r\n", "(k1·k2, e2) = g(k1·k2).

\r\n", "Finally, it is clear that the intersections of the two groups give just {(e1, e2)}.

\r\n", " \r\n", "Return to text \r\n", " \r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Theorem 6.3:

\r\n", " \r\n", "Note that since H is a subgroup of G, and N is a normal subgroup we have by Lemma 4.3 that N·H is a subgroup of \r\n", "G. We next want to define the homomorphism ϕ. For each h in H, we define\r\n", "

ϕh(k) = h·k·h-1

\r\n", "for all k ∈ N. We first need to show that ϕh is an automorphism on N for each h in H, and \r\n", "then we need to show that ϕ itself is a nontrivial homomorphism. Since N is normal, it is clear that this sends elements of N\r\n", "to elements of N. Note that \r\n", "

ϕh(k1·k2) = \r\n", "h·k1·k2·h-1 = \r\n", "(h·k1·h-1)·(h·k2·h-1) =\r\n", "ϕh(k1)·ϕh(k2).

\r\n", "So ϕh is a homomorphism from N to N. Since \r\n", "

y ∈ \r\n", "ϕh-1(k) ⟺ h·y·h-1 = \r\n", "k ⟺ y = h-1·k·h

\r\n", "we see that ϕh is a one-to-one and onto function. Thus, ϕh is an automorphism of N.

\r\n", "\r\n", "Next, we need to see that ϕ itself is a homomorphism from H to Aut(N). Note that\r\n", "

(ϕh₁·ϕh₂)(k) =\r\n", "ϕh₁(ϕh₂(k)) = \r\n", "ϕh₁(h2·k·h2-1) =\r\n", "h1·h2·k·h2-1·h1-1 =\r\n", "(h1·h2)·k·(h1·h2)-1 =\r\n", "ϕh₁·h₂(k).

\r\n", "So ϕh₁·ϕh₂ = ϕh₁·h₂\r\n", "and we see that ϕ is a homomorphism. In fact, the homomorphism must be nontrivial, because if ϕh(k) = k \r\n", "for all h and k, then since ϕh(k) = h·k·h-1 = k, \r\n", "we have that k·h = h·k for all h in H, and k in N. \r\n", "This would indicate that H is a normal subgroup of N·H, which contradicts our original assumption. Thus, ϕ is \r\n", "a nontrivial homomorphism.

\r\n", "\r\n", "We can now proceed in a way similar to how we proved the direct product theorem (6.1). As before, we will begin by showing that \r\n", "every element in \r\n", "N·H can be uniquely written in the form k·h, where k ∈ N and h ∈ H. \r\n", "Suppose that we have \r\n", "

k1·h1 = k2·h2.

\r\n", "Then k2-1·k1 = h2·h1-1. Since this element is in \r\n", "both N and H, which has just the identity element in the intersection, we must have \r\n", "

k2-1·k1 = h2·h1-1 = \r\n", "e.

\r\n", "Therefore, k1 = k2 and h1 = h2. Thus, we have shown that every element of \r\n", "N·H is written uniquely as k·h, where k is in N, and h is in H.

\r\n", "\r\n", "We now want to create a mapping\r\n", "

ƒ : N·H → N ⋊ϕH

\r\n", "defined by\r\n", "

ƒ(x) = (k, h),

\r\n", "where k and h are the unique elements such that k ∈ N, h ∈ H, and x = k·h. \r\n", "The function ƒ is one-to-one since the element (k, h) can only come from k·h. Also, the element \r\n", "k·h maps to (k, h), so ƒ is onto.
\r\n", "
\r\n", "\r\n", "The final step is to show that ƒ is a homomorphism. Let x = k1·h1, and \r\n", "y = k2·h2. Then \r\n", "

x·y = \r\n", "k1·h1·k2·h2 = \r\n", "(k1·h1·k2·h1-1)·(h1·h2).

\r\n", "Since N is a normal subgroup, h1·k2·h1-1 is in N, and so \r\n", "k1·h1·k2·h1-1 is in N while \r\n", "h1·h2 is in H. Thus,\r\n", "

ƒ(x·y) = \r\n", "ƒ((k1·h1·k2·h1-1)·(h1·h2))\r\n", "= (k1·h1·k2·h1-1, h1·h2) = (k1·ϕh₁(k2), h1·h2) = \r\n", "(k1, h1)·(k2, h2) = ƒ(x)·ƒ(y).

\r\n", "So ƒ is an isomorphism, and we have N·H ≈ N ⋊ϕH.

\r\n", " \r\n", "Return to text \r\n", " \r\n", "









































\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 6.7:

\r\n", " \r\n", "Let us write G = N ⋊ϕH, and M = N ⋊ƒ H. These are \r\n", "two different groups, even though they are both written using ordered pairs. Let us define a mapping\r\n", "

v : G → M

\r\n", "defined by\r\n", "

v( (k, h) ) =(w(k), h).

\r\n", "Because w(k) is one-to-one and onto, certainly v is one-to-one and onto. All we would have to check is that \r\n", "

v( (k1, h1) )·v( (k2, h2) ) = \r\n", "v( (k1, h1) · (k2, h2) )

\r\n", "We have that \r\n", "

v( (k1, h1) · (k2, h2) ) =\r\n", "(w(k1), h1)·(w(k2), h2) =\r\n", "(w(k1)·ƒh₁(w(k2)), h1·h2) =\r\n", "(w(k1)·w(ϕh₁(w-1(w(k2)))), h1·h2) = \r\n", "(w(k1)·w(ϕh₁(k2)), \r\n", "h1·h2)

\r\n", "On the other hand,\r\n", "

v( (k1, h1) · (k2, h2) ) =\r\n", "v( (k1·ϕh₁(k2), h1·h2) ) =\r\n", "(w(k1·ϕh₁(k2)), h1·h2) =\r\n", "(w(k1)·w(ϕh₁(k2)), \r\n", "h1·h2).

\r\n", "Since these are equal, we have an isomorphism.

\r\n", " \r\n", "Return to text

\r\n", " \r\n", "









































\r\n", " \r\n", "\r\n", "

Sage Interactive Problems

\r\n", "\r\n", "
\r\n", "6.1 ) Use Sage to define the group Z2 × Z6. Show that this group is not isomorphic to Z12.\r\n", "
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "6.2 ) Define the group S3 × Z2 in Sage. Show that this group is not isomorphic \r\n", "to A4.
\r\n", "(Hint: Count the elements of order 2.)
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "6.3 ) Use Sage's PartitionsP command to find the number of abelian groups of order 120,000.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "For Problems 6.4 through 6.7:Find all of the automorphisms of the following groups.
(Hint: For the non-abelian groups, find the inner automorphisms first.)
\r\n", "\r\n", "
\r\n", "6.4 ) S3.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "6.5 ) Z15*.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "6.6 ) D4.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "6.7 ) D5.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "6.8 ) Show that there is only one semi-direct product Z8* ⋊ Z2. Which of the five groups of order 8 is this \r\n", "group isomorphic to?
(Hint: Use Proposition 6.7.)
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "6.9 ) Use Sage to find the only semi-direct product Z8* ⋊ Z8*. Is this group \r\n", "isomorphic to any of the three groups of order 16 found by considering Z8 ⋊ Z2?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "6.10) Use Sage to define the only semi-direct product Z3 ⋊ Z4. Show that this group is different than both \r\n", "A4 and S3 × Z2.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "6.11) From Problems 6.1, 6.2, 6.10 and section 6.4, we have found six groups of order 12: Z12, Z2 × Z6, \r\n", "A4, D6, S3 × Z2, and Z3 ⋊ Z4.\r\n", "Yet the table on page 85 indicates that there are only five non-isomorphic groups of order 12. Which two of these groups are isomorphic? Use Sage to show \r\n", "the isomorphism.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "\r\n", "\r\n", "\r\n", "\r\n", "" ] } ], "metadata": { "kernelspec": { "display_name": "SageMath (stable)", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.14" } }, "nbformat": 4, "nbformat_minor": 0 }