Please Login to access more options.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
- 53 - Finite Subgroup test
- 61 - Practice with center.
- 63 - The order of $a^k$ depends on $\gcd(k,|a|)$.
- 64 - When do two elements span the same set?
- 65 - Subgroups of Cyclic groups are cyclic.
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$.
Let $H$ be a nonempty finite subset of $G$ that is closed under the operation. We'll use the subgroup test to prove that $H$ is a subgroup of $G$. Since $H$ is a nonempty subset of $G$ that is closed under the operation, the only thing that remains to be shown is that .... Let $a\in H$. We must show that $H$ contains $a^{-1}$. Note that since $H$ is closed under the operation, we know that $a^k\in H$ for every positive integer $k$. Consider the set $A=\{a^k\mid k\in \mathbb{N}\}=\{a,a^2,a^3,a^4, \ldots\}$. Since $A\subseteq H$ and because $H$ is finite, we know $A$ is a finite set. This means that in the list of elements of $A$, there must be a repeat, or in other words there exists $i,j\in \mathbb{N}$ such that $i\neq j$ and yet $a^i=a^j$. With loss of generality, assume $i>j$. Then the equation $a^i=a^j$ becomes $a^{i-j}=e$ upon right multiplication by $a^{-j}$. Since ...., we know that $a^{i-j-1}$ is the inverse of $a$. Since we assumed $i>j$, then clearly $i-j-1\geq 0$. If $i-j-1\geq 0$, then the inverse of $a$ is $a^0=e$ which means that $a=e$. Hence we see that $a^{-1}=e=a^1$, which shows that $a^{-1}\in H$. Otherwise we have $i-j-1> 0$ which means .... ....
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.
- What is $\langle R_{90} \rangle$? What is $\langle R_{180} \rangle$? What is $\langle R_{270} \rangle$? What is $\langle H \rangle$?
- Does $R_{90}\in Z(G)$? Explain. (Does $R_{90}$ commute with every element in $G$? In particular, does $R_{90}H=HR_{90}$?)
- 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 (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$.
Click to see a solution.
Suppose $a^k=e$. This means $a^k=a^0$, which from the previous problem is true if and only if $k-0$ is a multiple of $n$. This shows that $k=k-0$ 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$.
Click to see a solution.
Suppose the order of $a$ is infinite. Then by definition this means that $a^n\neq e$ unless $n=0$. Clearly if $i=j$ then $a^i=a^j$. We only need to prove the converse of this statement. Suppose that $a^i=a^j$, and assume without loss of generality that $i\geq j$. Then $a^{i-j}=e$ (just multiply both sides on the right by $a^{-j}$). Because $a$ has infinite order, then we know $a^k\neq e$ for any positive integer $k$. Since $i-j\geq 0$ and $a^{i-j}=e$, we must have $i-j=0$. This means $i=j$.
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)$?
Click to see a solution.
The integers are a group under addition (the sum of two integers is an integer, the identity is 0, the inverse of $n$ is $-n$, and addition is associative as an axiom). For multiplication, the inverse of $2$, which is $1/2$, is not an integer so $\mathbb{Z}$ is not closed under inverses. There is no multiplicative inverse of 0 as $0x\neq 1$ for any integer $x$.
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}$?
Click to see a solution.
The sum of two positive integers is a positive integer, so $\mathbb{N}$ is closed under the operation of $\mathbb{Z}$ (which is addition). However, the inverse of $2$ under addition is $-2$, but $-2\notin \mathbb{N}$. This shows that $\mathbb{N}$ is not closed under taking inverses, and hence is not a group (so not a subgroup of $\mathbb{Z}$).
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$.
- If $d$ is a divisor of $n$, then prove that $|a^d|=n/d$.
- 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.
Click to see a solution.
Since $G$ is cyclic, we know that there exists some $a\in G$ with $\langle a\rangle = G$. Let $x,y\in G$. We need to show that $xy=yx$. But we know that $x=a^m$ and $y=a^n$ for some $n,m\in \mathbb{Z}$ because $G$ is cyclic. This means that $$xy=a^ma^n=a^{m+n}=a^{n+m}=a^na^m=yx,$$ which is what we needed to show.
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$.
- Explain why this is not enough information to state the order of $a$. (Look at the definition. What are we missing?)
- 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$.
Click to see a solution.
- The order of an element is the SMALLEST positive integers $n$ such that $a^n=e$. If all we know is that $a^6=e$, then the order might be 6, or some number less.
- If we know that both $a^6=e$ and $a^4=e$, then since $6=4+2$ (the division algorithm), we know that $e=a^6=a^{4+2}=a^4a^2=ea^2=a^2$. This shows that $e=a^2$, which means the order now can at most be 2.
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:
- If $G$ is a cyclic group, then the order of $a$ divides the order of the group.
- We have $\langle a^i \rangle = \langle a^j \rangle$ if and only if $\gcd(i,n)=\gcd(j,n)$.
Click for a hint.
- If $G$ is cyclic, then pick a generator, say $b$. This means $G=\langle b\rangle$. Why does this mean $a=b^k$ for some $k$? Use this to show that $b$ has finite order, say $m$. Then use problem 63 with $b^k$, where $|b|=m$, rather than $a^k$ and $|a|=n$.
- Problem 63 will get you one direction, and problems 62 will get you the other.
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.
Click to see a hint.
How can you get the smallest positive integer $k$ such that $a^k\in H$?
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}$.
Click to see a solution.
The integers are a cyclic group, so every subgroup is also cyclic. If we let $H$ be a subgroup of $\mathbb{Z}$, then we know there exists $d\in\mathbb{Z}$ such that $H=\left<d\right>$. This shows that $H$ equals the set of multiples of $d$, which means that $H=d\mathbb{Z}$.
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