20161109

Please Login to access more options.

Today

Definition (Group Isomorphism)

Let $(G,\cdot)$ and $(H,\times)$ be groups. We say that the function $f:G\to H$ is a group $\textdef{isomorphism}$ if $f$ is a bijection and $f$ preserves the group structures, which means $f(a\cdot b)=f(a)\times f(b)$ for every $a,b\in G$. We say that $G$ and $H$ are isomorphic groups, and write $G\approx H$ if there exists an isomorphism between them.

The group $H_{26}$ of simple shift permutations on the standard 26 letter alphabet is an encryption group we have learned to work with. The group operation is function composition where the composition $\phi_{k}\circ \phi_j$ is equal to $\phi_{j+k} = \phi_{j+k+26n}$ for any integer $n$. This set is very similar to the group $\mathbb{Z}_{26}$ where the operation is addition mod 26. It's so similar, that when we've drawn Cayley graphs in class, we tend to leave off the $\phi$ and just write the subscripts. Because of this similarity, they should be isomorphic groups.

Exercise (The set of simple shift permutations on 26 letters is isomorphic to $\mathbb{Z}_{26}$.)

Prove that the function $f:H_{26}\to \mathbb{Z}_{26}$ defined by $f(\phi_j)=j$ is a group isomorphism.

The previous problem shows that any time we have a cyclic group of order $n$, then we are basically working with a structure that's very similar to $\mathbb{Z}_n$. The names of the elements may be changed, but otherwise it's basically identical. The next problem has you show that a similar fact is true for infinite cyclic groups.

Problem 66 (Every Infinite Cyclic Group Is Isomorphic to $\mathbb{Z}$)

Suppose $G$ is a cyclic group of infinite order. Prove that $ \mathbb{Z}\cong G$. In other words, produce a function $f:\mathbb{Z}\to G$ and show that $f$ is an isomorphism.

Any time we use a single element $a$ of a group and construct the set $\left<a\right>$, we are creating a cyclic group. Earlier in the semester we called this the span of a single permutation. The next problem has you practice using this notation, as well as practice computing the order of an element in various groups.

Problem 67 (SKIP) (Practice With Cyclic Subgroups)

In each part below, you are given a group. Find an integer $n$ so that the given group $G$ is isomorphic to $\mathbb{Z}_n$. If you were to create an isomorphism $f:\mathbb{Z}_n\to G$, what value would you assign to $f(1)$? The first one already has an answer.

1. Let $G=\langle R_{270} \rangle$ as a subgroup of $D_{4}$, the automorphisms of a square.
   • We know that $R_{270}$ has order 4, so this subgroup is isomorphic to $\mathbb{Z}_4$. To obtain an isomorphism, we'd just let $f(1)=R_{270}$, as $R_{270}$ is a generator for $\langle R_{270} \rangle = \{R_{270},R_{180},R_{90},R_{0}\}$.
2. Let $G=\langle R_{30} \rangle$ as a subgroup of $D_{24}$, the automorphisms of a regular 24-gon.
3. Let $G=\left<\begin{bmatrix}2&1\\1&0\end{bmatrix}\right>$ in the general linear group $\text{GL}(2,\mathbb{Z}_3)$. [Hint: Just as all the previous problems, start computing powers of this matrix until you obtain the identity.]
4. Let $G=\{(),(1,2,3), (1,3,2)\}$ as a subgroup of the set of all permutations of $X=\{1,2,3\}$.
5. Let $G=U(7)$. [Hint: You'll need to start by finding a generator.]
6. Let $G=U(17)$.

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

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

1. Construct a multiplication table, i.e. Cayley table, for $U(8)$ and $U(10)$. Which of these groups is isomorphic to $U(5)$?
2. 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)$?
3. 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|$.

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

For more problems, see AllProblems