Classification of small $(0,1)$ matrices

Miodrag Živković

Published 2005-11-25Version 1

Denote by $A_n$ the set of square $(0,1)$ matrices of order $n$. The set $A_n$, $n\le8$, is partitioned into row/column permutation equivalence classes enabling derivation of various facts by simple counting. For example, the number of regular $(0,1)$ matrices of order 8 is 10160459763342013440. Let $D_n$, $S_n$ denote the set of absolute determinant values and Smith normal forms of matrices from $A_n$. Denote by $a_n$ the smallest integer not in $D_n$. The sets $\mathcal{D}_9$ and $\mathcal{S}_9$ are obtained; especially, $a_9=103$. The lower bounds for $a_n$, $10\le n\le 19$, (exceeding the known lower bound $a_n\ge 2f_{n-1}$, where $f_n$ is $n$th Fibonacci number) are obtained. Row/permutation equivalence classes of $A_n$ correspond to bipartite graphs with $n$ black and $n$ white vertices, and so the other applications of the classification are possible.