Gröbner bases and cocyclic Hadamard matrices. (November 2018) - Álvarez, Víctor; Armario, José Andrés; Falcón, Raúl M.; Frau, María Dolores; Gudiel, Félix
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.