Classification of small $(0,1)$ matrices
| dc.creator | Živković, Miodrag | |
| dc.date | 2005-11-25 | |
| dc.date.accessioned | 2026-07-07T06:51:44Z | |
| dc.date.available | 2026-07-07T06:51:44Z | |
| dc.description | 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. | |
| dc.description | 45 pages. submitted to LAA | |
| dc.identifier | https://arxiv.org/abs/math/0511636 | |
| dc.identifier | http://arxiv.org/abs/math/0511636 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/105088 | |
| dc.subject | Combinatorics | |
| dc.subject | 15A21; 15A36; 11Y55 | |
| dc.title | Classification of small $(0,1)$ matrices | |
| dc.type | text |