9
$\begingroup$

I have four 4-cycles, given by: $(1452),(2563),(4785),(5896)$. I know that the group generated by these guys are $S(9)$ by asking mathematica for the order of the permutation group generated by these four 4-cycles, which came out to be 9!

I am looking for an elegant way to show this statement, but I can't come up with anything. We tried to show directly that we can get a 2-cycle and a 9-cycle without success.

The motivation for the problem is as follows:

9 squares are arranged in a 3 by 3 grid. I will refer to this grid as the "big square".

You have some kind of a picture drawn in the big square.

The individual squares are scrambled in some weird manner.

Is it possible to get the original picture back, using only the operation given by rotating four squares with the the center of the rotation on the vertex of the central square?

So basically:

\begin{pmatrix} 1 & 2 & 3 \\\ 4 & 5 & 6 \\\ 7 & 8 & 9 \end{pmatrix}

can become

\begin{pmatrix} 2 & 5 & 3 \\\ 1 & 4 & 6 \\\ 7 & 8 & 9 \end{pmatrix}

which corresponds to the cycle (1452).

  • 0
    @Myself: This was implemented as a combinatorial puzzle game named *Rotation* in earlier cellphone models of my former employer. This exact question made for a nice exercise in a freshman abstract algebra course during those years, when you could count on several students being familiar with the game.2012-01-07

2 Answers 2

7

Here's a more "theoretic" approach:

Let $a=(1452)$, $b=(2563)$, $c=(4785)$, and $d=(5896)$. Now note that $b$ and $c$ act transitively on $\lbrace 2,3,4,5,6,7,8\rbrace$ (you can show this directly or note that $bc$ is a $7$-cycle). Thus the subgroup $\langle b,c\rangle$ acts transitively - and thus primitively - on $7$ points. It contains a $3$-cycle $[b,c]=(4,6,5)$, and thus by a theorem of Jordan is isomorphic to $S_7$; that is, it is the full symmetry group on $\lbrace 2,3,4,5,6,7,8\rbrace$.

From here it is not hard to see $\langle b,c,d\rangle$ is isomorphic to $S_8$ on $\lbrace 2,3,4,5,6,7,8,9\rbrace$, and a similar result for $\langle a,b,c\rangle$. Together then, they must all generate $S_9$.

6

Apparently, If I denote $w=(1452)$ ,$x=(2563)$ and $y=(4785)$ then $(12) = x^y x^{-1} w^{-1}$. Other permutations of two adjacent elements on the border can of course be found from this one, by rotating or reflecting the square.

This observation allows one to "solve the square". First put the number 5 in the middle, then use these involutions to solve the border.

Please let me know if you find this too cryptic.

  • 0
    GAP :-) http://www.gap-system.org/2012-01-09