Math 360, Fall 2021, Assignment 9

The moving power of mathematical invention is not reasoning but the imagination.

- Augustus de Morgan

Read:

1. Section 8.

Carefully define the following terms, then give one example and one non-example of each:

1. Permutation (of a set $S$).
2. $\mathrm{Sym}(S)$ (the symmetric group on $S$).
3. $S_n$ (the symmetric group on $n$ letters).
4. Order (of a group; see the text for this definition).
5. $D_n$ (the $n$th dihedral group; see the text).

Carefully state the following theorems (you do not need to prove them):

1. Containment criterion for subgroups of $\mathbb{Z}_n$.
2. Theorem relating $\left\langle[a]\right\rangle$ to $\left\langle[\mathrm{gcd}(a,n)]\right\rangle$ (in $\mathbb{Z}_n$).
3. Classification of subgroups of $\mathbb{Z}_n$ ("Every subgroup of $\mathbb{Z}_n$ is generated by a unique...").
4. Theorem concerning the order of $S_n$.

Solve the following problems:

1. Section 6, problems 23, 25, and 27.
2. Section 8, problems 1, 3, 5, 7, 9, 11, 13, 17, 30, 31, and 33.
3. In class, we listed all permutations of the set $\{1,2,3\}$. Now, make a list of all permutations of the set $\{a,b,c\}$. Do you see any relationship between the two lists?
4. Suppose $S$ and $T$ are sets, and that $f:S\rightarrow T$ is a bijection. Define a function $\phi:\mathrm{Sym}(S)\rightarrow\mathrm{Sym}(T)$ by the formula $\phi(\pi)=f\circ\pi\circ f^{-1}$. Show that $\phi(\pi\circ\sigma)=\phi(\pi)\circ\phi(\sigma)$.
5. With notation as above, take $S=\{1,2,3\}$ and $T=\{a,b,c\}$, and let $f:S\rightarrow T$ be given by $f(1)=a, f(2)=b, f(3)=c$. For any specific $\pi\in\mathrm{Sym}(S)$ (e.g. for $\pi=\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}$), compute the permutation $\phi(\pi)\in\mathrm{Sym}(T)$. Do this in several more specific cases.
6. Returning to the general case, define a new function $\psi:\mathrm{Sym}(T)\rightarrow\mathrm{Sym}(S)$ by the formula $\psi(\tau)=f^{-1}\circ\tau\circ f$. Show that $\phi\circ\psi$ and $\psi\circ\phi$ are both the identity maps, so that $\psi$ is the inverse of $\phi$. (Note in particular that this shows that $\phi$ is an invertible function and hence is a bijection.)
7. Prove that $\phi$ is an isomorphism from $(\mathrm{Sym}(S),\circ)$ to $(\mathrm{Sym}(T),\circ)$.
8. Finally, show that whenever $S$ and $T$ are equinumerous sets, $\mathrm{Sym}(S)$ and $\mathrm{Sym}(T)$ are isomorphic groups.

--------------------End of assignment--------------------

Definitions:

1. Permutation (of a set $S$): Let $S$ be a set. A permutation of $S$ is a bijection from $S$ to itself.
2. $\mathrm{Sym}(S)$ (the symmetric group on $S$): $U(Fun(S, S), \circ) = (Sim(S), \circ)$. That is, $Sym(S)$ means the permutation of $S$, regarded as a group under function composition. It's called the symmetric group on $S$.
3. $S_n$ (the symmetric group on $n$ letters): $Sym(\{1,2,3 \cdots ,n\}) = S_n$.
4. Order (of a group; see the text for this definition): the number of elements present in that group $|S|$.
5. $D_n$ (the $n$th dihedral group; see the text): the group of symmetries of the regular n-gon.

Theorem:

1. Containment criterion for subgroups of $\mathbb{Z}_n$: In $\mathbb Z_n, \left\langle [a] \right\rangle \subseteq \left\langle [b] \right\rangle \iff gcd(b,n) | a.$
2. Theorem relating $\left\langle[a]\right\rangle$ to $\left\langle[\mathrm{gcd}(a,n)]\right\rangle$ (in $\mathbb{Z}_n$): In $\mathbb Z_n, \left\langle [a] \right\rangle = \left\langle [gcd(a,n)] \right\rangle$.
3. Classification of subgroups of $\mathbb{Z}_n$ ("Every subgroup of $\mathbb{Z}_n$ is generated by a unique..."): Each subgroup has a unique generator (between $1$ and $n$) which divides $n$.
4. Theorem concerning the order of $S_n$: $|S_n| = n!$.

Book Problems:

