Classification of small $(0,1)$ matrices

Details Classification of small $(0,1)$ matrices Classification of small $(0,1)$ matrices

2005-11-25

arxiv.org/abs/math/0511636v1

Mathematics

Combinatorics

45 pages. submitted to LAA

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Classification of small $(0,1)$ matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Classification of small $(0,1)$ matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Classification of small $(0,1)$ matrices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-365255