Please Login to access more options.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
Take the exam. See you Monday. No class.
When two groups are isomorphic, they must have the same order because the function $f$ is a bijection. However, not only do two isomorphic groups need to have the same cardinality, but in addition the bijection creates a correspondence between elements of the same order. Each group must have the same number of elements of each order, and any isomorphism must map an element of order $k$ to an element of order $k$. The next problem has you prove this.
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$.
Click here to see a partial proof that's missing one piece.
Suppose that $f:G\to H$ is an isomorphism and that $e_G$ and $e_H$ are the identities in $G$ and $H$ respectively. We first show that $f(e_G)=e_H$. Note that $e_Ge_G=e_G$. Apply $f$ to both sides to obtain $f(e_G)f(e_G)=f(e_G)$. Since $f(e_G)=f(e_G)e_H$, we now have $f(e_G)f(e_G)=f(e_G)\cdot e_H.$ Cancelling $f(e_G)$ from the left of both sides gives $f(e_G)=e_H$ as desired.
We now prove that if $a$ has order $n$, then $f(a)$ must have order $n$ as well. Suppose $a\in G$ has order $n$. This means that $n$ is the smallest positive integer such that $a^n=e_G$, or that $aa \cdots a=e$ (repeated $n$ times). If we apply $f$ to both sides of this equation, then we see that $f(a)f(a)\cdots f(a)=f(e_G)$. This means that $f(a)^n=f(e_G)$. Since we know $f(e_G)=e_H$, then we have shown $f(a)^n=e_H$ is the identity. This means the order of $f(a)$ must equal $n$. $\square$
What's missing? Pay close attention to the definition of order.
Problem 69 (Cayley Tables And Isomorophisms On A Group Of Order 4)
In the problem Orders Of $\mathbb{Z}_n$ And $U(n)$ And Their Elements we computed the orders of $U(n)$ of $n$ from 2 to 10. The groups $U(5)$, $U(8)$, and $U(10)$ all have order 4 (they have four elements). For $U(5)$, we can construct a multiplication table (called a Cayley table) that represents the binary operation of the group. We create this table exactly as we created the times tables in grade school, where we put the product $ab$ in the row corresponding to $a$ and the column corresponding to $b$. The table for $U(5)$ is shown below. $$\begin{array}{c|cccc} \cdot \text{ mod } 5 & 1&2&3&4 \\ \hline\hline 1 & 1&2&3&4 \\ 2 & 2&4&1&3 \\ 3 & 3&1&4&2 \\ 4 & 4&3&2&1 \\ \end{array}$$
- Construct a multiplication table, i.e. Cayley table, for $U(8)$ and $U(10)$. Which of these groups is isomorphic to $U(5)$?
- Let $G = \{a,b,c,d\}$ and $H=\{r,s,t,u\}$ and define the operation $*$ on $G$ in the table on the left below, and the operation $\times$ on $H$ by the table on the right below. $$ \begin{array}{c|cccc} * & a&b&c&d \\ \hline\hline a & a&b&c&d \\ b & b&d&a&c \\ c & c&a&d&b \\ d & d&c&b&a \\ \end{array} \quad\quad\quad \begin{array}{c|cccc} \times & r&s&t&u \\ \hline\hline r & t&u&r&s \\ s & u&t&s&r \\ t & r&s&t&u \\ u & s&r&u&t \\ \end{array}.$$ For each group, which element is the identity element? Which group is isomorphic to $U(8)$?
- Let $K=\{1,-1,i,-i\}$, which is a subset of the complex numbers (recall that $i=\sqrt{-1}$ and $i^2=-1$). Construct a multiplication table for $K$, and show that $K$ is isomorphic to one of the groups above.
To show that two groups are isomorphic, we must show that there is a bijection between them that preserves the group structures. In linear algebra, we encounter maps that preserve the group structure, but are not necessarily bijections. We called such maps linear transformations in linear algebra. In a general group setting, we call these maps homomorphisms. Here's a formal definition.
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$.
When we want to know if a matrix is invertible, or serves as a valid encryption key, we can discover this by computing the determinant. If the determinant of the matrix is non zero, has a multiplicative inverse, then we can invert this matrix. We shows this was true as well even when working with matrix encryption mod $n$.
Problem 70 (The Determinant Map Is A Homomorphism)
Let $n$ be an integer greater than 1, and consider the general linear group $\text{GL}(2,\mathbb{Z}_n)$ of two by two invertible matrices mod $n$. Let $f$ be the determinant map $f:\text{GL}(2,\mathbb{Z}_n)\to U(n)$ defined by $f(A)=\det A$, i.e. defined by $$f\left(\begin{bmatrix}a&b\\c&d\end{bmatrix}\right)= (ad-bc)\pmod n.$$ Show that $f$ is a homomorphism. Prove this result by direct computation, rather than by claiming it was already shown to be true in a previous course.
The set of matrices that have determinant one is a special group of matrices. We can use this group of matrices to learn quite a bit about all matrices. Here's a formal definition.
Definition (Special Linear Group $\text{SL}(m,\mathbb{Z}_n)$)
We have already defined the general linear group $\text{GL}(m,\mathbb{Z}_n)$ to be the set of $m$ by $m$ invertible matrices with coefficients in $\mathbb{Z}_n$, together with the binary operation of matrix multiplication mod $n$. The set of matrices in $\text{GL}(m,\mathbb{Z}_n)$ that have determinant 1 is called the special linear group, and we write $$\text{SL}(m,\mathbb{Z}_n)=\left\{ a\in \text{GL}(m,\mathbb{Z}_n) \mid \det(a)=1 \right\}.$$
Problem 71 (The Special Linear Group Is A Subgroup Of The General Linear Group)
Prove that $\text{SL}(m,\mathbb{Z}_n)$ is a subgroup of $\text{GL}(m,\mathbb{Z}_n)$. Why is the set of matrices whose determinant equals 2 not a subgroup of the general linear group?
Let's start with two small groups $G$ and $H$, and from them create a larger group by using the Cartesian product $G\times H = \{(g,h)\mid g\in G, h\in H\}$. To turn this into a group, we'll just use the group operation independently on each component. What we need to do today is to show this actually gives a group, learn how to graph such a group, and then analyze how we find the order of an element $(g,h)$ in the product $G\times H$ if we know the orders of $g$ and $H$ in their respective groups. First, let's get a formal definition. Feel free to read along in chapter 8 of your text.
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.
The first thing you should do is convince yourself that the external direct product is actually a group. This is a straightforward exercise that you should make sure you can do.
Exercise (The External Direct Product $G\oplus H$ is a Group of order $|G||H|$)
Prove that the external direct product $G\oplus H$ or $G\times H$ is a group. If both groups are finite, then show that the order of the external direct product is $|G||H|$.
Click to see a solution.
Let $G$ and $H$ be groups. The binary operation $(g,h)\times(a,b) = (ga,hb)$ is associative as we can compute $$((g,h)(a,b))(m,n)=(ga,hb)(m,n) = ((ga)m,(hb)n)$$ and similarly $$(g,h)((a,b)(m,n))=(g,h)(am,bn) = (g(am),h(bn)).$$ These two quantities are equal because the operation in both $G$ and $H$ is associative. The identity in $G\times H$ is simply $(e_g,e_H)$, and the inverse of $(g,h)$ is $(g^{-1},h^{-1})$. I'll let you show that these satisfy the requirements to be the identity and inverse.
If $G$ has order $|G|$ and $H$ has order $|H|$, and both are finite, then there are clearly $|G|$ choices for the first component, and $|H|$ choices for the second component. Hence the total number of elements in $G\times H$ is precisely $|G\times H|=|G||H|$.
Given a subgroup of $G$ and a subgroup of $H$, we can quickly create a subgroup of $G\times H$. This is what the next problem asks you to show. If you'd like a fun challenge, then prove that the converse of the following problem is true, or produce a counter example. Namely, if $C$ is a subgroup of $G\times H$, must it be true that $C=A\times B$ for some $A\leq G$ and $B\leq H$. First complete all the problems on this list, and then tackle this challenge.
Problem 72 (An External Direct Product Of Subgroups Is A Subgroup Of An External Direct Product)
Show that if $A$ is a subgroup of $G$ and $B$ is a subgroup of $H$, then $A\times B$ is subgroup of $G\times 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,2)\in \mathbb{Z}_2\times\mathbb{Z}_3$
- $(1,2)\in \mathbb{Z}_6\times\mathbb{Z}_4$
- $(1,2)\in \mathbb{Z}_6\times\mathbb{Z}_8$
- $(10,20)\in \mathbb{Z}_{4000}\times\mathbb{Z}_{600}$
Click to see a solution.
- We know $|1| = 2$ and $|2|=3$, and we can compute $(1,2)^k$ for each $k$ from $1$ to $6$ to obtain the sequence $((1,2),(0,1),(1,0),(0,2),(1,1),(0,0))$. This shows that $|(1,2)|=6$.
- We know $|1| = 6$ and $|2|=2$, and we can compute $(1,2)^k$ for each $k$ from $1$ to $6$ to obtain the sequence $((1,2),(2,0),(3,2),(4,0),(5,2),(0,0))$. This shows that $|(1,2)|=6$.
- We know $|1| = 6$ and $|2|=4$. Computing $(1,2)^k$ for each $k$ from $1$ to $12$ will show that the order is 12. Alternately, notice that in the product $(1,2)^k$, the first component will only equal 0 when $k$ is multiple of 6. Similarly, the second component will only be 0 when $k$ is a multiple of $4$. The number 12 is the smallest number for which both components will equal 0.
- We know $|10| = 400$ and $|20|=30$. In the product $(10,20)^k$, the first component will only equal 0 when $k$ is multiple of 400, and the second component will only be 0 when $k$ is a multiple of $30$. The least common multiple of 400 and 30 is 1200, which is the order of $(10, 20)$
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)$.
Click to see a solution.
If $p$ is prime, then every positive integer less than $p$ is relatively prime to $p$. This means that $U(p)=\{1,2,3,4,\ldots, p-1\}$, which means $|U(p)|=p-1$. The Euler $\varphi$ function is just the number of elements in $U(n)$, so we have $\varphi(p)=p-1$ for primes $p$.
If $n$ is not prime, then the set $U(n)$ does not contain every positive integer less than $n$, which makes it harder to work with $U(n)$ when $n$ is not prime.
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)$.
- 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))
- 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))
- 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?
- 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$.
- 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.$
- 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$?)
- 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.
- Prove that $f(e_G)=e_H$.
- In addition show that $f(a^{-1})=(f(a))^{-1}$.
Click to see a hint.
You know that $e_Ge_G=e_G$. How does $f(e_Ge_G)=f(e_G)$ help you know that $f(e_G)=e_H$? Remember to use the fact that $f$ is a homomorphism.
To show that $f$ preserves inverses, think about how you can prove that the determinant of an inverse is the inverse of the determinant. If we have two matrices $A$ and $B$ then we know that $|AB|=|A||B|$. If we know that $B=A^{-1}$, then we have $AA^{-1}=I$ and so we have $|A||A^{-1}|=|I|=1$. Since we know that $|A||A^{-1}|=1$, we can just multiply both sides on the left by $|A|^{--1}$ to get $|A^{-1}|=|A|^{-1}$. If you mimic this process with an arbitrary homomorphism, you should find the solution for any homomorphism. Just replace $|A|$ with $f(a)$. What you did in linear algebra is the key to the more generalized notion of a homomorphism.
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$.
- List the elements of $0+H$, $1+H$, $2+H$, $3+H$, $4+H$, $5+H$, $17+H$, and $-11+H$.
- How many different sets did you get?
Click to see a solution.
We know that $H=\{\ldots,-6, -3, 0, 3, 6, \ldots\}$. Adding 1 to each entry gives $H=\{\ldots,-5, -2, 1, 4, 7, \ldots\}$, which is the same as the set of integers whose remainder is 1 after dividing by 3. Similarly we have $$\begin{align} 0+H &= \{\ldots,-6, -3, 0, 3, 6, \ldots\}, \\ 1+H &= \{\ldots,-5, -2, 1, 4, 7, \ldots\}, \\ 2+H &= \{\ldots,-4, -1, 2, 5, 8, \ldots\}, \\ 3+H &= \{\ldots,-3, 0, 3, 6, 9, \ldots\} = \{\ldots,-6, -3, 0, 3, 6, \ldots\} = 0+H,\\ 4+H &= \{\ldots,-2, 1, 4, 7, 10, \ldots\} = \{\ldots,-5, -2, 1, 4, 7, \ldots\} = 1+H,\text{ and}\\ 5+H &= \{\ldots,-1, 2, 5, 8, 11, \ldots\} = \{\ldots,-4, -1, 2, 5, 8, \ldots\} = 2+H. \end{align}$$ In our computations above, we see that $k+H$ is equivalent to $k\pmod 3+H$. Since $17\pmod 3=2$ and $-11\pmod 3=1$, we have that $17+H = 2+H$ and we also have $-11+H = 1+H$.
There are only three different cosets. The cosets are $0+H$, $1+H$, and $2+H$. Every other coset is equal to one of these.
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$.
- 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.
- 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.
- For each $g\in G$, compute the left cosets $gA$ of $A$. Draw the identification graph of $G$ using left cosets of $A$.
- 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.
- For each $g\in G$, compute the left cosets $gB$ of $B$. Draw the identification graph of $G$ using left cosets of $B$.
- 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$.
- 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.
- For each $g\in G$, compute the right cosets $Ag$ of $A$. Draw the identification graph of $G$ using right cosets of $A$.
- For each $g\in G$, compute the left cosets $gA$ of $A$. Draw the identification graph of $G$ using left cosets of $A$.
- For each $g\in G$, compute the right cosets $Bg$ of $B$. Draw the identification graph of $G$ using right cosets of $B$.
- For each $g\in G$, compute the left cosets $gB$ of $B$. Draw the identification graph of $G$ using left cosets of $B$.
- 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$.
Click if you want a hint.
If you assume $H$ is a subgroup, pick $a\in H$ and then prove that $H\subseteq Ha$ and $Ha\subseteq H$.
If you assume that $Ha=H$ for every $a\in H$, then you must prove $H$ is a subgroup. You'll need to rely on the fact that if $b,c\in H$, then we know $H=Hb$ and $H=Hc$ as sets. One of these should get you closure pretty quickly. If you let $b\in H$, then why does $H=Hb$ force the existence of $h\in H$ such that $b=hb$, and as such why does this mean $e\in H$. A similar argument should get you the fact that $b^{-1}\in H$ (as $e\in H$ forces $e=bh$ for some $h\in H$).
Click if you want a hint.
If you assume $H$ is a subgroup, pick $a\in H$ and then prove that $H\subseteq Ha$ and $Ha\subseteq H$.
If you assume that $Ha=H$ for every $a\in H$, then you must prove $H$ is a subgroup. You'll need to rely on the fact that if $b,c\in H$, then we know $H=Hb$ and $H=Hc$ as sets. One of these should get you closure pretty quickly. If you let $b\in H$, then why does $H=Hb$ force the existence of $h\in H$ such that $b=hb$, and as such why does this mean $e\in H$. A similar argument should get you the fact that $b^{-1}\in H$ (as $e\in H$ forces $e=bh$ for some $h\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:
- The function $f:H\to Ha$ defined by $f(h)=ha$ is a bijection.
- We have $|H|=|Ha|$.
- 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:
- 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)).$$
- 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.
- We have $Ha=Hb$ if and only if $ab^{-1}\in H$.
- We must have $Ha=Hb$ or $Ha\cap Hb=\emptyset$.
- We have $Ha=aH$ if and only if $aHa^{-1}=H$.
We've already seen all of these properties before when studying modular arithmetic. Let $G=\mathbb{Z}$ and let $H=n\mathbb{Z}$ for some $n\in\mathbb{N}$. The cosets of $H$ are $r+n\mathbb{Z}$ for $0\leq r<n$.
- The first property above states that $a+n\mathbb{Z}=b+n\mathbb{Z}$ if and only if $a-b\in n\mathbb{Z}$. Wait, this just says two numbers have the same remainder if and only if their difference is a multiple of $n$.
- The second property above states that either $a$ and $b$ have the same remainder, or they don't. It basically states that remainders are unique.
- The third property is trivial for $\mathbb{Z}$ because $\mathbb{Z}$ is an Abelian group and we always know $a+n\mathbb{Z}=n\mathbb{Z}+a$.
Problem 85 (The Set Product Is A Binary Operation On Cosets Of Normal Subgroups)
Suppose that $N$ is a normal subgroup of $G$. Let $a,b\in G$, and consider the two cosets $Na$ and $Nb$. Show that the set product $(Na)(Nb)$ is again a coset of $N$, and that we have $(Na)(Nb)=N(ab)$.
This shows that the set product is a binary operation on right cosets (and left cosets) of a normal subgroup $N$.
Click if you want a hint.
You've got to make use of the fact that $Na=aN$ for every $a\in G$. So we have $Nb=bN$, $Nc=cN$, $Nx=xN$, etc. Why is this useful? Any time you see $na$ in your work for some $n\in N$, you know that $na\in Na$ which means $na\in aN$ which means there exists some $n'\in N$ with $na=an'$. You don't have the ability to commute, but we get ALMOST commutativity. We can write $na=an'$ for some different $n'\in N$. The $'$ symbol just means that it's a different element. It's not a derivative.
So in your work if you ever see $bn_1a$, you can instead either write $bn=n_2b$ or you could write $na=an_3$ for some $n_2,n_3\in N$, and then you have $bn_1a = n_2ba=ban_3$. Similarly, if you see $n_1an_2b$, then you should be able to write this, after some work, in either the form $n_3ab$ or the form $abn_4$ (you'll need to use the closure of the operation in $N$ to combine elements in $N$).
You can't use the commutative law, but you have something pretty close.
We need some more examples of homomorphisms. Simple shift permutations from cryptography provides us with quite a few. Make sure you can prove the following exercise.
Exercise (A Homomorphism From $\mathbb{Z}_n$ to $\mathbb{Z}_d$ when $d$ is a divisor of $n$)
Consider the map $f:\mathbb{Z}_{n}\to \mathbb{Z}_d$ defined by $f(x)=x\pmod d$ where $d$ is a divisor of $n$. Show that $f$ is a homomorphism.
Click to see a solution
We need to show that $((x+y)\pmod n)\pmod d = (x\pmod d+y\pmod d)\pmod d$. We know that $a\pmod d=b\pmod d$ if and only if $a-b$ is a multiple of $d$ (does this look like the coset property that says $Ha=Hb$ if and only if $ab^{-1}\in H$?). We just need to show that $(x+y)\pmod n - (x\pmod d+y\pmod d)$ is a multiple of $d$. To do this, first note that using the division algorithm we can write $x\pmod d = x-q_xd$ and $y\pmod d = y-q_yd$ for some integers $q_x$ and $q_y$, and we can write $(x+y)\pmod n = (x+y)-qn$ for some integer $q$. Since we know $d$ is a divisor of $n$, we can also write $n=md$ for some integer $m$. We then compute $$\begin{align} (x+y)\pmod n - (x\pmod d+y\pmod d) &=(x+y-qn)-(x-q_xd)-(y-q_yd)\\ &=-qmd+q_xd+q_yd\\ &=d(q_x+q_y-qm), \end{align}$$ which is a multiple of $d$ as desired.
What happens if $d$ is not a divisor of $n$? Does the map $f:\mathbb{Z}_n\to \mathbb{Z}_d$ defined by $f(x)=x\mod d$ result in a homomorphism?
Problem 94 (When is $x \pmod d$ a homomorphism from $\mathbb{Z}_n$ to $\mathbb{Z}_d$)
Let $G=\mathbb{Z}_{12}$ and $H=\mathbb{Z}_5$. Let $f:G\to H$ be the map defined by $f(x)=x\mod 5$.
- Is the map $f:G\to H$ a homomorphism? Either prove that it is, or produce a counter example.
- Let $n$ be an integer and suppose that the positive integer $d<n$ is not a divisor of $n$. Is the map $f:\mathbb{Z}_n\to \mathbb{Z}_d$ defined by $f(x)=x\mod d$ a homomorphism?
The problems above also give us homomorphisms from $U(n)$ to $U(d)$, as the next problem shows. These maps are crucial in understanding cryptography.
Problem 95 (The set $U_d(n)$ and the homomorphism from $U(n)$ to $U(d)$)
For each integer $n\geq 2$ and each divisor $d$ of $n$, consider the map $f:U(n)\to U(d)$ defined by $f(x)=x\pmod d$.
- Show that this map is a homomorphism. [Hint: You will probably want to use the fact that $a\pmod k=b\pmod k$ if and only if $a-b$ is a multiple of $k$. This is the easiest way to prove statements about modular arithmetic. You have to show that two things are equal, namely that $((x\cdot y)\pmod n)\pmod d = ((x \pmod d)\cdot (y \pmod d))\pmod d$. You can remove the outermost $\pmod d$ by instead showing that the difference is a multiple of $d$.]
- Then explain why the set $U_d(n)=\{x\in U(n)\mid x\pmod d = 1\}$ is a subgroup of $U(n)$. (Hint: What is the kernel of $f$?)
- List the elements of $U_{5}(60)$.
The next theorem should come as no surprise. We've already shown that given any subgroup $H$ of $G$, that every element of $H$ is in one of the cosets of $H$. We've also shown that the cosets of $H$ are disjoint. These two facts together show that we can partition $G$ into a disjoint union of cosets of $H$. We also know that the size of each coset matches the order of $H$. So if we have $r$ disjoint cosets $Ha_1$, $Ha_2$, $Ha_3$, ..., $Ha_r$, all of which have the same number of elements, then we should be able to use this information to show that the order of $H$ divides the order of the group. This fact is called Lagrange's theorem.
Problem 86 (Lagrange's Theorem Proof)
Prove Lagrange's Theorem.
Theorem (Lagrange's Theorem)
Suppose that $G$ is a finite group and that $H$ is a subgroup of $G$. Then the order of $H$ divides the order of $G$. In particular, we know that $|G|/|H|$ equals the number of distinct right (or left) cosets of $H$ in $G$.
We now have shown that the $|G|/|H|$ is precisely the number of cosets of $H$ there are in $G$. From a Cayley graph perspective, this is how many copies of $H$ are visible in the graph, as they are translated throughout the graph. The number of such cosets is called the index of $H$ in $G$, and written $|G:H|$.
Definition (Index of $H$ in $G$, or $|G:H|$)
If $H$ is a subgroup of $G$, then the index of $H$ in $G$, written $|G:H|$, is the number of distinct right (or left) cosets of $H$. Because of Lagrange's theorem, we know that $|G:H|=|G|/|H|$.
We'll now return to looking at when the left and right cosets of a subgroup agree, namely we'll be looking at normal subgroups. Let's first get ourselves a collection of subgroups that are normal.
Problem 87 (Some Normal Subgroups)
Prove the following facts.
- If $G$ is Abelian, then every subgroup of $G$ is normal.
- The center $Z(G)$ of any group $G$ is always a normal subgroup of $G$.
We are now ready to define a new group using the cosets of a normal subgroup. If $N$ is a normal subgroup of $G$, then we've already shown that the binary operation on the collection of cosets, defined by $(Na)(Nb)=N(ab)$, is well defined. Is this binary operation enough to forma a group? To say yes, we need to show that the operation is associative, that there is there an identity coset, and that every coset has an inverse coset. We're now ready to prove that the collection of cosets of a normal subgroup is actually a group, and we call this the factor group of $G$ by $N$, or the quotient group of $G$ by $N$, and we write $G/N$ to talk about this group of cosets.
Definition (Factor Group or Quotient Group of $G$ by $N$, or $G/N$)
Let $G$ be a group. Let $N$ be a normal subgroup of $G$. Then we define the factor group of $G$ by $N$, or the quotient group of $G$ by $N$, to be the set $G/N = \{Na\mid a\in G\}$, i.e the collection of right cosets of $N$ using the set product $(Na)(Nb)=N(ab)$ as the binary operation.
Problem 88 (The Quotient Group $G/N$ Is A Group)
Let $G$ be a group and let $N$ be a normal subgroup of $G$. Prove that the set $G/N$ is actually a group under the operation of coset products.
The next problem helps you refresh your memory about the definitions of homomorphism and order of an element. The problem has you show that if $f$ is a homomorphism from $G$ to $H$, then while $f$ may not preserve the order of elements in $a$, it has to send an element of order $n$ to an element whose order divides $n$. This must happen on an element by element basis. So if we know something about the order of $f(a)$, then we know that $|a|$ must be a multiple of $|f(a)|$.
Problem 89 (The order of $a$ is a multiple of the order of $f(a)$, or $|a|=k|f(a)|$)
Suppose that $f:G\to H$ is a homomorphism. Prove that if $a\in G$ has order $n$, show that $|f(a)|$ divides $n$, i.e. show that $|a|$ is a multiple of $|f(a)|$.
In addition to homomorphisms interacting nicely with elements and orders, even more can be said. In particular, if you know that there are $n$ things that map to the indentity $e$ in the codomain, then the homomorphism must carry exactly $n$ elements from the domain to each element of the codomain. For this reason, we say that a homomorphism is an $n$-to-one map. If you look back at last week's problems, you should see somewhere that we showed a result very similar to this, namely when we showed that the kernel of $f$ is a normal subgroup. Please look back at that problem before tackling this one.
Problem 90 (A homomorphism is an $n$-to-one map)
Let $f:G\to H$ be a homomorphism.
- Suppose that $\ker f$ has order $n$. If we know that $f(g)=h$ for some $g\in G$, prove that there are exactly $n$ different elements in $G$ that map to $h$, so we know that the preimage of $h$, namely $f^{-1}(h)$, is a set with $n$ elements. This shows that $f$ is an $n$-to-one map.
- Prove that $f$ is injective if and only if the kernel of $f$ is trivial, i.e. $\ker f = \{e\}$.
- Prove that if $f$ is surjective and the kernel of $f$ is trivial, then $f$ is an isomorphism.
Here are some comment's about these problems.
- This should follow without any additional work from a previous problem. Just figure out which problem.
- This is why in linear algebra we know that $A\vec x = b$ has a single solution if and only if the only solution to $A\vec x=\vec 0$ is $\vec x= 0$, which means the columns of $A$ are linearly independent. Finding the kernel, or null space, is crucial in linear algebra.
- This is why in linear algebra we know that when the kernel of a square matrix is trivial, then the matrix is invertible.
We now know that a homomorphism is an $n$-to-one map. This fact is basically a directly result of the fact that the kernel of a homomorphism is normal. The next exercise shows that every normal subgroup is the kernel of some homomorphism. This shows that studying normal subgroups is precisely equivalent to studying kernels of homomorphisms. We've actually been using the result below without every stating it formally. Given a Cayley graph, we can easily build a map from the Cayley graph to the corresponding identification graph using right cosets of $N$ by sending $a$ to $Na$. This exercise just has you shows that this map is indeed a homomorphism whose kernel is $N$.
Exercise (A Subgroup Is Normal If And Only If It Is The Kernel Of Some Homomorphism)
Prove that $N$ is a normal subgroup of $G$ if and only if $N$ is the kernel of some homomorphism $f:G\to H$ from $G$ to another group $H$.
Click to see a solution.
We already know that if $N$ is the kernel of a homomorphism, then it is normal. So one direction of this if and only if proof is complete.
If we know $N$ is normal, then we can let $H=G/N$ and define $f:G\to H$ by $f(g)=Ng$. This map is a homomorphism because we already showed that $f(ab)=N(ab)=(Na)(Nb) = f(a)f(b)$ when we showed that the set product is a binary operation on cosets of a normal subgroup. The kernel of this map is the set of elements $g\in G$ such that $f(g)=N$. This is precise the set of $g\in G$ such that $Ng=N$ which is true if and only if $g\in N$ by the properties of cosets. Hence the kernel of this map is $N$.
This next problem has you practice using Lagrange's theorem. Both facts in the problem should follow immediately from applying Lagrange's theorem and another observation. These facts are often considered corollaries of Lagrange's theorem.
Problem 91 (The Order Of An Element Divides The Order Of A Group)
Let $G$ be a finite group. Use Lagrange's theorem to prove the following two corollaries.
- Let $a\in G$. The order of $a$ divides the order of $G$.
- If $|G|=p$ for some prime $p$, then $G$ is cyclic.
We are now ready to state and prove what mathematicians call the first isomorphism theorem. We've seen the following result several times before, without every fully stating it. When we consider the dihedral group of order 8 and let $N$ be the set of rotations, the identification graph looked a lot like $\mathbb{Z}_2$. The map $f:D_8\to \mathbb{Z}_2$ defined by $f(g)=0$ if $g$ is a rotation and $f(g)=1$ if $g$ is a flip, is a homomorphism from $D_8$ to $\mathbb{Z}_2$. The kernel of this homomorphism is precisely the rotations $N$. So the factor group $G/N$ consists of two cosets and is isomorphic to $\mathbb{Z}_2$. We now formally state the first isomorphism theorem.
Here's a formal statement of the first isomorphism theorem. It's slightly different than the text's, and we'll talk about why it's different in class. The version in the text involves more notation, but is essentially equivalent to this version. The key you need to proving this theorem comes from some of the earlier problems today (which problem has you show that something is an isomorphism?).
Problem 92 (The First Isomorphism Theorem Proof)
Prove the First Isomorphism Theorem.
Theorem (The First Isomorphism Theorem)
Let $f:G\to H$ be a surjective homomorphism with kernel $K$. Because we know that $f(x)=f(y)$ for any $y\in Kx$ (elements in the same coset of the kernel have the same image under $f$), then we can define a map $\phi:G/K\to H$ by defining $\phi(Kg)=f(g)$. This map $\phi$ is always an isomorphism.
We'll start using this theorem almost every day from here on out, as this is one of the biggest ideas in abstract algebra. For now, just make sure you can prove it.
Exercise (The Integers Under Addition Are Isomorphic To The Positive Integers Under Multiplication)
The set $\mathbb{R}^+$ is the set of positive real numbers. Consider the two groups $G=(\mathbb{R},+)$ and $H=(\mathbb{R}^{+},\cdot)$. Show that these two groups are isomorphic by showing that the exponential function $f(x)=\exp(x)$ is a group isomorphism.
Click to see a solution.
You could prove this by showing that the map is a homomorphism, and that it is a bijection by producing the inverse (namely $g(x)=\ln x$) and proving that it is an inverse. We've already done this in class.
Let's instead use the first isomorphism theorem. We know that $\exp(a+b)=\exp(a)\exp(b)$ high school algebra, so $f$ is a homomorphism. Given $y\in \mathbb{R}^{+}$, we let $x=\ln y$ and then $\exp(x)=y$, so the map is surjective. The only value such that $f(x)=1$ is $x=0$, so the kernel is $K=\ker f = \{0\}$. We could stop here and note that this means $f$ is 1 to 1, i.e. injective, and hence a bijection. Alternately, we could notice that $G/K=G$ (the identification graph of $G/K$ is the same as $G$ since $|K|=1$) and the first isomorphism theorem states that $f:G/K\to H$ is an isomorphism.
One of the reasons we care about factor groups is that we can often determine information about large, possibly hard to explore groups, by taking information from the factor group and pulling it back to the larger group. We know that the map $f:G\to G/N$ defined by $f(g)=Ng$ is a homomorphism, so we can often obtain information about $G$ by using this homomorphism to pull back information from $G/N$. The next problem has you show an example of this, namely that if you can find an element of order $k$ in $G/N$, then there must be an element of this order as well in $G$. Your work from last time should make this problem quite fast, provided you remember that $\langle a\rangle$ is a cyclic group, and as such is isomorphic to $\mathbb{Z}_{|a|}$, which we understand quite well.
Problem 93 (If A Factor Group $G/N$ Has An Element Of Order $k$ Then So Does $G$)
Suppose that $N$ is a normal subgroup of a finite group $G$ and that $Na$ has order $k$ as an element of $G/N$. Prove the following two facts.
- The order of $a$ in $G$ is a multiple of the order of $Na$ in $G/N$.
- There exists an element $b\in G$ that has order $k=|Na|$.
In other words, if a factor group has an element of order $k$, the the original group before factoring must have an element of order $k$ as well.
We have already shown that $Ha=aH$ for every $a\in G$ if and only if $aHa^{-1}=H$ for every $a\in G$. So one way to prove that a subgroup is normal is to prove that $aHa^{-1}=H$ for every $a\in G$. However, this requires that for each $a\in G$ you show both $aHa^{-1}\subseteq H$ and $H\subseteq aHa^{-1}$. The next problem simplifies this process even more. It says that if you know $aHa^{-1}\subseteq H$, then the other set inclusion must follow immediately.
Problem 94 (The Normal Subgroup Test)
Suppose that $G$ is a group and $H$ is a subgroup of $G$. Prove that $H$ is a normal subgroup of $G$ if and only if $xHx^{-1}\subseteq H$ for all $x\in G$.
How does normality behave when we look at subgroups? The following problem has you show that if you know $N$ is normal in $G$, and $N$ lies in some subgroup $B$ of $G$, then $N$ must be normal in $B$ as well. However, if we know $N$ is normal in $B$, and $B$ is normal in $G$, this does not guarantee that $N$ is normal in $G$. In symbols, we have $N\leq B\leq G$ and $N\trianglelefteq G$ implies $N\trianglelefteq B$, but we cannot say that $N\trianglelefteq B\trianglelefteq G$ implies $N\trianglelefteq G$. Being normal in a large group is enough to pass down to subgroups, but being normal in a subgroup is not enough to force normality in a larger group.
Problem 95 (Subgroups And Normality)
Suppose that $G$ is a group and that $A\leq B\leq G$.
- If $A$ is normal in $G$, prove that $A$ is normal in $B$.
- If $A$ is normal in $B$ and $B$ is normal in $G$, must $A$ be normal in $G$? Find a counter example to this.
The next problem has you show that when you compute factor groups, lots of properties pass immediately from $G$ to $G/N$. In particular, if $G$ is Abelian then $G/N$ is Abelian. Also, if $G$ is cyclic, then $G/N$ is cyclic. Many other properties follow as well.
Problem 96 (Factor Groups Preserve Being Cyclic And Abelian)
Suppose that $N$ is a normal subgroup of $G$.
- If $G$ is cyclic, prove that $G/N$ is cyclic.
- If $G$ is Abelian, prove that $G/N$ is Abelian.
The previous problem is an application of the bigger idea connected to homomorphism. Namely that the image of an Abelian group is Abelian, and the image of a cyclic group is cyclic.
Problem 97 (Images Of Abelian And Cyclic Groups)
Let $f:G\to H$ be a homomorphism. We have already shown that the image of $f$, written $f(G)$, is a subgroup of $H$.
- Prove that if $G$ is Abelian, then $f(G)$ is Abelian.
- Prove that if $G$ is cyclic, then $f(G)$ is cyclic.
How do the properties of Abelian and cyclic behave when combined with external direct products?
Problem 98 (External Direct Products Of Abelian And Cyclic Groups)
Suppose that $G$ and $H$ are groups.
- Prove or disprove: If both $G$ and $H$ are Abelian, then $G\oplus H$ is Abelian.
- Prove or disprove: If $G\oplus H$ is Abelian,then both $G$ and $H$ are Abelian.
- Prove or disprove: If both $G$ and $H$ are cyclic, then $G\oplus H$ is cyclic.
- Prove or disprove: If $G\oplus H$ is cyclic, then both $G$ and $H$ are cyclic.
The next problem has you prove Fermat's little lemma. We already conjectured this earlier in the semester when we noticed that if $p$ is a prime, then regardless of which $a$ we pick from $U(p)$, we must always have $a^{p-1}=1$. Sometimes, this is the order of $a$, whereas sometimes it is not. First, let's look at another conjecture we made earlier in the semester, to get us back into thinking about the $U$ groups.
Exercise (The Last Element Of UN Is Always Its Own Inverse)
Pick an integer $n$ greater than 1. Prove that $(n-1)\in U(n)$ is always its own multiplicative inverse.
Click to see a solution.
Notice that $(n-1)\pmod n = (-1)\pmod n$, which means $(n-1)^2\pmod n = (-1)^\pmod n = 1\pmod n$. This shows that the order of $n-1$ is 2, and also that $n-1$ is its own inverse.
Problem 99 (Fermat's Little Lemma)
Let $G$ be a finite group. Use Lagrange's theorem to prove the following two corollaries.
- We have $a^{|G|}=e$ for every $a\in G$.
- [Fermat's Little Lemma] Let $p$ be a prime and suppose $a\in U(p)$. Then we must have $a^p\pmod p=a$. (Hint: What is the order of $U(p)$?)
Using Fermat's little lemma and/or Lagrange's theorem, you should be able to rapidly prove the next result.
Exercise (The Order Of A In UP Divides P-1)
Let $p$ be a prime. Let $a\in U(p)$. Then $|a|$ divides $p-1$.
Click to see a solution.
There are several ways to prove this result.
- Since we know $a^p\pmod p = a$, we konw $a^{p-1}\pmod p = 1$. We know that $a^k=e$ in any group only when $k$ is a multiple of the order of $|a|$, so this means $k=p-1$ is a multiple of $|a|$.
- We now that $|U(p)|=p-1$. Hence every subgroup of $U(n)$, in particular $\left<a\right>$, must have an order that divides $p-1$. Since we know $|a|=|\left<a\right>|$, we know that $|a|$ divides $p-1$.
Because we are working with homomorphisms quite a bit in our work, we see the notation $f(g)=g$ quite a bit. We have also seen the notation $f^{-1}(h)$, but because homomomorphisms are not necessarily injective, this is not the inverse of $f$ applied to $h$. We have to remember that when we write $f^{-1}(h)$ we are talking about a set, namely the set of all $x\in G$ such that $f(x)=h$. We are not talking about a single $g$ so that $f(g)=h$. The notation $f^{-1}(h)$ represents the preimage (or inverse image) of $\{h\}$ under $f$. Here's a reminder of the formal definition.
Definition (Preimage Or Inverse Image)
If $f:A\to B$ and $C\subseteq B$, then the preimage of $C$ under $f$ is the set of all $a\in A$ such that $f(a)\in C$, and we write the preimage of $C$ under $f$ as $$f^{-1}(C)=\{a\in A\mid f(a)\in C\}.$$ When $C=\{c\}$ contains a single element, we often write the preimage of $C$ under $f$ as $f^{-1}(c)$ instead of using the more formal cumbersome notation $f^{-1}(\{c\})$.
Preimages and subgroups interact in a very nice way, namely homomorphisms preserve subgroups when computing inverse images. Next time we'll show that preimages preserve normality.
Problem 100 (The Preimage Of A Subgroup Under A Homomorphism Is A Subgroup)
Suppose that $f:G\to H$ is a homomorphism. Let $B$ be a subgroup of $H$. Let $A$ be the preimage of $B$, namely $$A=f^{-1}(B)=\{g\in G\mid f(g)\in B\}.$$ Show that $A$ is a subgroup of $G$.
For more problems, see AllProblems