\documentclass{article}
\usepackage{theorem}
%\usepackage{pdfsync}
\input{mathmacros}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\title{Even and odd permutations}
\begin{document}
\maketitle
Let $S$ be a finite set.  Recall that any
permutation $\sigma \in Sym(S)$ can be written as a product
of disjoint cycles:
$$ \sigma =\gamma_1 \gamma_2 \cdots \gamma_r.$$
Furthermore this expression is unique up to reordering.
(Here we don't allow any $\gamma_i$ to be the identity permuation.)
Recall also that if $\gamma$ is a cycle of length $\ell > 0$,
then $\gamma$ can be written as a product of $\ell -1$
transpositions.  

\begin{definition}
  Let $\sigma$ be a permuation of a finite set $S$,
and write $\sigma$ as a product of disjoint cycles:
$$\sigma = \gamma_1\gamma_2 \cdots \gamma_r.$$
Then
$$N(\sigma) := (\ell_1 -1) + (\ell_2 -1) + \cdots + (\ell_r -1)
        = \ell_1 + \cdots + \ell_r -r,$$
where $\ell_i$ is the length of $\gamma_i$.
\end{definition}

Thus if $\ell_i$ is the length of 
the cycle $\gamma_i$ above, then $\sigma$ can
be written as a product of  $N(\sigma)$ transpositions.
However, such an expression is not unique, and in fact
even the number of transpositions in such an expression is not unique.
However, the following \textit{is} true\ 
\begin{theorem}\label{t1}
  Suppose that $\sigma$ is written as a product of $m$ transpositions
$$\sigma = \tau_1 \tau_2 \cdots \tau_m.$$
Then $m \equiv N(\sigma) \pmod 2$.
\end{theorem}
Since congruence is an equivalence relation, it follows that
if $ \sigma$ is also written as a product
of $m'$ transpositions: $\sigma = \tau'_1 \tau'_2 \cdots \tau'_{m'},$
then $m \equiv m' \pmod 2$. 

Theorem \ref{t1} follows from the following more suggestive result.

\begin{theorem}\label{t2}
   If $\alpha$ and $\beta$ are permuations of $S$, then
$$N(\alpha\beta) \equiv N(\alpha) + N(\beta) \pmod 2.$$
\end{theorem}
Indeed, note that if $\tau$ is a transposition, then $N(\tau) = 1$.
Hence it follows from Theorem \ref{t2} that
$$N(\sigma) = N(\tau_1\tau_2\cdots \tau_m) \equiv 1 + 1 + \cdots +1 \equiv
 m \pmod 2.$$
Note that in fact we only needed to apply Theorem \ref{t2} when




Here
$$(1\ 2\ 3\ 4)(4\ 5\ 6\ 7) = (1\ 2\ 3\ 4\ \5\ 6\ 7). $$

\end{document}


