The State Diagram & The Missing Permutations

  You may have noticed that there are no lines linking the states 0 and 4 or 0 and 5 on the state diagram in the last blog. These permutations require a combination of two successive elementary permutations that can be defined as Y = GR and M = BR. If we allow Y to operate repeatedly on state S₀ = (0,1,2) it produces the states S₄ = (1,2,0), S₅ = (2,0,1) and again S₀ = (0,1,2). Y operating repeatedly on S₁ = (1,0,2) produces S₂ = (0,2,1), S₃ = (2,1,0) and again S₁ = (1,0,2). If you study the changes in the states you will see that Y is the left-shift operator which moves the second two objects one space to the left and tacks the first object on the end. M is the right-shift operator and the inverse of Y so MY = I. There are a total of 6 permutation operations altogether which consist of the identity operation I, the 3 elementary pairs of exchanges and the 2 shift operations. The products of these operations form the group seen in the complete product table below where the operations in the upper row are followed by those in the left column giving the entry in the corresponding row and column of the table. Checking we see that R in the upper row followed by G in the left column is GR = Y and similarly BR = M.

Two sets of triangles in the state diagram are formed by the lines corresponding to the repeated action of Y and M which could be represented by yellow and magenta lines. They also point out that the lines in state diagrams are directional so we would have yellow lines going one way and magenta lines going the other.

This has nothing to do with global warming but shows how complicated state diagrams can get. The permutations have an interesting state diagram and form a good introduction to what is called group theory.

Supplemental (Nov 21): The complete state diagram (arrows indicate the action of a permutation):

The state diagram gives a better picture of the changes produced by the permutation operations than the product table does since it has the labeled states on it. Group theory helped to generate the state diagram for the permutations.