20161031

Please Login to access more options.

Today

We know that the following facts are true if $a$ is an element or order $n$.

• $\langle a\rangle = \{e,a,a^2,\ldots, a^{n-1}\}$.
• $a^i=a^j$ if and only if $i-j$ is a multiple of $n$.
• $|a|=|\langle a\rangle|$.
• $\langle a^k\rangle = \langle a^{\gcd(k,n)}\rangle$.
• If $d$ is a divisor of $n$, then $|a^d|=n/d$.
• For any $k\in \mathbb{N}$, we have $|a^k| = n/\gcd(k,n)$.

Use these facts to prove the next problem.

Problem 64 ($\langle a^i \rangle = \langle a^j \rangle$ iff $\gcd(i,n)=\gcd(j,n)$)

Let $G$ be a group. Suppose that $a\in G$ has order $n>1$. Prove the following two facts:

1. If $G$ is a cyclic group, then the order of $a$ divides the order of the group.
2. We have $\langle a^i \rangle = \langle a^j \rangle$ if and only if $\gcd(i,n)=\gcd(j,n)$.

The second fact proves the following three corollaries by letting $i=1$.

• We have $\langle a \rangle = \langle a^j \rangle$ if and only if $\gcd(n,j)=1$.
• A simple shift permutation $\phi_j$ on $n$ letters generates all simple shift permutations on $n$ letters if and only if $\gcd(n,j)=1$.
• An integer $j\in \mathbb{Z}_n$ is a generator of $\mathbb{Z}_n$ if and only if $\gcd(n,j)=1$.

What does this have to do with the problem When Does An Integer Have A Modular Multiplicative Inverse? You should see a connection between this problem and elements of $U(n)$.

We've spent a lot of time working with cyclic groups and cyclic subgroups generated by a single element. The Well ordering principle and the GCD theorem have shown up quite a bit in our work. Let's now show that any time we start with a cyclic group, then every subgroup must also be cyclic. We've already seen this fact when we consider the problem Simple Shift Repetition where we used repeated shifting to send encrypted message to several generals.

Problem 65 (Subgroups Of Cyclic Groups Are Cyclic)

Suppose that $G$ is a cyclic group generated by $a$. Suppose that $H$ is a subgroup of $G$. Prove that there exists $k\in\mathbb{Z}$ such that $H = \left<a^k\right>$. In other words, prove that $H$ is itself a cyclic group.

We've seen several times in class that when we compute $\text{span}(a,b)$ for integers $a$ and $b$, then their span equals $\text{span}(d)$ for a single integer $d$. In particular, we've also seen that this integer $c$ is precisely $d=\gcd(a,b)$. What if instead we wanted to look at the span of $k$ integers $\{a_1,a_2,a_3,\ldots, a_k\}$. Is there a single number $d$ that has the same span? The previous problem says that YES there must be a single number that achieves this. We call this the greatest common divisor of $a_1,a_2,a_3,\ldots, a_k$. The next exercise emphasizes this.

Exercise (The Subgroups Of $\mathbb{Z}$ are $n\mathbb{Z}$)

We know that $n\mathbb{Z}$ is a subgroup of $\mathbb{Z}$ for every integer $n$. Show that these are the only subgroups of $\mathbb{Z}$. In particular this means that the span of $k$ integers, which is a subgroup of $\mathbb{Z}$, must be equal to $d\mathbb{Z}$ for some $d\in \mathbb{Z}$.

Definition (Symmetric Group on $X$)

Let $X$ be any set. The $\textdef{symmetric group}$ on $X$, denoted $\sym(X)$, is the set of all permutations of $X$. We denote by $S_n$ the symmetric group on $X = \{1,2,\ldots, n\}$ and call it the symmetric group of degree $n$.

Exercise (The Symmetric Group of Degree $n$ Is A Group)

Show that $S_n$ is a group under function composition.

We've already seen that we can write every permutation as a product of disjoint cycles. The next problem has you show that there are other ways to write a permutations as a product. In particular, we'll show that given a cycle of length $n$, called an $n$-cycle, we can write that cycle as a product of 2-cycles, called transpositions.

Problem 65B (optional) (Every Disjoint Cycle Can Be Written As A Product Of Transpositions)

Start by convincing yourself that $(1,2,3,4,5)=(1,5)(1,4)(1,3)(1,2)$. This shows how to write a 5-cycle as a product of transpositions (2-cycles).

