Decomposition of Permutation/Permutation Cycles into Transpositions
Any Permutation Cycle of Order \(N\) can be Decomposed into a Product of \(N-1\) Transpositions in the following 2 forms
Pivot Form: In Pivot Form of Decomposition of a Permutation Cycle, the First Element of the Cycle serves as the Common Element of all the Transpositions
as given in the following examples
Chain Form: In Chain Form of Decomposition of a Permutation Cycle, the Last and the Second Last Element form the First Transposition, the Second Last and the Third Last Element form the Second Transposition and so on such that the Second and the First Element form the Last Transposition
as given in the following examples
In equations (1), (2), (3), (4), (5) and (6) given above the Left Hand Side of the equations give the Permutation Cycles and the Right Hand Side give their Decomposition into Corresponding Product of Transpositions.
Since Linear Permutations Without Repeatition are composed of a Single Permutation Cycle or Product of Two or More Disjoint Permutation Cycles, they can too be Decomposed into a Product of Transpositions
by Decomposing each of the Permutation Cycles that form them as given in the following example
In equations (7) given above the Left Hand Side of the equation gives a Permutation composed of Product of Two Disjoint Permutation Cycles and the Right Hand Side gives its Decomposition into Corresponding Product of Transpositions.
Please Note that Although both Permutation Cycles in the equation (7) have been Decomposed using the Pivot Form of Decomposition, either of them can be Decomposed using Pivot Form or Chain Form.
Also the Order in which the Permutation Cycles are Decomposed Does Not Matter.
Permutations that are Composed of (and hence can be Decomposed into) Product of Odd Number of Transpositions are called Odd Permutations. Permutations that are Composed of (and hence can be Decomposed into) Product of Even Number of Transpositions are called Even Permutations.