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

Lyndon wordnecklaceparallel algorithmdifference setparallel computationbinary matrixHadamard matrixquantile estimationcirculantmodular computationmaximal determinantHadamard boundcomputational imagingURABooth's algorithmcirculant coreconvolutional Gaussian channeldiscrete Mahler measureDuval's algorithmMURA

Mathematics Subject Classification ID

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

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

• 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?)
• A Family of Difference Sets
• A Survey of Difference Sets
• A Theorem in Finite Projective Geometry and Some Applications to Number Theory
• A family of difference sets
• 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 Pattern Matching in Strings
• Fast canonization of circular 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
• 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 fast algorithm for computing the determinants of banded circulant matrices
• Determinant evaluations for binary circulant matrices
• Determinant Optimization on Binary Matrices
• Determinant of binary circulant matrices
• A survey of the Hadamard maximal determinant problem

Describes a project that uses

Uses Software

• OEIS
• Magma
• gmp

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)