20171106

Please Login to access more options.

Today

There is no prep required for today. The point is that you should be using your time to prepare for and take the exam.

I will be introducing the last half of the semester today in class. We'll be using the time to introduce many of the patterns that we'll be proving during the last half of the semester. The hope is that today should be a fun introduction to the rest of the semester.

What's the goal today:

1. Start by defining the external direct product $G\times H = G\oplus H$. Then draw the Cayley graphs of $\mathbb{Z}_3\oplus \mathbb{Z}_4$. We can build large groups by combining small groups in this way.
   • Question: Given a large group, can we decompose it into an external direct product of simpler groups. We'd like to know what the most basic building blocks of groups are.
   • This question has two answers, based on whether or not the group is Abelian. We'll look at some examples.
2. We'll draw the Cayley graph of $\mathbb{Z}$ in several different ways.
   • There is an obvious map from $\mathbb{Z}$ to $\mathbb{Z}_n$, namely $f:\mathbb{Z}\to\mathbb{Z}_n$ defined by $f(x) = x\bmod n$. This function between groups is what we will be generalizing to develop the rest of the semester.
   • For a subgroup $H=n\mathbb{Z}$, we'll define cosets($a+H$), identification graphs, and quotient groups ($G/H=\mathbb{Z}/n\mathbb{Z}$).
   • Why use the notation $G/H$ for quotient groups? What does $G\approx H\times G/H$ mean?
3. We'll draw the Cayley graph of $U(n)$ for $n$ from 2 to 60. Software makes this automatic.
   • Look for symmetries, in particular we'll be finding cosets and making identification graphs.
   • Construct a map from the group to the identification graph, called a homomorphism.
   • Discuss the fundamental theorem of finitely generated abelian groups.
4. Now construct the Cayley graph of some non-abelian groups.
   • Look for symmetries, in particular we'll be finding both right and left cosets and making identification graphs.
   • Construct a map from the group to the identification graph.
   • Under what situations does the identification graph happen to be the Cayley graph of a group?

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.

We used Cayley graphs to give us a visual representation of the span of a set of permutations. Similarly, we can use Cayley graphs to help us visualize groups. The definition is very similar.

Definition (Cayley Graph Of A Group)

Let $G$ be a group that is generated by a set $S$. The Cayley graph of $G$ generated by $S$, which we'll write as $(G,S)$, is a colored directed graph that satisfies the the following three properties:

1. The vertex set is $G$. Each vertex corresponds to an element of the group.
2. Each element $s \in S$ is assigned a unique color which we'll denote by $c_s$.
3. For each color $c_s$, and each vertex $g$, we draw the colored arrow $(g ,s g)$.

Most of the time we assume that $S$ does not contain the identity. However, if it does contain the identity, then we just draw a colored loop $(g,g)$ at each vertex.

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.

If the Cayley graphs of two groups are isomorphic, we would expect the groups to be isomorphic as well. We'll prove this eventually, but for now let's just use this fact to start sorting out isomorphic groups. The next problem has you look at 60+ Cayley graphs and visually start sorting groups.

Problem (Cayley Graphs and Isomorphisms between $\mathbb{Z}_n$ and $U(m)$)

In this problem, we will construct Cayley graphs of $\mathbb{Z}_n$ and $U(n)$ for many values of $n$. Our goal is to build a table of groups, where each row of the table consists of isomorphic groups.

