4
$\begingroup$

My question is an extension to a classic one:

On a square $N \times N$ grid, select exact $N$ cells that satisfy condition: only one cell selected in same row and column. How many solutions will be? The answer is very simple: $N!$.

But, if we rotate above selections by $90$ degrees, some selections will be equal to others. Then we get rid of all selections which could be derived from rotations and call remainders "non-isomorphic permutation selections". Here is my question:

How many non-isomorphic permutation selections are for arbitrary $N$ ?

I could not get direct answer, and I created a project on github for getting answers for small $N$ in brute force way. Please see more information from https://github.com/gnozil/permatrix.

Some sample images:

  • $4\times 4$ matrix:

https://github.com/gnozil/permatrix/raw/master/results/image-4x4.png

  • 0
    I have searched OEIS with first 11 numbers, but it was not recognized. I also agreed with anon. When I looked into Symmetric Group for hours, I thought my question should be a case in this area, although I have not found direct solution or lemmas.2012-05-30

1 Answers 1

9

Every permutation matrix has one of three symmetry types:

  1. no symmetry, orbit size 4,
  2. $180^\circ$ rotational symmetry, but not $90^\circ$ rotational symmetry, orbit size 2,
  3. $90^\circ$ rotational symmetry, orbit size 1.

Denote the number of $N\times N$ permutation matrices of each of the listed symmetry types $n_1(N)$, $n_2(N)$, $n_3(N)$. If we can figure out $n_2(N)$ and $n_3(N)$ then we can compute $n_1(N)=N!-n_2(N)-n_3(N)$. Since the set of matrices of type 1 is partitioned into orbits of size 4 and the set of matrices of type 2 is partitioned into orbits of size 2, the number of essentially different matrices of size $N$ is $ n(N)=\frac{n_1(N)}{4}+\frac{n_2(N)}{2}+n_3(N). $

Matrices with 180$^\circ$ rotational symmetry. What must a permutation look like if its permutation matrix is unchanged by 180$^\circ$ rotation? Observe that if $N$ is odd, row $(N+1)/2$ undergoes reversal when the matrix is rotated by 180$^\circ$. In a matrix with 180$^\circ$ rotational symmetry, row $(N+1)/2$ must therefore be symmetric under reversal, which means that its single $1$ must lie in column $(N+1)/2$. This corresponds to the center point of the matrix, which is fixed under rotation. In other words, a permutation whose matrix has 180$^\circ$ rotational symmetry must fix $(N+1)/2$ if $N$ is odd.

Now suppose that our permutation with 180$^\circ$ rotational symmetry maps $1$ to $j$. Because, under 180$^\circ$ rotation, row $1$ becomes row $N$ with order of elements reversed, $N$ must then map to $N+1-j$. When $N$ is odd and greater than $1$, we know that $j\ne(N+1)/2$ since $(N+1)/2$ maps to itself and therefore cannot be the image of $1$. Hence there are $N-1$ choices for $j$. When $N$ is even, there are $N$ choices for $j$.

Let $\sigma(b)$ denote the image of $b$ under the permutation we are considering. Consider $k=\sigma(2)$. Symmetry tells us by the argument of the previous paragraph that $\sigma(N-1)=N+1-k$. Since $k$ cannot coincide with $j$ or $N+1-j$, there are $N-3$ choices for $k$ when $N$ is odd, and $N-2$ choices when $N$ is even. Continuing in this fashion we find that when $N$ is even we have

  • $N$ choices for $\sigma(1)$,
  • $N-2$ choices for $\sigma(2)$,
  • $N-4$ choices for $\sigma(3)$,
  • $\vdots$
  • $2$ choices for $\sigma(N/2)$

