Please Login to access more options.


Today

« November 2013 »

Sun

Mon

Tue

Wed

Thu

Fri

Sat

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

Now that we have factor groups, we can take large groups and break them down into smaller groups which are easier to study. We'd like to reverse this process, namely start with some small groups and then combine them together to build larger groups. It would be nice if we could build all groups in this way. Then we could reduce our study of group theory to just understanding the simplest building blocks (called simple groups), and from those building blocks we could build every group. We will not fully obtain this goal this semester, but we're headed in that direction.

The first problem today helps you refresh your memory about the definitions of homomorphism and order of an element. You'll also need to use induction. The problem has you show that if $f$ is a homomorphism from $G$ to $H$, then while $f$ may not preserve the order of elements in $a$, it has to send an element of order $n$ to an element whose order divides $n$. This must happen on an element by element basis. So if we know something about the order of $f(a)$, then we know that $|a|$ must be a multiple of $|f(a)|$.

Problem 89 (The order of $a$ is a multiple of the order of $f(a)$, or $|a|=k|f(a)|$)

Suppose that $f:G\to H$ is a homomorphism. Prove that if $a\in G$ has order $n$, show that $|f(a)|$ divides $n$, i.e. show that $|a|$ is a multiple of $|f(a)|$.

In addition to homomorphisms interacting nicely with elements and orders, even more can be said. In particular, if you know that there are $n$ things that map to the indentity $e$ in the codomain, then the homomorphism must carry exactly $n$ elements from the domain to each element of the codomain. For this reason, we say that a homomorphism is an $n$-to-one map. If you look back at last week's problems, you should see somewhere that we showed a result very similar to this, namely when we showed that the kernel of $f$ is a normal subgroup. Please look back at that problem before tackling this one.

Problem 90 (A homomorphism is an $n$-to-one map)

Let $f:G\to H$ be a homomorphism.

  1. Suppose that $\ker f$ has order $n$. If we know that $f(g)=h$ for some $g\in G$, prove that there are exactly $n$ different elements in $G$ that map to $h$, so we know that the preimage of $h$, namely $f^{-1}(h)$, is a set with $n$ elements. This shows that $f$ is an $n$-to-one map.
  2. Prove that $f$ is injective if and only if the kernel of $f$ is trivial, i.e. $\ker f = \{e\}$.
  3. Prove that if $f$ is surjective and the kernel of $f$ is trivial, then $f$ is an isomorphism.

Here are some comment's about these problems.

  1. This should follow without any additional work from a previous problem. Just figure out which problem.
  2. This is why in linear algebra we know that $A\vec x = b$ has a single solution if and only if the only solution to $A\vec x=\vec 0$ is $\vec x= 0$, which means the columns of $A$ are linearly independent. Finding the kernel, or null space, is crucial in linear algebra.
  3. This is why in linear algebra we know that when the kernel of a square matrix is trivial, then the matrix is invertible.

We now know that a homomorphism is an $n$-to-one map. This fact is basically a directly result of the fact that the kernel of a homomorphism is normal. The next exercise shows that every normal subgroup is the kernel of some homomorphism. This shows that studying normal subgroups is precisely equivalent to studying kernels of homomorphisms. We've actually been using the result below without every stating it formally. Given a Cayley graph, we can easily build a map from the Cayley graph to the corresponding identification graph using right cosets of $N$ by sending $a$ to $Na$. This exercise just has you shows that this map is indeed a homomorphism whose kernel is $N$.

Exercise (A Subgroup Is Normal If And Only If It Is The Kernel Of Some Homomorphism)

Prove that $N$ is a normal subgroup of $G$ if and only if $N$ is the kernel of some homomorphism $f:G\to H$ from $G$ to another group $H$.

Click to see a solution.

We already know that if $N$ is the kernel of a homomorphism, then it is normal. So one direction of this if and only if proof is complete.

