Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have a square matrix, that all elements on main diagonal are zero, and other elements are following:

$$a_{i,j}=\begin{cases} 1,&\text{if i+j belongs to Fibonacci numbers,}\\ 0,&\text{if i+j doesn't belong to 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.

share|improve this question
    
how can i prove that ? –  Zoha Shams Feb 11 '13 at 17:22
    
Hint: write out the 2x2 and 3x3 cases. Prove your statements for those. Next, use induction to prove the general case. Regards. –  Amzoti Feb 11 '13 at 17:24
4  
i know that i should use induction, i ask you how can use induction?could u prove it? –  Zoha Shams Feb 11 '13 at 17:26
2  
Posted a few days ago to MO, mathoverflow.net/questions/121243/… --- best to check the progress there before spending too much time on it. –  Gerry Myerson Feb 12 '13 at 5:34
    
@julien: Took a quick look and these are the things I have so far: matrix is always symmetric, rank is always even, n-odd $\det = 0$, sum eigenvalues = trace matrix = $0$, product of the eigenvalues = $\det = 0, 1, -1$ (for n-even, it is magnitude 1). Have not made more progress. You? –  Amzoti Jul 13 '13 at 20:29
show 1 more comment

1 Answer 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$:

Graph with $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:

Graph with $n=7$

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}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.