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.

Improve this question
$\endgroup$
8
  • 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, 2018 at 12:40
  • 1
    $\begingroup$ arxiv.org/pdf/1303.3776.pdf and its references might help. $\endgroup$
    – Brian Hopkins
    Jan 8, 2018 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, 2018 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, 2018 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, 2018 at 8:14

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.