A pattern in determinants of Fibonacci numbers?

Question

Let $F_n$ denote the $n$th Fibonacci number, adopting the convention $F_1=1$, $F_2=1$ and so on. Consider the $n\times n$ matrix defined by

$$\mathbf M_n:=\begin{bmatrix}F_1&F_2&\dots&F_n\\F_{n+1}&F_{n+2}&\dots&F_{2n}\\\vdots&\vdots&\ddots&\vdots\\F_{n^2-n+1}&F_{n^2-n+2}&\dots&F_{n^2}\end{bmatrix}.$$

I have the following conjecture:

Conjecture. For all integers $n\geq3$, $\det\mathbf M_n=0$.

I have used some Python code to test this conjecture for $n$ up to $9$, but I cannot go further. Note that $\det\mathbf M_1=\det\mathbf M_2=1$. Due to the elementary nature of this problem I have to assume that it has been discussed before, perhaps even on this site. But I couldn't find any reference on it, by Googling or searching here. Can someone shed light onto whether the conjecture is true, and a proof of it if so?

Answer 1

Here's a hint: what's the relationship between $F_{k+1}+F_{k+2}$ and $F_{k+3}$? What does that say about the 1st, 2nd, and 3rd columns of this matrix?

Answer 2

The resolution is remarkably simple (many thanks to obscurans' answer for the hint!) By the definition of the Fibonacci numbers, $F_k+F_{k+1}=F_{k+2}$ for all $k$. If $n\geq3$ then these numbers are going to be in the first three columns of every row. Hence the first three rows are linearly dependent, so the determinant is $0$. It follows from this that any such sequence following a linear recurrence (of the form $F_{n}=aF_{n-1}+bF_{n-2}$, $a,b$ are constant), with possibly different starting terms, also satisfies the stated conjecture. In fact, this shows that all such matrices have rank $2$, with the only two linearly independent columns being the first two. If the linear recurrence is of higher order, say $m$, then the determinant is $0$ when $n>m$, and the rank of the matrix will be $m$.