Gracious Living

Homomorphisms, Generators, and Cyclic Groups
November 12, 2010, 16:07
Filed under: Algebra, Math | Tags: , , , ,

Last time we saw the group D_8 of symmetries of the square represented in terms of a single flip and a single rotation.  This time, I plan on going more deeply into what this means, and what it does for group theory.  Actually, I don’t really have a plan — basically I’m going to keep talking about things that seem useful until the post is done.  Who’s with me?

Let’s actually start out with a couple basic facts about groups — things you can prove from just the group axioms.  For instance, you know that there’s only one identity.  Why?  Let e and f be two identities.  Then ef=e because f is an identity — but ef=f because e is an identity.  So they’re equal, which means the identity is unique.  Similarly, an element only has one inverse: if g^{-1}_1 and g^{-1}_2 are both inverses for g, then g^{-1}_1=g^{-1}_1gg^{-1}_2=g^{-1}_2, because g cancels with either one.  It’s been a while since I read a textbook about this stuff, so I might throw in a short proof like this here and there if I say something nontrivial.  But there are lots of these little things you can prove — they’re sort of like trig identities.

Okay, so the next important concept is that of a homomorphism.  Don’t confuse this with “homeomorphism” — the prefixes are respectively Greek “homos,” meaning “the same,” and “homoios,” meaning “similar.”  A homomorphism is a structure-preserving function between groups: f:G\rightarrow H is a homomorphism if f(g\circ h)=f(g)\bullet f(h) for all g,h\in G, where \circ is the multiplication in G and \bullet is the multiplication in H.  So basically what it does is preserve the group multiplication, much like a continuous map of topological spaces preserves the topology.  Again, “preserve” is being used weakly here — the map between any two groups sending every element of the first to the identity of the second is a homomorphism.

The equivalent of a homeomorphism in group theory is just called an isomorphism.  This is a bijective homomorphism whose inverse is also a homomorphism.  Isomorphic groups really do have the same structure: all the isomorphism does, when you get down to it, is relabel the elements of the group.  An example is D_8 from yesterday.  We defined it as the group of symmetries of a square, but for a while I was talking about in terms of how it permuted the vertices, basically as a group of certain ways of moving letters around.  Alternatively, if I drew a coordinate system on the plane containing my square, I would have discovered that all the elements of the group were linear maps and could be represented by matrices, with the group composition being matrix multiplication.  These groups aren’t “the same,” but they work the same, and for math, that’s all we need.  I write G\cong H to indicate that G and H are isomorphic.

Here’s another example, and an important kind of group that I forgot to introduce last time.  It’s usually first seen as “clock arithmetic.”  Look at the numbers on a 12-hour clock: clearly, when it’s 8 hours from 7 o’clock, it’s not 15 o’clock, it’s 3 o’clock.  When it’s 12 hours from 3 o’clock, it’s 3 o’clock again.  If we allow ourselves to forget whether it’s day or night and what day it is, we have a group with 12 elements, whose operation is addition of hours, and whose identity is 12 o’clock.  This is called addition modulo 12.   Another way of thinking about it is by defining an equivalence relation on the integers, given by a\sim b if a-b is divisible by 12.  There are 12 equivalence classes, each containing a unique number from 0 to 11.  This is the remainder you get when you divide any element of the equivalence class by 12.  We say a+b=c\quad (\mod 12) if a+b is in the equivalence class containing c.  This is well-defined, and it gives you the same group as the clock.  We call this group \mathbb{Z}/12,\mathbb{Z}_{/12},\mathbb{Z}/12\mathbb{Z}, or \mathbb{Z}_{12}  (read as “z mod twelve,” “z mod twelve z,” or “z twelve”).  We can clearly do this for any number p instead of 12.

Now, if p is prime, \mathbb{Z}/p-\{0\}=\mathbb{Z}/p^\times also has a multiplicative structure.  You can’t do this when p is composite because you have nonzero things multiplying to 0, as in 4\times 3=0\quad(\mod 12), so multiplication won’t be closed.  (And, just to remind you, you don’t want to allow 0 because it has no multiplicative inverse.)  Let’s look at \mathbb{Z}/13^\times.  Take any element — say, 2 — and look at its successive powers — what you get when you multiply it by itself repeatedly.  Starting with 2, we get


Just by multiplying by 2, we’ve gone all the way through the group and back to 2!

A set of elements are generators for a group if every group element is a product of them and their inverses (as many times as we need, in whatever order we need).  This is a little like a basis for a topology: it’s a smaller set that gives you all the information you need.  Last time, we proved that D_8 was generated by its elements f and r.  We showed above that \mathbb{Z}/13^\times is generated by its element 2, and it’s clear that any additive group \mathbb{Z}/n is generated by the element 1.  If a group is generated by a single group, we call it a cyclic group. So every element of a cyclic group is of the form a^i, where a is a generator.

We defined the order of a group to be the number of elements in it.  In this case, I claim that every cyclic group of the same order is isomorphic.  Why?  Let a and b generate cyclic groups of order n.  Then a^n and b^n are the respective identities of their groups, and this is true for no smaller n besides 0.  Let f(a)=b; there is only one such f that is a homomorphism, because we must then have f(a^i)=b^i for all i.  If f(a^j)=b for any 1<j\le n, then f(a^{j-1})=e, so f(a)^{j-1}=b^{j-1}=e.  This is a contradiction because 0<j-1<n.  Thus, f is a bijection, and clearly its inverse, defined by f^{-1}(b)=a, is a homomorphism.  This proves that there’s only one cyclic group of a given order, up to (unique) isomorphism.

In particular, \mathbb{Z}/12\cong\mathbb{Z}/13^\times, and for any prime p, \mathbb{Z}/(p-1)\cong\mathbb{Z}/p^\times.  Surprising, isn’t it?  (To prove the second bit, we need something called Fermat’s Little Theorem, of which proofs are here and elsewhere.)

2 Comments so far
Leave a comment

[…] Last time, we talked about homomorphisms (functions between groups that preserve the group operation), isomorphisms (bijections that are homomorphisms both ways), generators (elements which give you the whole group through inversion and multiplication), and cyclic groups (groups generated by a single element, which all work like modular arithmetic).  Let me start with two factoids I should have mentioned last time.  We can get a cyclic group generated by an element , but without any requirement that .  So the elements of the group are , and they’re all distinct.  This group is isomorphic to , the integers under addition!  In this sense, we call the infinite cyclic group.  As expected, there aren’t “any other” infinite cyclic groups: for example, no rational generates every other rational through repeated addition, nor does any real generate every other real. […]

Pingback by Subgroups and Symmetric Groups « Gracious Living

[…] 16 11 2010 Today we’re going to take the abstract group machinery we’ve been building up, and unleash it on some sets. When mathematicians say that […]

Pingback by Group Actions « Gracious Living

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: