20131108

Please Login to access more options.

Today

Please make sure you have spent at least 10 minutes with each of these problems.

1. If you don't get this on your first go through the problems, please make sure you come back to this one a few times before class. This is one of the big ideas for the rest of the semester.
2. See the hints if you are stuck.
3. The proof is almost identical to what you did in class on Wednesday to prove that $SL(2,\mathbb{Z}_p)$ is a subgroup.
4. You start with a Cayley graph with 8 elements, and then combine terms to create a graph with 4 elements. You do this 4 times.
5. Very similar to 4, except now the group is not Abelian. Something odd happens on the last few graphs.
6. This is another problem to help you practice with subgroups.
7. Please make sure you look at open problem 4, and if you have time look at 3 as well.

Thanks for your work.

You should have noticed in the problem Conjecturing The Order Of General Linear Groups that the number of matrices with determinant 1 always equals the number of matrices with a fixed determinant $k$. What we would like to do next is find a nice way to prove this. To do so, we first need to talk about the product of a set and an element. This will allow us to take any matrix $a$ and multiply it by each matrix with determinant 1 to obtain all matrices whose determinants match $a$. Here's the formal definition of the product of a set and an element.

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

Problem 75 (The Set Product $Ha$ Preserves Determinants)

Let $m=2$ and let $p$ be a prime (it could be any integer, but $U(p)$ is easier to understand when $p$ is prime). Let $H=\text{SL}(2,\mathbb{Z}_p)$ and $G=\text{GL}(2,\mathbb{Z}_p)$. Let $a\in G$, so $a$ is a 2 by 2 invertible matrix. Recall that the set $Ha$ is the set $$Ha=\{ha\mid h\in H\},$$ so to obtain an element in $Ha$, we just take a matrix $h$ with determinant 1 and then multiply it on the right by the matrix $a$.

1. Let $b\in GL(2,\mathbb{Z}_p)$. Prove that $b\in Ha$ if and only if $\det(b)=\det(a)$.
   • When you prove if $b\in Ha$ then $\det(b)=\det(a)$, you'll show that every matrix in $Ha$ has the same determinant as $a$.
   • When you prove if $\det(b)=\det(a)$ then $b\in Ha$, you'll show that every matrix with the same determinant as $a$ must be in $Ha.$
2. Prove that the function $f:H\to Ha$ defined by $f(h)=ha$ is a bijection. (What is the inverse of multiplying on the right by $a$?)
3. Explain why $|H|=|Ha|$, in other words the number of matrices whose determinant equals 1 is the same as the number of matrices whose determinant equals $\det(a)$.

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 (Continue Working On Open Problems)

Please look at the Open Problems list, and continue working on these. In your preparation, please tell me which of the problems on the list you would feel comfortable presenting to the class. When we have a critical mass of students ready to present each problems, we'll discuss it in class (sometimes with a presentation, sometimes with just a discussion).

For more problems, see AllProblems