1. Start by drawing the Cayley graphs of $\mathbb{Z}_2$, $\mathbb{Z}_3$, $\mathbb{Z}_4$, and $\mathbb{Z}_5$ using $x=1$ as the generator. What pattern do you notice?
2. If you wanted to draw the Cayley graph of $\mathbb{Z}_{50}$ using $x=1$ as the generator, what would your graph look like?
3. If $\mathbb{Z}_n\cong\mathbb{Z}_m$, what do you know about $n$ and $m$?
4. The two blocks of sage code below will draw Cayley graphs of $U(n)$ for each $n$ from 2 to 60. Evaluate each block of code now.

   for n in (2..30):
    Zn = Integers(n)
    Un = [x for x in Zn if gcd(ZZ(x), n) == 1]  #This creates Un
    show(table(["U("+str(n)+") has order "+str(len(Un))+
                ".The elements, with orders below them, are listed below."]))
    orders=[x.multiplicative_order() for x in Un] #This computes the multiplicative order of each element.
    show(table([Un,orders])) #This creates a table of elements (top row) and their orders (bottom row).
   
    Un = [int(x) for x in Zn if gcd(ZZ(x), n) == 1]  #This creates Un
    S=Zn.unit_gens()
   
    CG=DiGraph([Un,lambda i,j:False])
    for k in S:
     CGk=DiGraph([Un,lambda i,j: mod(j*inverse_mod(i,n),n)==k])
     for u,v,l in CGk.edges():
      CGk.set_edge_label(u,v,k)
     CG.add_edges(CGk.edge_iterator()) 
   
    CG.graphplot(color_by_label=True,edge_labels=True).show()
   

   for n in (31..60):
    Zn = Integers(n)
    Un = [x for x in Zn if gcd(ZZ(x), n) == 1]  #This creates Un
    show(table(["U("+str(n)+") has order "+str(len(Un))+
                ".The elements, with orders below them, are listed below."]))
    orders=[x.multiplicative_order() for x in Un] #This computes the multiplicative order of each element.
    show(table([Un,orders])) #This creates a table of elements (top row) and their orders (bottom row).
   
    Un = [int(x) for x in Zn if gcd(ZZ(x), n) == 1]  #This creates Un
    S=Zn.unit_gens()
   
    CG=DiGraph([Un,lambda i,j:False])
    for k in S:
     CGk=DiGraph([Un,lambda i,j: mod(j*inverse_mod(i,n),n)==k])
     for u,v,l in CGk.edges():
      CGk.set_edge_label(u,v,k)
     CG.add_edges(CGk.edge_iterator()) 
   
    CG.graphplot(color_by_label=True,edge_labels=True).show()
   
5. For each $n$ between 2 and 60, use a Cayley graph to determine if $U(n)$ is isomorphic to $U(m)$ for some $m<n$. Place your results in a table. If $U(n)$ is not isomorphic to any previous group on your table, put it in the left column of the table as a new row. Otherwise, place $U(n)$ to the right of the corresponding $U(m)$ to which it is isomorphic. If $U(n)$ has a single generator, add the appropriate $\mathbb{Z}_m$ to your table as well. Each row in your table should consists of isomorphic groups, and groups on different rows should not be isomorphic to each other. I've already done up through $U(12)$ in the table below, but I suggest you start at $U(2)$ and check that the table below is correct. $$\begin{array}{|c|c|} \hline \text{Group}&\text{Isomorphic Groups}\\ \hline U(2)&\mathbb{Z}_1, \\ U(3)&\mathbb{Z}_2, U(4), U(6),\\ U(5)&\mathbb{Z}_4, U(10), \\ U(7)&\mathbb{Z}_6, U(9), \\ U(8)&U(12)\\ U(11)&\mathbb{Z}_{10} \\ \vdots&\vdots\\ \end{array} $$
   • When you encounter a graph that is not generated by a single element, compare it to previous graphs that you've already seen. How could you make the new graph by combining previous graphs? For example, the graph of $U(8)$ looks like a bunch of graphs of $\mathbb{Z}_2$. The graph of $U(15)$ looks like two copies of $\mathbb{Z}_4$ connected with $\mathbb{Z}_2$'s. The first 5 new graphs (not generated by a single element) that you should encounter after $U(12)$ are at 15, 21, 24, 32, and 33.

Definition (The Product Of A Set And An Element)

