20171113

Please Login to access more options.

Today

Problem 68 (The Orders Of Elements Match In Isomorphic Groups)

Suppose that $f:G\to H$ a group isomorphism. Suppose that $f(g)=h$. Prove that the order of $g$ and the order of $h$ are the same, in other words show that $|g|=|h|$. In particular, since the only elements of order 1 in each group are the identities $e_G\in G$ and $e_H\in H$, then we must have $f(e_G)=e_H$.

The next exercise has you compute the orders of a few elements in some external direct products, as it prepares you to tackle the problem after.

Exercise (Practice With Orders In External Direct Products)

In each part below, you are given an element $(g,h)$ and a group $G\oplus H$. Compute the order of $g$ in $G$, the order of $h$ in $H$, and the order of $(g,h)\in G\oplus H$.

1. $(1,2)\in \mathbb{Z}_2\times\mathbb{Z}_3$
2. $(1,2)\in \mathbb{Z}_6\times\mathbb{Z}_4$
3. $(1,2)\in \mathbb{Z}_6\times\mathbb{Z}_8$
4. $(10,20)\in \mathbb{Z}_{4000}\times\mathbb{Z}_{600}$

Did you see in the exercise that the order of $(g,h)$ is the least common multiple of $|g|$ and $|h|$? The next problem has you prove this fact in general.

Problem 73 (The Order Of An Element In An External Direct Product Is The Least Common Multiple Of The Orders Of The Elements)

If $g\in G$ has order $n$ and $h\in H$ has order $m$, prove that the order of $(g,h)$ in $G\times H$ is the least common multiple of $n$ and $m$.

Given $m,n\geq 2$, how many elements are in $GL(2,\mathbb{Z}_n)$? In other words, how many different matrix encryption keys are there, given the size of the matrix and what coefficients we'll allow. This is a nontrivial problem, but its answer provides a key to knowing how to decrypt a message by brute force. We'll find that knowing something about the special linear groups will help us answer this question. First, let's make an observation that should simplify some computations if we assume that $n$ is prime.

Exercise (The Order Of $U(p)$ When $p$ Is Prime)

If $p$ is a prime, then what is the order of $U(p)$? In other words, what is the Euler $\varphi$ function at $p$, namely what is $\varphi(p)$.

Problem 74 (Conjecturing The Order Of General Linear Groups)

Let's focus on 2 by 2 matrices with entries in $\mathbb{Z}_p$ where $p$ is a prime. So we let $p$ be a prime and consider $G = \text{GL}(2,\mathbb{Z}_p)$.

1. Here is a list of all 81 of the 2 by 2 matrices with entries in $\mathbb{Z}_3$. Underneath that list you'll see the determinant of each matrix has already been computed for you. How many matrices have determinant 1, in other words how many matrices are in $\text{SL}(2,\mathbb{Z}_3)$. How many matrices are invertible, i.e. how many matrices are in $\text{GL}(2,\mathbb{Z}_3)$? What patterns did you use to help you count?

   • 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)
     show(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)
     show(table(dets))
     
2. This sage code below repeats the above with $n=5$. Use this to count how many matrices have determinant 1 (are in $\text{SL}(2,\mathbb{Z}_5)$) and then how many are invertible (are in $\text{GL}(2,\mathbb{Z}_5)$). What patterns did you use to help you count?

   • n=5  #Change this number as needed. 
     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)
     #show(table(matrices))  #Uncomment this line (remove the #) if you want to see all the 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)
     show(table(dets))
     

3. You can modify the sage code above to let $n=7, 11, 13,$ etc. How many matrices are in $\text{SL}(2,\mathbb{Z}_7)$ and $\text{GL}(2,\mathbb{Z}_7)$? What patterns did you use to help you count?
4. If $p$ is a prime, make a conjecture about the order of $\text{SL}(2,\mathbb{Z}_p)$ and the order of $\text{GL}(2,\mathbb{Z}_p)$. You do not have to prove your conjecture.

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