'Canonical' form of permutations, product of transpositions

Question

I have such 'canonical' form of permutations: $\prod_{i=0}^n (i \ k_i)$, where $i \leq k_i \leq n$.

For example, there are all $6$ permutations of $3$ elements. Of course, some transpositions do nothing and can be removed.

$(0 \ 0) (1 \ 1) (2 \ 2) \\ (0 \ 0) (1 \ 2) (2 \ 2) \\ (0 \ 1) (1 \ 1) (2 \ 2) \\ (0 \ 1) (1 \ 2) (2 \ 2) \\ (0 \ 2) (1 \ 1) (2 \ 2) \\ (0 \ 2) (1 \ 2) (2 \ 2)$

Is there some simple algorithm to find this form of any permutation (given as product of transpositions, for example, $(0 \ 1)(2 \ 3)(1 \ 2)(1 \ 3)$ ), using only operations with transpositions?

Answer 1

Yes there is. Every permutation can be expressed in terms of disjoint cycles. Every cycle can be written in terms of elementary transpositions.

For example a cycle $(1,2,3)$ means $1\rightarrow 2 \rightarrow 3\rightarrow 1$ can be written as $(1\; 3)(1\; 2)$.

In general any cycle $(a_1,a_2,\ldots a_n)$ can be expressed as

$$(a_1,a_2,\ldots a_n)=(a_1\; a_n)(a_1\; a_{n-1})\cdots (a_1\; a_2)$$

Notice one important detail. If two transpositions do not act on the same elements (the same goes for cycles) they commute, for example $(1\; 2)(3\; 4)=(3\; 4)(1\; 2)$ but not $(1\; 2)(2\; 4)=(2\; 4)(1\; 2)$.

Therefore, in breaking up a permutation into transpositions, order must be preserved.

EDIT:

There are two possible cases when we consider a product of two transpositions. $(a\; b)(c\; d)$ where all the elements are distinct. These transpositions commute. The other case is $(a\; b)(a\; c)$ and we use the previous cycle notation to see that

$$(a\; b)(a\; c)=(a,c,b)$$

But this is the same as

$$(a,c,b)=(c,b,a)=(b,a,c)$$

Breaking this up into transpositions gives the equalities

$$(a\; b)(a\; c)=(a\; c)(b\; c)=(b\; c)(a\; b)$$

Of course $(a\; b)=(b\; a$).

Now we can use this to find the canonical form of any product of transpositions. In your example $(1\;3)(1\;2)$ gives

$$(1\;3)(1\;2)=(1\;2)(2\;3)$$

We ignore transpositions of the form $(a\;a)$. To solve the permutation in your original answer:

$$(0\; 1)(2\;3)(1\;2)(1\;3)=(0\; 1)(2\;3)\left((1\;2)(1\;3)\right)=(0\; 1)(2\;3)(2\;3)(1\;2)=(0\; 1)(2\;3)^2(1\;2)=(0\;1)(1\;2)$$

Answer 2

You can apply the following rewrite rules (I assume you only write $(ab)$ when $a \le b$) :

$(c d)(a b) \to (a b)(c d)$ when $a < c \le d, a \le b, b \neq c, b \neq d$
$(b c)(a b) \to (a c)(b c)$ when $a < b \le c$
$(a b)(a c) \to (a c)(b c)$ when $a < b \le c$
$(a c)(a b) \to (a b)(b c)$ when $a < b < c$
$(a b)(a b) \to (a a)(b b)$ when $a < b$
$(a b)(a a) \to (a b)$ when $a \le b$
$(a a)(a b) \to (a b)$ when $a \le b$

This will have the effect of moving anything involved with $0$ to the left of the string of transpositions, and then merging every occurence of $0$ into only one. What remains after this is a one transposition involving $0$, followed by a string of transpositions who can only involve things up from $1$. Then the rules will moves all the $1$s to the left, merge them, etc.

To make sure the permutation is in its canonical form you have to fill in the gaps in the end result by adding $(aa)$s as necessary, or you could append $(00)(11)(22)\ldots(nn)$ to the original string before starting.