20161114

Please Login to access more options.

Today

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

Let's now turn our attention back to homomorphisms. We'll see very soon that there is a big connection between homomorphisms and cosets. For today, let's just focus on some more properties of homomorphisms, namely that homomorphisms preserve subgroups. If you've forgotten the definition of the image of a set under a function, then here is a reminder.

Definition (Definition.The image of a function $f(A)$)

Let $f:G\to H$ be a function and let $A$ be subset of $G$. Recall that the image of $A$ under $f$ is the set $$f(A)=\{f(a)\mid a\in A\}.$$

If the set $A$ is a subgroup, then we would expect that a homomorphism maps the subgroup $A$ to a subgroup of $H$. This is precisely what the next problem asks you to show.

Problem 81 (The Image Of A Subgroup Under A Homomorphism Is A Subgroup)

Suppose that $f:G\to H$ is a homomorphism. Let $A$ be a subgroup of $G$. Show that $f(A)$ is a subgroup of $H$.

We now generalize some facts that we learned about the determinant map. We have already shown that the determinant map breaks up the set of possible matrices into equally sized cosets, where each coset consists of matrices of the same determinant. The next problem has you show that this property was not dependent on the determinant map, rather it has to do with the fact that the special linear group is a subgroup, and nothing more. You should find that your work on the problem The Set Product $Ha$ Preserves Determinants can almost be copied directly over to solve the next problem.

Problem 82 (Properties Of Cosets)

Let $G$ be a group, and let $H$ be a subgroup of $G$. Let $a,b \in G$. Prove the following:

1. The function $f:H\to Ha$ defined by $f(h)=ha$ is a bijection.
2. We have $|H|=|Ha|$.
3. We know $b\in Ha$ if and only if $Hb=Ha$.

We've seen that when we create an identification graph of $G$ using right cosets of $H$, we sometimes get a Cayley graph, and we sometimes don't. Today, we'll be focusing on the question, "When is an identification graph of $G$ using cosets of $H$ another Cayley graph?" To answer this question, we'll need to explore the properties of cosets in depth.

When working with the determinant map $f:GL(2,\mathbb{Z}_p)\to U(p)$, we have already shown that the kernel of this map is the special linear group $K=SL(2,\mathbb{Z}_p)$. We've also shown that the coset $Ka$ equals the set of all matrices whose determinant matches the determinant of $a$. Another way to say this is that $Ka$ equals the set of values $b\in G(2,\mathbb{Z}_p)$ such that $f(b)=f(a)$. A similar argument would show that $aK$ is the exact same set, which means we have $Ka=aK$. The next problem has you show that for any homomorphism $f:G\to H$ with kernel $K$, we always have $Ka=aK$ and that $Ka$ equals the set of $b\in G$ such that $f(b)=f(a)$.

Problem 83 (The Right And Left Cosets Of The Kernel Are Equal)

Suppose that $f:G\to H$ is a homomorphism. Let $K$ be the kernel of $f$ and let $a\in G$. Prove the following:

1. The right coset $Ka$ equals the set of values $b\in G$ such that $f(b)=f(a)$, or symbolically we have $$Ka = \{b\in G\mid f(b)=f(a)\} = f^{-1}(f(a)).$$
2. The left coset $aK$ equals the same set $\{b\in G\mid f(b)=f(a)\}$, which means the left and right cosets are the same or $Ka=aK$.

In the previous problem, we saw that any time $K$ is the kernel of a homomorphism, we can talk about left or right cosets and obtain the exact same result, namely $Ka=aK$ for every $a\in G$. Any time a subgroup of $G$ satisfies this result, we'd like to have a special name for that subgroup. We call these subgroups normal.

Definition (Normal Subgroup $N\trianglelefteq G$)

We say that a subgroup $N$ of $G$ is a normal subgroup of $G$ if for each $a\in G$ the right coset $Na$ and left coset $aN$ are equal, so we have $Na=aN$ for every $a\in G$. We write $N\trianglelefteq G$ to mean that $N$ is a normal subgroup of $G$.

Before we can move too much farther, we need to prove some additional properties about cosets. We have already shown the following for a subgroup $H$ of the group $G$ with $a,b\in G$:

• We know $a\in Ha$.
• We know $Ha=H$ if and only if $a\in H$.
• We know $b\in Ha$ if and only if $Hb=Ha$.
• The function $f:H\to Ha$ defined by $f(h)=ha$ is a bijection.
• We have $|H|=|Ha|$.

Let's add to this list of properties.

Problem 84 (Properties Of Cosets Part Two)

Let $H$ be a subgroup of $G$. Let $a,b\in G$. Prove the following facts about cosets.

1. We have $Ha=Hb$ if and only if $ab^{-1}\in H$.
2. We must have $Ha=Hb$ or $Ha\cap Hb=\emptyset$.
3. We have $Ha=aH$ if and only if $aHa^{-1}=H$.

For more problems, see AllProblems