Circulant Partial Hadamard Matrices: Properties and Construction

Abstract

Abstract?A question arising in stream cypher cryptanalysis is reframed as follows: For given n, what is the maximum value of m for which there exists a circulant m by n matrix A such that AA^T = nI, where each entry is A is (+1) or (-1). Such matrices named as circulant partial Hadamard matrices (CPHM) that were first introduced by Craigen et. al. in 2013. Furthermore, the question is reframed as, ``For each n, what is the maximum value of m such that the row sums are equal to r?'' They compiled a table of maximum values of m for small n via the exhaustive computer search. However, the constructions of all designs attained their bounds were not mentioned. An application of circulant partial Hadamdard designs in constructing good fMRI designs has been discussed recently. In this paper, we introduced a new concept called general difference sets (GDS), and derived an important theorem that connects GDS and circulant partial Hadamard designs. By using GDS, circulant partial Hadamdard designs can be constructed systematically. Moreover, we proposed an algorithm, called difference variance algorithm (DVA), to search GDS. In this work, we successfully utilized DVA to find the GDSs with respect to CPHM listed by Craigen et. al. when r = 0, 2, and some new lower bounds are given here for the first time.? Keywords：Circulant; Partial Hadamard Designs; Difference Sets; Functional Magnetic Resonance Imaging (fMRI).