nt.number theory - Is the determinant of this "Fibonacci sum" indicator matrix always $-1$, $0$, or $1$? - MathOverflow
Is the determinant of this "Fibonacci sum" indicator matrix always $-1$, $0$, or $1$?
Ask Question
Asked<br>yesterday
Modified<br>today
Viewed<br>453 times
28
$\begingroup$
Let $M_n$ be the $n\times n$ matrix with entries<br>$$<br>(M_n)_{ij} \;=\; \begin{cases} 1 & \text{if } i+j \text{ is a Fibonacci number,}\\[2pt] 0 & \text{otherwise,}\end{cases}<br>\qquad 1 \le i,j \le n.<br>$$
Conjecture. $\det M_n \in \{-1,0,1\}$ for all $n$.
Equivalently: among the permutations $\pi$ of $\{1,\dots,n\}$ such that $i+\pi(i)$ is a Fibonacci number for every $i$, the even and odd ones differ in number by at most $1$.
Evidence and remarks.
Verified for all $n \le 120$. The cancellation is massive: for $n=33$ there are $10800$ such permutations, splitting exactly $5400$ even and $5400$ odd.
The values of $n$ with $\det M_n \neq 0$ are<br>$$<br>1,\,2,\,3,\,5,\,9,\,14,\,15,\,23,\,24,\,25,\,37,\,39,\,41,\,60,\,64,\,66,\,67,\,97,\,98,\,103,\,104,\,107,\,108,\,109,\ldots<br>$$<br>clustered just above the Fibonacci numbers; a characterization would also be of interest.
Is this matrix unimodular? Numerical evidence says yes.
nt.number-theory<br>co.combinatorics<br>linear-algebra<br>fibonacci-numbers
Share
Cite
Improve this question
Follow
edited yesterday
asked yesterday
Philip Weiss
61344 silver badges1515 bronze badges
$\endgroup$
$\begingroup$<br>Perhaps one can try to see whether the answers and comments here can apply to this case.<br>$\endgroup$
Fabius Wiesner
Fabius Wiesner
2026-07-18 08:15:49 +00:00
Commented<br>yesterday
$\begingroup$<br>Some random tests suggest that the matrix might be totally unimodular. It might be true also with Lucas numbers and Pell numbers.<br>$\endgroup$
Fabius Wiesner
Fabius Wiesner
2026-07-18 16:28:00 +00:00
Commented<br>yesterday
$\begingroup$<br>Oh wow. Verified (conjecturally, up to same n<br>$\endgroup$
Philip Weiss
Philip Weiss
2026-07-18 16:59:26 +00:00
Commented<br>yesterday
$\begingroup$<br>Powers of 2, 3, tribonacci also have this property. So not exclusive to Lucas.<br>$\endgroup$
Philip Weiss
Philip Weiss
2026-07-18 17:09:24 +00:00
Commented<br>yesterday
$\begingroup$<br>Growth rate alone can’t be it. Counterexample: the sequence 2, 6, 8, 14, 22, 36, 58, … satisfies the Fibonacci recurrence exactly (so it grows at rate φ), yet the 5×5 sum-indicator matrix already has determinant 2.<br>$\endgroup$
Philip Weiss
Philip Weiss
2026-07-18 17:44:01 +00:00
Commented<br>yesterday
Show 3 more comments
1 Answer 1
Sorted by:
Reset to default
Highest score (default)
Date modified (newest first)
Date created (oldest first)
$\begingroup$
Not a solution, but way too long for a comment as conjecture about the values of $n$ with $\det M_n \neq 0$:
The sequence of the differences between consecutive values appears to be (as may be expected for Fibonacci related stuff) self-similar. The following table shows the values, their Zeckendorf decomposition and the difference with the preceding one.
0 0<br>1 1 1<br>2 10 1<br>3 100 1<br>5 1000 2<br>9 10001 4<br>14 100001 5<br>15 100010 1<br>23 1000010 8<br>24 1000100 1<br>25 1000101 1<br>37 10000100 12<br>39 10001000 2<br>41 10001010 2<br>60 100001000 19<br>64 100010001 4<br>66 100010100 2<br>67 100010101 1<br>97 1000010000 30<br>98 1000010001 1<br>103 1000100001 5<br>104 1000100010 1<br>107 1000101000 3<br>108 1000101001 1<br>109 1000101010 1<br>157 10000100000 48<br>158 10000100001 1<br>159 10000100010 1<br>167 10001000010 8<br>168 10001000100 1<br>169 10001000101 1<br>173 10001010000 4<br>174 10001010001 1<br>175 10001010010 1<br>176 10001010100 1<br>177 10001010101 1<br>254 100001000000 77<br>255 100001000001 1<br>256 100001000010 1<br>257 100001000100 1<br>258 100001000101 1<br>270 100010000100 12<br>272 100010001000 2<br>274 100010001010 2<br>280 100010100000 6<br>282 100010100010 2<br>284 100010100101 2<br>285 100010101000 1<br>286 100010101001 1<br>287 100010101010 1<br>411 1000010000000 124<br>412 1000010000001 1<br>413 1000010000010 1<br>414 1000010000100 1<br>416 1000010001000 2<br>418 1000010001010 2<br>437 1000100001000 19<br>441 1000100010001 4<br>443 1000100010100 2<br>444 1000100010101 1<br>453 1000101000000 9<br>454 1000101000001 1<br>456 1000101000100 2<br>460 1000101001010 4<br>462 1000101010001 2<br>463 1000101010010 1<br>464 1000101010100 1<br>465 1000101010101 1<br>665 10000100000000 200<br>666 10000100000001 1<br>667 10000100000010 1<br>668 10000100000100 1<br>670 10000100001000 2<br>674 10000100010001 4<br>676 10000100010100 2<br>677 10000100010101 1<br>707 10001000010000 30<br>708 10001000010001 1<br>713 10001000100001 5<br>714 10001000100010 1<br>717 10001000101000 3<br>718 10001000101001 1<br>719 10001000101010 1<br>733 10001010000000 14<br>734 10001010000001 1<br>735 10001010000010 1<br>738 10001010001000 3<br>739 10001010001001 1<br>744 10001010010100 5<br>748 10001010100010 4<br>750 10001010100101 2<br>751 10001010101000 1<br>752 10001010101001 1<br>753 10001010101010 1<br>1076 100001000000000 323<br>1077 100001000000001 1<br>1078 100001000000010 1<br>1079 100001000000100 1<br>1081 100001000001000 2<br>1085 100001000010001 4<br>1090 100001000100001 5<br>1091 100001000100010 1<br>1094 100001000101000 3<br>1095 100001000101001 1<br>1096...