Comment by dietrichepp | Hacker News Reader

Comment by dietrichepp | Hacker News Reader

I think the proof for the closed-form version is accessible to people with a background in linear algebra. The matrix is diagonalizable (not all matrixes are diagonalizable, but this one is):

  M = P Δ P^-1

Here, P is some invertible matrix and Δ is a diagonal matrix. The powers of M reveal how useful this is:

  M^N = (P Δ P^-1) * … * (P Δ P^-1)

If you adjust the parentheses, you’ll see N-1 terms of (P^-1 P), which can be removed, giving:

  M^N = P Δ^N P^-1

The powers of a diagonal matrix is done by taking powers of the entries on the diagonal.

You see the φ values (1±√5)/2 in the matrix Δ.

Diagonalization of a 2x2 matrix is simple to do on paper. The diagonal of Δ contains the eigenvalues of M, which can be found using the quadratic formula. Proving that this is a correct way to diagonalize any diagonalizable matrix is more of a chore, but for this specific 2x2 matrix, you can just show that that you’ve found the values for P and Δ.

This is very elegant mathematically, but I would not use the closed-form solution if I wanted the exact answer, because you’d need a lot of precision, and that’s inconvenient.

(Author of the article here) Thanks for writing this up, it's much much more intuitive than what I've read everywhere else. I primarily looked up Knuth (TAOCP Vol 1) for this part, and he showed a longish proof using generating functions which looked too long to show in the article, and I would not have done a better job than him.

The thirty three miniatures book showed a more abstract proof, which would have been accessible to people deeply familiar with the concept of basis vectors.

My own personal experience is that, in linear algebra, there are a lot of different ways to prove the same thing. When you search for a proof of something, you may find a proof that is overly basic and verbose, or a proof that is overly advanced and terse.

Finding an explanation of a linear algebra concept that strikes the right balance can be time-consuming or difficult. This is why you see, for example, a hojillion different articles explaining what quaternions are. Everybody is most comfortable at a different place on the complexity spectrum—from “a vector is (x,y,z), here are rules for how that works” to “a vector space is an abelian group V, field F, and a map in Hom(F,End(V))”.

That's quite true. And so many books to teach it.

I am a software engineer and don't have a major in math beyond studying discrete math in college. So I really have to work hard to understand these proofs. And I certainly value proofs explained in simple terms. :)

I agree. In fact finding an explanation of pretty much any significant mathematical concept that strikes that balance (across the broad range of individual talents and backgrounds) is time-consuming or difficult.

Which is why a significant chunk of mathematics research effort and funding should go to making such explanations less time-consuming and difficult. IMHO. It may be as simple as a vetted compilation of explanations for a single idea so the individual can find the ones that work for them, or formal development of new explanations. What’s more significant: a new incremental result in some obscure corner of math, or 100M more people understanding what an eigenvalue actually means? Or a new explanation that makes a concept more relevant in an entire application area?

The generating function proof is also really beautiful! I think I maybe like it even more than the linear algebra proof.

The generating function approach is the standard way of solving recurrences. In that sense, it isn't beautiful, just routine. But yes the first time I'd seen it I felt my body shudder at that sorcery.

If anyone wants to read this in book form, Linear Algebra Done Right includes it as an exercise at the end of a very short and readable chapter 5.C on eigenspaces and diagonal matricies.

The treatment in thirty-three miniatures describes the steps you take but doesn't mention what you are actually doing (finding eigenvalues) or leave you with any intuition for why this was a natural thing to have tried

Yes, that book (thirty three miniatures) has great content, but a hard read. Basically someone like me needs to go back, read other sources, and spend time on paper to get it.

Yes! This is close the explanation I first encountered in Hubbard & Hubbard. One of the nicest math textbooks and going from zero up to differential forms.

https://matrixeditions.com/5thUnifiedApproach.html

what if you use the closed-form answer, but without any floating-point or other approximations

i mean it all comes out to an integer in the end, all the radicals cancel

i see tromp already suggested a form of this

But that seems to be computationally same amount of work as the matrix form, so we get similar performance?

hmm, maybe? i haven't tried it so i can't be sure, but it's plausible

Yes, I believe so, up to some multiplicative factor.

You can carry out the exponentiations in the field Q[sqrt(5)], which is two-dimentional over Q. The interesting thing here is that diagonalization is trading one 2d vector space for another -- one with a very well-behaved multiplication operation (it's distributive, commutative, associative, and invertible).

There's no need to do this to quickly compute fibonacci numbers, but it's pretty neat.

I did this years ago to demonstrate to my students that the "exact solution" can still be written in code. There are implementations in Ruby and Python, with some benchmarking code: https://github.com/jfarmer/fib-bench/

Code winds up looking like:

  def fib_phi(n)
    ((PhiRational(0,1)**n - PhiRational(1,-1)**n)/PhiRational(-1, 2)).a.to_i
  end

The exponentiation operation uses basic exponentiation by squaring for performance: https://en.wikipedia.org/wiki/Exponentiation_by_squaring

(Technically implemented arithmetic over Q(ϕ) not Q(√5) because it simplifies the code a bit.)

Nice! Thank you for sharing.

> what if you use the closed-form answer, but without any floating-point or other approximations

You can use a field extension here, ℚ(√5), to represent your numbers. The numbers would be represented as pairs, (a,b), which represents the number a+b√5. You can see for yourself that this set is closed under addition and multiplication.

But when you try to implement code that computes exponents with this representation, you’re probably going to fall back to the old “repeated squaring” trick. But that’s how you calculate exponents with your matrix representation anyway—and you can note that the matrix powers (for this matrix) always take the form

  | a b |
  | 0 a |

So you can represent these matrixes as (a,b) pairs anyway. We are right back where we started—our state is represented as a pair of numbers, and we use repeated squaring to calculate an exponent.

Sometimes these different ideas for representing the problem give us new insight or new algorithms, and sometimes it turns out to be a new perspective on the same piece of code.

Reply on news.ycombinator.com