# determinant of fibonacci-sum graphs

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.

• When n is 1, the determinant is 1. Gerhard "Ask Me About Binary Matrices" Paseman, 2013.02.08 – Gerhard Paseman Feb 8 '13 at 22:34
• For $n=1$ it's zero because $A_{ii}=0$ (simple graph). But the general rule isn't that simple, at least if I computed correctly. The gp program v = 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:03
• The problem is his rule is an algebraic one, and (in my view) does not make it clear if the diagonal is zero (in spite of his words on it being an adjacency matrix). I choose the purely algebraic rule and am ignoring the graph theoretic aspect. If you could run the algebraic version (my smart phone has lousy matrix computation capability), I would be appreciative. I am guessing similar results will occur for this version. Gerhard "Thank You For Your Trouble" Paseman, 2013.02.08 – Gerhard Paseman Feb 9 '13 at 0:30
• That's what I did at first (simply omit the line for(m=1,#A,A[m,m]=0); from the gp code). 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
• Also posted to m.se, math.stackexchange.com/questions/300379/… – Gerry Myerson Feb 12 '13 at 5:35