Computation of maximal determinants of binary circulant matrices

MaRDI QIDQ4568052zbMATH OpenFDO

Authors Richard P. Brent, Adam B. Yedidia

Publication date 15 June 2018

Full work available at URL https://arxiv.org/abs/1801.00399, https://cs.uwaterloo.ca/journals/JIS/VOL21/Brent/brent11.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

binary matrixBooth's algorithmcirculantcirculant corecomputational imagingconvolutional Gaussian channeldifference setdiscrete Mahler measureDuval's algorithmHadamard boundHadamard matrixLyndon wordmaximal determinantmodular computationMURAnecklaceparallel algorithmparallel computationquantile estimationURA

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Numerical methods for discrete and fast Fourier transforms (65T50) Combinatorics on words (68R15)

Abstract: We describe algorithms for computing maximal determinants of binary circulant matrices of small orders. Here "binary matrix" means a matrix whose elements are drawn from $0,1$ or $-1,1$. We describe efficient parallel algorithms for the search, using Duval's algorithm for generation of necklaces and the well-known representation of the determinant of a circulant in terms of roots of unity. Tables of maximal determinants are given for orders $le53$. Our computations extend earlier results and disprove two plausible conjectures.

Recommendations

• Determinant evaluations for binary circulant matrices
• scientific article; zbMATH DE number 34417
• On minors of maximal determinant matrices
• Determinants of binary matrices achieve every integral value up to \(\Omega (2^n/n)\)
• The maximal determinant and subdeterminants of \(\pm\)1 matrices.

Cites work

• A Family of Difference Sets
• A family of difference sets
• A Survey of Difference Sets
• A Theorem in Finite Projective Geometry and Some Applications to Number Theory
• Application of the discrete Fourier transform to the search for generalised Legendre pairs and Hadamard matrices
• Average cost of Duval's algorithm for generating Lyndon words
• Computing k-th Lyndon word and decoding lexicographically minimal de Bruijn sequence
• Determinantenabschätzung für binäre Matrizen mit \(n\equiv 3\bmod 4\)
• Determinantenabschätzungen für binäre Matrizen. (Estimation of determinants for binary matrices)
• Fast canonization of circular strings
• Fast Pattern Matching in Strings
• Génération d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée. (Generation of a section of conjugation classes and trees of Lyndon words of bounded length)
• Hadamard's determinant theorem and the sum of four squares
• scientific article; zbMATH DE number 5127186 (Why is no real title available?)
• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 3010750 (Why is no real title available?)
• scientific article; zbMATH DE number 3082632 (Why is no real title available?)
• Lexicographically least circular substrings
• On Burnside's Problem
• On Hadamard's inequality for the determinants of order non-divisible by 4
• On Orthogonal Matrices
• The Magma algebra system. I: The user language
• The Mahler measure of algebraic numbers: a survey
• The maximum determinant of \(\pm 1\) matrices

Cited in

(6)

• Maximum determinants of complementary acyclic matrices of zeros and ones
• A survey of the Hadamard maximal determinant problem
• Determinant evaluations for binary circulant matrices
• Determinant of binary circulant matrices
• Determinant Optimization on Binary Matrices
• A fast algorithm for computing the determinants of banded circulant matrices

Describes a project that uses

Uses Software

• gmp
• OEIS
• Magma

This page was built for publication: Computation of maximal determinants of binary circulant matrices

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