A permutation $\sigma$ of a set $\{1,2,...,k\}$ is a bijective function mapping this set onto it self. Denote the set of all permutations of this set by $S_{k}$.

An elementary permutation $e_{i}$ of $S_{k}$ is a permutation that satisfies $e_{i}(j)=j$ if $j\notin\{i,i+1\}$, $e_{i}(i)=i+1$ and $e_{i}(i+1)=i$. That is, $e_{i}$ change $i$ with $i+1$ and preserves another numbers.

We know that every permutation $\sigma$ can be written by a composition of elementary permutations. But I'm thinking in something that I didn't saw at any book: Every permutation $\sigma$ can be written by a composition of elementary permutations with no repetition? By 'no repetition' I mean that a elementary permutation $e_{i}$ doesn't appear more than one time in the composition for $\sigma$

  • $\begingroup$ I think the answer to your question is yes. It is enough to do it for cycles and for those is quite easy. $\endgroup$ – Quimey Jun 1 '18 at 19:45
  • $\begingroup$ I doubt it is enough to consider the cycle case, since by composing cycles you might get repetitions. $\endgroup$ – Hw Chu Jun 1 '18 at 19:47
  • 3
    $\begingroup$ Did you try to do this for $S_3$? $\endgroup$ – Tobias Kildetoft Jun 1 '18 at 19:50
  • $\begingroup$ Cycles are disjoint and transposition for each cycle only use those elements (en.wikipedia.org/wiki/Cycle_decomposition) $\endgroup$ – Quimey Jun 1 '18 at 19:50
  • 3
    $\begingroup$ At $S_{3}$ I found the permutation $(\sigma (1),\sigma (2),\sigma (3))=(3,2,1)$. There's no way to express $\sigma$ in terms of elementary permutations without repetition. Is there some rule about that? $\endgroup$ – Mateus Rocha Jun 1 '18 at 21:31

As discussed in the comments, the permutation $(13)\in S_3$ cannot be represented as a product of neighbour exchanges without either of the two available exchanges being used twice.

More generally, there are $n-1$ neighbour exchanges, and we can form at most $\sum_{k=0}^{n-1}k!$ different products from them. For $n\gt2$, this is less than $n!$ (which you can prove by induction), so we can't generate all $n!$ permutations with these products.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.