Editing Symmetric group (section)

=== Transpositions, sign, and the alternating group ===
{{main article|Transposition (mathematics)}}
A '''transposition''' is a permutation which exchanges two elements and keeps all others fixed; for example (1 3) is a transposition. Every permutation can be written as a product of transpositions; for instance, the permutation ''g'' from above can be written as ''g'' = (1 2)(2 5)(3 4). Since ''g'' can be written as a product of an odd number of transpositions, it is then called an [[Even and odd permutations|odd permutation]], whereas ''f'' is an even permutation.

The representation of a permutation as a product of transpositions is not unique; however, the number of transpositions needed to represent a given permutation is either always even or always odd. There are several short proofs of the invariance of this parity of a permutation.

The product of two even permutations is even, the product of two odd permutations is even, and the product of one of each is odd.  Thus we can define the '''sign''' of a permutation:

:<math>\operatorname{sgn}f = \begin{cases} +1, & \text{if }f\mbox { is even} \\ -1, & \text{if }f \text{ is odd}. \end{cases}</math>

With this definition,
:<math>\operatorname{sgn}\colon \mathrm{S}_n \rightarrow \{+1, -1\}\ </math>
is a [[group homomorphism]] ({+1, −1} is a group under multiplication, where +1 is e, the [[neutral element]]). The [[Kernel (algebra)|kernel]] of this homomorphism, that is, the set of all even permutations, is called the '''[[alternating group]]''' A<sub>''n''</sub>. It is a [[normal subgroup]] of S<sub>''n''</sub>, and for {{nowrap|''n'' ≥ 2}} it has {{nowrap|''n''!/2}} elements. The group S<sub>''n''</sub> is the [[semidirect product]] of A<sub>''n''</sub> and any subgroup generated by a single transposition.

Furthermore, every permutation can be written as a product of ''[[adjacent transposition]]s'', that is, transpositions of the form {{nowrap|(''a'' ''a''+1)}}.  For instance, the permutation ''g'' from above can also be written as {{nowrap|1=''g'' = (4 5)(3 4)(4 5)(1 2)(2 3)(3 4)(4 5)}}. The sorting algorithm [[bubble sort]] is an application of this fact.  The representation of a permutation as a product of adjacent transpositions is also not unique.