\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}