# 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

$2,4,8,16=3,6,12,24=11,22=9,18=5,10,20=7,14=1,2.$

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, then $f(a^{j-1})=e$, so $f(a)^{j-1}=b^{j-1}=e$.  This is a contradiction because $0.  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.)