size of group of row and column flips of a square board

58 Views Asked by At

Let $X$ be the set of numberings of the squares in a $n \times n$ board with the numbers $1$ to $n^2$. Let $G$ be the group of transformations of boards generated by row and column flips, where a flip reverses the numbers along a row or column. Clearly $G$ acts on $X$. What is $|G|$, or equivalently, what are the sizes of the orbits of $G$ in $X$?

Here is what I have done so far. First of all if $n$ is odd then items in the middle row and column can only move by flipping about the middle. Thus $|G(n)| = 4 |G(n-1)|$ so it suffices to consider the case where $n$ is even. From now on we make this assumption.

There is an equivalence relation "item in square $x$ can be moved to square $y$", which partitions the board into compatible sets of squares. One compatible set is depicted in the image below. As each flip reflects an item about the middle of the board, each compatible set is of size 4.

a compatible set

A trivial upper bound is obtained by the number of ways to arrange items in each compatible set. If all arrangements are considered (not all can be obtained from transformations in $G$), we see: $$|G| \le 24^{\left(\frac{n}{2}\right)^2}.$$ This bound isn't remotely optimal.

A lower bound follows from the observation that any 3 items in a 4 square compatible set can be cyclically permuted while fixing all other items on the board. For example, if the compatible set is in the intersections of columns $i$ and $j$ and rows $k$ and $l$, flip column $i$, flip row $k$, flip column $i$, and flip row $k$. There are 12 arrangements of items in a compatible set generated by cyclic permutations of 3 items and there are $\left(\frac{n}{2}\right)^2$ compatible sets of size 4, giving the lower bound: $$|G| \ge 12^{\left(\frac{n}{2}\right)^2}.$$

1

There are 1 best solutions below

1
On BEST ANSWER

Since you've shown that even permutations can be applied to each compatible set separately, the remaining degrees of freedom are fully described by the parity of the permutation in each compatible set. Let's represent the compatible sets by the $\frac n2\times\frac n2$ squares in one of the quadrants. Every flip changes all parities in one row or one column. These $2\cdot\frac n2=n$ operations on the parities correspond to $n$ vectors in $\mathbb F_2^{\frac n2\times\frac n2}$. They sum to zero and no proper subset of them sums to zero, so they span a space of dimension $n-1$. Thus $2^{n-1}$ different parity patterns are accessible, which yields a total of $2^{n-1}\cdot12^{\left(\frac n2\right)^2}$ different states.