\documentclass[11pt]{article} % Define the document type. The 11pt refers to font size.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Include packages required to compile document:

\usepackage{amssymb, amsthm, amsmath} % These packages are used for the basic math symbols and environments.
\usepackage{enumerate} % This package is used to provide various types of numbering for lists.
\usepackage[margin=1.25in]{geometry} % This is to set wide margins, so there is room to leave comments
\usepackage[parfill]{parskip} % This provides formatting for paragraphs so that there are no indents and paragraphs are separated by a line skip.
\usepackage[pdftex,colorlinks=true,urlcolor=blue]{hyperref}
% You may need to add additional packages depending on the commands you want to use.

%%%%%%%%%%%%%%%%%%%%
% User defined commands:

\newcommand{\br}{\mathbb R} % this is the symbol for the real numbers.  mathbb is the "blackboard bold" font
\newcommand{\bz}{\mathbb Z} % integers
\newcommand{\bq}{\mathbb Q} % rationals
\newcommand{\bn}{\mathbb N} % natural numbers

\newcommand{\co}{\colon\thinspace} % this is a good way to write functions, i.e instead of $f: X \to Y$, you would write $f\co X \to Y$.  It looks nicer.
\newcommand{\ssm}{\smallsetminus} % A nice way of writing set subtraction 

% You may add shortcuts for any commands you find yourself using frequently.  

\DeclareMathOperator{\ord}{ord} % This command lets you declare math operators.  Some built in operators are \sin for sine and \cos for cosine.  This makes the operators appear nicely in the math environment.  If I wanted to make the sine operator myself, it would look like \DeclareMathOperator{\sin}{sine}.  

% Ender user defined commands
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% These establish different environments for stating Theorems, Lemmas, Remarks, etc.

\newtheorem{Thm}{Theorem}
\newtheorem{Prop}[Thm]{Proposition}
\newtheorem{Lem}[Thm]{Lemma}
\newtheorem{Cor}[Thm]{Corollary}

\theoremstyle{definition}
\newtheorem{Def}[Thm]{Definition}

\theoremstyle{remark}
\newtheorem{Rem}[Thm]{Remark}
\newtheorem{Ex}[Thm]{Example}

\theoremstyle{definition}
\newtheorem{Exercise}{Exercise}
\newtheorem{ExGraded}[Exercise]{*Exercise}
\newtheorem{ExChallenge}[Exercise]{**Exercise}

\newenvironment{Solution}{\noindent{\it Solution.}}{\qed}

%End environments
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Now we're ready to start
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

% This is for the title
{\Large {\bf Homework 7}} \hfill MATH 301/601 \\
{Solutions to Graded Problems\\[-2mm]
\line(1,0){470}

\medskip





\medskip
\begin{Exercise}[Section 5.4 \#25]
Prove that in \( A_n \) with \( n \geq 3 \), any permutation is a product of cycles of length 3. 
\end{Exercise}

\begin{proof}
Let us first show that the product two transpositions is either trivial, a  3-cycle, or a product of two  3-cycles. 
Let \( \tau_1 \) and \( \tau_2 \) be transpositions.  
Then we can write \( \tau_1 = ( a \, \, b ) \)  and \( \tau_2 = ( c \, \, d ) \) for some \( a, b,c,d \in \{1, \ldots, n \} \).
Up to relabelling, there are three cases: (1) \( a = c \) and \( b = d \), (2) \( a \neq c \) and \( b = d \), and (3) both \( a \) and \( b \) are distinct from \( c \) and \( d \). 
In the first case, \( \tau_1\tau_2 \) is the identity.
In the second case, \( \tau_1\tau_2  = ( a \, \, b \, \, c ) \). 
In the third case, we have
\begin{align*}
\tau_1 \tau_2 	&= ( a \, \, b ) (c \, \, d) \\
			&= ( a \, \, b ) (b \, \,c ) (b \, \, c) (c \, \, d) \\
			&= ( a \, \, b \, \, c) ( b \, \, c \, \, d)
\end{align*}
Now, if \( \sigma \in A_n \), then \( \sigma \) is a product of a non-zero even number of transpositions (this is true for the identity as well).
So, there exists transpositions \( \tau_1, \tau_2, \ldots, \tau_{2k} \) such that \( \sigma = \tau_1\tau_2 \cdots \tau_{2k} \).
For \( j \in \{1, \ldots, k\} \), let \( \sigma_j = \tau_{2j-1}\tau_{2j} \).
Then, our above argument implies that \( \sigma_j \) is either the identity, a 3-cycle, or a product of two 3-cycles.
Therefore, \( \sigma = \sigma_1 \sigma_2 \cdots \sigma_k \) expresses \( \sigma \) as a product of 3-cycles. 
\end{proof}


\setcounter{Exercise}4
\medskip
\begin{ExChallenge}
Let \( \sigma = (1 \,\, 2 \,\, 3 \,\, 4 \,\, 5) \in A_9 \) and \( \tau = ( 5 \,\, 6 \,\, 7 \,\, 8 \,\, 9 ) \in A_9 \). 
Prove that the permutation \( ( 1 \, \, 2 \, \, 3 ) \) can be written as a word in \( \{\sigma, \tau\} \), i.e., there exists \( r \in \bn \) and \( n_1, \ldots, n_r, m_1, \ldots m_r \in \bz \) such that \( ( 1 \, \, 2 \, \, 3 ) = \sigma^{n_1}\tau^{m_1}\sigma^{n_2}\tau^{m_2} \cdots \sigma^{n_r}\tau^{m_r} \). 
\end{ExChallenge}

\begin{Solution}
Talk to Eric.  I forgot to write down his solution, so I can't share it.  I didn't take the time to figure it out on my own, so I gave everyone full credit.  The goal was to get you to think visually about a group, so I hope you spent some time doing that.  
\end{Solution}



\end{document}