Prove the determinant of this matrix

We have an $n\times n$ square matrix $\left(a_{i,j}\right)_{1\leq i\leq n, \ 1\leq j\leq n}$ such that all elements on main diagonal are zero, whereas the other elements are defined as follows:

$$a_{i,j}=\begin{cases} 1,&\text{if } i+j \text{ belongs to the Fibonacci numbers,}\\ 0,&\text{if } i+j \text{ does not belong to the Fibonacci numbers}.\\ \end{cases}$$

We know that when $n$ is odd, the determinant of this matrix is zero.

Now prove that when $n$ is even, the determinant of this matrix is $0$ or $1$ or $-1$. (Use induction or other methods.)

Also posted on MO.

Solution 1:

This is just a partial answer, too long to fit in a comment, written in order to start collecting ideas.

We have: $$\det A=\sum_{\sigma\in S_n}\operatorname{sign}(\sigma)\prod_{i=1}^n a_{i,\sigma(i)},$$ hence the contribute of every permutation in $S_n$ belongs to $\{-1,0,1\}$. In particular, the contribute of a permutation differs from zero iff $i+\sigma(i)$ belongs to the Fibonacci sequence for every $i\in[1,n]$. If we consider the cycle decomposition of such a $\sigma$: $$\sigma = (n_1,\ldots, n_j)\cdot\ldots\cdot(m_1,\ldots, m_k)$$ this condition gives that $n_1+n_2,\ldots,n_j+n_1,\ldots,m_1+m_2,\ldots,m_k+m_1$ belong to the Fibonacci sequence, so, if the contribute of $\sigma$ differs from zero, the contribute of $\sigma^{-1}$ is the same.

However, not so many permutations fulfill the condition. For instance, the only possible fixed points of the contributing permutations are half of the even Fibonacci numbers, hence numbers of the form $\frac{1}{2}F_{3k}$:$1,4,17,72,\ldots$.

Moreover, the elements of $[1,n]$ can be arranged in a graph $\Gamma$ in which the neighbourhood of a node with label $m$ is made of the integers in $[1,n]$ whose sum with $m$ is a Fibonacci number, i.e. all the possible images $\sigma(m)$ for a contributing permutation.

For istance, for $n=5$:

we get (apart from the self-loops in $1$ and $4$) an acyclic graph. The only contibuting permutation is $\sigma=(1 2)(3 5)(4)$, hence $|\det A|=1$. When $n=6$ or $n=7$ the neighbourhood of $5$ is still made of only one element:

When $n=7$ the contributing permutations are of the form $\sigma=(4)(3 5)\tau$, where $\tau\in\{(1,2,6,7),(1,7,6,2),(1,2)(6,7),(1 7)(6 2)\}$, hence $\det A=0$.

In general, the neighbourhood of the greatest Fibonacci number $F_k\leq n$ is made of $F_{k-1}$ only, hence $F_k$ is always paired with $F_{k-1}$ in a transposition of every contributing permutation.

Now I believe that the conjecture $\det A\in\{-1,0,1\}$ heavily correlated with the structure of the cycles in $\Gamma_\mathbb{N}$, a graph over $\mathbb{N}$ where two integers are connected when their sum is a Fibonacci number.

There are many trivial cycles in $\Gamma_\mathbb{N}$: $$(k,F_m-k),\quad (k,F_m-k,F_{m+1}+k,F_{m+2}-k),\quad (k,F_m-k,F_{m+1}+k,F_{m+2}-k,F_{m+3}+k,F_{m+4}-k),\ldots$$ and my claim is that all the cycles have even length, and all the cycles are of the given type. Given that $F$ is the set of all the Fibonacci number, it is straightforward to prove that the only elements of $F-F$ represented twice are the Fibonacci numbers, hence there are no cycles of length $3$ in $\Gamma_\mathbb{N}$.