Classification of small (0, 1) matrices

DOI10.1016/J.LAA.2005.10.010MaRDI QIDQ819784zbMATH OpenOpenAlexFDO

Authors Miodrag Živković

Publication date 29 March 2006

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1823817 (Why is no real title available?)
• scientific article; zbMATH DE number 22654 (Why is no real title available?)
• scientific article; zbMATH DE number 41614 (Why is no real title available?)
• scientific article; zbMATH DE number 3245540 (Why is no real title available?)
• scientific article; zbMATH DE number 3419161 (Why is no real title available?)
• An on-line version of ``The Encyclopedia of Integer Sequences
• Determinants Whose Elements Are 0 and 1
• Lectures on Polytopes
• The maximum determinant of \(\pm 1\) matrices

Cited in

(8)

• scientific article; zbMATH DE number 774598 (Why is no real title available?)
• 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
• A classification of small operators using graph theory
• Subgroups of odd depth -- a necessary condition.
• Lower bound for Buchstaber invariants of real universal complexes
• Mod \(p\) Buchstaber invariant

Describes a project that uses

Uses Software

• OEIS
• UBASIC

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)