We have a simple graph with vertices $\{v_1, v_2, ... v_n\}$.

The adjacency matrix of this graph is $A= (a_{ij})$ so that

$a_{ij}=1$ if $i+j$ belongs to the Fibonacci sequence;

$a_{ij}=0$ if $i+j$ doesn't belong to the Fibonacci sequence.

We claim that the determinant of this matrix is $0$ when $n$ is odd. And that when $n$ is even, it is $1$, $-1$ or $0$.

How can we prove this claim?

**Edit:** on MSE, the OP added that $a_{ii}=0$ along the diagonal which is confirmed by the OP's observation that the determinant should be zero in the odd case (e.g. $n=1,3$ do yield $0$ then). So in particular, this is not a Hankel transform.

gpprogramv = vector(10,n,fibonacci(n+1));A = matrix(50,50);for(n=1,#v,f=v[n];for(i=max(1,f-#A),min(f-1,#A),A[i,f-i]=1));for(m=1,#A,A[m,m]=0);vector(#A,m,matdet(vecextract(A,vector(m,k,k),vector(m,k,k))))yields $\det(A_n)=(-1)^{n/2}$ for $n \leq 8$ but then $\det A = 0$ for $n \in [9,50]$ except for $\det A_{38}=-1$ and $\det A_{40}=1$. – Noam D. Elkies Feb 9 '13 at 0:03for(m=1,#A,A[m,m]=0);from thegpcode). This gives $\det A_n = 1$ for $n=1,5,9,14,25,37,41$ and $\det A_n = -1$ for $n=2,3,15,23,24,39$, with $\det A_n = 0$ for all other $n \leq 50$. I'm guessing that the zero-diagonal version is what was meant, because it matches the "claim" (that the determinant is $0$ or $\pm 1$ according as $n$ is odd or even) for $n \leq 9$, while the data above looks nothing like this "claim" even for the smallest few $n$. – Noam D. Elkies Feb 9 '13 at 3:39