6
$\begingroup$

I believe that the circulant Hadamard conjecture (that there are no circulant Hadamard matrices of size greater than $4\times4$) is still open.

I also know that examples of $(n/2) \times n$ matrices which are partial Hadamard circulant have been found experimentally for moderate values of $n.$

To clarify, a partial circulant $m(n)\times n$ Hadamard matrix $A$ has entries from $\{-1,+1\}$ and if its first row is $a,$ then its subsequent rows are $T(a),\ldots,T^{m(n)-1}(a)$ where $T$ denotes, say, the left cyclic shift operator and $T^k$ is $T$ composed with itself $k$ times.

Is there a known infinite construction for partial circulant Hadamard matrices? Equivalently does a sequence of $m_k(n_k)\times n_k$ Hadamard matrices exist, where $n_k\rightarrow \infty$ and so does $m_k(n_k)$. Note that $m_k(n_k)=o(n_k)$ is allowed, under this definition.

I am aware of references arXiv:1201.4021, Armario et al and arxiv:1003.4003, De Launey and Levin, which address generic partial Hadamard matrices, as opposed to those that are partial circulant.

Edit: To make things explicit, the best results I have found without the circulant constraint are the following: For any $\varepsilon>0$ and for $n$ large enough, $t\equiv 0~(mod~4)$ there is a $n\times t$ partial Hadamard matrix if $n\leq \frac{t}{2}-t^{\frac{113}{132}+\varepsilon}.$ Subject to the extended Riemann hypothesis the $\frac{113}{132}$ in the exponent can be replaced by $\frac{7}{12}.$ This matches computational results, see https://codegolf.stackexchange.com/questions/55726/an-optimization-version-of-the-hadamard-problem, that have found $\frac{n}{2}\times n$ partial Hadamard matrices up to $n$ somewhere between 50 and 100.

$\endgroup$
  • $\begingroup$ I just posed a very similar question but have deleted it after seeing this. It turns out that for $n/2$ by $n$ Hadamard partial circulant matrices with $n=4,8,12,16,20,24,28$ the numbers of these matrices is: $12,40,144,128,80,192,560$. There exist $0$ for $n=32$ but more than $0$ for $n=36$. $\endgroup$ – dorothy Jan 15 '16 at 20:46
  • $\begingroup$ Can you give a reference for the result you refer to in your Edit? $\endgroup$ – dorothy Jan 15 '16 at 20:48
  • $\begingroup$ @dorothy: do you mean the computational results? It's from a computational stackexchange group . I added the link to the question. $\endgroup$ – kodlu Jan 15 '16 at 21:43
  • $\begingroup$ I meant the part directly following "the best result I have found is the following" where you quote some result when $n\leq \frac{t}{2}-t^{\frac{113}{132}+\varepsilon}$. Is that not to do with Hadamard partial circulant matrices after all? $\endgroup$ – dorothy Jan 15 '16 at 21:51
  • $\begingroup$ sorry, to clarify that result is for the general partial hadamard matrices. $\endgroup$ – kodlu Jan 15 '16 at 23:12
3
+50
$\begingroup$

Let $r\mbox{-}H(k\times n)$ denote a $k\times n$ partial circulant Hadmard matrix in which a row (and hence all) sums to $r$. It's a known result, see Theroem 9 in [1], that $2\mbox{-}H((p+1)\times 2(p+1))$ exists for any prime power $p$. This is because negacyclic $C$-matrices of order $p+1$ exist. In [2], Paley gave a construction of $C$-matrices using the Legendre symbol $\chi$ of the Galois field GF$(p)$. A variation of this construction leads to a negacyclic form for these Paley matrices, see [3] for details.

[1] $\textit{Circulant partial Hadamard matrices}$ by Craigen, Faucher, Low, and Wares, Lin. Alg. Appl. 439 (2013)

[2] $\textit{On orthogonal matrices}$ by Paley, J. Math. Phys. 12 (1933)

[3] $\textit{Orthogonal matrices with zero diagonal II}$ by Delsarte, Goethals, and Seidel, Can. J. Math., Vol. XXIII No. 5 (1971)

$\endgroup$
  • 1
    $\begingroup$ Thank you. Someone just put much the same answer on math.se. On the off chance you are not the same person, would you be able to explain the construction explicitly? Ultimately I would like to write computer code to construct these matrices. $\endgroup$ – dorothy Jan 19 '16 at 8:51
  • $\begingroup$ @dorothy I'm the same person! Should I change my se name? $\endgroup$ – Oliver Jones Jan 19 '16 at 9:02
  • 1
    $\begingroup$ I don't think it matters, but why not? $\endgroup$ – dorothy Jan 19 '16 at 9:05
  • $\begingroup$ @dorothy the construction in [1] is quite lengthy. if you don't have access to [1] I am able to access a pdf of the paper. $\endgroup$ – kodlu Jan 21 '16 at 5:58
  • $\begingroup$ @kodlu Thank you. Yes I managed to get hold of the paper in the end and it is a little too complicated for me to follow properly. What I am looking for is a nice explicit proof-free construction. $\endgroup$ – dorothy Jan 21 '16 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.