Let $H$ be a subset of a group $G$ and let $a\in G$. Then we define the product $Ha$ and $aH$ to be the sets $$Ha = \{ha \mid h\in H\}\quad \text{and}\quad aH=\{ah\mid h\in H\}.$$ If the group $G$ is Abelian, then we generally use the operation $+$ instead of $\cdot$, and so we'll write $H+a$ instead of $Ha$ and we'll write $a+H$ instead of $aH$. However, since the operation is commutative, we know that $a+h=h+a$, and so we have $$H+a = \{h+a \mid h\in H\} = \{a+h\mid h\in H\}=a+H.$$

Definition (Cosets $Ha$ and $aH$)

Let $G$ be a group and let $H$ be a subgroup of $G$. Let $a\in G$. We say that the set product $aH$ is a left coset of $H$ and the set product $Ha$ is a right coset of $H$. Remember that when the group is Abelian and we use the symbol $+$ to represent the group operation, then we write $a+H$ for the left cosets and $H+a$ for the right cosets.

Definition (Identification Graph Using Cosets)

Let $G$ be a group, and let $\mathcal{G}=(G,S)$ be the Cayley graph of $G$ using the elements in $S$ to construct the colored arrows. Let $H$ be a subgroup of $G$. The identification graph of $G$ using the right cosets of $H$ is a colored directed graph such that

• The set of vertices is the set of right cosets $\{Ha\mid a\in G\}$, and
• We draw a colored arrow from the coset $Ha$ to the coset $Hb$ if and only if there exists a colored arrow $(c,d)$ with $c\in Ha$ and $d\in Hb$ in the original Cayley graph.

If instead of using right cosets, we used left cosets $aH$ as the vertices, then we'd call the graph the identification graph of $G$ using the left cosets of $H$.

Problem (Visualizing Cosets In A Cayley Graph)

The graph below is the Cayley graph of a group of order 12. A multiplication table for this group would consist of 144 entries. On this problem, we will visually construct the cosets of several subgroups of $G$ to illustrate how the cosets create a partition of $G$. Your goal is to understand visually the difference between right cosets $Hg$ and left cosets $gH$. You will need 4 colors to complete this problem.

1. Let $H=\left<a\right> = \{e,a,a^2\}$. Compute all the right cosets $Hx$ of $H$ for $x\in G$. You should obtain 4 different right cosets. Use the graph below on your left and color the vertices so that two vertcies are colored the same if and only if they are in the same right coset. Then repeat this with the left cosets $gH$ of $H$, and color your vertices in the graph on the right.
   
2. Now let $H=\left<b\right> = \{e,b\}$ and repeat part 1. Because $|H|=2$, you should obtain 6 cosets.
   
3. Now let $H= \{e,b,i,k\}$ and repeat part 1. Because $|H|=4$, you should obtain 3 cosets.
   
4. Now draw the 6 identification graphs obtained by considering either right cosets or left cosets for each of the subgroups above. You should notice that the only identification graph that is a Cayley graph is the last one where $H= \{e,b,i,k\}$. This happens precisely because the left and right cosets are the same, namely $gH=Hg$ for every $g\in G$. This is not a coincidence.

Definition (Group Homomorphism)

Let $(G,\cdot)$ and $(H,\times)$ be groups. We say that the function $f:G\to H$ is a group $\textdef{homomorphism}$ if $f$ preserves the group structures, which means $f(a\cdot b)=f(a)\times f(b)$ for every $a,b\in G$.

Definition (Kernel Of A Homomorphism)

The kernel of a homomorphism $f:G\to H$ is the set of elements in $G$ that are mapped to the identity $e_H\in H$. In symbols, we'll write the kernel of $f$ as $$\ker(f)=f^{-1}(e_H) = \{g\in G\mid f(g)=e_H\}.$$

Cayley Tables

H = DihedralGroup(4)
print(H.cayley_table())
H.cayley_graph().show(color_by_label=True)