1. Find another way to write $(1,2,3,4,5)$ as a product of transpositions. This shows that there are multiple ways to write a cycle as a product of transpositions.
2. Suppose $m,n\in \mathbb{N}$ with $m\geq n$. Also suppose that $\alpha = (a_1,a_2,a_3, \ldots, a_n)\in S_m$ is a disjoint cycle. Give a way to rewrite $\alpha$ as a product of 2-cycles.

Definition ($A_n$ - Alternating Group of Degree $n$)

Let $n\in\mathbb{N}$. Suppose that $\alpha\in S_n$.

1. We say that $\alpha$ is a transposition if $\alpha$ is a cycle $(a,b)$ of length 2.
2. We say that $\alpha$ is an even permutation if we can write $\alpha$ as the product of an even number of transpositions. Otherwise, we say that $\alpha$ is odd.
3. The alternating group of degree $n$, written $A_n$, is the subset of $S_n$ of all even permutations.

Exercise (Even Permutations)

Show that each permutation below is an even permutation.

1. $(1,2)(3,4)$
2. $(1,2,3)$
3. $(1,2)(3,4)(1,2,3)$
4. $()$
5. $(1,4,3,5)(2,3,1,4,7,6)$

We can show that each of the permutations above is the product of an even number of transpositions, and hence an even permutation. However, there are many other ways to write each one. Could it be that some permutations can be written as a product of an even number of transpositions, and then written a different way as an odd number of permutations? We'll leave this as an open question, and come back to it if interest and/or time permits. Regardless, we can still show that the alternating group $A_n$ of degree $n$ is a subgroup of the symmetric group $S_n$. We'll do this to make sure we have some more practice with proving that subsets are subgroups.

Problem 65C (optional) (The Alternating Group Is A Subgroup Of The Symmetric Group)

Let $n\in \mathbb{N}$. Prove that $A_n$ is a subgroup of $S_n$.

1. Do this using the problem The Subgroup Test - Subgroups Are Subsets That Are Closed Under Products And Taking Inverses.
2. Do this using the problem Finite Subgroup Test.

Exercise (The Order Of An Inverse)

Let $G$ be a group and let $a\in G$ have order $n$. Prove that the order of $a^{-1}$ equals $n$, in other words prove that $$|a|=|a^{-1}|.$$

We've been studying groups in a variety of settings all semester long. We've studied simple shift permutations $H_n$, the dihedral groups $D_{2n}$, spans of a permutations $\text{span}(S)$, modular addition $\mathbb{Z}_n$, modular multiplication $U(n)$, general linear groups $GL(m,\mathbb{Z}_n)$, and more. However, each time we introduce a new group, we might ask the question, "Have we already seen this group in some other context?" Cayley graphs give us a very visual way to explore a group, and can make it extremely easy to tell when two groups that appear in completely different context might actually be "the same."

What do we mean when we say that two groups $G$ and $H$ are "the same" when the groups might on surface appear to be very different? We have already talked about what it means to have two graphs be "the same" even when the vertex structure different. We called this a graph isomorphism. The key was to create a bijection between the vertices of the graphs that preserved the edge structure. This means that the answer to whether two vertices are connected or not connected by an edge should be the same either before or after we apply the bijection. In a graph, the important relationship is the edge structure, and we want an isomorphism to preserve this structure.

Now we want to build an isomorphism between groups. The key is to create a bijection $f:(G,\cdot)\to (H,\times)$ between the underlying sets so that the group operation structures are preserved. We could perform an operation $a\cdot b$ in $G$ and then compute $f(a\cdot b)$, or we could first compute $f(a)$ and $f(b)$ and then perform the operation $f(a)\times f(b)$ in $H$. If the group structures are to be preserved, we should obtain the exact same result whether we apply the bijection first or last. We call such a map a group isomorphism.

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.

This next problem asks you to show that the two groups are isomorphic.

Problem 73 (Every Finite Cyclic Group Of Order $n$ Is Isomorphic To $\mathbb{Z}_n$)

Let $H_n$ be the set of simple shift permutations on a set of $n$ letters so $H_n=\{\phi_k\mid 0\leq k\leq n\}$.

1. Start by drawing the Cayley graphs of $H_7$ and $\mathbb{Z}_7$, just to make sure that the graphs are similar.
2. Show that $f:H_n\to \mathbb{Z_n}$ defined by $f(\phi_k)=k$ is a group isomorphism. Remember, this means you must show that $f$ is a bijection (what's the inverse) and that $f(\phi_j\circ \phi_k) = (f(\phi_k)+f(\phi_j))\pmod n$.
3. Show that if $G$ is a cyclic group of order $n$ with generator $a$, then the function $f:\mathbb{Z}_n\to G$ defined by $f(k)=a^k$ 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)$.

For more problems, see AllProblems