Project Euler Problem 626

Solution

Answer: 695577663

Let the group $G$ act on $n\times n$ binary matrices by:

permuting rows,
permuting columns,
flipping rows,
flipping columns.

Then $c(n)$ is exactly the number of orbits of this action, so we use Burnside’s Lemma.

For a fixed pair of permutations $(\sigma,\tau)$, with row-cycle lengths $a_i$ and column-cycle lengths $b_j$:

the induced action on matrix entries splits into

$$K=\sum_{i,j}\gcd(a_i,b_j)$$

cycles,

and the row/column flip variables contribute a system of linear equations over $\mathbb F_2$.

If $d$ is the dimension of the solution space of those parity constraints, then the number of matrices fixed by the corresponding group element is

$$2^{K}\cdot 2^{,2n-m_r-m_c+d},$$

where $m_r,m_c$ are the numbers of row/column cycles.

Summing over all conjugacy classes (i.e. partitions of $n$) gives:

$$c(n)=\frac1{2^{2n}(n!)^2} \sum_{\lambda,\mu} \frac{(n!)^2}{z_\lambda z_\mu} \cdot 2^{K(\lambda,\mu)} \cdot 2^{,2n-m_\lambda-m_\mu+d(\lambda,\mu)}.$$

Implementing this computation in Python reproduces the given checks:

$c(3)=3$
$c(5)=39$
$c(8)=656108$

and for $n=20$ yields

$$c(20)\equiv 695577663 \pmod{1001001011}.$$

Answer: 695577663