Amidakuji Puzzle and math behind it

Question

Ghost Leg (Chinese: 畫鬼腳), known in Japan as Amidakuji (阿弥陀籤, "Amida lottery", so named because the paper was folded into a fan shape resembling Amida's halo1) or in Korea as Sadaritagi (사다리타기, literally "ladder climbing"), is a method of lottery designed to create random pairings between two sets of any number of things, as long as the number of elements in each set is the same. This is often used to distribute things among people, where the number of things distributed is the same as the number of people.

The picture depicts how the game is played

You can add as many rungs on the ladders as you want. But the minimal rungs needed to show the same permutation of above and below elements is what wikipedia calls 'Prime Ladder'.

To get a prime ladder Wikipedia describes bubble sort method where 2 operations happen usually.

These 2 operations :

These 2 operations reduce the number of rungs keeping the permutation of elements as the same when the rungs were not reduced.

The second operation of eliminating 2 rungs consecutively can be easily understood since you go to the other vertical line through one rung and come back to the original vertical line through the next rung.

But why does the first operation work? How can we mirror switch the rungs like shown in the 1st operation.

To get more clarity about this question you can go here

Answer 1

For both pairs the ladders are equivalent: The first pair of ladders maps (a,b,c) to (3,2,1), the second pair of ladders maps (a,b) to (1,2)

Another interesting question is, why is this always a permutation? Is it possible the at two letters are assigned to the same number? With induction we can prove that it this mapping is always a permutation. We start with a ladder with no rungs. This is always a permutation (if we identify a with 1, b with 2,...)

Now assume that we have already assigned some rungs. We are not interested in details, so we don't show the actual rungs. We only assume that all rungs are in the black area.

If we now add a new rung, e.g. the red one, we still have a permutation. The only thing that changes is that the letter that had previously assigned 3 has now assigned 4 and the latter that had previously assigned 4 has now assigned 3. So we can build such a ladder step by step and we will always have a permutation after each step. From these pictures we also can deduce: Every segment on the horizontal line is traversed only by one path, every rung is traversed exactly two times. These two traversals have opposite direction.

Answer 2

In addition to the pictorial proof that is perhaps more intuitive, we may interpret this kind of diagram as representing permutations, or in other words elements of the symmetric group, by decomposing them into adjacent transpositions (permutations involving only neighbouring elements), and provide an algebraic proof (or motivation) of the operations.

Taking this view, we can write down the element of the symmetric group that each element represents. Each rung between leg $i$ and leg $i+1$ corresponds to the $i$-th transpostion $\sigma_i$, and we can go from the top of the diagram and enumerate all the transpositions, then multiply them in order. For example, the two diagrams in rule 1 can be interpreted as $\sigma_1 \sigma_2 \sigma_1$ and $\sigma_2 \sigma_1 \sigma_2$, respectively.

Now, the generators $\sigma_1, \dots, \sigma_{n-1}$ of the symmetric group satisfy the relations $\sigma_i^2 = 1$, $\sigma_i \sigma_j = \sigma_j \sigma_i$ for $|i-j|>1$ and $(\sigma_i\sigma_{i+1})^3 = 1$. The first relation corresponds to operation 2. The second relation means that disjoint cycles commute. Put differently, two transpositions that involve two sets of objects that don't share elements can be done in any order. This property is reflected in the amidakuji diagram by the fact that rungs that don't share legs can be drawn at any vertical position relative to each other, or that you can "slide" a rung up and down, as long as it doesn't touch the end of another rung.

The third relation corresponds to operation 1. To see this, we need to first expand $(\sigma_i\sigma_{i+1})^3$ into $\sigma_i \sigma_{i+1} \sigma_i \sigma_{i+1} \sigma_i \sigma_{i+1}$. Multiplying from the right by $\sigma_{i+1}\sigma_i\sigma_{i+1}$, and using the fact that $\sigma_i^2 = 1$ for all $i$, we get the relation $\sigma_i \sigma_{i+1}\sigma_i = \sigma_{i+1}\sigma_i\sigma_{i+1}$. In the case where there are only three objects to permute, this relation tells us $\sigma_1 \sigma_2 \sigma_1 = \sigma_2 \sigma_1 \sigma_2$. As we've seen earlier, the group elements on the two sides of this equation are precisely represented by the two configurations involved in operation 1.