Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

share|improve this question
3  
Orbit counting sounds relevant. –  anon May 30 '12 at 3:10
    
I think anon has the right idea. It might not be too hard to count the number with rotational symmetry and then divide the others by 4, etc. Another tack is to calculate for small $n$, as you say you have done, and then look it up in the Online Encyclopedia of Integer Sequences. –  Gerry Myerson May 30 '12 at 10:11
    
This question was originally posted on Programmers but cross-posted here before migration could be considered. –  Mark Booth May 30 '12 at 12:32
    
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. –  gnozil May 30 '12 at 14:44
add comment

1 Answer

up vote 7 down vote accepted

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} $$

share|improve this answer
    
A lot lot of thanks! So beautiful! May we follow the same approach for 3-D cube (or higher dimention) case? –  gnozil May 31 '12 at 2:44
    
If you are happy with Will's answer, you can "accept" it by clicking in the check mark next to it. –  Gerry Myerson May 31 '12 at 2:49
1  
$n_3(N)$ is in OEIS, twice, I think, as A037224 and again as A122670. –  Gerry Myerson May 31 '12 at 2:54
1  
@gnozil : I'm glad you found my remarks helpful. Can you say more about the 3-D case? In particular, what generalization of 2-D permutation matrices are you interested in? –  Will Orrick May 31 '12 at 13:26
1  
@gnozil: In 3-D, the same counting strategy is applicable, but you need to distinguish more cases. You have quarter or half turns about each of the three axes plus third turns around the body diagonals, and some matrices will be symmetric under more than one of these. –  Ross Millikan Jun 6 '12 at 2:52
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.