Counting Binary Matrices

A binary matrix is a matrix consisting entirely of $0$s and $1$s. Consider the following transformations that can be performed on a binary matrix:

Swap any two rows
Swap any two columns
Flip all elements in a single row ($1$s become $0$s, $0$s become $1$s)
Flip all elements in a single column

Two binary matrices $A$ and $B$ will be considered equivalent if there is a sequence of such transformations that when applied to $A$ yields $B$. For example, the following two matrices are equivalent:
$A=\begin{pmatrix}
1 & 0 & 1 \\
0 & 0 & 1 \\
0 & 0 & 0 \\
\end{pmatrix} \quad B=\begin{pmatrix}
0 & 0 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
\end{pmatrix}$
via the sequence of two transformations “Flip all elements in column 3” followed by “Swap rows 1 and 2”.
Define $c(n)$ to be the maximum number of $n\times n$ binary matrices that can be found such that no two are equivalent. For example, $c(3)=3$. You are also given that $c(5)=39$ and $c(8)=656108$.
Find $c(20)$, and give your answer modulo $1\,001\,001\,011$.

This problem can be solved using Burnside’s Lemma, which deals with the number of orbits in the action of a group on a set. The lemma states that the number of orbits (in this case, the different non-equivalent matrices) is equal to the average number of fixed points of the action of each element in the group.

The first step is to identify the group. In this problem, the group consists of all possible sequences of the four transformations. This group can be decomposed into multiple subgroups based on the number of cascades (i.e., consecutive row or column operations). It turns out that there are $2n$ non-cascade operations, $(n-1)n$ one-cascade operations, and $(n-2)(n-1)n$ two-cascade operations.

The second step is to compute the number of fixed points for each operation. For a non-cascade operation, each $n \times n$ matrix has to be a palindrome, and there are $2^{n^2/2}$ such matrices. For a one-cascade operation, each $n \times n/2$ matrix has to be a palindrome, and there are $2^{n^2/2}$ such matrices, but only $1/2$ of them are fixed due to the symmetry of the operation. For a two-cascade operation, each $n/2 \times n/2$ matrix has to be a palindrome, and there are $2^{n^2/4}$ such matrices, and only $1/2$ of them are fixed.

Finally, substitute these results into Burnside’s Lemma to obtain $c(n) = (2n \cdot 2^{n^2/2} + (n-1)n \cdot 2^{n^2/2} \cdot 1/2 + (n-2)(n-1)n \cdot 2^{n^2/4} \cdot 1/2) / (2n + (n-1)n + (n-2)(n-1)n)$. It remains to compute $c(20)$ modulo $1\,001\,001\,011$.

Since the computation is likely to be very large, it’s necessary to use a fast modular exponentiation algorithm. Also, one may need to use the method of squaring, combined with the repeated multiplication strategy, to compute the powers of $2$.

Note: This is a rough sketch of how one might approach this problem. There’s quite a lot of calculation here to actually find the answer, and the end result would be a very large number!

More Answers: