7
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ Fun question. Next time I teach matrix theory I might use this as an extra credit problem on a homework set involving determinants. As you know now, the solution isn't hard, but it would take a pretty clever student to spot it on their own. Thanks. $\endgroup$ Dec 3, 2018 at 12:19
  • 1
    $\begingroup$ Problem A3 from the 2009 Putnam competition has a very similar statement and a very similar solution, only replacing $F_k$ by $\cos k$ (in radians). $\endgroup$ Dec 3, 2018 at 15:46

2 Answers 2

24
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ One note: the matrix will have rank $\leq$ the order of the linear recurrence, which is not necessarily 2. $\endgroup$
    – obscurans
    Dec 3, 2018 at 2:11
  • $\begingroup$ @obscurans Suppose that the matrix has rank $k$. Does that not mean that the linear recurrence can be rewritten as a linear recurrence of order $k$? I was under the impression that the order of a linear recurrence was the order of its simplest form, though I realize now that that may not be the case. $\endgroup$
    – Sam Benner
    Dec 3, 2018 at 15:31
  • $\begingroup$ There are two different things: a particular linear recurrence, which is an equation with $n$ degrees of freedom of solutions, vs a particular fixed sequence of numbers generated by some linear recurrence. The matrix having rank $k$ does mean a linear recurrence of order $k$ can generate this sequence of numbers. $\endgroup$
    – obscurans
    Dec 4, 2018 at 2:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .