Problem 626

Counting Binary Matrices

A binary matrix is a matrix consisting entirely of 0s and 1s. 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 (1s become 0s, 0s become 1s)
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{matrix} 1 & 0 & 1 0 & 0 & 1 0 & 0 & 0 \end{matrix}) B = (\begin{matrix} 0 & 0 & 0 1 & 0 & 0 0 & 0 & 1 \end{matrix})$

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

01矩阵计数

01矩阵指的是只由0或1构成的矩阵。对于任意01矩阵，可以进行以下变形：

交换任意两行
交换任意两列
翻转一行中所有元素（1变成0，0变成1）
翻转一列中所有元素

现有两个01矩阵 $A$ 和 $B$ ，如果能够通过一系列上述变形能够将 $A$ 变为 $B$ ，则称 $A$ 和 $B$ 是等价的。例如，如下的两个矩阵就是等价的：

$A = (\begin{matrix} 1 & 0 & 1 0 & 0 & 1 0 & 0 & 0 \end{matrix}) B = (\begin{matrix} 0 & 0 & 0 1 & 0 & 0 0 & 0 & 1 \end{matrix})$

只需先翻转 $A$ 中第三列的元素，然后交换第一行和第二行即可得到 $B$ 。

在所有 $n \times n$ 的01矩阵中，记两两互不等价的01矩阵数目最多为 $c (n)$ 。例如， $c (3) = 3$ ， $c (5) = 39$ ，以及 $c (8) = 656108$ 。

求 $c (20)$ ，并将你的答案对 $1 001 001 011$ 取余。