11
$\begingroup$

Let $n > 13$ be a positive integer. Is there any $n \times n$ circulant $\pm1$ matrix $A$ satisfying the following property

$$AA^T=(n-1)I+J$$

where $I$ is the $n \times n$ identity matrix and $J$ is the $n\times n$ matrix of ones?

I conjecture that the answer is no. But I can't prove it.

Improve this question
$\endgroup$
12
  • 2
    $\begingroup$ $n$ must be odd and $2n-1$ must be a square. Clearly $n=1$ works. The next cases are 5, 13, 25, 41. $\endgroup$
    – Brendan McKay
    Commented Nov 11, 2022 at 5:01
  • 6
    $\begingroup$ Relevant reference: cs.uwaterloo.ca/journals/JIS/VOL21/Brent/brent11.pdf On page 8 they say "It is an open question whether [such a circulant matrix exists] for any n > 13." but they don't give a reference for that statement. $\endgroup$
    – Nathaniel Johnston
    Commented Nov 11, 2022 at 14:21
  • 3
    $\begingroup$ Let $n = (m^2+1)/2$ for an odd $m$. The 01-matrix $B:=(A+J)/2$ represents the incidence matrix of a symmetric $(n,k,k-\frac{n-1}4)$-design, where $k$ is the number of 1s in each row of $A$ and may take values $\frac{(m\pm1)^2}4$. The design parameters can be also stated as $\left(\frac{m^2+1}2, \frac{(m\pm1)^2}4, \frac{m^2\pm4m+1}8\right)$. $\endgroup$
    – Max Alekseyev
    Commented Nov 11, 2022 at 17:41
  • 3
    $\begingroup$ Richard Brent reports that Will Orrick's table of $\pm 1$ matrices up to order 120 satisfying the Barba bound doesn't contain any circulant matrices past order 13. web.archive.org/web/20200218010153/http://www.indiana.edu/… $\endgroup$
    – Brendan McKay
    Commented Nov 12, 2022 at 0:18
  • 3
    $\begingroup$ No such matrices exist for $13<n\leq 20201$ per Corollary 2.5 in the Jungnickel and Pott paper (linked in @kodlu's answer). $\endgroup$
    – Max Alekseyev
    Commented Nov 12, 2022 at 23:17

1 Answer 1

Reset to default
7
$\begingroup$

This is a question about a sequence $a(t)\in \{\pm 1\}$ of period $n$ with 2 level periodic autocorrelations, with the nontrivial autocorrelations identically equal to 1. All these problems have a design theoretic aspect as well. For the relationship to the $\{0,1\}$ alphabet see the question here and its answer.

Here we define the periodic autocorrelation as $$ C_a(\tau)=\sum_{t=0}^{n-1} a(t) a(t+\tau) $$ where the shift by $\tau$ is modulo $n.$

Jungnickel and Pott have a paper on perfect and almost perfect autocorrelation sequences where related questions are discussed here.

Edit: As @MaxAlekseyev points out, Corollary 2.5 in the Jungnickel and Pott paper actually rules out the existence of a circulant matrix as desired by the OP for lengths $13<n\le 20201.$

Maximal length sequences obtained from finite fields give rise to circulant matrices which satisfy $$ A A^T = (n+1)I-J $$ and they exist for $n=2^m-1,$ for all $m\geq 1.$ Thus they have $$ C_a(\tau)=-1,\quad \forall \tau \neq 0 \pmod n $$ Legendre sequences (terminology used in coding and cryptography regarding sequences derived from quadratic characters, see comments to this answer) obtained from multiplicative characters exist for odd prime lengths with the same property.

Another conjecture of similar form, which also (curiously) is open for $n>13$ is the existence of a Barker sequence $a(t) \in \{\pm 1\}$ (or Barker code according to engineers) of length $n$ whose aperiodic autocorrelation $$ C_a(\tau)=\sum_{t=0}^{n-1-\tau} a(t)a(t+\tau) $$ satisfies $$ |C_a(\tau)| \leq 1, \forall \tau \neq 0. $$ This has been checked up to $n$ in the thousands. A good general reference for these problems is the chapter by Helleseth and Kumar in the Handbook of Coding Theory, Vol. 2.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ For an explicit construction of example circulant matrices $X$ where $X^T X = (n+1)I - J$, try for a finite field with $n=4k+3$ elements and specify $X(i,j)=sgn(i-j)$ where $sgn(x)=1$ iff $x$ is a square modulo $n$ and $-1$ otherwise. $\endgroup$
    – Maarten Havinga
    Commented Nov 11, 2022 at 19:45
  • 1
    $\begingroup$ Indeed, that's what I am referring to as Legendre sequences they are derived from quadratic characters. Thanks for pointing this out. $\endgroup$
    – kodlu
    Commented Nov 11, 2022 at 19:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .