OFFSET
1,4
COMMENTS
Let V = {0,1}^n be the vertices of the n-dimensional Boolean hypercube. A complement pair is a set {v, ~v} where ~v is the bitwise negation of v. We consider the set of all 2^(n-1) - 1 complement pairs, excluding the trivial pair {(0...0), (1...1)}.
We select a subset of exactly n pairs. A subset is considered "full-rank" if there exists at least one way to choose a representative vector from each of the n pairs such that the resulting n x n matrix has a nonzero determinant over the real numbers.
The symmetric group S_n acts on these subsets by permuting the n coordinate axes. This sequence gives the number of distinct orbits (equivalence classes) under this group action.
For n=1, excluding the trivial pair leaves 0 available pairs, so a(1) = 0.
For n=2, excluding the trivial pair leaves 1 available pair. We must choose n=2 pairs, which is impossible, so a(2) = 0.
For n=3, there are 3 available pairs. We choose 3, yielding exactly 1 subset, which is full-rank. Thus a(3) = 1.
The terms a(1) through a(8) were computed using parallelized depth-first search with lexicographical symmetry pruning, and verified up to a(6) using Burnside's Lemma over the conjugacy classes of S_n.
LINKS
M. A. Harrison, On the number of classes of binary matrices, IEEE Trans. Computers, 22 (1973), 1048-1051. doi:10.1109/T-C.1973.223649.
M. A. Harrison, On the number of classes of binary matrices, IEEE Transactions on Computers, C-22.12 (1973), 1048-1052. (Annotated scanned copy)
Adrien Mabire, C++ codes, GitHub.
EXAMPLE
For n=1, the only possible vectors are {0} and {1}. Both are 0s and 1s so they are are excluded => a(1)=0.
For n=2, {01} and {10} are equivalent leaving a single vector so the set cannot be full rank => a(2)=0.
For n=3, the valid canonical vectors are {001},{010},{011}. {011} and {100} are equivalent which makes the set equivalent to {001},{010},{100} which is valid. Those are the only possible vectors => a(3)=1.
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Adrien Mabire, May 14 2026
STATUS
approved