We can find even mor examples of groups with the examples we already know.
e.g. $\Z \subseteq \mathbb{Q} \subseteq \R \subseteq \mathbb{C}$. All of them form groups under $+$, addition.
e.g. Recall $\Z^={1,-1}$, $\Z^ \subseteq { \pm 1, \pm i} \subseteq \mathbb{C}^*$. They form groups under $\times$ multiplication.
e.g. ${r_0, r_1, r_2, r_3} \subseteq D_4$. It is a group under composition of symmetries (movements).
Subgroup
- Definition - Subgroup
- Let $(G, \cdot)$ be a group. A subset $H$ of $G$ is called a subgroup of $G$ if $(H, \cdot)$ is a group.
- We write $H \le G$ under operation $\cdot$.
Remarks:
- The operation on $G$ and $H$ must be the same one.
- If $G$ is a group under operation $\cdot$ and $e \in G$ is its identity, then $G \le G$ and ${e} \le G$.
- Definition - Trivial and Proper Subgroup
- Let $G$ be a group. ${e}$ is called the trivial subgroup. Any subgroup that is neither ${e}$ nor $G$ is called a proper subgroup, denoted $H < G$
e.g. $2\Z = {…, -4, -2, 0, 2, 4, …}$ is a subgroup of $\Z$ under addition.
For any $n \in \Z$, $n\Z = {…, -2n, -n, 0, n, 2n, …}$ is a subgroup of $\Z$ under addition.
Is $\Z_n={0, 1, …, n-1}$ a subgroup of $\Z$? No. Because the operation of $\Z_n$ is modular addition but for $\Z$ it’s addition. Besides, $\Z_n \nsubseteq \Z$. Elements in $\Z$ are integers, but those in $\Z_n$ are $[0], [1], …$, classes or sets of integers.
Is $\Z_8^*$ a subgroup of $\Z$ under multiplication? No, for similar reasons.
- Proposition 2.1
- If $G$ is a group and $H$ is a subgroup of $G$ then the identity of $G$ is the identity of $H$.
Proof:
Suppose $e$ is the identity of $G$ and $f$ is the identity of $H$, then $f = ff$. Since $f \in G$, it has inverse $f^{-1} \in G$ and $ff^{-1} = e$. Then $e = ff^{-1} = (ff)f^{-1} = f(ff^{-1}) = fe = f$
Subgroup Test
- Theorem 2.2 - Subgroup Test
- Let $(G, \cdot)$ be a group. A non-empty subset $H$ of $G$ is a subgroup of $G$ if and only if:
- $\forall a,b \in H ; a \cdot b \in H$
- $\forall a \in H ; a^{-1} \in H$
Proof:
Let $H \subseteq G$.
($\Rightarrow$) Suppose $H$ is a subgroup of $(G, \cdot)$. Since $H$ is a group, by definition, $\cdot$ is closed in $H$, so (1) holds. And the inverse exists for all elements in $H$, so (2) holds.
($\Leftarrow$) Suppose $H \neq \emptyset$ and (1), (2) holds.
- Closure: (1) shows that $\cdot$ is closed in $H$
- Associativity: Since $(G, \dot)$ is a group, $\cdot$ is associative.
- Identity: Let $a \in H$. By (2), $a^{-1} \in H$. By (1), $a \cdot a^{-1} = e \in H$.
- Inverse: (2) shows that $a^{-1} \in H$ for any $a \in H$.
Thus $H$ is a group and hence a subgroup of $G$.
e.g. Show that $SL_n(\R)={A \in M_{n \times n}(\R) : \det(A) = 1 }$ is a subgroup of $GL_n(\R)={A \in M_{n \times n}(\R) : \det(A) \neq 0 }$
Proof:
Let $A \in SL_n(R)$, then $\det(A) = 1 \neq 0$. Thus $A \in GL_n(\R)$, and $SL_n(\R) \subseteq GL_n$.
Consider $I_{n \times n}$. $\det(I)=1$. Thus $I \in SL_n(\R)$, and $SL_n(\R) \neq \emptyset$.
Let $A, B \in SL_n(\R)$, then $\det(A)=\det(B)=1$. $\det(AB) = \det(A)\det(B) = 1 \times 1 = 1$. Hence, $AB \in SL_n(\R)$. (1) holds.
Let $A \in SL_n(\R)$, then $\det(A)=1$. Consider $A^{-1}$. $\det(A^{-1}) = \frac{1}{\det(A)} = \frac{1}{1} = 1$. Hence, $A^{-1} \in SL_n(\R)$. (2) holds.
By the subgroup test, $SL_n(R)$ is a subgroup of $GL_n(\R)$.
Cyclic Groups
- Theorem 2.3 - Generated Subgroup
- Let $(G, \cdot)$ be a group and $a \in G$. The set $\langle a \rangle = {a^k : k\in\Z}$ is a subgroup of $G$.
- We call it the subgroup generated by $a$.
Proof:
Clearly, $\langle a \rangle \subseteq G$ and it is non-empty because $e=a^0 \in \langle a\rangle$.
Let $a^i \in \langle a \rangle$, then $a^i a^j = a^{i+j} \in \langle a\rangle$. (1) holds.
Let $a^i \in \langle a \rangle$, then $a^{-i} \in \langle a \rangle$ and $a^{-i}a^{i} = a^0 = e$. (2) holds.
By the subgroup test, $\langle a \rangle \le G$.
e.g. Consider $(\Z, +)$ and $n \in \Z$. What is $\langle n \rangle$?
If $n=0$, $\langle n\rangle = {0}$. Otherwise $\langle n \rangle = {…, -3n, -2n, -n, 0, n, 2n, 3n, …}$.
e.g. Consider $(\Z_6, +)$. What is $\langle 3 \rangle, \langle 4 \rangle, \langle 5 \rangle$?
- $\langle 3 \rangle = {0, 3}$
- $\langle 4 \rangle = {0, 4, 2}$
- $\langle 5 \rangle = {0, 5, 4, 3, 2, 1}$
e.g. Consider $(\Z_{10}^, \times)$, where $\Z_{10}^ = {1, 3, 7, 9}$. What are its generated subgroups?
- $\langle 1 \rangle = {1}$
- $\langle 3 \rangle = {1, 3, 9, 7}$
- $\langle 7 \rangle = {1, 7, 9, 3}$
- $\langle 9 \rangle = {1, 9}$
If $a^k=e$ for some $k > 0$ then it looks like $\langle a \rangle$ contains only ${e, a, a^2, …, a^{k-1}}$, and then our elements start to repeat. Also negative power of $a$ gave us nothing new. Indeed, if $a^k=e$ for some $k>0$ then $a^{k-1}a=e$, $a^{-1} = a^{k-1}$, so the negative power of $a$ are really just positive power. It is therefore interesting to ask: what is the smallest positive integer $k>0$ such that $a^k=e$?
- Definition - Order of Element
- Let $(G, \cdot)$ be a group and $a \in G$. The order of element $a$, denoted $|a|$, is the smallest positive integer $k$ such that $a^k = e$. If no such $k$ exists, then $|a|=\infty$.
e.g. In $\Z$, for $n \neq 0$, we have $|n|=\infty$.
e.g. In $\Z_6$, $|4|=3$, and $|5|=6$.
e.g. In $\Z_{10}^*$ $|3|=|7|=4$, and $|9|=2$.
It looks like $|a|=|\langle a\rangle|$. This is actually true in general.
- Lemma 2.4
- Let $G$ be a group and $a \in G$.
- If $|a|=\infty$, then $a^i = a^j$ if and only of $i=j$.
- If $|a|=n$, then $\langle a \rangle = {e, a, a^2, …, a^{n-1}}$, and $a^i=a^j$ if and only if $n \mid (i-j)$.
Proof:
(1) Assume $|a|=\infty$. Then there is not positive integer $k$ such that $a^k=e$. If $i=j$, then $a^i = a^j$. If $a^i = a^j$, then $a^{i-j} = e$. Without loss of generality, assume $i \ge j$, so $i-j$ is positive or zero, but there is no $i-j$ for $a^{i-j}=e$. Hence $i-j=0$, and $i=J$.
(2) Assume $|a| = n$.
(2a) Clearly, ${e, a, …, a^{n-1}} \subseteq \langle a \rangle$. Let $a^k \in \langle a \rangle$. There exists $q\in \Z$ and $r \in {0,…,n-1}$ such that $k=nq+r$. Then $a^k= a^{nq+r}= (a^n)^q a^r = e^q a^r = a^r$. Thus $a^k=a^r \in {e, a, …, a^{n-1}}$, and $\langle a \rangle \subseteq {e, a, …, a^{n-1}}$. Hence, $\langle a \rangle = {e, a, …, a^{n-1}}$
(2b) Suppose $a^i = a^j$, then $e = a^{i-j}$. There exists $q\in \Z$ and $r \in {0,…,n-1}$ such that $i-j=nq+r$. Then $e=(a^n)^q a^r = a^r$. But $n$ is the smallest positive number for $a^{\Box}=0$, so $r=0$. Hence, $n \mid i-j$.
- Corollary 2.5
- Let $G$ be a group and $a \in G$. Then $|a| = |\langle a \rangle|$
- Corollary 2.6
- Let $G$ be a group and $a \in G$. If an integer $k$ satisfies $a^k=e$, then $|a| \mid k$.
Proof:
Assume $a^k=e$. Then $a^k=a^0$. By lemma 2.4 (2), $|a|$ divides $k-0=k$.
e.g. In $\Z_6$, consider $4$. $4^6=0$. Then $|4| \mid 6$.
In general, for $a \in \Z_n$, $a^n = 0$, so $|a|$ divides $n$.
- Definition - Cyclic Group and Generator
- A group $G$ is cyclic if $G=\langle a \rangle$ for some $a \in G$.
- This $a$ is a generator of $G$.
e.g. Recall $n\Z = {…, -2n, -n, 0, n, 2n, …}$. Since $n\Z = \langle n \rangle$, it is a cyclic group and $n$ is a generator. One of other generators of $n\Z$ is $-n$.
e.g. ${\pm 1, \pm i}$ is cyclic with generator $i$ or $-i$.
e.g. $\Z_n$ is cyclic for all $n$ with generator $1$.
e.g. The set of rotation $\langle r_1 \rangle = {r_k : k \in \Z}$ in the dihedral group $D_n$.
e.g. $\Z_8^* = {1, 3, 5, 7}$ is NOT cyclic.
Properties of Cyclic Groups
- Proposition 2.7
- If a group $G$ is cyclic, it is also Abelian.
Proof:
Let $G=\langle a \rangle$ and $a^i, a^j \in G$. Then $a^i a^j = a^{i+j} = a^j a^i$.
Consider a cyclic group $G = \langle a \rangle$. If $|a|=\infty$, then $G={…, a^{-2}, a^{-1}, a^0, a^1, a^2, …}$ and the group operation is $a^i a^j = a^{i+j}$. The group is isomorphic to $(\Z, +)$. If $|a|=n$, then $G={a^0, a^1, …, a^{n-1}}$. The group is isomorphic to $(\Z_n,+)$.
Q: How many generators are there is a cyclic group? What are they?
Q: Are subgroups of cyclic group also cyclic? Yes.
Q: What is the order of an element in a cyclic group?
- Theorem 2.8
- If a group is cyclic, then its subgroup are also cyclic.
Proof:
Let $H$ be a subgroup of $G = \langle a \rangle$.
If $H={e}$, then $H = \langle e \rangle$ is cyclic.
Let $H \supseteq {e}$. Then there exists $a^t \in H$ and $a^t \neq e$. Since $H$ is a group, $a^{-t} \in H$. Therefore, there is a positive power of $a$ inside $H$. Thus, there is a smallest positive integer $m$ such that $a^m \in H$. We guess $H=\langle a^m \rangle$.
Let $b=a^k \in H$. Then we have $k=mq+r$ for some $q \in \Z$ and $r \in {0, …, m-1}$. Then $b=a^{mq+r}$ and $a^r = ba^{-mq}$. Since $b, (a^m)^{-q} \in H$, $a^r \in H$. We defined $m$ is the smallest positive, so $r$ has to be $0$. Consequently $b=(a^m)^q$, and $H = \langle a^m \rangle$.
The theorem implies that for a cyclic group it subgroup looks like $\langle a^k \rangle$.
e.g. What are subgroups of $\Z=\langle 1 \rangle$? Every subgroup looks like $\langle a^n \rangle = \langle n \rangle = n\Z$.
e.g. What are subgroups of $\Z_n=\langle 1 \rangle$? They are $\langle 1^0 \rangle, …, \langle 1^{n-1} \rangle$
For $n=6$, they are:
| Generator | Subgroup |
|---|---|
| $0$ | ${0}$ |
| $1$ | ${0,1,2,3,4,5}$ |
| $2$ | ${0,2,4}$ |
| $3$ | ${0,3}$ |
| $4$ | ${0,4,2}$ |
| $5$ | ${0,5,4,3,2,1}$ |
For $n=8$, they are:
| Generator | Subgroup |
|---|---|
| $0$ | ${0}$ |
| $1$ | ${0,1,2,3,4,5,6,7}$ |
| $2$ | ${0,2,4,6}$ |
| $3$ | ${0,3,6,1,4,7,2,5}$ |
| $4$ | ${0,4}$ |
| $5$ | ${0,5,2,7,4,1,6,3}$ |
| $6$ | ${0,6,4,2}$ |
| $7$ | ${0,7,6,5,4,3,2,1}$ |
We observed that the content and order of subgroups are related with $\gcd$.
- Theorem 2.9
- Let $G$ be a group and $a \in G$. If $|a| = n < \infty$, then for any $k\in \N$:
- $\langle a^k \rangle = \langle a^{\gcd(k,n)} \rangle$
- $|a^k| = \frac{n}{\gcd(k,n)}$
Proof:
Let $|a| = n$ and $d = \gcd(k,n)$.
(1) Since $d \mid k$, $k = dt$ for some $t\in \Z$. Then $a^k = a^{dt} = (a^d)^t \in \langle a^d \rangle$ Therefore $\langle a^k \rangle \subseteq \langle a^d \rangle$. By Bézout’s identity, $d=\gcd(k,n)=xk+yn$ for some $x,y \in \Z$. Then $a^d = a^{xk+yn} = (a^k)^x (a^n)^y= (a^k)^x e^y = (a^k)^x \in \langle a^k \rangle$. Therefore, $\langle a^d \rangle \subseteq \langle a^k \rangle$.
(2) Consider $|a^d|$. Let $j$ be the smallest integer such that $(a^d)^j = a^{dj} = e$. Observe that $(a^d)^\frac{n}{d} = a^n = e$, then $j \le \frac{n}{d}$. Since $n$ is the smallest number that $a^{\Box}=e$, $dj \ge n$, so $j \ge \frac{n}{d}$. Thus, $j = |a^d| = |a^k| = \frac{n}{d}$.
- Corollary 2.10
- Let $G$ be a group, $a \in G$, and $|a|=n < \infty$. Then for any $i,j \in \Z$, $\langle a^i \rangle = \langle a^j \rangle$ if and only if $\gcd(i,n) = \gcd(j,n)$
Proof:
($\Leftarrow$) Assume $\gcd(i,n) = \gcd(j,n)$. By theorem 2.9 (1), $\langle a^i \rangle = \langle a^{\gcd(i,n)} \rangle = \langle a^{\gcd(j,n)} \rangle = \langle a^j \rangle$.
($\Rightarrow$) Assume $\langle a^i \rangle = \langle a^j \rangle$. By theorem 2.9 (2), $\gcd(i,n) = \frac{n}{|a^i|} = \frac{n}{|a^j|} = \gcd(j,n)$.
One can show that $\Z_{18}^*={1, 5, 7, 11, 13, 17}$ is generated by $5$.
Q: What is another generator?
$\Z_{18}^* = {5^0, 5^1, 5^2, 5^3, 5^4, 5^5}$. All generators are given by $5^k$ where $\gcd(6, k)=1$. They are $5^1 = 5$ and $5^5=11$.
Q: For which components $k$ is $|5^k|=3$?
$|5^k|=3=\frac{6}{\gcd(k,6)}$. Thus, $\gcd(k,6)=2$, which implies $k=4$ or $k=2$.
Fundamental Theorem of Cyclic Group
Using previous result, we can prove a useful theorem about subgroups of cyclic groups.
- Theorem 2.11 - the Fundamental Theorem of Cyclic Group
- Let $G=\langle a \rangle$ be a cyclic group and $|G|=n < \infty$. Then:
- If $H \le G$, then $|H| \mid n$.
- For each positive divisor $k$ of $n$, there is a unique subgroup $\langle a^{\frac{n}{k}} \rangle$ of $G$ of order $k$.
Proof:
(1) Let $H \le G$. Then $H$ is cyclic, so $H=\langle a^k\rangle$ for some $k \in \N$. By theorem 2.9 (2), $|H|=|a^k|=\frac{n}{\gcd(k,n)}$. Thus, $|H| \mid n$.
(2a) Consider subgroup $\langle a^{\frac{n}{k}} \rangle$ where $k \mid n$. By theorem 2.9 (1), $|\langle a^{\frac{n}{k}} \rangle| = |a^{\frac{n}{k}}| = \frac{n}{\gcd(n,n/k)}= \frac{n}{n/k} = k$.
(2b) Let $H$ be another subgroup of order $k$. Then $H$ is also cyclic, so $H=\langle a^j \rangle$ for some $j \in N$. By theorem 2.9 (2), $|H|=|a^j|=\frac{n}{\gcd(j,n)} = k$. Then $\gcd(j,n)=\frac{n}{k}$. Again by theorem 2.9 (1), $H=\langle a^j \rangle= \langle a^{\gcd(j,n)}\rangle= \langle a^{\frac{n}{k}} \rangle$. Hence, the subgroup is unique.
e.g. Find all subgroups of $\Z_{12} = \langle 1 \rangle$. Since $|\Z_{12}|=12$, its divisors are $1, 2, 3, 4, 6, 12$.
| Divisor(Order) | Subgroup |
|---|---|
| $1$ | $\langle 1^{\frac{12}{1}}\rangle={0}$ |
| $2$ | $\langle 1^{\frac{12}{2}}\rangle={0,6}$ |
| $3$ | $\langle 1^{\frac{12}{3}}\rangle={0,4,8}$ |
| $4$ | $\langle 1^{\frac{12}{4}}\rangle={0,3,6,9}$ |
| $6$ | $\langle 1^{\frac{12}{6}}\rangle={0,2,4,6,8,10}$ |
| $12$ | $\langle 1^{\frac{12}{12}}\rangle={0,1,2,…,12}$ |
e.g. Let $G=\langle a \rangle$ and $|G|=20$. What are subgroups of $G$? The divisors of $20$ are $1, 2, 4, 5, 10, 20$.
| Divisor(Order) | Subgroup |
|---|---|
| $1$ | $\langle 1^{\frac{20}{1}}\rangle$ |
| $2$ | $\langle 1^{\frac{20}{2}}\rangle$ |
| $4$ | $\langle 1^{\frac{20}{4}}\rangle$ |
| $5$ | $\langle 1^{\frac{20}{5}}\rangle$ |
| $10$ | $\langle 1^{\frac{20}{10}}\rangle$ |
| $20$ | $\langle 1^{\frac{20}{20}}\rangle$ |
Subgroup Lattices
For any group $G$. We can visually depict its subgroups in a lattice. This is particular easy for cyclic group as we can easily fin all subgroup. We connect a subgroup $K$ to a subgroup $H$ at a higher level if and only if $K$ is properly contained in $H$.