20171025

Please Login to access more options.

Today

Problem 51 (Inverses In Groups)

Suppose that $G$ is a group with $a,b\in G$.

1. Prove that the inverse of $a^{-1}$ is $a$.
2. Prove that the inverse of $ab$ is $b^{-1}a^{-1}$.
3. If $a_1,a_2,a_3,\ldots, a_n\in G$, state the inverse of $a_1a_2a_3\cdots a_n$. Use induction to prove your claim.

Problem 53 (Finite Subgroup Test)

Let $G$ be a group. Suppose that $H$ is a nonempty finite subset of $G$ and that $H$ is closed under the operation of $G$ (so if $a,b\in H$, then we must have $ab\in H$). Prove that $H$ is a subgroup of $G$.

Problem 54 (The Intersection Of Two Subgroups)

Suppose that $G$ is a group and that $H$ and $K$ are subgroups of $G$. Prove that $H\cap K$ is a subgroup of $G$.

Problem 55 (The Union Of Two Subgroups)

Suppose that $G$ is a group and that $H$ and $K$ are subgroups of $G$. Is $H\cup K$ a subgroup of $G$? Either prove that is, or find a counterexample.

Definition (Abelian Group)

Let $G$ be a group. If $ab=ba$ for every $a,b\in G$ (so the group operation is commutative), then we say that $G$ is Abelian.

Definition ($Z(G)$ - Center Of A Group)

Let $G$ be a group. The center of the group, written $Z(G)$, is the set of elements $x\in G$ that commute with every element of $G$, which we can write symbolically as $$Z(G)=\{x\in G\mid gx=xg \text{ for all } g\in G\}.$$

Problem 56 (The Center Of Group Is A Subgroup)

Prove that the center $Z(G)$ of a group $G$ is a subgroup of $G$. If $G$ is Abelian, then what is $Z(G)$?

Problem 57 (Powers Of Products In An Abelian Group)

Suppose $G$ is an Abelian group. Prove that if $a,b\in G$, then $(ab)^2=a^2b^2$. Then use induction to prove that if $a,b\in G$, then $(ab)^n=a^nb^n$ for each $n\in \mathbb{N}$.

Definition (Subgroup Generated By An Element)

Let $G$ be a group and $a\in G$. Then the subgroup generated by $a$ is the set $$\langle a\rangle = \{a^n\mid n\in\mathbb{Z}\},$$ where we define $a^0=e$ and $a^{-n}=(a^{-1})^n$.

Problem 58 (The Subgroup Generated By An Element Is Actually A Subgroup)

Let $G$ be a group with $a\in G$. Show that $\langle a\rangle$, using the definition above, is a subgroup of $G$.

Problem 59 (The Intersection Of Two Subgroups Of $\mathbb{Z}$)

Let $G=\mathbb{Z}$. Because the group operation is addition, remember that $a^2$ actually means $a+a$, and $a^5=a+a+a+a+a=5a$. Beware of this issue, as $a^n$ actually means $na$ because the group operation is addition when working in $\mathbb{Z}$.

1. What is $\langle 2\rangle$? What is $\langle 3\rangle$? Convince yourself that $\langle 2\rangle\cap \langle 3\rangle = \langle 6\rangle$.
2. What is $\langle 4\rangle$? What is $\langle 6\rangle$? Find an integer $c$ so that $\langle c\rangle=\langle 4\rangle\cap \langle 6\rangle$? Prove that your result is true.
3. If $a,b\in \mathbb{Z}$, then conjecture what $c$ should equal so that $\langle c\rangle=\langle a\rangle\cap \langle b\rangle$. You don't have to prove this result (unless you'd rather prove this result than proving part 2).

Definition (The Subgroup $n\mathbb{Z}$)

For each $n\in \mathbb{N}$ we define $n\mathbb{Z}$ to be the subgroup $\langle n\rangle = \{kn\mid k\in \mathbb{Z}\}$ of the group $\mathbb{Z}$ under addition. This is just the multiples of $n$.

