is the Japanese name for a popular method of randomly pairing the elements of a finite set with the elements of another finite set of the same size. This method is also well-known (under different names) in parts of Korea and China, but it was new to me until I read a recent paper on the arXiv written by Chinese authors: http://arxiv.org/abs/1303.3776
The main picture shows an example of how this pairing procedure works, by randomly matching eight people with eight drinks. We start by listing the people and the drinks in some order (such as alphabetical order) from left to right, and then we draw vertical lines connecting each person to a drink. Next, we randomly draw horizontal line segments between adjacent pairs of vertical lines, in such a way that we never have four lines meeting at the same point.
To create the corresponding random matching, we follow each vertical line from top to bottom in such a way that we make a right angled turn every time we hit a T-shaped junction, and in such a way that at all stages of the process we are either moving sideways or downwards. The second picture shows what happens after this procedure has been carried out to create four pairings between two sets of four people. The red, orange, green and cyan paths show which individuals end up paired together.
Sometimes people are surprised that this procedure results in everyone finding a partner, but if you are familiar with group theory
, this is not a surprise. Group theory is the branch of mathematics that deals with the abstract study of symmetry. Even better, the amidakuji model can be used to illustrate various results from group theory.
The group that is relevant in this situation is the symmetric group
, S_n, which consists of all ways of permuting n
objects among themselves, where the objects are numbered from 1 up to n
. Each horizontal line segment in the picture corresponds to a simple transposition
in S_n, that is, the exchange of two adjacent objects, i
. A theorem that can be proved about the symmetric group is that the group is generated by the simple transpositions
. What this means in terms of the picture is that it is possible to create any pairing you like between the input set and the output set by inserting a suitable set of horizontal lines
It is possible for different arrangements of horizontal lines to result in the same pairing between the input and output sets. The black and white diagram gives two examples of this. In the first situation, three horizontal lines are moved around in a way that results in the same pairing; mathematicians sometimes call this rearrangement a braid move
. In the second situation, two consecutive horizontal lines that can be slid into each other transversely end up cancelling each other out; we will refer to this move as creation
, depending on the direction in which it is applied. As well as these situations, one is free to slide the horizontal lines upwards and downwards, so long as one never has four lines meeting at a point at any intermediate stage; we will refer to such a move as a legal slide
Another theorem about the symmetric group that can be easily stated in terms of the picture is the following. If one takes two identical diagrams and adds two different sets of horizontal lines that result in the same pairing between the input and the output sets, then it is possible to transform one of these pictures into the other by a sequence of legal slides, braid moves, creations and deletions.
If one never has an opportunity to apply any deletions, even after performing a sequence of braid moves or legal slides, then it is a theorem that the number of horizontal lines in the picture is as small as possible for the permutation it achieves. This number is called the length
of the permutation. For example, the arrangement or horizontal lines in the picture matching eight people in pairs is very inefficient: although it uses 10
horizontal lines, it is possible to achieve the same effect with only 2
horizontal lines; one between the first and second vertical lines, and the other between the third and fourth. So the length of this permutation is 2
. It is a (non-obvious) theorem about permutations that it is not possible to represent the same permutation in two different ways, one of which uses an odd number of horizontal lines and the other of which uses an even number of horizontal lines. A permutation is called odd
depending on whether one needs an odd or an even number of horizontal lines to represent it. The permutation in the second picture is even, because 10 and 2 are both even numbers.
Another Japanese idea that can be illustrated by these pictures is Matsumoto's Theorem
. In this situation, Matsumoto's Theorem says that if one has two ways to represent the same permutation, both of which use the minimal number of horizontal edges, then it is possible to transform one picture into the other by using only braid moves and legal slides; in particular, one never needs to use any creation or deletion moves.#mathematics