If we know $N$ is normal, then we can let $H=G/N$ and define $f:G\to H$ by $f(g)=Ng$. This map is a homomorphism because we already showed that $f(ab)=N(ab)=(Na)(Nb) = f(a)f(b)$ when we showed that the set product is a binary operation on cosets of a normal subgroup. The kernel of this map is the set of elements $g\in G$ such that $f(g)=N$. This is precise the set of $g\in G$ such that $Ng=N$ which is true if and only if $g\in N$ by the properties of cosets. Hence the kernel of this map is $N$.

This next problem has you practice using Lagrange's theorem. Both facts in the problem should follow immediately from applying Lagrange's theorem and another observation. These facts are often considered corollaries of Lagrange's theorem.

Problem 91 (The Order Of An Element Divides The Order Of A Group)

Let $G$ be a finite group. Use Lagrange's theorem to prove the following two corollaries.

  1. Let $a\in G$. The order of $a$ divides the order of $G$.
  2. If $|G|=p$ for some prime $p$, then $G$ is cyclic.

We are now ready to state and prove what mathematicians call the first isomorphism theorem. We've seen the following result several times before, without every fully stating it. When we consider the dihedral group of order 8 and let $N$ be the set of rotations, the identification graph looked a lot like $\mathbb{Z}_2$. The map $f:D_8\to \mathbb{Z}_2$ defined by $f(g)=0$ if $g$ is a rotation and $f(g)=1$ if $g$ is a flip, is a homomorphism from $D_8$ to $\mathbb{Z}_2$. The kernel of this homomorphism is precisely the rotations $N$. So the factor group $G/N$ consists of two cosets and is isomorphic to $\mathbb{Z}_2$. We now formally state the first isomorphism theorem.

Here's a formal statement of the first isomorphism theorem. It's slightly different than the text's, and we'll talk about why it's different in class. The version in the text involves more notation, but is essentially equivalent to this version. The key you need to proving this theorem comes from some of the earlier problems today (which problem has you show that something is an isomorphism?).

Problem 92 (The First Isomorphism Theorem Proof)

Prove the First Isomorphism Theorem.

Theorem (The First Isomorphism Theorem)

Let $f:G\to H$ be a surjective homomorphism with kernel $K$. Because we know that $f(x)=f(y)$ for any $y\in Kx$ (elements in the same coset of the kernel have the same image under $f$), then we can define a map $\phi:G/K\to H$ by defining $\phi(Kg)=f(g)$. This map $\phi$ is always an isomorphism.

We'll start using this theorem almost every day from here on out, as this is one of the biggest ideas in abstract algebra. For now, just make sure you can prove it.

Exercise (The Integers Under Addition Are Isomorphic To The Positive Integers Under Multiplication)

The set $\mathbb{R}^+$ is the set of positive real numbers. Consider the two groups $G=(\mathbb{R},+)$ and $H=(\mathbb{R}^{+},\cdot)$. Show that these two groups are isomorphic by showing that the exponential function $f(x)=\exp(x)$ is a group isomorphism.

Click to see a solution.

You could prove this by showing that the map is a homomorphism, and that it is a bijection by producing the inverse (namely $g(x)=\ln x$) and proving that it is an inverse. We've already done this in class.

Let's instead use the first isomorphism theorem. We know that $\exp(a+b)=\exp(a)\exp(b)$ high school algebra, so $f$ is a homomorphism. Given $y\in \mathbb{R}^{+}$, we let $x=\ln y$ and then $\exp(x)=y$, so the map is surjective. The only value such that $f(x)=1$ is $x=0$, so the kernel is $K=\ker f = \{0\}$. We could stop here and note that this means $f$ is 1 to 1, i.e. injective, and hence a bijection. Alternately, we could notice that $G/K=G$ (the identification graph of $G/K$ is the same as $G$ since $|K|=1$) and the first isomorphism theorem states that $f:G/K\to H$ is an isomorphism.

