# permutations and transpositions

How a permutation be converted to a product of transpositions. inversions() gives an incorrect anser.

P=Permutation([4, 8, 3, 1, 9, 2, 6, 7, 5]); P.inversions()
[(1, 3),(1, 4),(1, 6),(2, 3),(2, 4),(2, 6),(2, 7),(2, 8),(2, 9),(3, 4),(3, 6),(5, 6),(5, 7),(5, 8),(5, 9),(7, 9),(8, 9)]


I expect

[(1,3),(1,4),(2,3),(2,4),(2,6),(2,7),(2,8),(3,6),(5,9)]

edit retag close merge delete

( 2022-04-15 15:59:03 +0200 )edit

Sort by ยป oldest newest most voted

This can be done via reduced words:

P = Permutation([4, 8, 3, 1, 9, 2, 6, 7, 5])
r = P.reduced_word()
q = [(i,i+1) for i in r]
assert prod(Permutation(str(i)) for i in q[::-1]) == P
print(q)

more

Note that this decomposition is pretty long:

sage: q
[(3, 4),
(2, 3),
(1, 2),
(7, 8),
(6, 7),
(5, 6),
(4, 5),
(3, 4),
(2, 3),
(4, 5),
(3, 4),
(8, 9),
(7, 8),
(6, 7),
(5, 6),
(7, 8),
(8, 9)]
sage: len(q)
17

( 2022-04-15 17:13:48 +0200 )edit

Yes, since it uses adjacent transpositions.

( 2022-04-15 18:12:03 +0200 )edit

First, note that the image of 1 is 4, the image of 6 is 2:

sage: P(1)
4
sage: P(6)
2
sage: P(6) < P(1)
True


Hence, (1,6) should be part of the inversions (an inversion is a pair (i,j) such that i<j and P(i)>P(j)).

Now, if you want to decompose a permutations into transpositions, note that there are many ways, none of them is canonical. However, you can decompose your permutation into disjoint cycles and then each cycle can be decomposed into transpositions.

sage: C = P.cycle_tuples() ; C
[(1, 4), (2, 8, 7, 6), (3,), (5, 9)]


From such a decomposition, you can easily get a decomposition of the permutation into tuples (because (a1,a2,a3,...,an) = (a1,a2)(a1,a3)...(a1,an)) :

sage: L = []
....: for c in C:
....:     if len(C) >= 2:
....:         a = c[0]
....:         for b in c[1:]:
....:             L.append((a,b))

sage: L
[(1, 4), (2, 8), (2, 7), (2, 6), (5, 9)]


You can check:

sage: prod(Permutation(t) for t in L)
[4, 8, 3, 1, 9, 2, 6, 7, 5]

sage: prod(Permutation(t) for t in L) == P
True

more