TAOCP 7.2.1.2 Exercise 36

Let the $4\times 4$ board be identified with coordinates $(r,c)$, where $0\le r,c\le 3$, and the given labeling is \begin{matrix} 0 & 1 & 2 & 3\\ 4 & 5 & 6 & 7\\ 8 & 9 & a & b\\

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.1.2: Generating All Permutations

Exercise 36. [M23] [M23] Find a Sims table for the group of all automorphisms of the 4×4 tic-tac-toe board 0 1 2 3 4 5 6 7 8 9 a b c d e f , namely the permutations that take lines into lines, where a “line” is a set of four elements that belong to a row, column, or diagonal.

Verified: no
Solve time: 2m16s

Solution

Let the $4\times 4$ board be identified with coordinates $(r,c)$, where $0\le r,c\le 3$, and the given labeling is

$$ \begin{matrix} 0 & 1 & 2 & 3\ 4 & 5 & 6 & 7\ 8 & 9 & a & b\ c & d & e & f \end{matrix} $$

so that

$$ 0=(0,0),\ 1=(0,1),\ \dots,\ f=(3,3). $$

A line is a 4-element set forming a row, column, or a diagonal of the square. Any automorphism must send rows to rows or columns, since rows are exactly the 4-element lines whose pairwise intersections with the family of all lines match the row pattern, and no diagonal has that same incidence profile. Consequently, every automorphism is induced by a permutation of the coordinate square that preserves adjacency of the grid structure and preserves diagonals as lines.

The only permutations of the $4\times 4$ grid preserving rows, columns, and both main diagonals are the dihedral symmetries of the square. Hence the group is isomorphic to $D_4$ and has order $8$. A Sims table is therefore given by any strong generating list of these $8$ permutations acting on ${0,1,\dots,f}$.

We now write the $8$ permutations explicitly in the given labeling.

The identity permutation is

$$ I = (0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f). $$

Rotation by $90^\circ$ clockwise, given by $(r,c)\mapsto(c,3-r)$, is

$$ \rho = \begin{pmatrix} 0&1&2&3&4&5&6&7&8&9&a&b&c&d&e&f\ 3&7&b&f&2&6&a&e&1&5&9&d&0&4&8&c \end{pmatrix}. $$

Rotation by $180^\circ$, $(r,c)\mapsto(3-r,3-c)$, is

$$ \rho^2 = \begin{pmatrix} 0&1&2&3&4&5&6&7&8&9&a&b&c&d&e&f\ f&e&d&c&b&a&9&8&7&6&5&4&3&2&1&0 \end{pmatrix}. $$

Rotation by $270^\circ$, $(r,c)\mapsto(3-c,r)$, is

$$ \rho^3 = \begin{pmatrix} 0&1&2&3&4&5&6&7&8&9&a&b&c&d&e&f\ c&8&4&0&d&9&5&1&e&a&6&2&f&b&7&3 \end{pmatrix}. $$

Reflection across the vertical axis, $(r,c)\mapsto(r,3-c)$, is

$$ \sigma_v = \begin{pmatrix} 0&1&2&3&4&5&6&7&8&9&a&b&c&d&e&f\ 3&2&1&0&7&6&5&4&b&a&9&8&f&e&d&c \end{pmatrix}. $$

Reflection across the horizontal axis, $(r,c)\mapsto(3-r,c)$, is

$$ \sigma_h = \begin{pmatrix} 0&1&2&3&4&5&6&7&8&9&a&b&c&d&e&f\ c&d&e&f&8&9&a&b&4&5&6&7&0&1&2&3 \end{pmatrix}. $$

Reflection across the main diagonal, $(r,c)\mapsto(c,r)$, is

$$ \sigma_d = \begin{pmatrix} 0&1&2&3&4&5&6&7&8&9&a&b&c&d&e&f\ 0&4&8&c&1&5&9&d&2&6&a&e&3&7&b&f \end{pmatrix}. $$

Reflection across the anti-diagonal, $(r,c)\mapsto(3-c,3-r)$, is

$$ \sigma_{ad} = \begin{pmatrix} 0&1&2&3&4&5&6&7&8&9&a&b&c&d&e&f\ f&b&7&3&e&a&6&2&d&9&5&1&c&8&4&0 \end{pmatrix}. $$

These eight permutations form a group under composition, closed because they are exactly the dihedral symmetries of the square, and each preserves rows, columns, and diagonals, hence maps every line to a line. No further automorphisms exist because any automorphism is determined by the image of a single cell and its two independent incident directions (row and column directions), which forces a rigid placement consistent with one of the eight symmetries above.

A Sims table for the group can therefore be taken as the ordered list

$$ (I,\ \rho,\ \rho^2,\ \rho^3,\ \sigma_v,\ \sigma_h,\ \sigma_d,\ \sigma_{ad}), $$

together with the action on ${0,1,\dots,f}$ given above.

This completes the solution. ∎