MATH 415 Lecture 5

« previous | Tuesday, September 10, 2013 | next »

Review

Theorem 6.14

Let $G$ be a cyclic group with $n$ elements and generated by $a$. Let $b\in G$ and $b=a^s$. Then $b$ generates a cyclic group of order $\frac{n}{d}$ where $d=\mathrm{g}\mathrm{c}\mathrm{d}(n,s)$. Also $⟨a^s⟩=⟨a^t⟩⟺\mathrm{g}\mathrm{c}\mathrm{d}(s,n)=\mathrm{g}\mathrm{c}\mathrm{d}(t,n)$

Proof. Let $m$ be the order of $a^s$.

Recall that if $X$ has order $m$ and $x^k=e$, then $m$ divides $k$.

From our definition of $m$ above, we have ${\left(a^s\right)}^{\frac{n}{d}}={\left(a^n\right)}^{\frac{s}{d}}=e^{\frac{s}{d}}=e$, so $m\mid \frac{n}{d}$

Thus we have $\mathrm{g}\mathrm{c}\mathrm{d}(n,s)=d$, and $\mathrm{g}\mathrm{c}\mathrm{d}(\frac{n}{d},\frac{s}{d})=1$.

$1={\left(a^s\right)}^m=a^{sm}$, so $n$ divides $sm$, and $sm=un$ for some $u$.

$\left(\frac{s}{d}\right)m=u\left(\frac{n}{d}\right)$, so $\frac{n}{d}$ divides $\left(\frac{s}{d}\right)m$ . . . $m=\frac{n}{d}$

To prove the bi-implication, start with the first part: assume the order of $a^s$ is equal to the order of $a^t$. Then $\frac{n}{\mathrm{g}\mathrm{c}\mathrm{d}(n,s)}=\frac{n}{\mathrm{g}\mathrm{c}\mathrm{d}(n,t)}$, and thus $\mathrm{g}\mathrm{c}\mathrm{d}(n,s)=\mathrm{g}\mathrm{c}\mathrm{d}(n,t)$.

Next, proving the converse; assume

$\mathrm{g}\mathrm{c}\mathrm{d}(s,n)=\mathrm{g}\mathrm{c}\mathrm{d}(t,n)$

. Then we have

$|⟨a^s⟩|=|⟨a^t⟩|$

. Furthermore, since in

$G$

there is only one subgroup of the given order, we have

$⟨a^s⟩=⟨a^t⟩$

.

quod erat demonstrandum

Corollary

If $a$ is a generator of a finite cyclic group $G$ of order $n$, then the generators of $G$ are the elemonts of the form $a^s$, where $\mathrm{g}\mathrm{c}\mathrm{d}(n,s)=1$.

Proof.

$\mathrm{g}\mathrm{c}\mathrm{d}(n,s)=1$

if and only if

$|⟨a^s⟩|=\frac{n}{\mathrm{g}\mathrm{c}\mathrm{d}(n,s)}=n$

if and only if

$a^s$

is a generator.

quod erat demonstrandum

Exercise 6.17

Find all subgroups of ${\mathbb{\mathbb{Z}}}_{18}$, and draw the subgroup diagram.

${\mathbb{\mathbb{Z}}}_{18}=\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17\}$

The following numbers are coprime with 18: 1, 5, 7, 11, 13, 17. Therefore, they are all generators of ${\mathbb{\mathbb{Z}}}_{18}$: so ${\mathbb{\mathbb{Z}}}_{18}=⟨1⟩=⟨5⟩=⟨7⟩=⟨11⟩=⟨13⟩=⟨17⟩$

The group generated by 2 is $⟨2⟩=\{0,2,4,6,8,10,12,14,16\}$. By the theorem above, this is equivalent to the groups generated by other numbers that only share only a common factor of 2 with 18: 4, 8, 10, 14, 16.

The group generated by 3 is $⟨3⟩=\{0,3,6,9,12,15\}$. In this case, the only number that shares only a common factor of 3 with 18 is 15.

Similarly, $⟨6⟩=\{0,6,12\}=⟨12⟩$.

