from Hacker News

The Fibonacci Matrix

by ianthehenry on 7/31/23, 1:14 PM with 23 comments

  • by Strilanc on 7/31/23, 4:42 PM

    Awesome.

    Something I noticed in the plot where you can add points is that it's not actually using the continuous version of the transformation to interpolate the paths. It looks like the points are being linearly interpolated between integer powers of the transition matrix. Once you've got the eigenvalues and eigenvectors, you can easily raise the transition matrix to fractional powers to get things like square roots and show halfway points. I think if you interpolated that way then you'd get smooth spirals towards the golden ratio line, instead of bounces (keeping in mind that because one of the eigenvalues is negative you'd end up with complex numbers requiring a projection down from 4d to 2d...).

  • by inasio on 7/31/23, 6:14 PM

    It reminded me Cleve Moler's (Matlab creator) awesome paper: 19 dubious ways to exponentiate a matrix [1]:

    [1]: https://www.math.purdue.edu/~yipn/543/matrixExp19-I.pdf

  • by ducttapecrown on 7/31/23, 4:40 PM

    This was the content of the final lecture of a linear algebra class I took. It was magical to learn about the explicit formula for Fibonacci numbers found via eigendecomposition.

    One funny trick that brought some realism to the lecture: If a and b are the golden ratio and its conjugate, then f_n = a^n + b^n. But since |b| < 1, you can just do f_n = nearest_integer(a^n).

  • by glonq on 7/31/23, 4:17 PM

    This was written to be surprisingly accessible to somebody who hasn't touched a college math textbook in two or three decades. Well done!

  • by rahkiin on 7/31/23, 5:35 PM

    Loved the reference to ‘dynamic programming’ in university. This is exactly what happened in mine and love to see the normal non-recursive version is just nicer.

    Nice quip at the end as well :)

  • by hammock on 7/31/23, 5:28 PM

    There are a couple of errors I noticed. When the author says:

    Even if we start with two numbers that are completely unrelated in the Fibonacci sequence – say, 8 and 41 – the simple way that we pick the next number of the Fibonacci sequence will cause us to approximate the golden ratio after only a few iterations:

      8 / 41 = 0.1951219
  (8 + 41 = 49) / 8 = 6.125
  (49 + 8 = 57) / 49 = 1.16326531
  (57 + 49 = 106) / 57 = 1.85964912
  (106 + 57 = 163) / 106 = 1.53773585
    Why is that? Well, because of the definition of the golden ratio.

    He mis-adds in the third step 8+41 ought to be 41+49..

    But that's not all. He says "if we start with [any] two numbers...in the Fibonacci sequence" but in fact you can start with ANY two numbers WHETHER OR NOT they are fibonacci numbers.. and perform the Fibonacci operation and divide adjacent numbers and it will converge to the golden ratio. E.g.

      8 
  10 1.25
  18 1.8
  28 1.555555556
  46 1.642857143
  74 1.608695652
  120 1.621621622
  194 1.616666667
  314 1.618556701

  • by srean on 8/1/23, 5:59 AM

    The "how to fibonacci" table is missing one other fun and clever way that I want to share -- using a field extension.

    Using the Binet closed form for Fibonacci with floating point numbers is problematic because of finite precision. Naive exponentiations of the golden ratio are not accurate. Part of the problem is the infinite precision needed to deal with sqrt(5).

    One way to deal with that is to represent numbers in the numerator or denominator as (a + b √5) with a and b as integers. Whenever the √5 gets multiplied you separate it out as 5.

    This is way is not faster. One ends up with the logarithmic complexity of exponentiation by squaring. Nonetheless its quite fun and accurate.

  • by hgsgm on 7/31/23, 11:37 PM

    Isn't eigendecomposition pretty much the same as exponentiation (Binet's Formula)?

    https://artofproblemsolving.com/wiki/index.php/Binet%27s_For...

  • by alanbernstein on 7/31/23, 8:53 PM

    I like your interactive animation, would you mind briefly describing how you did the canvas pixel art?

  • by Rietty on 7/31/23, 4:17 PM

    This was a really good post, I have no formal math training and could read it easily.

  • by dpflan on 7/31/23, 4:03 PM

    Excellent post!

  • by danaugrs on 7/31/23, 9:57 PM

    Very cool! Love the visualizations.