15
$\begingroup$

Let $n$ be a positive integer. Suppose we fill a square matrix $n\times n$ row-by-row with the first $n^2$ elements of the Thue–Morse sequence (with indexes from $0$ to $n^2-1$). Let $\mathcal D_n$ be the determinant of this matrix. For example, $$\small\mathcal D_7=\left| \begin{array}{} t_0 & t_1 & t_2 & t_3 & t_4 & t_5 & t_6 \\ t_7 & t_8 & t_9 & t_{10} & t_{11} & t_{12} & t_{13} \\ t_{14} & t_{15} & t_{16} & t_{17} & t_{18} & t_{19} & t_{20} \\ t_{21} & t_{22} & t_{23} & t_{24} & t_{25} & t_{26} & t_{27} \\ t_{28} & t_{29} & t_{30} & t_{31} & t_{32} & t_{33} & t_{34} \\ t_{35} & t_{36} & t_{37} & t_{38} & t_{39} & t_{40} & t_{41} \\ t_{42} & t_{43} & t_{44} & t_{45} & t_{46} & t_{47} & t_{48} \\ \end{array} \right|=\left| \begin{array}{} 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ \end{array} \right|=0.$$ Question: For which $n$ does $\mathcal D_n\ne0$ hold?

Using a brute-force computer search I found only $5$ cases: $\mathcal D_2 = -1,\,$ $\mathcal D_{11} = 9,\,$ $\mathcal D_{13} = -9,\,$ $\mathcal D_{19} = 270,\,$ $\mathcal D_{23} = -900,$ and no other cases for $n\le1940$. Are there any other cases except these five?

Improve this question
$\endgroup$
7
  • $\begingroup$ Maybe it is better to consider the differnce $n-{\rm rank }\, \mathcal D_n$? $\endgroup$
    – Alexey Ustinov
    Commented Nov 7, 2018 at 7:21
  • $\begingroup$ I guess you can define Thue-Morse matrices using the pattern $\begin{pmatrix}A & B \\ B & A\end{pmatrix}$, like the Thue-Morse sequence is defined using the pattern $AB$. $\endgroup$
    – François Brunault
    Commented Nov 7, 2018 at 13:31
  • $\begingroup$ Experimentally there seems to be a simple formula for the rank of your matrix in the case $n=2^k-1$, which corresponds to the iteration $n \to 2n+1$. Using $n \to 2n$ the rank seems to stabilize. Maybe you can try other iterations. $\endgroup$
    – François Brunault
    Commented Nov 7, 2018 at 13:34
  • 3
    $\begingroup$ If $n \geq 4$ is even then the determinant is 0 because the columns $C_0, C_1,... C_{n-1} $ satisfy $C_{2k}+C_{2k+1}=(1,1,...,1) $ for every $k $. $\endgroup$
    – François Brunault
    Commented Nov 8, 2018 at 9:40
  • 3
    $\begingroup$ Searching the OEIS gives 4 results of those A207039 - "Primes whose binary expansion is not palindromic" seems the most relevant. It would be interesting to try to prove that for composite numbers or non-palindromic binary numbers the determinant is zero. This also suggest the question: does there exists ternary (and higher) analog of the Thue–Morse sequence such that numbers for which determinant is non-zero is subsets of non-palindromic ternary primes? $\endgroup$
    – i9Fn
    Commented Nov 8, 2018 at 15:20

1 Answer 1

Reset to default
1
$\begingroup$

not an answer just the result of a computation. The following plot shows for each $n$ the minimal number $k$ such that the first $k$ rows are linearly dependent. The question is to find all $n$ such that $k=n+1$.

enter image description here

Improve this answer
$\endgroup$

You must log in to answer this question.

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