Now that we have discussed how to take a large group $G$ and create a factor group $G/N$, it's time to work this process in reverse. Let's start with two small groups $G$ and $H$, and from them create a larger group from them by using the Cartesian product $G\times H = \{(g,h)\mid g\in G, h\in H\}$. To turn this into a group, we'll just use the group operation independently on each component. What we need to do today is to show this actually gives a group, learn how to graph such a group, and then analyze how we find the order of an element $(g,h)$ in the product $G\times H$ if we know the orders of $g$ and $H$ in their respective groups. First, let's get a formal definition. Feel free to read along in chapter 8 of your text.

Definition (External Direct Products $G\times H$ or $G\oplus H$)

Suppose that $G$ and $H$ are both groups. The cartesian product $G\times H$ is the set $$G\times H = \{(g,h)\mid g\in G, h\in H\}.$$ The external product of $G$ and $H$ is this Cartesian product $G\times H$ together with the group operation $(g_1,h_1)\cdot(g_2,h_2)=(g_1g_2,h_1h_2)$. We'll use the notation $G\times H$ of $G\oplus H$ to talk about the external direct product of $G$ and $H$. We can also define the external direct product of $n$ groups. The definition is analagous, where instead of having two components, we now have $n$ components, and we multiply two elements of the external direct product by performing the product componentwise.

Is there a difference between the notation $G\times H$ and $G\oplus H$? Yes. The notation $G\times H$ is called the external direct product. The notation $G\oplus H$ is called the direct sum. You will probably hear me use both interchangeably in class. These two concepts are exactly the same when looking at the external direct product, or direct sum, of two groups (or finitely many groups). The difference shows up when we consider the external product, or direct sum, of an infinite number of groups, in which case $\ds \prod G_i\neq \bigoplus G_i$. We will restrict ourselves to a finite product of groups, and for this reason we are free to use either notation as $G\times H=G\oplus H$. Feel free to read more on Wikipedia.

The first thing you should do is convince yourself that the external direct product is actually a group. This is a straightforward exercise that you should make sure you can do.

Exercise (The External Direct Product $G\oplus H$ is a Group of order $|G||H|$)

Prove that the external direct product $G\oplus H$ or $G\times H$ is a group. If both groups are finite, then show that the order of the external direct product is $|G||H|$.

Click to see a solution.

Let $G$ and $H$ be groups. The binary operation $(g,h)\times(a,b) = (ga,hb)$ is associative as we can compute $$((g,h)(a,b))(m,n)=(ga,hb)(m,n) = ((ga)m,(hb)n)$$ and similarly $$(g,h)((a,b)(m,n))=(g,h)(am,bn) = (g(am),h(bn)).$$ These two quantities are equal because the operation in both $G$ and $H$ is associative. The identity in $G\times H$ is simply $(e_g,e_H)$, and the inverse of $(g,h)$ is $(g^{-1},h^{-1})$. I'll let you show that these satisfy the requirements to be the identity and inverse.

If $G$ has order $|G|$ and $H$ has order $|H|$, and both are finite, then there are clearly $|G|$ choices for the first component, and $|H|$ choices for the second component. Hence the total number of elements in $G\times H$ is precisely $|G\times H|=|G||H|$.

Given a subgroup of $G$ and a subgroup of $H$, we can quickly create a subgroup of $G\times H$. This is what the next problem asks you to show. If you'd like a fun challenge, then prove that the converse of the following problem is true, or produce a counter example. Namely, if $C$ is a subgroup of $G\times H$, must it be true that $C=A\times B$ for some $A\leq G$ and $B\leq H$. First complete all the problems on this list, and then tackle this challenge.

Problem 72 (An External Direct Product Of Subgroups Is A Subgroup Of An External Direct Product)

Show that if $A$ is a subgroup of $G$ and $B$ is a subgroup of $H$, then $A\times B$ is subgroup of $G\times H$.

What does the Cayley graph of an external direct product look like? In particular if you know that $G$ and $H$ are both cyclic with generators $g$ and $h$, then what does the Cayley graph of $G\times H$ look like if we use the generators $(g,e_H)$ and $(e_G,h)$? The next problem has you draw several Cayley graphs of the product of cyclic groups.

