4
$\begingroup$

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.

Improve this question
$\endgroup$
17
  • $\begingroup$ When n is 1, the determinant is 1. Gerhard "Ask Me About Binary Matrices" Paseman, 2013.02.08 $\endgroup$
    – Gerhard Paseman
    Commented Feb 8, 2013 at 22:34
  • $\begingroup$ 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$. $\endgroup$
    – Noam D. Elkies
    Commented Feb 9, 2013 at 0:03
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Feb 9, 2013 at 0:30
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Noam D. Elkies
    Commented Feb 9, 2013 at 3:39
  • 4
    $\begingroup$ Also posted to m.se, math.stackexchange.com/questions/300379/… $\endgroup$
    – Gerry Myerson
    Commented Feb 12, 2013 at 5:35

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .