4
$\begingroup$

Let $\omega$ be the set of non-negative integers. If $f,g:\omega\to\{-1,1\}$ are maps, then we say $f,g$ are almost orthogonal if there is a positive integer $C_0\in \omega$ such that for all $n\in\omega$ we have $$\Big|\sum_{k=0}^n \big(f(k)\cdot g(k)\big)\Big|< C_0.$$

An infinite Hadamard matrix is a map $M:\omega^2 \to \{-1,1\}$ such that whenever $i\neq j \in\omega$ then the "row vectors" $M[i,\cdot]$ and $M[j,\cdot]$ are almost orthogonal. (Given $a\in\omega$, the map $M[a,\cdot]:\omega\to\{-1,1\}$ is defined by $n\mapsto M(a, n)$.) It takes a bit of work to show that infinite Hadamard matrices do exist.

For $M:\omega^2\to\{-1,1\}$, the transpose $M^{\text{tr}}:\omega^2 \to \omega$ is defined by $(a,b) \in\omega^2 \mapsto M(b,a)$.

Question. If $M$ is an infinite Hadamard matrix, is the transpose $M^{\text{tr}}$ also an infinite Hadamard matrix?

$\endgroup$
5
  • 2
    $\begingroup$ No. just add two rows of ones at the top. $\endgroup$ Commented Sep 6 at 6:46
  • 1
    $\begingroup$ @HenrikRüping But then $\left\lvert \sum_{k=0}^n \bigl( M[0,k] \cdot M[1,k] \bigr) \right\rvert = n+1$, which is not bounded by any positive integer $C_0$, so the first two rows aren't almost orthogonal, right? $\endgroup$ Commented Sep 6 at 9:53
  • 6
    $\begingroup$ Ah yes. I got confused with rows and columns. The stated definition here is that rows are almost orthogonal. So lets add two columns of ones add the left instead. Then the bound $C_0$ increases by two, but the two columns are not almost orthogonal, so transposing doesn't work. $\endgroup$ Commented Sep 6 at 9:56
  • 1
    $\begingroup$ @HenrikRüping What if we relax the definition to "all but finitely many rows are almost orthogonal"? $\endgroup$ Commented Sep 13 at 6:42
  • 1
    $\begingroup$ Then we could repeat each column once. Then the bound doubles,but after transposing all pairs $(2k,2k+1)$ would violate this. What if we relax the condition further so that for a given $k$ there can only be finitely many violatings with that $k$ ? $\endgroup$ Commented Sep 13 at 6:54

1 Answer 1

3
$\begingroup$

Define $f_i(n) = (-1)^{b_i(n)}$ where $b_i(n)$ is the $i$th binary digit of $n$ (Speyer's example with $\lambda = e_i$). Then $(f_1, f_2, \dots)$ defines an "infinite Hadamard matrix" because the partial sums of $f_i(n) f_j(n) = (-1)^{b_i(n) + b_j(n)}$ (for $i \ne j$) are zero over any interval of length $2^{\max(i,j)}$. On the other hand the transpose matrix is very far from being Hadamard-like. We have $f_i(m) f_i(n) = (-1)^{b_i(m) + b_i(n)} = 1$ whenever $2^i > m, n$, so $\sum_i f_i(m) f_i(n) = +\infty$ for all $m, n$.

$\endgroup$

You must log in to answer this question.

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