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 {gcd} (n,s)$. Also $\left\langle a^{s}\right\rangle =\left\langle a^{t}\right\rangle \iff \mathrm {gcd} (s,n)=\mathrm {gcd} (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 {\tfrac {n}{d}}$

Thus we have $\mathrm {gcd} (n,s)=d$, and $\mathrm {gcd} \left({\frac {n}{d}},{\frac {s}{d}}\right)=1$.

$1=\left(a^{s}\right)^{m}=a^{s\,m}$, so $n$ divides $s\,m$, and $s\,m=u\,n$ 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 {gcd} (n,s)}}={\frac {n}{\mathrm {gcd} (n,t)}}$, and thus $\mathrm {gcd} (n,s)=\mathrm {gcd} (n,t)$.

Next, proving the converse; assume $\mathrm {gcd} (s,n)=\mathrm {gcd} (t,n)$. Then we have $|\left\langle a^{s}\right\rangle |=|\left\langle a^{t}\right\rangle |$. Furthermore, since in $G$ there is only one subgroup of the given order, we have $\left\langle a^{s}\right\rangle =\left\langle a^{t}\right\rangle$.

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 {gcd} (n,s)=1$.

Proof. $\mathrm {gcd} (n,s)=1$ if and only if $|\left\langle a^{s}\right\rangle |={\frac {n}{\mathrm {gcd} (n,s)}}=n$ if and only if $a^{s}$ is a generator.

quod erat demonstrandum

Exercise 6.17

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

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

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

The group generated by 2 is $\left\langle 2\right\rangle =\left\{0,2,4,6,8,10,12,14,16\right\}$. 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 $\left\langle 3\right\rangle =\left\{0,3,6,9,12,15\right\}$. In this case, the only number that shares only a common factor of 3 with 18 is 15.

Similarly, $\left\langle 6\right\rangle =\left\{0,6,12\right\}=\left\langle 12\right\rangle$.

And $\left\langle 9\right\rangle =\left\{0,9\right\}$.

Finally, the trivial subgroup containing only the identity element $\left\langle 0\right\rangle =\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 ={\begin{pmatrix}1&2&3&4&5\\4&2&5&3&1\end{pmatrix}}$

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 ={\begin{pmatrix}1&2&3&4&5\\3&5&4&2&1\end{pmatrix}}\,\!$

We can find $\sigma \circ \tau ={\begin{pmatrix}1&2&3&4&5\\5&1&3&2&4\end{pmatrix}}$

Inverse Permutations

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

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

$\sigma ^{-1}={\begin{pmatrix}1&2&3&4&5\\5&2&4&1&3\end{pmatrix}}\,\!$

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 $\left\langle S_{A},\circ \right\rangle$ 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; Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{-1} \in S_A} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f \in S_A} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f \circ f^{-1} = f^{-1} \circ f = id} )

Example

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = \{ 1, 2, \ldots, n \}} be a nonempty set of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} elements.

$S_{A}$ is called the symmetric group on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} letters

Note: If $A$ and $B$ have the same cardinality (i.e. there is a bijective function from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} to $A$ and vice versa), then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_A} is isomorphic to any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_B} .

Proof. We define Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi : S_A \to S_B} to be $\phi (\sigma )=f^{-1}\circ \sigma \circ f$, where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} is a bijective function from $B$ to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} . The claim is that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} is a group isomorphism.

Homomorphism:

${\begin{aligned}\phi (\sigma \circ \tau )&=f^{-1}\circ \sigma \circ \tau \circ f\\&=f^{-1}\circ \sigma \circ f\circ f^{-1}\circ \tau \circ f\\&=\phi (\sigma )\circ \phi (\tau )\end{aligned}}$

Injectivity:

If $\phi (\sigma )=\phi (\tau )$, then we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{-1} \circ \sigma \circ f = f^{-1} \circ \tau \circ f} for all elements of $B$. Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{-1}} is bijective, we can say $\sigma (f(b))=\tau (f(b))$. Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} is bijective, we can say that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma(a) = \tau(a)} . Thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma} is injective.

Surjectivity

Let $\gamma \in S_{B}$. Then $f\circ \gamma \circ f^{-1}\in S_{A}$. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(f \circ \gamma \circ f^{-1}) = f^{-1} \circ f \circ \gamma \circ f^{-1} \circ f = \gamma} . Therefore Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} is surjective.