20171115

Please Login to access more options.

Today

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.$$

Now that we've got a little practice with homomorphisms, we need to prove some general facts about them. In particular, it would be nice to know how homomorphisms interact with the identity, and how they interact with inverse. For the determinant map, we know that the determinant of the identity is 1, which means that the determinant of the identity matrix is the identity in $U(p)$. The homomorphism mapped the identity to the identity. In addition, if the determinant of a matrix $A$ is $k$, then the determinant of the inverse of $A$ is $k^{-1}$. This shows that the determinant of an inverse is the inverse of the determinant. The next problem has you show that these two facts are true for any homomorphism.

Problem 76 (Homomorphisms Preserve The Identity And Inverses)

Suppose that $f:G\to H$ is a homomorphism, and that $e_G$ and $e_H$ are the identities of $G$ and $H$ respectively.

1. Prove that $f(e_G)=e_H$.
2. In addition show that $f(a^{-1})=(f(a))^{-1}$.

Recall the determinant map. The special linear group was the set of things that got mapped to the identity in $U(p)$. In Linear algebra, you looked at linear transformations and defined the kernel of the linear transformation to be the set of vectors that mapped to zero. This is precisely the set of vectors that mapped to the additive identity. The set of vectors which map to the identity is a special set, that we now define to be the kernel of a homomorphism. The kernel is the center, or core, of a seed, and we'll soon see that understanding the kernel of a homomorphism is central, or core, to understanding most problems in mathematics. Please ask me in class to discuss applications of this idea that you have seen in other courses. You've been studying the kernel of a homomorphism for quite a while, without every putting a name to it.

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\}.$$

For any prime $p$, if we let let $G=GL(2,\mathbb{Z}_p)$ and we consider the homomorphism $f:G\to U(p)$ which is the determinant map, then we've already shown that the kernel of the determinant map, namely $f^{-1}(1)$, is the special linear group $SL(2,\mathbb{Z}_p)$. The kernel of the map was a subgroup of $G$. The next problem has you show this result in general, namely that the kernel of any homomorphism $f:G\to H$ is always a subgroup of $G$. Your proof should be almost identical to what you did for the special linear group.

Problem 77 (The Kernel Of A Homomorphism Is A Subgroup)

Suppose that $f:G\to H$ is a homomorphism and that $e_H$ is the identity in $H$. Prove that the kernel of $f$, namely $\ker f$ or $f^{-1}(e_H)$, is a subgroup of $G$.

For the rest of today, we'll be looking at the set products $aH$ and $Ha$ and what they physical mean in Cayley graphs. Once we can see these sets in Cayley graphs, we'll have a very visual way to describe the remainder of the ideas in this course. The sets $aH$ and $Ha$ are so crucial to the rest of this course that they have been given a name and are referred to as cosets. Here is a formal definition

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.

We have already seen cosets when working with matrices that have the same determinant. We've also seen cosets already when working with modular arithmetic. This next exercise has you practice this.

Exercise (Practice With Cosets Of $3\mathbb{Z}$)

Let $G=\mathbb{Z}$ and let $H=3\mathbb{Z}$, the multiples of $3$.

1. List the elements of $0+H$, $1+H$, $2+H$, $3+H$, $4+H$, $5+H$, $17+H$, and $-11+H$.
2. How many different sets did you get?

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$.

The identification graphs just described will generally be a smaller graphs than the original graph. Sometimes those graphs will themselves be Cayley graphs, and sometimes they won't. One of our goals right now is to determine under which conditions we'll obtain a Cayley graph after computing an identification graph.

Problem 78 (Exercise - Solution provided) (Practice With Identification Graphs On An Abelian Group)

Let $G = U(15)$. Consider the subgroups $A=\left<4\right> = \{1,4\}$ and $B= \left<14\right> = \{1,14\}$. We'll use the set $S=\{7,11\}$ to draw the Cayley graph of $G$.

1. Start by drawing the Cayley graph of $G$ with generators in $S$. You can check your answer with the Sage code at the end of this problem.
2. For each $g\in G$, compute the right cosets $Ag$ of $A$. Draw the identification graph of $G$ using right cosets of $A$. You should get a graph with 4 vertices (each vertex should have two numbers in it). The graph should look like the Cayley graph of $U(8)$ using the generating set $S=\{3,5\}$, shown in the sage code below.
3. For each $g\in G$, compute the left cosets $gA$ of $A$. Draw the identification graph of $G$ using left cosets of $A$.
4. For each $g\in G$, compute the right cosets $Bg$ of $B$. Draw the identification graph of $G$ using right cosets of $B$. Again you should get a graph with 4 vertices, however your graph should not be the same as that in part 2. You should obtain something similar to the graph of $U(10)$ using the generating set $S=\{3,9\}$, shown in the sage code below. Click "Evaluate" a few times as the way the computer displays this graph can change.
5. For each $g\in G$, compute the left cosets $gB$ of $B$. Draw the identification graph of $G$ using left cosets of $B$.
6. Why are the answer to 2 and 3 the same? Why are the answers to 4 and 5 the same?

n=15
S=[7,11]

Zn = Integers(n)
Un = [int(x) for x in Zn if gcd(ZZ(x), n) == 1]  #This creates Un
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()) 
print("Here is a graph of U("+str(n)+") using the generating set "+str(S))
CG.graphplot(color_by_label=True,edge_labels=True).show()

n=8
S=[3,5]

Zn = Integers(n)
Un = [int(x) for x in Zn if gcd(ZZ(x), n) == 1]  #This creates Un
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()) 
print("Here is a graph of U("+str(n)+") using the generating set "+str(S))
CG.graphplot(color_by_label=True,edge_labels=True).show()


n=10
S=[3,9]

Zn = Integers(n)
Un = [int(x) for x in Zn if gcd(ZZ(x), n) == 1]  #This creates Un
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()) 
print("Here is a graph of U("+str(n)+") using the generating set "+str(S))
CG.graphplot(color_by_label=True,edge_labels=True).show()

Problem 79 (Exercise - Solution Provided) (Practice With Identification Graphs On A Non Abelian Group)

Let $G$ be the automorphisms of the square, i.e. the dihedral group of order 8. Consider the subgroups $A=\left<R_{180}\right> = \{R_0,R_{180}\}$ and $B= \left<H\right> = \{R_0,H\}$. We'll use the set $S=\{R_{90}, V\}$ to draw the Cayley graph of $G$.

1. Start by drawing the Cayley graph of $G$ with generators in $S$. You can check your answer with the Sage code at the end of this problem.
2. For each $g\in G$, compute the right cosets $Ag$ of $A$. Draw the identification graph of $G$ using right cosets of $A$.
3. For each $g\in G$, compute the left cosets $gA$ of $A$. Draw the identification graph of $G$ using left cosets of $A$.
4. For each $g\in G$, compute the right cosets $Bg$ of $B$. Draw the identification graph of $G$ using right cosets of $B$.
5. For each $g\in G$, compute the left cosets $gB$ of $B$. Draw the identification graph of $G$ using left cosets of $B$.
6. Make a conjecture about what happens with identification graphs when $gA=Ag$.

R90="(1,2,3,4)"
V="(1,4)(2,3)"

S=[R90,V]

G=PermutationGroup(S)
G.cayley_graph().show(color_by_label=True)

Problem 80 (When Does $H=Ha$)

Let $H$ be a nonempty subset of a group $G$. Prove that $H$ is a subgroup of $G$ if and only if $Ha=H$ for every $a\in H$.

For more problems, see AllProblems