Gröbner bases and cocyclic Hadamard matrices. (November 2018)

• Record Type: Journal Article
• Authors: Álvarez, Víctor; Armario, José Andrés; Falcón, Raúl M.; Frau, María Dolores; Gudiel, Félix
• Is Part Of: Journal of symbolic computation. Volume 89(2018)
• Page Start: 26
• Page End: 40
• Publication Date: 2018-11
• Subjects: Hadamard matrix -- Basis of cocycles -- Polynomial ring -- Ideal; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2017.09.001
• Languages: English
• ISSNs: 0747-7171

Abstract

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 enables us to describe a polynomial ideal that characterizes the set of cocyclic Hadamard matrices over a fixed finite group G of order 4 t . Nevertheless, the complexity of the computation of the reduced Gröbner 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 aforementioned set of cocyclic Hadamard matrices over G . The complexity of the computation decreases in this way to 2 O ( t ) . Particularly, we design two specific procedures for looking for Z t × Z 2 2 -cocyclic Hadamard matrices and D 4 t -cocyclic Hadamard matrices, so that larger cocyclic Hadamard matrices (up to t ≤ 39 ) are explicitly obtained.