23. $<0>, <1>, <2>, <3>, <4>, <6>, <9>, <12>$ and $<18>$. (The subgroup diagram is laid out similarly to Figure 6.18, with one subgroup above another precisely when its generator divides the other's generator.)

25. $|<1>|=6/1=6, |<2>|=6/2=3, |<3>|=6/3=2, |<0>|=|<6>|=6/6=1$.

27. $|<1>|=12/1=12, |<2>|=12/2=6, |<3>|=12/3=4, |<4>|=12/4=3, |<6>|=12/6=2, |<0>|=|<12>|=12/12=1.$

1. $\begin{pmatrix}1&2&3&4&5&6\\1&2&3&6&5&4\end{pmatrix}$

3. $\begin{pmatrix}1&2&3&4&5&6\\3&4&1&6&2&5\end{pmatrix}$

5. $\begin{pmatrix}1&2&3&4&5&6\\2&6&1&5&4&3\end{pmatrix}$

7. 2

9. $\mu^2=\iota$, so $\mu^{100}=(\mu^2)^{50}=\iota^{50}=\iota.$

In problems 11 and 13, the orbit of a point is the set of all points to which it can be moved by repeated application of the permutation.

11. {1,2,3,4,5,6}.

13. {1,5}.

17. There are four choices for where to send $1$, only one choice for where to send $2$, three choices for where to send $3$, two choices for where to send $4$, and one choice for where to send $5$, so $4*1*3*2 = 24.$

30. Yes, this is a permutation. For injectivity note that $f(x_1)=f(x_2)\implies x_1+1=x_2+1\implies x_1=x_2$, and for surjectivity note that for any $y\in\mathbb{R}, f(y-1)=y$.

31. No, this map is not injective: $f(-1)=f(1)$ but $1\neq-1$.

33. Although this map is injective, it is not a permutation because it is not surjective: its image consists of the positive reals, not all reals.

Other Problems:

1. $\begin{pmatrix}a&b&c\\a&b&c\end{pmatrix}, \begin{pmatrix}a&b&c\\a&c&b\end{pmatrix}, \begin{pmatrix}a&b&c\\b&a&c\end{pmatrix}, \begin{pmatrix}a&b&c\\b&c&a\end{pmatrix}, \begin{pmatrix}a&b&c\\c&b&a\end{pmatrix}, \begin{pmatrix}a&b&c\\c&a&b\end{pmatrix}$. It seems as though writing down all of the permutations of $\{1,2,3\}$ and then systematically making the replacements $1\mapsto a, 2\mapsto b, 3\mapsto c$ results in a correct list of permutations of $\{a,b,c\}$. Perhaps this correspondence might even be a group isomorphism.
2. $\phi(\pi\circ\sigma)=f\circ\pi\circ\sigma\circ f^{-1}$ while $\phi(\pi)\circ\phi(\sigma)=f\circ\pi\circ f^{-1}\circ f\circ\sigma\circ f^{-1}$.
3. $\begin{pmatrix}1&2&3\\a&b&c\end{pmatrix} \circ \begin{pmatrix}1&2&3\\3&2&1\end{pmatrix} = \begin{pmatrix}1&2&3\\c&b&a\end{pmatrix}$, $\begin{pmatrix}1&2&3\\c&b&a\end{pmatrix} \circ \begin{pmatrix}1&2&3\\a&b&c\end{pmatrix}^{-1}$ $= \begin{pmatrix}1&2&3\\c&b&a\end{pmatrix} \circ \begin{pmatrix}a&b&c\\1&2&3\end{pmatrix} = \begin{pmatrix}a&b&c\\c&b&a\end{pmatrix} \in Sym(T)$. By some miraculous coincidence, simply making the replacements $i\mapsto f(i)$ in the two-row notation for $\pi$ yields correct two-row notation for $\phi(\pi)$.
4. For any permutation $\pi\in\mathrm{Sym}(T)$, we have $\phi(\psi(\pi))=\phi(f^{-1}\circ\pi\circ f)=f\circ f^{-1}\circ\pi\circ f\circ f^{-1}=\pi$. Similarly, for any $\sigma\in\mathrm{Sym}(S)$ we have $\psi(\phi(\sigma))=\sigma$. This shows that $\psi=\phi^{-1}$ and, in particular, that $\phi$ is a bijection.
5. We showed above that $\phi$ is bijective and preserves operations, so it is an isomorphism.
6. If $S$ and $T$ are equinumerous sets, then we can choose a bijection $f:S\rightarrow T$ and use it as above to produce an isomorphism $\phi:\mathrm{Sym}(S)\rightarrow\mathrm{Sym}(T)$.