9
$\begingroup$

I apologize in advance if this is too amateur, this is not really my area, but I'm very curious.

We have a permutation $\pi \in S_n$ and we want to represent it as a product of $\sigma = (1\;2)$ and $\rho = (1\;2\;\ldots\; n)$. What is the minimum number of transpositions needed to do it? For example the cost of representation of $(2\;3) \in S_3$ as $(1\;2\;3)^{-1} (1\;2) (1\;2\;3)$ is $1$. Is this problem well-known?

I've experimented with it and I have the following algorithm that works correctly for all permutations with $n \le 10$ and for a decent amount of random bigger permutations (with $n \le 30$) but I have no clue why it does.

This problem could be reduced to the following: represent $\pi$ as the product of the least amount of transpositions $(1\;2), (2\;3), \ldots, (n-1\;n),(n\;1)$ as possible. The answer to the initial problem is minimum of the lengths of shortest representations of $\langle \rho \rangle \pi \cup \pi \langle \rho \rangle$.

Without the transposition $(n\;1)$, it'd be trivial bubble sort problem. Each element of the set $\{1,\ldots,n\}$ has a trajectory with respect to a representation as a product of these transpositions i.e. if $\pi = \alpha_1 \cdot \ldots \cdot \alpha_k$ then the trajectory of $i$ is $\alpha_k(i), \alpha_{k-1}\alpha_k(i), \ldots, \pi(i)$ For the bubble sort, the trajectory in the optimal representation is unique up to the repetitions, if $\pi(i) < i$ then it looks like $i, \ldots, i, i-1, \ldots, i-1, i-2, \ldots, i-2, \ldots, \pi(i) \ldots, \pi(i)$.

With the transposition $(n\;1)$ the situation changes and there are two possibilities for the trajectory of each element: for $i > \pi(i)$ the new option for trajectory is $i, i+1, \ldots, n, 1, \ldots, \pi(i)$ (repetitions omitted). We say that $i_0$ and $j_0$ form an inversion with respect to the trajectories $a_1, \ldots, a_k$ (the trajectory of $i_0$) and $b_1, \ldots, b_m$ (the trajectory of $j_0$) iff for every sequence $(x_1, y_1), \ldots, (x_{m+k-2}, y_{m+k-2}) \in [k] \times [m]$ such that $(x_{i+1}, y_{i+1}) \in \{(x_i+1,y_i), (x_i, y_i+1)\}$ for each $i \in \{1, \ldots, m+k-3\}$, $x_1 = y_1 = 1$, $x_{m+k-2} = k;\;y_{m+k-2}=m$ there exists $i \in [m+k-3]$ such that $a_{x_i} = b_{y_i}$ or $a_{x_{i+1}} = b_{y_{i+1}}$ or $a_{x_i} = b_{y_{i+1}} \land a_{x_{i+1}} = b_{y_i}$ i.e. it's not possible to move $i_0$ and $j_0$ along their trajectories such that they never swap. Therefore if we fix one of the options for each element in $\{1,\ldots,n\}$ then the number of transpositions needed to represent $\pi$ with fixed trajectories equals to the number of inversions with respect to the trajectories.

The algorithm. Fix $s \in \{0, \ldots, n-1\}$ and consider a permutation $\sigma = (1\;2\;\ldots\;n)^s \pi$. For each $i \in [n]$ select the trajectory involving $(1\;n)$ if $|i - \sigma(i)| > {n \over 2}$ and select the standard trajectory otherwise. For each $s$ calculate the number of inversions with respect to selected trajectories and print the minimum of these values.

$\endgroup$
  • 4
    $\begingroup$ I believe that you are just asking about the length of an element in the symmetric group considered as a Coxeter group for the standard Coxeter system of generators $\{\sigma, \rho^{-1}\sigma\rho, \dots, \rho^{-(n-1)}\sigma\rho^{(n-1)}\}$ with $\sigma=(1,2)$ and $\rho=(1,2,\dots,n)$. $\endgroup$ – Jason Starr Jan 8 '18 at 12:40
  • 1
    $\begingroup$ arxiv.org/pdf/1303.3776.pdf and its references might help. $\endgroup$ – Brian Hopkins Jan 8 '18 at 13:57
  • 2
    $\begingroup$ I'm a bit puzzled. For $\mathfrak S_3$, is the length of the long cycle zero or two? In @JasonStarr's generating system, if I made no mistake, a minimal expression would be $\rho^{-1}\sigma\rho\sigma$. $\endgroup$ – Martin Rubey Jan 8 '18 at 15:30
  • 2
    $\begingroup$ @MartinRubey, oh, you are right, thank you! The cost of an element $\pi$ is the minimum among the lengths of elements $\langle \rho \rangle \pi \cup \pi \langle \rho \rangle$ in JasonStarr's system. $\endgroup$ – Artur Riazanov Jan 8 '18 at 16:18
  • 1
    $\begingroup$ @ArturRyazanov: the cost of an element $\pi$ is now findstat.org/St001078. There, you can also find code to compute it (using gap or sage). $\endgroup$ – Martin Rubey Jan 10 '18 at 8:14

Your Answer

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

Browse other questions tagged or ask your own question.