General Linear Groups

n=3
matrices=[];
for i in [0..n-1]:
 for j in [0..n-1]:
  tempmatrices=[]
  for k in [0..n-1]:
   for l in [0..n-1]:
    tempmatrices.append(matrix(2,2,[i,j,k,l]))
  matrices.append(tempmatrices)
html.table(matrices)

dets=[];
for i in [0..n-1]:
 for j in [0..n-1]:
  tempdets=[]
  for k in [0..n-1]:
   for l in [0..n-1]:
    tempdets.append(matrix(2,2,[i,j,k,l]).det().mod(n))
  dets.append(tempdets)
html.table(dets)

Here's a Cayley graph of $GL(2,\mathbb{Z}_3)$.

g1 =  GL(2,3)
d1=g1.cayley_graph()                                                 
d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=False)   

d1.show3d(color_by_label=True, vertex_size=0.03, vertex_labels=False)

Cayley Graphs of Presentations

We've seen presentations before. The dihedral group of order $8$ has the presentation $$\left<a,b\mid a^4=b^2=(ab)^2=e \right>.$$ We can get all the other dihedral groups by changing the 4 on $a^4$ to an $n$, namely $$\left<a,b\mid a^n=b^2=(ab)^2=e \right>.$$ What happens if we change some of the other parts? What's the Cayley graph of the following: $$\left<a,b\mid a^3=b^2=(ab)^3=e \right>$$ $$\left<a,b\mid a^4=b^2=(ab)^3=e \right>$$ $$\left<a,b\mid a^5=b^2=(ab)^3=e \right>$$ $$\left<a,b\mid a^6=b^2=(ab)^3=e \right>$$ $$\left<a,b\mid a^3=b^2=(ab)^4=e \right>$$ $$\left<a,b\mid a^4=b^2=(ab)^4=e \right> (\text{Infinite})$$ $$\left<a,b\mid a^5=b^2=(ab)^4=e \right>$$ $$\left<a,b\mid a^6=b^2=(ab)^4=e \right>$$

The answers to the questions above is non trivial, and we won't be able to answer them all in our course. Here's a few.

$$\left<a,b\mid a^3=b^2=(ab)^3=e \right>$$

g1 =  PermutationGroup(["(1,2,3)(4,5,6)(7,8,9)(10,11,12)","(1,12)(2,4)(3,9)(6,7)(8,10)(5,11)"])    
d1=g1.cayley_graph()                                                 
d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=True)   

g1.subgroups()


g1 =  PermutationGroup(["(1,2,3)(4,5,6)(7,8,9)(10,11,12)","(1,12)(2,4)(3,9)(6,7)(8,10)(5,11)","(1,6)(2,8)(3,11)(4,10)(5,9)(7,12)", "(1,7)(2,10)(3,5)(4,8)(6,12)(9,11)"])    
d1=g1.cayley_graph()                                                 
d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=True)   

g1 =  PermutationGroup(["(1,2,3)(4,5,6)(7,8,9)(10,11,12)","(1,12)(2,4)(3,9)(6,7)(8,10)(5,11)", "(1,7)(2,10)(3,5)(4,8)(6,12)(9,11)"])    
d1=g1.cayley_graph()                                                 
d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=True)
d1.show3d(color_by_label=True, vertex_size=0.03, vertex_labels=True)

Here's the graph of $$\left<a,b\mid a^5=b^2=(ab)^3=e \right>.$$

g1 =  PermutationGroup(["(1,2,3,4,5)","(1,2)(3,4)"])
d1=g1.cayley_graph()                                                 
d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=False)   


d1.show3d(color_by_label=True, vertex_size=0.03, vertex_labels=False)

Subgroups

D = AlternatingGroup(5)
D.cayley_graph().show(color_by_label=True)
for K in D.conjugacy_classes_subgroups():
 K.cayley_graph().show(color_by_label=True)

For more problems, see AllProblems