# The number of transpositions in a representation of a permutation is even for even permutation and odd for odd permutation

This is exercise 9.6b from Section. The Rational Numbers in textbook Analysis I by Amann/Escher.

On the symmetric group $$\mathrm{S}_n$$, define the sign function by $$\operatorname{sign} \sigma := \prod_{1 \leq j

The alternating group $$\mathrm{A}_{n}$$ is defined as $$\mathrm{A}_{n} := \{\sigma \in \mathrm{S}_{n} \mid \operatorname{sign} \sigma = 1\}$$.

A transposition is a permutation which interchanges two numbers and leaves the others fixed.

Prove that

1. $$\mathrm{A}_{n}$$ has order $$n!/2$$ for $$n \geq 2$$, and $$1$$ for $$n=1$$.

2. For $$n \ge 2$$, any permutation $$\sigma \in \mathrm{S}_{n}$$ can be represented as a composition of transpositions: $$\sigma=\sigma_{1} \circ \sigma_{2} \circ \cdots \circ \sigma_{N}$$, and then $$\operatorname{sign} \sigma=(-1)^{N}$$, independent of this representation. Thus the number of transpositions in the representation is even for even permutations and odd for odd permutations.

Could you please verify if my attempt is fine or contains logical gaps/errors?

My attempt:

1. For $$\sigma \in \mathrm{A}_{n}$$, we define $$\sigma' \in \mathrm{S}_{n}$$ by $$\sigma' (k) = \sigma (k)$$ for all $$k \in \{2 , \ldots,n\}$$, $$\sigma' (1) = \sigma (2)$$, and $$\sigma' (2) = \sigma (1)$$. It follows that $$\operatorname{sign} \sigma' = -1$$ and that the function

$$\begin {array}{lrcl} & \mathrm{A}_{n} & \longrightarrow & \mathrm{S}_{n} - \mathrm{A}_{n} \\ & \sigma & \longmapsto & \sigma' \end{array}$$

is bijective. Then $$|\mathrm{A}_{n}| = |\mathrm{S}_{n} - \mathrm{A}_{n}| = |\mathrm{S}_{n}|/2 = n!/2$$ for $$n \ge 2$$.

1. For $$\sigma \in \mathrm{S}_{n}$$, we define $$(\sigma_m)_{m \le n}$$ recursively by $$\sigma_0 = \operatorname{id}_{\{1,\ldots,n\}}$$ and $$\sigma_{m}$$ by transposing $$m$$ and $${(\sigma_0 \circ \cdots \circ \sigma_{m-1})}^{-1} \circ \sigma (m)$$.

Next we prove $$\sigma_0 \circ \cdots \circ \sigma_{m} \restriction \{1, \ldots, m\} = \sigma \restriction \{1, \ldots, m\}$$ by induction on $$m$$. Since $$\sigma_1$$ transposes $$1$$ and $$\sigma_0^{-1} \circ \sigma(1) = \sigma(1)$$. It follows that the statement holds for $$m = 1$$. Let it hold for $$m$$. Then $$\sigma_0 \circ \cdots \circ \sigma_{m} \restriction \{1, \ldots, m\} = \sigma \restriction \{1, \ldots, m\}$$. Because $$\sigma_{m+1}$$ transposes $${m+1}$$ and $${(\sigma_0 \circ \cdots \circ \sigma_{m})}^{-1} \circ \sigma ({m+1})$$, we have \begin{aligned}\sigma_0 \circ \cdots \circ \sigma_{m} \circ \sigma_{m+1} (m+1) &= \sigma_0 \circ \cdots \circ \sigma_{m} \left ({(\sigma_0 \circ \cdots \circ \sigma_{m})}^{-1} \circ \sigma ({m+1}) \right)\\ &= {(\sigma_0 \circ \cdots \circ \sigma_{m})} \circ {(\sigma_0 \circ \cdots \circ \sigma_{m})}^{-1} \circ \sigma ({m+1})\\ &= \sigma ({m+1})\end{aligned}

I claim that $${(\sigma_0 \circ \cdots \circ \sigma_{m})}^{-1} \circ \sigma ({m+1}) > m$$. If not, $${(\sigma_0 \circ \cdots \circ \sigma_{m})}^{-1} \circ \sigma ({m+1}) = m' \le m$$. Then $$\sigma ({m+1}) = \sigma_0 \circ \cdots \circ \sigma_{m} (m') = \sigma (m')$$ by inductive hypothesis. This contradicts the fact that $$\sigma$$ is bijective.

If $$i \le m$$ then $$m+1 \neq i < {(\sigma_0 \circ \cdots \circ \sigma_{m})}^{-1} \circ \sigma ({m+1})$$ and thus $$\sigma_0 \circ \cdots \circ \sigma_{m} \circ \sigma_{m+1} (i) = \sigma_0 \circ \cdots \circ \sigma_{m} (i) = \sigma (i)$$ by inductive hypothesis.

As a result, $$\sigma_0 \circ \cdots \circ \sigma_{m+1} \restriction \{1, \ldots, m+1\} = \sigma \restriction \{1, \ldots, m+1\}$$

This completes the proof. It follows directly that \begin{aligned}\sigma_1 \circ \cdots \circ \sigma_{n} &= \sigma_0 \circ \cdots \circ \sigma_{n} \restriction \{1, \ldots, n\} \\ &= \sigma \restriction \{1, \ldots, n\} \\ &= \sigma \end{aligned}

where $$\sigma_1, \ldots, \sigma_n$$ are transpositions.

• $\sigma'$ is not well-defined. Perhaps you can define for all $k\in\{3,\ldots, n\}.$ – Thomas Shelby Jun 23 at 7:54
• Thank you so much @ThomasShelby ;) You are right. Have you seen any other error/gap in my attempt? – MadnessFor MATH Jun 23 at 14:01
• Hi @ThomasShelby, Since the function $\mathrm{A}_{n} \longrightarrow \mathrm{S}_{n} - \mathrm{A}_{n}$ is bijective, $|\mathrm{A}_{n}| = |\mathrm{S}_{n} - \mathrm{A}_{n}|$. On the other hand, $\mathrm{A}_{n} \cup (\mathrm{S}_{n} - \mathrm{A}_{n}) = \mathrm{S}_{n}$ and thus $|\mathrm{A}_{n}| + |\mathrm{S}_{n} - \mathrm{A}_{n}| = |\mathrm{S}_{n}|$. The result then follows. – MadnessFor MATH Jun 23 at 15:24
• Okay, proof of part $(1)$ looks fine to me. I don't know about part $(2)$. Sorry:-( – Thomas Shelby Jun 23 at 15:41
• Thank you so much for your dedicated support @ThomasShelby. I am more than happy to see you again in my question ;) – MadnessFor MATH Jun 23 at 15:44