Circulant partial Hadamard matrices

A question arising in stream cypher cryptanalysis is reframed and generalized in the setting of Hadamard matrices as follows: For given n, what is the maximum value of k   for which there exists a k×nk×n(±1)(±1)-matrix A   such that AAT=nIkAAT=nIk, with each row after the first obtained by a cyclic shift of its predecessor by one position? For obvious reasons we call such matrices circulant partial Hadamard matrices. Further, what is the maximum value of k subject to the condition that the row sums are equal to r?Craigen, Faucher, Low and Stamp (2005) [18] considered the case r=0r=0. Here we compile a table of maximum values of k for small n and all values of r  , noting some remarkable classes approaching or attaining theoretical bounds. In particular, for r=2r=2 the maximum value, k=n2, is attained by infinitely many matrices—with a surprising connection to negacyclic conference matrices. We also improve known bounds on k   in the original case, r=0r=0.This problem is closely connected to Ryserʼs Conjecture that there is no circulant Hadamard matrix of order >4, in support of which we provide a new heuristic argument.