Gröbner bases and cocyclic Hadamard matrices

DOI10.1016/J.JSC.2017.09.001zbMATH Open1396.13024arXiv1603.01859OpenAlexW2294836888MaRDI QIDQ1635271FDOQ1635271

Authors: José Andrés Armario, Raúl M. Falcón, María Dolores Frau, Félix Gudiel, Victor Alvarez 

Publication date: 6 June 2018

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: Hadamard ideals were introduced in 2006 as a set of nonlinear polynomial equations whose zeros are uniquely related to Hadamard matrices with one or two circulant cores of a given order. Based on this idea, the cocyclic Hadamard test enable us to describe a polynomial ideal that characterizes the set of cocyclic Hadamard matrices over a fixed finite group $G$ of order $4t$. Nevertheless, the complexity of the computation of the reduced Gr"obner basis of this ideal is $2^{O(t^2)}$, which is excessive even for very small orders. In order to improve the efficiency of this polynomial method, we take advantage of some recent results on the inner structure of a cocyclic matrix to describe an alternative polynomial ideal that also characterizes the mentioned set of cocyclic Hadamard matrices over $G$. The complexity of the computation decreases in this way to $2^{O(n)}$, where $n$ is the number of $G$-coboundaries. Particularly, we design two specific procedures for looking for $mathbb{Z}_{t}imesmathbb{Z}_2^2$-cocyclic Hadamard matrices and $D_{4t}$-cocyclic Hadamard matrices, so that larger cocyclic Hadamard matrices (up to $tleq31$) are explicitly obtained.

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

Recommendations

• scientific article; zbMATH DE number 1341911
• scientific article; zbMATH DE number 1736030
• scientific article; zbMATH DE number 1163423
• Cocyclic Hadamard matrices from forms over finite Frobenius rings
• Gröbner bases with coefficients in rings
• Some combinatorial applications of Gröbner bases
• On higher dimensional cocyclic Hadamard matrices
• Gröbner bases for complete uniform families
• An introduction to cocyclic generalised Hadamard matrices
• scientific article; zbMATH DE number 4112737

zbMATH Keywords

polynomial ringidealHadamard matrixbasis of cocycles

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Cites Work

• The Magma algebra system. I: The user language
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Title not available (Why is that?)
• Hadamard matrices and their applications
• Cocyclic Hadamard matrices and Hadamard groups are equivalent
• Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
• Orthogonal Matrices with Zero Diagonal
• Homology
• On decomposing systems of polynomial equations with finitely many solutions
• Title not available (Why is that?)
• Some new orders of Hadamard and skew-Hadamard matrices
• Computation of Hilbert functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algebraic design theory
• Sharper complexity bounds for zero-dimensional Gröbner bases and polynomial system solving
• Solving zero-dimensional algebraic systems
• Nullstellensätze for zero-dimensional Gröbner bases
• Williamson matrices up to order 59
• The homological reduction method for computing cocyclic Hadamard matrices
• A system of equations for describing cocyclic Hadamard matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Switching Operations for Hadamard Matrices
• Application of the discrete Fourier transform to the search for generalised Legendre pairs and Hadamard matrices
• Calculation of cocyclic matrices
• Title not available (Why is that?)
• Computing 2-cocyeles for central extensions and relative difference sets
• Hadamard ideals and Hadamard matrices with two circulant cores
• On \(\mathbb{Z}_t\times\mathbb{Z}^2_2\)-cocyclic Hadamard matrices
• On linear shift representations.
• On \(D_{4t}\)-cocyclic Hadamard matrices
• Title not available (Why is that?)

Cited In (3)

• Hadamard ideals and Hadamard matrices with two circulant cores
• Hadamard ideals and Hadamard matrices from two circulant submatrices
• Formal orthogonal pairs via monomial representations and cohomology

Uses Software

• Magma
• SINGULAR

This page was built for publication: Gröbner bases and cocyclic Hadamard matrices

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