← Complete problem index

PROJECT EULER · #0626

Counting Binary Matrices

Statement only · UnsolvedOriginal problem ↗

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=(101001000)B=(000100001)

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×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 1001001011.

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.