Ask Your Question
0

permutations and transpositions

asked 2022-04-15 15:22:33 +0200

tunekamae gravatar image

updated 2022-04-15 15:54:32 +0200

tmonteil gravatar image

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 flag offensive close merge delete

Comments

2 Answers

Sort by ยป oldest newest most voted
0

answered 2022-04-15 16:55:34 +0200

Max Alekseyev gravatar image

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)
edit flag offensive delete link more

Comments

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
tmonteil gravatar imagetmonteil ( 2022-04-15 17:13:48 +0200 )edit

Yes, since it uses adjacent transpositions.

Max Alekseyev gravatar imageMax Alekseyev ( 2022-04-15 18:12:03 +0200 )edit
0

answered 2022-04-15 15:59:33 +0200

tmonteil gravatar image

updated 2022-04-15 17:23:42 +0200

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
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-04-15 15:22:33 +0200

Seen: 39 times

Last updated: Apr 15