Please Login to access more options.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
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}$).
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$.
- 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}$.
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.
Click to see a solution.
We've already shown this in our work earlier in the semester. Given any two permutations of $X$, their composition is a permutation of $X$ so $S_n$ is closed. We also know that function composition is associative. The identity permutation $\text{id}_X$ definded by $\text{id}_X(x)=x$ is an element of $S_n$. The inverse of $\alpha \in S_n$ is the inverse function $\alpha^{-1}$, which is again a permutation and so in $S_n$. This shows that $S_n$ satisfies the definition of being a group.
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).
- 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.
- 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$.
- We say that $\alpha$ is a transposition if $\alpha$ is a cycle $(a,b)$ of length 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.
- 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,2)(3,4)$
- $(1,2,3)$
- $(1,2)(3,4)(1,2,3)$
- $()$
- $(1,4,3,5)(2,3,1,4,7,6)$
Click to see a solution.
With each permutation, we just have two show that when we write the permutation as a product of transpositions, that the number of them is even.
- The permutation $(1,2)(3,4)$ is already written as a product of two transpositions, so it's an even permutation.
- We can write $(1,2,3)=(1,3)(1,2)$, which is two transpositions.
- Combining the two parts above, we can write $(1,2)(3,4)(1,2,3) = (1,2)(3,4)(1,3)(1,2)$. This is a product of 4 transpositions, so the permutation is in $A_n$.
- The identity is a product of zero transpositions, which is even. Alternately, we can write the identity as the product $(1,2)(1,2)$, which is two transpositions.
- We can write $(1,4,3,5)=(1,5)(1,3)(1,4)$ and also $(2,3,1,4,7,6)=(2,6)(2,7)(2,4)(2,1)(2,3)$. This means that $$(1,4,3,5)(2,3,1,4,7,6) = (1,5)(1,3)(1,4)(2,6)(2,7)(2,4)(2,1)(2,3), $$ which is the product of 8 transpositions.
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$.
- Do this using the problem The Subgroup Test - Subgroups Are Subsets That Are Closed Under Products And Taking Inverses.
- Do this using the problem Finite Subgroup Test.
For more problems, see AllProblems