Permutation is transposition product

Dependencies:

1. Permutation is disjoint cycle product

Every finite permutation can be written as a product of transpositions.

Proof

The cycle $(a_1, a_2, \ldots, a_n)$ can as a product of transpositions in many ways. Here are two ways of doing it:

• $(a_1, a_2)(a_2, a_3)\ldots(a_{n-2}, a_{n-1})(a_{n-1}, a_n)$
• $(a_1, a_n)(a_1, a_{n-1})\ldots(a_1, a_3)(a_1, a_2)$

Since every permutation can be written as a product of disjoint cycles, every permutation can be written as a product of transpositions.

Dependency for: None

Info:

• Depth: 4
• Number of transitive dependencies: 6

Transitive dependencies:

1. /sets-and-relations/relation-composition-is-associative
2. /sets-and-relations/composition-of-bijections-is-a-bijection
3. Group
4. Subgroup
5. Permutation group
6. Permutation is disjoint cycle product