And $⟨9⟩=\{0,9\}$.

Finally, the trivial subgroup containing only the identity element $⟨0⟩=\left\{0\right\}$.

Thus there are only 6 subgroups of this group. We arrange these groups on a subgroup diagram by which groups are included in which other groups:

Section 8: Groups of Permutations

Let $A$ be a set. A function $f:A\to A$ which is bijective is called a permutation of $A$.

Composition of Permutations

If $f$ and $g$ are permutations on $A$, then $f\circ g:A\to A$ is also a permutation

Proof. If $(f\circ g)(a)=(f\circ g)(b)$, then $g(a)=g(b)$ by injectivity of $f$, and thus $a=b$ by injectivity of $g$.

Let

$a\in A$

. Since

$f$

is onto, there exists a

$b\in A$

such that

$f(b)=a$

. Since

$g$

is onto, there exists a

$c\in A$

such that

$g(c)=b$

. Then

$(f\circ g)(c)=f(b)=a$

. Thus

$f\circ g$

is onto.

quod erat demonstrandum

Notation: Let $\sigma$ be a permutation. We denote it as a 2×1 matrix. For example,

$\sigma =\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 4& 2& 5& 3& 1\end{array}\right)$

What we mean by this is that 1 maps to 4, 2 maps to 2, 3 maps to 5, and so on.

Suppose we have another permutation

$\tau =\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 3& 5& 4& 2& 1\end{array}\right)$

We can find $\sigma \circ \tau =\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 5& 1& 3& 2& 4\end{array}\right)$

Inverse Permutations

It's possible to find ${\sigma }^{-1}$ because $\sigma$ is bijective.

Let's find the inverse of $\sigma$ above:

${\sigma }^{-1}=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 5& 2& 4& 1& 3\end{array}\right)$

Theorem 8.5

Let $A$ be a non-empty set. Let $S_A$ be the set of all permutations on $A$. Then $S_A$ is a group under composition of permutations.

Note: We just showed above that composition is a binary operation. Now we will show that it can be used to define a group.

Proof. In order to show that $⟨S_A,\circ ⟩$ is a group, we need to show:

1. Associativity (check; since composition of functions is always associative)
2. Identity (check; $id:A\to A$ is the identity function, and $f\circ id=id\circ f=f$)
3. Inversion (check; $f^{-1}\in S_A$ for $f\in S_A$, and $f\circ f^{-1}=f^{-1}\circ f=id$)

Example

Let $A=\{1,2,\dots ,n\}$ be a nonempty set of $n$ elements.

$S_A$ is called the symmetric group on $n$ letters

Note: If $A$ and $B$ have the same cardinality (i.e. there is a bijective function from $B$ to $A$ and vice versa), then $S_A$ is isomorphic to any $S_B$.

Proof. We define $\varphi :S_A\to S_B$ to be $\varphi (\sigma )=f^{-1}\circ \sigma \circ f$, where $f$ is a bijective function from $B$ to $A$. The claim is that $\varphi$ is a group isomorphism.

Homomorphism:

$\begin{array}{rl}\varphi (\sigma \circ \tau )& =f^{-1}\circ \sigma \circ \tau \circ f\\ & =f^{-1}\circ \sigma \circ f\circ f^{-1}\circ \tau \circ f\\ & =\varphi (\sigma )\circ \varphi (\tau )\end{array}$

Injectivity:

If $\varphi (\sigma )=\varphi (\tau )$, then we have $f^{-1}\circ \sigma \circ f=f^{-1}\circ \tau \circ f$ for all elements of $B$. Since $f^{-1}$ is bijective, we can say $\sigma (f(b))=\tau (f(b))$. Since $f$ is bijective, we can say that $\sigma (a)=\tau (a)$. Thus $\sigma$ is injective.

Surjectivity

Let $\gamma \in S_B$. Then $f\circ \gamma \circ f^{-1}\in S_A$. $\varphi (f\circ \gamma \circ f^{-1})=f^{-1}\circ f\circ \gamma \circ f^{-1}\circ f=\gamma$. Therefore $\varphi$ is surjective.