7
$\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$
6
  • $\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$
    – graffe
    Jan 15, 2016 at 20:46
  • $\begingroup$ Can you give a reference for the result you refer to in your Edit? $\endgroup$
    – graffe
    Jan 15, 2016 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, 2016 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$
    – graffe
    Jan 15, 2016 at 21:51
  • $\begingroup$ sorry, to clarify that result is for the general partial hadamard matrices. $\endgroup$
    – kodlu
    Jan 15, 2016 at 23:12

1 Answer 1

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$
5
  • 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$
    – graffe
    Jan 19, 2016 at 8:51
  • $\begingroup$ @dorothy I'm the same person! Should I change my se name? $\endgroup$ Jan 19, 2016 at 9:02
  • 1
    $\begingroup$ I don't think it matters, but why not? $\endgroup$
    – graffe
    Jan 19, 2016 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, 2016 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$
    – graffe
    Jan 21, 2016 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.