\documentclass[12pt]{article}
\newcommand{\set}[1]{\lbrace #1 \rbrace}
\newcommand{\setc}[2]{\lbrace #1 \mid #2 \rbrace}
\usepackage{amssymb,amsfonts,amsmath}
\pagestyle{myheadings} \markright{Battaglino}
\newenvironment{hwproblem}[1]
{\noindent{\bf{Problem #1:}} }
{\vspace{0.2 in}}

\newenvironment{solution}
{\noindent{\underline{Solution:}} }
{\vspace{0.2 in}}

\begin{document}
\begin{center}
\Large
21-373: Algebraic Structures\\
Assignment 3
\end{center}

\begin{flushright}
Peter Battaglino\\ 18. February, 2005
\end{flushright}

\begin{hwproblem}{5.19}
Show that if $H$ is a subgroup of $S_n$, then either every member of $H$ is an even permutation
or exactly half of the members are even.
\end{hwproblem}

\begin{solution}
Let $H\leqslant S_n$. If every element of $H$ is an even permutation, then there is nothing
to show. Suppose there is at least one odd permutation in $H$. Let $A$ denote the set of all
even permutations in $H$ and $B=H\setminus A$ denote the set of all odd permutations
in $H$. Let $\beta \in B$ and let $f\colon A \rightarrow B$ be defined by $f(\alpha)=\alpha\beta$
for each $\alpha\in A$. Now suppose $f(\gamma)=f(\delta)$, where $\gamma,\delta\in A$. Then
$\gamma\beta=\delta\beta$. Since $H$ is a group, we know that there is an element $\beta^{-1}$ of
$H$ such that $\beta\beta^{-1}=\varepsilon$, so we can write
$\gamma\beta\beta^{-1}=\delta\beta\beta^{-1}$, so we see that $\gamma=\delta$. Thus $f$ is
injective. Now let $\omega\in B$ be given. We know that
$\omega=\omega(\beta^{-1}\beta)=(\omega\beta^{-1})\beta$. Since the identity cycle $\varepsilon$ is
even and $\beta\beta^{-1}=\varepsilon$ and $\beta$ is odd, we know that $\beta^{-1}$ is also odd.
Thus, since $\omega$ and $\beta^{-1}$ are both odd, $\omega\beta^{-1}$ is even. Thus we have found
for every element $\omega\in B$ an element $\omega\beta^{-1}\in A$ such that $f(\omega\beta^{-1})
=\omega$, proving that $f$ is also surjective. Hence, $f$ is a bijection, and it follows that
there exists a bijection between $A$ and $B$, which implies that the cardinality of $A$ is equal
to the cardinality of $B$. In other words, the number of even permutations is equal to the number
of odd permutations, which is half the total number of elements in $H$.
\end{solution}
\clearpage
\begin{hwproblem}{5.32}
Let $\beta = (1,3,5,7,9,8,6)(2,4,10)$.
What is the smallest positive integer $n$ for which $\beta^n=\beta^{-5}$?
\end{hwproblem}

\begin{solution}
The orders of the two disjoint cycles that comprise $\beta$ are 7 and 3. The least common
multiple of 7 and 3 is 21, so we know that the order of $\beta$ is 21. Let $n$ be a positive
integer. We see that $\beta^n =  \beta^{-5}$ follows from
\begin{eqnarray}
\beta^5\beta^n & = & \beta^5\beta^{-5} \\
\beta^{n+5} & = & \varepsilon,
\end{eqnarray}
which follows from the statement $21 \mid (n+5)$. The smallest positive integer $n$ that makes
this statement true is 16. This is what we were asked to find.
\end{solution}
\clearpage
\begin{hwproblem}{5.46}
Show that for $n\geq3$, $Z(S_n)=\set{\varepsilon}$.
\end{hwproblem}

\begin{solution}
If $n=1$, then $S_n=\set{\varepsilon}$. If $n=2$, then $S_n=\set{\varepsilon,(1,2)}$. Since
$(1,2)$ commutes with itself, $Z(S_2)=S_2$. Now suppose $n\geq3$, and denote
$n^{]}:=\set{1,2,\cdots,n}$. Let $\sigma\in Z(S_n)$. Then, for every two-cycle $(a,b)\in S_n$,
with $a,b\in n^], a\neq b$
we have $\sigma (a,b) = (a,b)\sigma$. This means that ($\sigma(a)=a$ and $\sigma(b)=b$), or
($\sigma(a)=b$ and $\sigma(b)=a$). Suppose $\sigma(a)=b$ and $\sigma(b)=a$. Then, since we have
assumed $n\geq3$, we can choose an element $c\in n^], c\neq b, c\neq a$ such that $\sigma$
commutes with $(a,c)$. Once again, this implies that ($\sigma(a)=a$ and $\sigma(c)=c$), or
($\sigma(a)=c$ and $\sigma(c)=a$). We've already excluded the case $\sigma(a)=a$, so we see
that since $\sigma(a)=b$, it is true that $b=c$. However, this contradicts our earlier assumption
that $c\neq b$ so it follows that the only possibility is that $\sigma(a)=a$ for all $a\in n^]$.
Thus, $\sigma=\varepsilon$. Since we chose $\sigma\in Z(S_n)$ arbitrarily, it follows that
$Z(S_n)=\set{\varepsilon}$ for $n\geq3$.
\end{solution}
\clearpage
\begin{hwproblem}{5.50}
(Indiana College Mathematics Competition) A card-shuffling machine always rearranges cards in the
same way relative to the order in which they were given to it. All of the hearts arranged in order
from ace to king were put into the machine, and then the shuffled cards were put into the machine
again to be shuffled. If the cards emerged in the order 10, 9, Q, 8, K, 3, 4, A, 5, J, 6, 2, 7,
in what order were the cards after the first shuffle?
\end{hwproblem}

\begin{solution}
We can represent this permutation by the matrix
\[
\left(\begin{array}{ccccccccccccc}
A&2&3&4&5&6&7&8&9&10&J&Q&K \\
10&9&Q&8&K&3&4&A&5&J&6&2&7\end{array}\right)
\]
Calling this permutation $\gamma$, we see that $\gamma$ has the decomposition
\begin{equation}
\gamma = (A,10,J,6,3,Q,2,9,5,K,7,4,8).
\end{equation}
We seek a cycle $\alpha\in S_{13}$ such that $\alpha^2=\gamma$ is satisfied. To do this,
examine the cycle $(a,b,c,d,e,f,g,h,i,j,k,l,m)$, with each of its elements in the set
$\set{1,2,\cdots,13}$, noting that it has the same length as $\gamma$.
We see that its square is
\[
(a,c,e,g,i,k,m,b,d,f,h,j,l).
\]
Now, to read off the original cycle, we pick the first element as $a$ and write it down,
and then count off seven elements until we get to $b$, and then count off another seven elements,
circling back around to the beginning when we reach the end until we get to $c$, etc. until we
have thirteen elements written down. It is easy to see that this cycle is the original cycle
we started with. We simply apply this approach to the card-shuffling cycle of this problem to
get
\begin{equation}
\alpha = (A,9,10,5,J,K,6,7,3,4,Q,8,2).
\end{equation}
Applying this permutation to the original sorted deck of cards yields
\[
\left(\begin{array}{ccccccccccccc}A&2&3&4&5&6&7&8&9&10&J&Q&K \\
9&A&4&Q&J&7&3&2&10&5&K&8&6\end{array}\right).
\]
The bottom row of this permutation represents the deck after one shuffle, which is what we
were asked to find.
\end{solution}
\end{document}