When we were working with simple shift permutations of the standard 26 letter alphabet, we showed that the set of all simple shift permutations, denoted $H=\{\phi_n\mid n\in\mathbb{Z}\}$, is actually a set that consists of just 26 distinct elements, namely we showed that $H=\{\phi_0,\phi_1, \ldots,\phi_{25}\}$. We can generate each of these simple shifts using $\phi_1$, and the order of $\phi_1$ is $|\phi_1|=26$. Using the language of groups, we showed that $$H =\langle \phi_1\rangle = \{\phi_0,\phi_1, \ldots,\phi_{25}\}.$$ This is true because if $n\in \mathbb{Z}$, then we can use the division algorithm to write $n=26q+r$ where $0\leq r<26$. Then we know that $$\phi_1^{n}=\phi_1^{26q+r}=\phi_1^{26q}\circ \phi_1^r = \phi_0\circ \phi_r = \phi_r.$$ This shows that $\langle \phi_1\rangle\subseteq \{\phi_0,\phi_1, \ldots,\phi_{25}\}$, and the reverse set containment is obvious by definition of $\langle \phi_1\rangle$. In addition, we know that $\phi_i= \phi_j$ if and only if $i-j$ is a multiple of $26$, which means that the 26 elements given in the list $\phi_0,\phi_1, \ldots,\phi_{25}$ are distinct. The fact that $H=\{\phi_0,\phi_1, \ldots,\phi_{25}\}$ tells us that $H$ has at most 26 elements, and the fact that each of the elements in the list $\phi_0,\phi_1, \ldots,\phi_{25}$ are distinct tells us that $H$ has exactly 26 elements.

We now generalize the above work to show that if an element of a group has order $n$, then $\langle a\rangle$ must always consist of the elements $\{e,a,a^2,\ldots, a^{n-1}\}$.

Problem 60 (Properties Of $\langle a \rangle$ When $a$ Has Finite Order)

Let $G$ be a group with $a\in G$. Suppose that the order of $a$ is $|a|=n$. Prove the following:

1. We have $\langle a\rangle = \{e,a,a^2,\ldots, a^{n-1}\}$. (You are showing two sets are equal.)
2. We have $a^i=a^j$ if and only if $i-j$ is a multiple of $n$.
3. The order of an element equals the order of the subgroup generated by that element, namely $|a|=|\langle a\rangle|$. (How can you combine 1 and 2 to get this.)

Exercise (If $a^k=e$, Then The Order Of $a$ Divides $k$)

Suppose that $a$ is a group element with order $n$. If $a^k=e$, prove that $k$ is a multiple of $n$.

Exercise (Properties Of An Element With Infinite Order)

Let $G$ be a group with $a\in G$. Suppose that the order of $a$ is infinite. Show that $a^i=a^j$ if and only if $i=j$, and state the order of $\langle a\rangle$.

The next problem asks you to compute the center $Z(G)$ of a nonabelian group, and the result is not trivial group. The automorphisms of the square gave us a group with 8 elements. This group consisted of 4 rotations and 4 reflections. Similarly, for any regular $n$-gon we can construct the automorphism group which will have order $2n$ and consist of $n$ rotations and $n$ reflections.

Definition (The Dihedral Groups $D_{n}$)

For each integer $n\geq 2$, we define the dihedral group on $n$ vertices, written $D_{n}$, to be automorphism group of the regular $n$-gon. This group consists of $n$ rotations and $n$ reflections, so has order $2n$.

Problem 61 (The Center Of A Dihedral Group)

Let $G=D_4$, the automorphism group of the square. Recall that $Z(G)$ is the center of the group, or the set of elements that commute with every element of the group.

1. What is $\langle R_{90} \rangle$? What is $\langle R_{180} \rangle$? What is $\langle R_{270} \rangle$? What is $\langle H \rangle$?
2. Does $R_{90}\in Z(G)$? Explain. (Does $R_{90}$ commute with every element in $G$? In particular, does $R_{90}H=HR_{90}$?)
3. Compute the center $Z(G)$ and show that it consists of more than just $R_0$. Make sure you can explain why each element is either in $Z(G)$, or not in $Z(G)$.

