35
$\begingroup$

Let $\mathbf{1}$ be the all-ones vector, and suppose $\mathbf{1}, \mathbf{v_1}, \mathbf{v_2}, \ldots, \mathbf{v_{n-1}} \in \{-1,0,1\}^n$ are mutually orthogonal non-zero vectors. Does it follow that $n \in \{1,2\} \cup \{4k : k \in \mathbb{N}\}$?

A few notes are in order:

  1. If we do not allow "$0$" entries in the vectors then this is a well-known necessary condition for the existence of an $n \times n$ Hadamard matrix, so the answer to my question is "yes" if we replace $\{-1,0,1\}$ with$\{-1,1\}$.

  2. With some computer help, I have shown that there do not exist collections of vectors with these properties when $n = 3$, $5$, or $6$, so the answer to my question is "yes" when $n \leq 6$.

Edit (May 19, 2023): In the comments, Max Alekseyev has shown that the answer is "yes" when $n \leq 12$, and Ilya Bogdanov has shown that the answer is "yes" when $n$ is an odd prime.

Improve this question
$\endgroup$
28
  • 6
    $\begingroup$ I confirm the affirmative answer for all $n\leq 10$ with ILP. $\endgroup$
    – Max Alekseyev
    Commented May 17, 2023 at 21:19
  • 5
    $\begingroup$ As a first step, $n$ cannot be an odd prime. This is because the matrix $A$ composed from those columns should be such that $D=A^TA$ is diagonal, so $B=AD^{-1/2}$ should be orthogonal. But the diagonal element s in $BB^T$ may equal $1$ only I’d $D=nI$ which is impossible by Hadamard. It seems that one may investigate $BB^T$ or, equivalently, the relation $AD^{-1}A^T=I$ further… $\endgroup$
    – Ilya Bogdanov
    Commented May 18, 2023 at 13:09
  • 5
    $\begingroup$ @NathanielJohnston Each diagonal element of $BB^T$ is a sum of $n$ njmbers each of them is either 0 or of the form $1/k$ with $k\leq n$. At least one summand is $1/n$; if there are less than $n$ such, then $n$ in the denominators cannot cancel. $\endgroup$
    – Ilya Bogdanov
    Commented May 18, 2023 at 14:29
  • 5
    $\begingroup$ Further, $n = 2p$ for odd prime $p$ is also a no-go. $1 = 1/2p + \ldots$ requires at least one more $1/2p$, and their sum $1 / p$ requires an extra (even) denominator divisible by $p$ (thus, another $2p$). We now have three full rows, which is enough to invoke Hadamard. $\endgroup$
    – Mikhail Tikhomirov
    Commented May 19, 2023 at 21:29
  • 5
    $\begingroup$ I've computationally verified the conjecture $n=15$ and together with Ilya's and Mikhail's arguments that makes it proved for all $n\leq 20$. For $n=21$, I can tell for now that if a counterexample exists, it should have at least 6 vectors with exactly 14 nonzero components. $\endgroup$
    – Max Alekseyev
    Commented May 22, 2023 at 2:12

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .