3
$\begingroup$

I'm interested in counting the number of n×n 0-1 matrices with a given number of 1s up to rotation and reflection. What is the best way to do this if n is not too small?

For example, consider 4×4 matrices with 7 1s. There are ${16\choose7}=11440$ such matrices in total, but most equivalence classes under reflection and rotation have 8 members, so the total is closer to 11440/8 = 1430. In fact if I am correct the total is 1465.

One method would be enumerating all such matrices, counting the number of distinct matrices resulting from each of the eight symmetries. But this takes too long, even for a computer, for n > 6 or so.

Burnside's lemma seems promising, but this requires counting fixed points and I do not know how to do this rapidly. In any case I have very little familiarity with group theory and so pointers, even basic ones, would be appreciated.

Perhaps there are other methods which can be used as well. I have seen this described as an easy problem, so I must be missing something (unless it was mischaracterized!).

$\endgroup$
  • $\begingroup$ This is easily within computer checking, but writing such a program is not easy. Do you know how many matrices with $6\ 1$'s there are? That would allow checking in OEIS. I find $18$ pages with $1465$ in them. $\endgroup$ – Ross Millikan May 10 '13 at 3:05
  • $\begingroup$ When you say "up to rotation and reflection", do you mean up to acting on the matrix by a rotation or reflection matrix with 0-1 entries? $\endgroup$ – Alex Becker May 10 '13 at 3:06
  • 1
    $\begingroup$ @RossMillikan: I believe the relevant entry is oeis.org/A054252 $\endgroup$ – Charles May 10 '13 at 3:10
  • $\begingroup$ It looks like it. Unfortunately no references are given. $\endgroup$ – Ross Millikan May 10 '13 at 3:12
  • $\begingroup$ @AlexBecker: I'm not sure what you mean (sorry, I'm a novice here). I mean that rotating the matrix by 90, 180, or 270 degrees, or reflecting it vertically, horizontally, or across either diagonal, is counted only once. So there are just 2 2x2 matrices with 2 1s, the one with 1s touching and the one with 1s diagonal. $\endgroup$ – Charles May 10 '13 at 3:12
3
$\begingroup$

Burnside's lemma is indeed helpful here. What you have is the group $D_4$ (the group of symmetries on the square) acting on the set of $n\times n$ 0-1 matrices with $k$ ones, and you want to count the number of orbits. By Burnside's lemma this is $$\frac18\sum\limits_{g\in D_4}|X^g|$$ where $X^g$ is the set of matrices fixed by the element $g\in D_4$. Since $D_4$ has only $8$ elements, this calculation is fairly easy. I shall illustrate the case $n=4, k=6$.

We can view the $4\times 4$ matrix as a block matrix $$\begin{pmatrix} A & B \\ C & D\end{pmatrix}$$ where each block is a $2\times 2$ matrix. Clearly the identity fixes all $\binom{16}{6}=8008$ matrices. Rotation by $90^\circ$ counterclockwise permutes this to give $$\begin{pmatrix} B & D \\ A & C\end{pmatrix}$$ so the matrix is fixed iff $A=B=D=C$. But this means the number of ones in the matrix is a multiple of $4$, yet $k$ is not divisible by $4$, thus no matrices are fixed by rotation by $90^\circ$. It is easy to see that the result is the same for rotation by $270^\circ$. Rotation by $180^\circ$ permutes the original matrix to $$\begin{pmatrix} D & C \\ B & A\end{pmatrix}$$ which is the same as the original iff $A=D$ and $B=C$. Thus since $k=6$ we can either have $3$ ones in $A$, $2$ in $A$ and $1$ in $B$, $1$ in $A$ and $2$ in $B$, or $3$ in $B$. Since choosing $A$ and $B$ completely determines the matrix, the number of matrices fixed by rotation by $180^\circ$ is $$\binom43\binom40+\binom42\binom41+\binom41\binom42+\binom40\binom43=56.$$ Now for reflection. Vertical or horizontal reflection is easy; a matrix is fixed iff its left (upper) half is the same as its right (lower) half, so each half must have $3$ ones and the number of matrices fixed by each is $\binom83=56$. Note that reflection across the main diagonal is a standard operation in linear algebra called transposition, which is denoted by a superscript $t$. A matrix equal to its own transpose is called symmetric, and a symmetric matrix is determined entirely by its main diagonal and bottom left entries, of which there are $4$ and $6$ respectively. If we let $d$ be the number of ones on the diagonal and $b$ the number of ones in the bottom left, we have $k=d+2b$, thus we can have $d=0$ and $b=3$, $d=2$ and $b=2$ or $d=4$ and $b=1$. The number of such matrices is $\binom4d\binom6b$ for each value of $b$ and $d$, thus the number of matrices fixed by transposition is $$\binom40\binom63+\binom42\binom62+\binom44\binom61=116.$$ It is easy to see that the result for reflection across the other diagonal is the same. Thus we have $$|X/D_4|=\frac18\sum\limits_{g\in D_4}|X^g|=\frac{1}{8}(8008+0+56+0+56+56+116+116)=1051.$$ This result agrees with oeis.org/A054252. It also shows some interesting dependence of $|X/D_4|$ on the divisibility of $k$ by $2$ and $4$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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