Computation of maximal determinants of binary circulant matrices

zbMATH Open1388.05028arXiv1801.00399MaRDI QIDQ4568052FDOQ4568052

Authors: Richard P. Brent, Adam B. Yedidia 

Publication date: 15 June 2018

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.

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

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

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.

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)

Cites Work

• The Magma algebra system. I: The user language
• Title not available (Why is that?)
• Computing \(k\)-th Lyndon word and decoding lexicographically minimal de Bruijn sequence
• A Theorem in Finite Projective Geometry and Some Applications to Number Theory
• Title not available (Why is that?)
• On Burnside's Problem
• Fast Pattern Matching in Strings
• Determinantenabschätzungen für binäre Matrizen. (Estimation of determinants for binary matrices)
• A Family of Difference Sets
• On Orthogonal Matrices
• A family of difference sets
• The Mahler measure of algebraic numbers: a survey
• Lexicographically least circular substrings
• 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)
• On Hadamard's inequality for the determinants of order non-divisible by 4
• A Survey of Difference Sets
• Determinantenabschätzung für binäre Matrizen mit \(n\equiv 3\bmod 4\)
• Application of the discrete Fourier transform to the search for generalised Legendre pairs and Hadamard matrices
• Hadamard's determinant theorem and the sum of four squares
• The maximum determinant of \(\pm 1\) matrices
• Average cost of Duval's algorithm for generating Lyndon words
• Title not available (Why is that?)
• Title not available (Why is that?)

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

Uses Software

• gmp
• Magma
• OEIS

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)