Classification of small (0, 1) matrices

DOI10.1016/J.LAA.2005.10.010zbMATH Open1091.15022arXivmath/0511636OpenAlexW2139794974MaRDI QIDQ819784FDOQ819784

Authors: Miodrag Živković 

Publication date: 29 March 2006

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: Denote by $A_n$ the set of square $(0,1)$ matrices of order $n$. The set $A_n$, $nle8$, 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$, $10lenle19$, (exceeding the known lower bound $a_{n}ge2f_{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.

Full work available at URL: https://arxiv.org/abs/math/0511636

Recommendations

• scientific article; zbMATH DE number 774598
• scientific article; zbMATH DE number 4002280
• Maximum determinant of (0,1) matrices with certain constant row and column sums
• scientific article; zbMATH DE number 4172993
• Alternating sign matrices, related (0,1)-matrices, and the Smith normal form

zbMATH Keywords

determinantpermutation equivalenceSmith normal form(0,1)-matrices

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Matrices of integers (15B36) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Canonical forms, reductions, classification (15A21) Calculation of integer sequences (11Y55)

Cites Work

• An on-line version of ``The Encyclopedia of Integer Sequences
• Lectures on Polytopes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Determinants Whose Elements Are 0 and 1
• The maximum determinant of \(\pm 1\) matrices

Cited In (8)

• On the nature of saturated \(2^k\)-factorial designs for unbiased estimation of non-negligible parameters
• Determinants of binary matrices achieve every integral value up to \(\Omega (2^n/n)\)
• D-optimal saturated designs for main effects and interactions in 2 ^k -factorial experiments
• Subgroups of odd depth -- a necessary condition.
• A classification of small operators using graph theory
• Lower bound for Buchstaber invariants of real universal complexes
• Mod \(p\) Buchstaber invariant
• Title not available (Why is that?)

Uses Software

• UBASIC
• OEIS

This page was built for publication: Classification of small (0, 1) matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q819784)