The images of the remaining $N/2$ elements are fixed by symmetry. Consequently, if $N=2M$, there are $2^M\cdot M!$ permutations with 180$^\circ$ rotational symmetry. The odd case is handled in a similar fashion. Since the matrices with 90$^\circ$ rotational symmetry have 180$^\circ$ rotational symmetry as well, we conclude that $ n_2(N)+n_3(N)=2^M\cdot M!\qquad\text{where}\qquad\begin{cases}N=2M & \text{if $N$ even}\\ N=2M+1 & \text{if $N$ odd.}\end{cases} $

Matrices with 90$^\circ$ rotational symmetry. Now we enumerate the permutation matrices with 90$^\circ$ rotational symmetry. Suppose that such a permutation maps $1$ to $j$. Then, since row $1$ becomes column $N$ after a 90$^\circ$ clockwise rotation, we see that $j$ maps to $N$. We know from the preceding discussion of 180$^\circ$ rotations that $N$ maps to $N+1-j$. Finally, under a 270$^\circ$ clockwise rotation, row 1 becomes column 1 with the order of elements reversed. Therefore $N+1-j$ maps to $1$. As a consequence, the permutation contains the 4-cycle $(1,j,N,N+j-1)$.

More generally, a permutation whose matrix has 90$^\circ$ rotational symmetry consists of 4-cycles of the form $(a,b,N+1-a,N+1-b)$. Note that $a$ cannot equal $b$ unless $a=b=(N+1)/2$ since a 90$^\circ$ clockwise rotation sends the matrix element $(a,a)$ to $(a,N+1-a)$, which would produce two $1$s in row $a$ unless $N+1-a=a$. By similar reasoning, $b$ cannot equal $N+1-a$ unless $a=b=(N+1)/2$. In the case $a=(N+1)/2$, which requires $N$ odd, the permutation contains the 1-cycle $((N+1)/2)$. This represents the center point of the matrix, which, as we have already discussed, is fixed by rotation.

Since a permutation whose matrix has 90$^\circ$ rotational symmetry consists entirely of 4-cycles if $N$ is even and of 4-cycles and a single 1-cycle if $N$ is odd, we find that the number of such permutations is $ n_3(N)= \begin{cases} (4P-2)\cdot(4P-6)\cdot\ldots\cdot2=2\dfrac{(2P-1)!}{(P-1)!} & \text{if $N=4P$ or $4P+1$}\\ 0 & \text{if $N=4P+2$ or $4P+3$.} \end{cases} $

With these ingredients, we obtain $ \begin{array}{r|rrr|r} N & \frac{n_1(N)}{4} & \frac{n_2(N)}{2} & n_3(N) & n(N)\\ \hline 1 & 0 & 0 & 1 & 1 \\ 2 & 0 & 1 & 0 & 1 \\ 3 & 1 & 1 & 0 & 2 \\ 4 & 4 & 3 & 2 & 9 \\ 5 & 28 & 3 & 2 & 33 \\ 6 & 168 & 24 & 0 & 192 \\ 7 & 1248 & 24 & 0 & 1272 \\ 8 & 9984 & 186 & 12 & 10182 \\ 9 & 90624 & 186 & 12 & 90822 \\ 10 & 906240 & 1920 & 0 & 908160 \\ 11 & 9978240 & 1920 & 0 & 9980160 \\ 12 & 119738880 & 22980 & 120 & 119761980 \\ 13 & 1556743680 & 22980 & 120 & 1556766780 \\ 14 & 21794411520 & 322560 & 0 & 21794734080 \\ 15 & 326918430720 & 322560 & 0 & 326918753280 \\ 16 & 5230694891520 & 5160120 & 1680 & 5230700053320 \\ 17 & 88921854443520 & 5160120 & 1680 & 88921859605320 \end{array} $

  • 0
    @Ross, I agreed with you. While the rotational symmetries will be more complex than 2-D case. e.g., the number of rotational symmetries of an 3-D cube is 24, it will introduce more orbit number cases. Previously I tried to generalize the question to N-dimension space, now I realized the complicity and want to give up. Here is reference for [OEIS A002866: number of rotational symmetries of an n-cube](http://oeis.org/A002866)2012-06-06