Every time you seen an Exercise in the problem set, you should spend a couple minutes trying to answer the question. These questions are designed as a quick check of some facts that you should be familiar with. Come up with a solution, and then click to see the solution.

Exercise (What Is The Group Operation On The Integers)

If we want to consider $\mathbb{Z}$ as group, then which operation do we use, addition or multiplication? Why? Which is a group, is it $(\mathbb{Z},+)$ or is it $(\mathbb{Z},\cdot)$?

Exercise (Are The Natural Numbers A Subgroup Of The Integers)

Is $\mathbb{N}$ closed under the operation of addition? Is $\mathbb{N}$ a subgroup of $\mathbb{Z}$?

Take a moment to reread the problem The Span Of A Simple Shift. In this problem, we looked at the span of various simple shift permutations. We saw many patterns that we conjectured without proof. In particular, we noticed that two simple shifts $\phi_i$ and $\phi_j$ had the same span if they had the same greatest common divisor with 12 (the size of the alphabet). It's time to prove this conjecture, as well as many more.

The following problem requires that you use the GCD theorem. If you let $d=\gcd(n,k)$, then remember that there are integers $s$ and $t$ such that $d=sn+tk$. This will be your key tool in working with the greatest common divisor.

Problem 62 ($\langle a^k\rangle = \langle a^{\gcd(k,|a|)}\rangle$)

Let $a$ be an element of order $n$ and let $k\in\mathbb{N}$. Prove that $\langle a^k\rangle = \langle a^{\gcd(k,n)}\rangle$.

Problem 63 ($|a^k| = |a|/\gcd(k,|a|)$)

Let $a$ be an element of order $n$.

1. If $d$ is a divisor of $n$, then prove that $|a^d|=n/d$.
2. For any $k\in \mathbb{N}$, prove that $|a^k| = n/\gcd(k,n)$.

The previous two problems are the key tools to unlocking all of our other conjectures about simple shift permutations. In particular, the order of a simple shift permutation on $n$ letters will always be a divisor of $n$. Let's first make a new definition, a cyclic group, to generalize any group that behaves like the simple shift permutations.

Definition (Cyclic Group)

Let $G$ be a group. If there exists an element $a\in G$ such that $\langle a\rangle=G$, then we say that $G$ is a cyclic group.

Exercise (Cyclic Groups Are Abelian)

Suppose that $G$ is a cyclic group. Prove that $G$ is an Abelian group.

We need to review the definition of the order of a group.

Definition ($|a|$ and $|G|$ - Order For Elements and Groups)

Let $G$ be a group with identity $e$, and let $g\in G$.

• The $\textdef{order}$ of $G$, denoted $|G|$, is the cardinality of $G$.
• The $\textdef{order}$ of $g$, denoted $|g|$, is the smallest positive integer $n$ such that $g^n = e$, if such an $n$ exists. If no such $n$ exists, we say $g$ has infinite order.

If you feel like you need extra practice with this definition, then please complete the following exercise.

Exercise (Order Is The Smallest Positive Integer)

Suppose we know that $a^6=e$.

1. Explain why this is not enough information to state the order of $a$. (Look at the definition. What are we missing?)
2. In addition to knowing that $a^6=e$, someone else notices that $a^4=e$. Prove that the order of $a$ cannot be 4. In particular show that $a^2=e$, so the order of $a$ is either $2$ or $1$.

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.

Exam

We'll have an exam in the testing center sometimes during the first week of November. The problems and ideas discussed prior to this are the things that you shoudl study to prepare for the exam. What you should you know for the exam? All the definitions, problems, and ideas we've discussed up to this point. I purposefully won't narrow it down more than this. My real goal is to help you prepare to pass your masters qualifying exam in grad school (which covers undergraduate abstract algebra - all of it). By not telling you exactly what you need to study, you'll have to go through the content, isolate big ideas, and organize the material in a way that you can remember it. This process is crucial for preparing for graduate school.

For more problems, see AllProblems