Express a permutation using minimal number of simple reflections.

Question

I have a permutation $w=(25673)(14)$. I want to express $w$ in terms of minimal number of simple reflections of type A Weyl group. I can do this as follows. First we have $w=(23)(27)(26)(25)(14)$. Then using $(ij)=s_i s_{i+1} \cdots s_{j-2} s_{j-1} s_{j-2} \cdots s_{i+1} s_i$ and $s_i^2=1$ and $s_i s_{i+1} s_{i} = s_{i+1} s_{i} s_{i+1}$, $s_i s_j = s_j s_i (|i-j|\geq 2)$, we have $w=s_6 s_5 s_2 s_3 s_4 s_1 s_2 s_3 s_1$. Are there some software which can do this? Thank you very much.

Answer 1

Here's a simpler way to do this. First, list the images of the numbers $1,\ldots,n$ under the permutation, e.g. $$ (2\;5\;6\;7\;3)(1\;4) \quad\text{gives}\quad 4\;5\;2\;1\;6\;7\;3 $$ Next, use the bubble sort algorithm to sort this list of numbers, keeping track of the positions of the switched numbers in each case: $$ \begin{multline*} 4\;5\;2\;1\;6\;7\;3 \;\underset{23}{\longrightarrow}\; 4\;2\;5\;1\;6\;7\;3 \;\underset{34}{\longrightarrow}\; 4\;2\;1\;5\;6\;7\;3 \;\underset{12}{\longrightarrow}\; 2\;4\;1\;5\;6\;7\;3 \\[6pt] \;\underset{23}{\longrightarrow}\; 2\;1\;4\;5\;6\;7\;3 \;\underset{12}{\longrightarrow}\; 1\;2\;4\;5\;6\;7\;3 \;\underset{67}{\longrightarrow}\; 1\;2\;4\;5\;6\;3\;7\\[6pt] \;\underset{56}{\longrightarrow}\; 1\;2\;4\;5\;3\;6\;7 \;\underset{45}{\longrightarrow}\; 1\;2\;4\;3\;5\;6\;7 \;\underset{34}{\longrightarrow}\; 1\;2\;3\;4\;5\;6\;7 \end{multline*} $$ Then $$ (2\;5\;6\;7\;3)(1\;4) \;=\; (2\;3)(3\;4)(1\;2)(2\;3)(1\;2)(6\;7)(5\;6)(4\;5)(3\;4). $$ It should be easy to modify any standard implementation of bubble sort to implement this algorithm.