Please Login to access more options.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
Just as we spanned sets of permutations, we can span subsets of a group. After defining this, we'll show that spanning a subset of a group always gets you a subgroup of the group. This should be analogous to the fact that spanning a subset of permutations leads to a closed set of permutations.
Definition (The Subgroup Generated By A Subset)
Let $G$ be a group. Suppose that $S$ is a subset of $G$.
- A word from the alphabet $S$ is a product of the form $$x=s_1s_2\cdots s_k$$ where for each $i$ either $s_i\in S$ or $s_i^{-1}\in S$.
- The subgroup generated by $S$ is the set of words from the alphabet $S$, namely $$\left<S\right> = \{s_1s_2\cdots s_k\mid k\in \mathbb{N} \text{ and either $s_i\in S$ or $s_i^{-1}\in S$ for each } i\in\{1,2,\ldots, k\}\}.$$
- If $H=\left<S\right>$, then we say that $H$ is the subgroup generated by $S$, or that $S$ is a generating set for $H$.
- If $S=\{a\}$, then we'll write $\left<a\right>$ instead of $\left<\{a\}\right>$. We call $\left<a\right>$ the subgroup generated by $a$.
We call $\left<S\right>$ the subgroup of $G$ generated by $S$, but we have not yet shown this is in fact a subgroup. The next problem has you verify this, so that we can definitely refer to $\langle S\rangle$ as a subgroup.
Problem 51 (The Subgroup Generated By S Is Actually A Subgroup)
Let $G$ be a group and $S$ be a nonempty subset of $G$. Prove that $\left<S\right>$ is a subgroup of $G$.
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$.
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 9(Simple Shift Repetition)
Let's now devise a way to not only encrypt a message, but also keep track of who has seen the message? There are several ways to do this. Let's look at an example that involves repeated application of the same encrpytion key. For this example, let's use the encryption key $\phi_4:S\to S$ (the simple shift permutation that shifts right 4).
A group of military commanders decide to send messages using a message chain. The message passes sequentially from one person to the next, where at each stage they apply the encryption key to the ciphertext before sending it on. If I want to send the plain text message $attackatdawn$, then I'd send the message $exxegoexhear$ to the person after me in the chain. This person would decipher the text using $\phi_4^{-1}$ (shift left 4), and then apply $\phi_4$ to the cipher text $exxegoexhear$ and then send the ciphertext $ibbiksibliev$ to the person after them in the chain. This would repeat until the message made it to every commander.
- You receive the cipher text $skkzgzkomnz$. What is the plain text message? How many people have seen this message?
- How many commanders can we include in this encryption scheme and still tell who sent the message?
- If we use $\phi_5$ instead of $\phi_4$, how many commanders can we include in this encryption scheme and still tell who sent the message?
- Is there an encryption key $\phi_n$ so that $\phi_n^2=\phi_0$. In other words, is there an encryption key $\phi_n$ that will only allow up to two commands to be in the chain?
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}$.
- What is $\langle 2\rangle$? What is $\langle 3\rangle$? Convince yourself that $\langle 2\rangle\cap \langle 3\rangle = \langle 6\rangle$.
- 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.
- 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:
- We have $\langle a\rangle = \{e,a,a^2,\ldots, a^{n-1}\}$. (You are showing two sets are equal.)
- We have $a^i=a^j$ if and only if $i-j$ is a multiple of $n$.
- 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$.
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$.
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 (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}$).
For more problems, see AllProblems