\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage{cancel}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage{multicol}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}


\usepackage{tikz}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\input{preamble.tex}

\begin{document}

\homework{8: The Symmetric Group}{Due Friday, Week 4}

This problem set is different.  Do the \textbf{one} problem on this set!  (It's an important enough problem that I want you to do just this one question, instead of the typical $\binom{n}{k}$-style we've used so far.)

\begin{enumerate}
\item  In class, we showed that you can write any element of $S_n$ as a product of \textbf{transpositions}: that is, permutations of the form $(ab)$ for distinct $a, b \in \{ 1, \ldots n\}$.  However, there are many ways to write the same permutatuon $\sigma \in S_n$ as a product of transpositions: for example, we have
\begin{align*}
(123) = (13)(12) \textrm{ and } (123) = (12)(23),
\end{align*}
because
\begin{align*}
\quad(123)=\left(\begin{gathered}\xymatrix{
1 \ar[rd] & 2 \ar[rd] & 3 \ar[lld] \\
1 & 2 & 3
}
\end{gathered}\right)
\end{align*}
is the same as both 
\begin{align*}
\quad(12)(23)=\left(\begin{gathered}\xymatrix{
1 \ar[d] & 2 \ar[rd] & 3 \ar[ld] \\
1 \ar[rd]& 2 \ar[ld] & 3\ar[d]\\
1 & 2 & 3\\
}
\end{gathered}\right) \quad\textrm{and} \quad
(13)(12)=\left(\begin{gathered}\xymatrix{
1 \ar[rd] & 2 \ar[ld] & 3 \ar[d] \\
1 \ar[rrd]& 2 \ar[d] & 3\ar[lld]\\
1 & 2 & 3\\
}
\end{gathered}\right).\\
\end{align*}

Suppose that $\sigma \in S_n$ is a permutation that can be written as a product of an \textbf{odd} number of transpositions.  Prove that it cannot also be written as a product of a \textbf{even} number of transpositions.  

(In this sense, the \textbf{parity} of the number of transpositions used to create any permutation $\sigma \in S_n$ is an \textbf{invariant} for that permutation.)
\end{enumerate}

\end{document}