Problem (Cayley Graphs Of External Direct Products Of Cyclic Groups)

Please complete the following: (Don't let the different notation $G\times H$ and $G\oplus H$ throw you off. They mean the exact same thing.)

  1. Draw the Cayley graph of $\mathbb{Z}_2\times\mathbb{Z}_2$ using the generating set $S=\{(1,0), (0,1)\}$.
  2. Draw the Cayley graph of $\mathbb{Z}_2\times\mathbb{Z}_3$ using the generating set $S=\{(1,0), (0,1)\}$.
  3. Draw the Cayley graph of $\mathbb{Z}_2\oplus\mathbb{Z}_5$ using the generating set $S=\{(1,0), (0,1)\}$.
  4. Draw the Cayley graph of $\mathbb{Z}_3\oplus\mathbb{Z}_5$ using the generating set $S=\{(1,0), (0,1)\}$.
  5. Draw the Cayley graph of $\mathbb{Z}_2\times\mathbb{Z}_3\times\mathbb{Z}_5$ using the generating set $S=\{(1,0,0), (0,1,0),(0,0,1)\}$.
  6. Draw the Cayley graph of $U(15)$ using the generating set $S=\{7,11\}$. Which graph above does this look like?

What patterns did you see above when constructing Cayley graphs? We'll discuss what you saw in class. The next exercise has you compute the orders of a few elements in some external direct products, as it prepares you to tackle the problem after.

Exercise (Practice With Orders In External Direct Products)

In each part below, you are given an element $(g,h)$ and a group $G\oplus H$. Compute the order of $g$ in $G$, the order of $h$ in $H$, and the order of $(g,h)\in G\oplus H$.

  1. $(1,2)\in \mathbb{Z}_2\times\mathbb{Z}_3$
  2. $(1,2)\in \mathbb{Z}_6\times\mathbb{Z}_4$
  3. $(1,2)\in \mathbb{Z}_6\times\mathbb{Z}_8$
  4. $(10,20)\in \mathbb{Z}_{4000}\times\mathbb{Z}_{600}$

Click to see a solution.

  1. We know $|1| = 2$ and $|2|=3$, and we can compute $(1,2)^k$ for each $k$ from $1$ to $6$ to obtain the sequence $((1,2),(0,1),(1,0),(0,2),(1,1),(0,0))$. This shows that $|(1,2)|=6$.
  2. We know $|1| = 6$ and $|2|=2$, and we can compute $(1,2)^k$ for each $k$ from $1$ to $6$ to obtain the sequence $((1,2),(2,0),(3,2),(4,0),(5,2),(0,0))$. This shows that $|(1,2)|=6$.
  3. We know $|1| = 6$ and $|2|=4$. Computing $(1,2)^k$ for each $k$ from $1$ to $12$ will show that the order is 12. Alternately, notice that in the product $(1,2)^k$, the first component will only equal 0 when $k$ is multiple of 6. Similarly, the second component will only be 0 when $k$ is a multiple of $4$. The number 12 is the smallest number for which both components will equal 0.
  4. We know $|10| = 400$ and $|20|=30$. In the product $(10,20)^k$, the first component will only equal 0 when $k$ is multiple of 400, and the second component will only be 0 when $k$ is a multiple of $30$. The least common multiple of 400 and 30 is 1200, which is the order of $(10, 20)$

Did you see in the exercise that the order of $(g,h)$ is the least common multiple of $|g|$ and $|h|$? The next problem has you prove this fact in general.

Problem 73 (The Order Of An Element In An External Direct Product Is The Least Common Multiple Of The Orders Of The Elements)

If $g\in G$ has order $n$ and $h\in H$ has order $m$, prove that the order of $(g,h)$ in $G\times H$ is the least common multiple of $n$ and $m$.

For more problems, see AllProblems