4

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?

zaa
  • 708

2 Answers2

2

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)$$

eyedropper
  • 1,323
  • I have bad wording in question, probably. In my question I have (or tried to say that I have): 1) list of multiplied elementary transpositions; 2) a form into what I want to simplify this product - using only operations with transpositions. (Calculating the given permutation and from that needed result is easy but that's not what I'm searching for.) – zaa Mar 14 '16 at 13:22
  • For example, $(1 3)(1 2)$ results in $(1 2)(2 3)(3 3)$. (Last transposition will always be like $(3 3)$ and therefore can always be skipped, actually.) – zaa Mar 14 '16 at 13:27
  • @zaarcis Yes I misunderstood. Does this answer your question? – eyedropper Mar 14 '16 at 14:21
  • Yes. Thank you! – zaa Mar 14 '16 at 14:26
  • This method (as I got told - also used in permutation parity theorem proof) is natural and possibly the only reasonable one. Thanks for your answer. – zaa Mar 14 '16 at 21:30
  • You're welcome. – eyedropper Mar 14 '16 at 21:34
1

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.

mercio
  • 50,180