order of transpositions making up a permutation

If I understood correctly, any permutation can be written as a sequence $s$ ("product") of distinct transpositions (2-element swaps, each swap occurs at most once in the sequence (I consider 2 swaps equal if they swap the elements at the same positions, no matter which elements occupy the position at that time in the sequence)). For example, consider the permutation $(3,4,2,1)$ which can be obtained by swapping positions $(1,4)$, $(2,3)$, and then $(1,2)$ (at that point positions 1 and 2 are occupied by elements 4 and 3).

Now, I'm very uncertain about the degree to which I can reorder the transpositions without changing the resulting permutation. For example $(3,4,2,1)$ can also be obtained by swapping $(2,3), (1,4),(1,2)$, but not by $(1,2),(1,4),(2,3)$.

In particular, I want to assume without loss of generality that, for any given permutation, there is a sequence $s$ of transpositions such that the following transposition $(i,j)$ is last in $s$: here, $j$ is the maximum element and $i$ is the maximum over all elements occuring with $j$ in a transposition in $s$.

Can I assume this without loss of generality and what should I cite to support this? Can I assume other properties about the sequence (for example, could all transpositions be of the form $(1,j)$ while maintaining the property that none of them is repeated)?

Solution 1:

Any permutation breaks down into cycles. For example $(3,1,2,5,4)$ is the composition of cycles $(123)(45)$. The cycles can be performed in any order and we will get the same permutation.

Further each cycle can be broken down into a product of transpositions of the form $(a_ka_{k-1})(a_{k-1}a_{k-2})\cdots (a_2a_1)$, with the $a_i$ distinct. For example: $$(12345)=(54)(43)(32)(21).$$ Note (in the case of products as above, of the form $(a_ka_{k-1})(a_{k-1}a_{k-2})\cdots (a_2a_1)$ with the $a_i$ distinct) we can cycle the order of these transpositions around, and still get the same cycle.

Thus for this breakdown of a permutation into a product of cycles, you can put any transposition you like last, by first reordering the cycles, then cycling the transpositions that give you the last cycle.

Note that this product of cycles does not use any transposition more than once.

We have $$(ij)=(1i)(1j)(1i),$$ so any permutation can be expressed as a product of $(1i)$. However it may that you need to use the same transposition more than once. For example the permutation $(1,3,2)$ is not equal to $(12)(13)$ or $(13)(12)$.