Now Reading
The Fibonacci Matrix

The Fibonacci Matrix

2023-07-31 08:14:32

When you concentrate on the Fibonacci sequence, you in all probability think about a swirling vortex of oscillating factors stretching outwards to infinity:


Okay, no, clearly you don’t. But.

When you concentrate on the Fibonacci sequence, you in all probability flush with a latent rage if you do not forget that it’s, as a rule, the way in which that we introduce the idea of “recursive features” to new programmers, in some type of merciless hazing supposed to make it tougher for them to ever admire how recursion may also help them write higher packages. Typically we even add memoization, and name it “dynamic programming,” with the intention to impress upon them that even probably the most trivial issues deserve advanced, inefficient options.

Er, okay, you in all probability don’t take into consideration the Fibonacci sequence a lot in any respect. It doesn’t, you understand, come up fairly often.

However I hope that you’ll spend a while excited about it with me as we speak, as a result of I feel that the Fibonacci sequence – regardless of being a horrible showcase for recursion – is a very attention-grabbing vector for discussing some strategies from linear algebra.

learn how to fibonacci house complexity time complexity
insane recursion exponential exponential
memoized insane recursion linear linear
trivial iteration fixed linear
exponentiation-by-squaring fixed logarithmic
eigendecomposition let’s discuss

We are going to spend no time on the recursive Fibonaccis; I’m certain that you just’ve seen them earlier than. As an alternative, let’s skip proper to the “apparent” option to calculate Fibonacci numbers:

operate fib(n) {
  if (n == 0) {
    return 0;
  }
  let present = 1;
  let earlier = 0;
  for (let i = 0; i < n - 1; i++) {
    const subsequent = present + earlier;
    earlier = present;
    present = subsequent;
  }
  return present;
}

No recursion, no memoization. We have now two items of state: the “present quantity” and the “earlier” quantity, and at each step of the iteration we advance each of those to new values.

However there’s one thing very attention-grabbing about this operate: the brand new values for our state are a linear mixture of the outdated values.

present'  = present + earlier
earlier' = present

Utilizing x' to imply “the following worth for x.”

And also you may acknowledge this as a “system of linear equations.” I feel it’s extra apparent once we write it like this:

present'  = 1 * present + 1 * earlier
earlier' = 1 * present + 0 * earlier

And also you may do not forget that there’s one other, extra cryptic option to write down a system of linear equations:

That is precisely the identical factor! That is simply one other method of writing the equation – it’s only a shorthand notation.

Right here, let’s try it out to verify of that:

=

1 • 8 + 1 • 5
1 • 8 + 0 • 5

=

Effectively that’s precisely what we anticipated – 13 is the following Fibonacci quantity within the sequence, and eight was the earlier one.

We are able to, in fact, repeat this course of, by making use of the system of linear equations once more:

Or, to place that one other method:

And right here’s why we care: matrix multiplication is associative, so we are able to really consider that like this:

Or:

In different phrases: given a system of linear equations to search out the subsequent state of our iteration, we are able to sq. the matrix-of-coefficients of the system to discover a new system of linear equations that represents “two states from now.”

After all we don’t want matrices to do that. We are able to compute a method for “two steps” of our iteration utilizing time period substitution:

present'  = present + earlier
earlier' = present

present''  = present' + earlier'
earlier'' = present'

present''  = (present + earlier) + present
earlier'' = (present + earlier)

present''  = 2 * present + earlier
earlier'' = present + earlier

Which is a brand new system of linear equations – which we are able to characterize as a matrix as properly.

We obtained the identical end result, due to course we did: multiplying by this matrix actually means “advance to the following state.” Multiplying twice means “advance to the following state after which advance to the following state after that.”

And we are able to maintain going. What’s the state three steps from now?

Or, extra concisely:

If we do that repeatedly, you may discover a well-recognized sample begin to emerge:

Which is sensible, doesn’t it? As a result of if we multiply this matrix with the matrix [1 0] – our beginning values – then it’s going to advance ahead by way of six steps of the Fibonacci sequence in a single leap. So naturally we now have to be encoding one thing concerning the sequence itself within the matrix – in any other case we wouldn’t be capable of advance by N steps in fixed time.

Now, the perception that takes this from linear to logarithmic is that we don’t have to do that multiplication one step at a time. We are able to multiply in leaps and bounds.

Let’s name our unique beginning matrix F, for Fibonacci.

We’ve already calculated F2:

And now it’s just one extra matrix multiplication to calculate F4:

We are able to use this reality to calculate arbitrary matrix powers, by breaking the issue up into sums of powers of two:

And by doing that, we are able to calculate the nth Fibonacci quantity in solely log2(n) steps.

Okay, in order that’s enjoyable and all, however that’s not likely what this weblog publish is about.

I don’t learn about you, but when I got here throughout this matrix within the wild, I’d not assume “Oh, that’s the Fibonacci sequence”:

I’d in all probability assume “huh, I dunno, it’s like, a mirrored image, type of, or possibly a shear; what’s a shear once more, grasp on, I have to see an image.”

That’s, I’m used to considering of matrices as transformations of factors in house – scales and rotations and issues like that. I’m not likely used to considering of matrices of “state machines.”

However this duality is the great thing about linear algebra! Matrices are transformations of factors in house and graphs and state machines all on the identical time.

So let’s check out the Fibonacci transformation, utilized to arbitrary factors in R2:

That animation is progressively making use of and eradicating the transformation, so we are able to get some instinct for the way it deforms a sq.. However we’re actually extra taken with repeated functions of the transformation. So let’s begin with the identical factors, however multiply by that very same matrix time and again:

Attention-grabbing. Over time, they generally tend to stretch out alongside the lengthy diagonals of this rhombus. Let’s zoom out:

Each time some extent displays over that diagonal, it displays at a barely totally different angle, slowly converging in the direction of this straight line.

You may have already got an concept of what that straight line means. You may know that, for those who take a look at the ratio between subsequent Fibonacci numbers, they approximate the golden ratio:

1  /  1 = 1
2  /  1 = 2
3  /  2 = 1.5
5  /  3 = 1.666...
8  /  5 = 1.6
13 /  8 = 1.625
21 / 13 = 1.61538462
34 / 21 = 1.61904762

The golden ratio is irrational, however each subsequent Fibonacci quantity is a greater and higher rational approximation. (The golden ratio is round 1.618033988749 – so we’re already fairly shut.)

It’s attention-grabbing to see that these estimations don’t “sneak up” on the golden ratio. The truth is they alternate between over- and under-estimating it. Which is precisely what we noticed in our visualization!

In case you return to the “state machine” interpretation of our matrix, do not forget that the worth we’re plotting as x is actually “the present Fibonacci quantity,” and the worth we’re plotting as y is “the earlier Fibonacci quantity.” So the ratio between successive numbers – x/y – is simply the slope of the traces that our factors are touring alongside. And we may see factors reflecting over that diagonal, over- and under-shooting it, slowly converging&mldr; in the direction of the road whose slope is the golden ratio.

Which is, in truth, the “lengthy diagonal” of our rhombus.

And this is sensible, I feel – this isn’t some bizarre coincidence. The golden ratio is all concerning the ratio between components and wholes being the identical as ratio between components. And the Fibonacci sequence is all about including collectively components to turn out to be wholes that turn out to be components within the subsequent variety of the sequence.

Right here, our two components are the “present” and “earlier” values, and the entire that they make is the “subsequent” Fibonacci quantity. Even when we begin with two numbers which can be utterly unrelated within the Fibonacci sequence – say, 8 and 41 – the easy method that we decide the following variety of the Fibonacci sequence will trigger us to approximate the golden ratio after only some 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? Effectively, due to the definition of the golden ratio.

That is extraordinarily unrigorous, however I can attempt to sketch out a really casual argument for why that is:

Let’s say the ratio between A and B is a few unknown amount S. It’s not the golden ratio, it won’t be wherever close to the golden ratio; we do not know what it’s. In my 8 and 41 instance, it wasn’t even in the fitting ballpark.

A/B = S

(A + B) / A = (1 + B / A) = 1 + (1/S)

So the ratio between the following ingredient in our sequence and A will likely be (1 + (1/S)).

We nonetheless don’t know what S is! But when we do that once more&mldr;

A’ / B’ = 1 + (1/S)

(A’ + B’) / A’ =

(1 + (B’ / A’)) =

1 + (1 / (1 + (1 / S)))

After every iteration, the unique S will turn out to be a smaller and smaller part within the ultimate reply, till finally we’ll simply have an expression that appears like this:

1 + (1 / (1 + (1 / (1 + (1 / (1 + (1 / …)))))))

No matter our unique S was, its contribution to the ultimate end result will finally be negligible. Even after only a few iterations, we are able to see that the selection of S doesn’t make an enormous distinction within the final result:

1 + (1 / (1 + (1 / (1 + (1 / (1 + (1 / -5000))))))) = 1.6667

1 + (1 / (1 + (1 / (1 + (1 / (1 + (1 / 0.001))))))) = 1.5002

And naturally even that may fade away after a couple of extra steps.

The truth is the model of that expression with an infinite variety of steps – the place there isn’t any S in any respect, however simply an infinite sequence of divisions – is the “continued fraction” expression of the golden ratio.

Besides, properly, I’m mendacity right here.

That residue won’t fade away for all values of S. To start with, if S is zero, it doesn’t matter how small that time period will get – you’re not going to squeeze a quantity out of it.

However there may be one other, extra attention-grabbing worth of S that breaks this rule. There may be one different quantity that won’t have a tendency in the direction of 1.618 if you repeatedly take its reciprocal and add one. It’s the quantity that’s already one plus its personal reciprocal:

1 + (1 / 1.61803399) = 1.61803399

Oh, gosh, sure, the golden ratio is one plus its personal reciprocal. However I used to be speaking concerning the different quantity with that property:

1 + (1 / -0.61803399) = -0.61803399

This quantity is (1 – φ), and additionally it is -φ-1. The golden ratio is bizarre like that.

That quantity is a bizarre quantity, as a result of if we now have two numbers with that ratio – say, -1.236 and 2 – and we utilized our transformation, these factors wouldn’t unfold their wings in the direction of the diagonal. What would they do as a substitute?

Aha. Effectively, that is sensible.

Some factors have a tendency in the direction of the highest proper, some factors have a tendency in the direction of the underside left, however some factors get caught. Sucked into the origin, cursed to without end journey alongside this one straight line.

Factors alongside the lengthy diagonal additionally journey in a straight line – they don’t bounce over the diagonal, as a result of they’re already on it. Let’s simply concentrate on these completely straight traces:

Not all matrices will produce straight traces like this if you apply them repeatedly. A rotation matrix, for instance, will all the time change the course of each single line every time you multiply some extent by it.

These straight traces are referred to as eigenvectors, which is German for one thing like “intrinsic vector” or “attribute vector.”

Effectively, to be extra exact, any specific level on these straight traces is an “eigenvector.” The vector [φ 1] is an eigenvector, and so is [-2.1φ -2.1]. And the vector [-1/φ 1] is an eigenvector, and so is [-2/φ 2].

However all the eigenvectors on every line are “related,” so I’m simply going to choose [φ 1] and [(1-φ) 1] as our two consultant eigenvectors.

While you multiply an eigenvector of a matrix by the matrix itself, you get again a brand new eigenvector on “the identical line.” That’s to say, you get again one other eigenvector that’s just a few scalar a number of of the unique eigenvector.

For instance, once we multiply our first eigenvector by the Fibonacci matrix:

Effectively&mldr; it’s not apparent that that is the case, however we really simply scaled the vector by φ. As a result of φ2 = φ + 1. The golden ratio is bizarre.

Equally:

We scaled it by (1 – φ), once more considerably cryptically:

(1 – φ)(1 – φ) =

(1 – 2φ + φ2) =

(1 – 2φ + φ + 1) =

(2 – φ)

So once we multiply our Fibonacci matrix with its eigenvectors, we scale these numbers by φ and (1 – φ). These scaling components are referred to as “eigenvalues,” and it’s bizarre that they give the impression of being a lot just like the eigenvectors. That’s&mldr; that’s a bizarre Fibonacci coincidence, a bizarre golden ratio factor, and never a normal sample that holds for eigenvectors and eigenvalues normally.

Okay, so why can we care about this?

Effectively, as soon as we all know the eigenvectors and eigenvalues of the matrix, we are able to really carry out repeated matrix multiplication in fixed time.

&mldr;Type of. You need to think about an enormous asterisk after that sentence, which I’ll clarify beneath.

To elucidate how, we’re going to want to do some little bit of linear algebra. However first, I simply wish to restate every little thing I’ve stated up to now in specific notation:

Multiplying F with every eigenvector is identical as multiplying that eigenvector by its corresponding eigenvalue. So:

And:

Proper. However there’s really a option to write these two equalities as a single equality:

As an alternative of writing out every eigenvector as a separate column vector, I caught them right into a matrix. And as a substitute of scaling each by a scalar, I multiplied that matrix by a diagonal matrix.

This is identical assertion, although: right-multiplication by a diagonal matrix simply means “scale the columns of the left matrix by the corresponding diagonal worth.” We are able to intestine examine this by performing the multiplcation, and seeing that we’re making the very same statements as earlier than:

However now we’re making these assertion about each eigenvectors in parallel.

This equality – this assertion about how multiplication by the Fibonacci matrix scales eigenvectors – is the key to computing Fibonacci numbers in “fixed time”:

The trick right here is that we’re going to right-multiply either side of the equation by the inverse of our eigenvector matrix. This can get rid of it from the left-hand facet totally:

And now we now have a brand new option to calculate the “subsequent Fibonacci quantity.” Beforehand we knew learn how to do it by multiplying with the matrix F. Now we are able to do it by multiplying with, uhh, this inverse eigenvector matrix factor, after which the diagonal matrix of eigenvalues, after which the non-inverse matrix-of-eigenvectors.

A lot less complicated, proper?

That is getting actually lengthy and sophisticated and I’m going to expire of house quickly, so let’s give this stuff names:

That’s an upper-case lambda, and look, it’s simply the conference for the eigenvalue matrix. Eigenvalues are referred to as λ, and if you put them in a diagonal matrix you name it Λ. I don’t make the principles right here.

See Also

Now that we now have some abbreviations, we are able to write that because the way more palatable:

Now, the entire motive that we’re doing that is to benefit from one other trick of associativity:

F2 = (Q Λ Q-1)(Q Λ Q-1)

That was very summary, so take a second to consider what this means. F2 is the matrix that calculates two steps of our Fibonacci state machine. And we are able to use this identical trick to calculate any energy of F, simply by calculating powers of Λ.

And that is good, as a result of Λ is a diagonal matrix. And it’s very easy to exponentiate a diagonal matrix! You simply exponentiate every ingredient of its diagonal. We don’t even want to make use of repeated squaring.

Because of this we are able to really calculate arbitrary powers of F in fixed time&mldr; if we fake that exponentiation of a scalar is a continuing time operation.

It’s not, although. I imply, sure, exponentiation of an IEEE 754 64-bit floating-point is fixed time, however that’s not what we stated. We’re speaking about exponentiating an irrational quantity, and my pc can solely characterize approximations of that quantity, and that floating-point error provides up quick. So with the intention to really use this to compute giant Fibonacci numbers, we would wish to make use of arbitrary-precision floating level, and exponentiating arbitrary precision values is not fixed time. It’s&mldr; I don’t know, in all probability logarithmic? However like each to the exponent and the dimensions of the end result, and the dimensions of the result’s rising exponentially, so it nets out to linear? I don’t really know.

However I don’t wish to spoil the enjoyable. That is nonetheless a really attention-grabbing trick, and it’s value understanding the way it works, even when it doesn’t really give us a option to compute arbitrarily giant Fibonacci numbers in fixed time.

So: what are we doing.

We moved a bunch of symbols round, and we wound up with this expression:

However I don’t actually know what Q-1 means, and it’s not likely clear to me why I ought to care. Why is multiplying by these three bizarre matrices the identical as multiplying by F? What, intuitively, are we doing right here?

At a excessive degree, we’re translating factors into a special coordinate system, then doing one thing to it, after which translating them again into our unique coordinate system.

You already know that we are able to write any level in house as a vector – X and Y coordinates. That’s what we’ve been doing this complete time.

However we are able to additionally write some extent in house because the sum of two different vectors. Like, [5 3]. We may write that as [1 2] + [4 1] as a substitute. Which, okay, certain. That’s not very attention-grabbing.

One “attention-grabbing” option to write [5 3] is because the sum of those two vectors: [5 0] + [0 3]. Or, to say that one other method:

That is attention-grabbing as a result of [1 0] and [0 1] are principally the “X axis” and “Y axis.” And we are able to consider the purpose [5 3] as a (trivial!) linear mixture of those two axes.

However we may decide totally different axes. We are able to decide any vectors we wish as our axes, so let’s fake for a second that our axes are [1 1] and [1 -1] as a substitute. Which implies that we’d write [5 3] as:

Or, to write down that one other method:

Alright. Why can we care?

Effectively, we are able to consider this vector-of-coefficients, [4 1], as one other option to establish the purpose in house x=5 y=3 once we we’re pretending that our axes are [1 1] and [1 -1]. Besides in linear algebra we’d name these “foundation vectors” as a substitute of “axes.”

However how did we discover the coefficients [4 1]? Effectively, I simply discovered that one by hand; it was fairly straightforward. However normally, if we wish to specific another level utilizing these foundation vectors – let’s say [63 -40] – we’ll want to unravel an equation that appears like this:

And we are able to do this by, you understand, common algebra. We “divide” either side by our matrix-of-basis-vectors, by left-multiplying with the inverse matrix:

And after the inverses cancel, we’re left with the next method:

And the issue reduces to matrix inversion.

Now, I don’t learn about you, however I don’t bear in mind learn how to invert a matrix. I do know there’s a method in two dimensions, however the one factor I bear in mind about it’s that it includes calculating the determinant, and I forgot how to try this too. So let’s simply ask a pc to invert it for us:

Hmm. I really feel like I in all probability may’ve labored that out myself.

However that lets us clear up the equation, and determine learn how to write the purpose [63 -40] as a mix of the vectors [1 1] and [1 -1]:

Nice! We did it.

And right here’s why we care:

We are able to use this very same trick to write down down the factors in our Fibonacci sequence as a linear mixture of our two eigenvectors. Like this:

Click on or faucet so as to add factors there, to see how we are able to write every level in house as a mix of the “quick diagonal” and “lengthy diagonal” eigenvectors of our matrix.

Usually to establish some extent in house we’d give its XY coordinates: go this far alongside the X-axis, then this far alongside the Y-axis. However right here we’re representing factors in “φ” and “1 – φ” coordinates: go this far alongside the quick diagonal, then this far alongside the lengthy diagonal.

However how do we all know how far to go alongside these diagonals? Effectively, we “divide by” the eigenvectors. In different phrases, we now have to compute the inverse of this matrix:

Now, matrix inversion is boring, so I’m simply presenting the reply right here. This inverse matrix is how we are able to convert from “XY coordinates” into “eigenvector coordinates.”

Let’s work by way of a concrete instance to verify this works.

[8 5] is some extent on the Fibonacci sequence. We are able to specific that as a mix of eigenvectors as a substitute:

4.96 and 0.04 are the coefficients we are going to pair with our eigenvectors: we now have to journey 4.96 models down the lengthy diagonal, and 0.04 models alongside the quick diagonal to reach on the level [8 5].

Nice. It labored!

However that wasn’t very attention-grabbing – we simply transformed our level into the eigenvector foundation after which proper again into the traditional XY foundation. It was sort of a pointless transformation.

However we don’t need to do the unconversion instantly. We are able to maintain the purpose on this “eigenbasis” for a short time, and do stuff to the vector-of-coefficients, and then convert it again.

Particularly, we are able to scale the coefficients by the eigenvalues of our Fibonacci matrix. We are able to multiply the “lengthy diagonal” part by Φ2, and multiply the quick diagonal part by (1 – Φ)2, and we’ll have a brand new level: one thing near [12.985 0.015]. And if we convert that again into XY coordinates:

We simply superior our level two extra steps alongside the Fibonacci sequence, with nothing greater than scalar exponentiation and a continuing variety of vector operations.

That is precisely the identical because the expression:

However as somebody with no background in linear algebra, I discover it straightforward to get misplaced within the notation, so it’s simpler for me to consider this as operations on separate column vectors relatively than as operations on matrices. Though they’re the identical factor.

After all, calculating two steps of the Fibonacci sequence in fixed time isn’t that spectacular. However we are able to do the identical with Φ1000, and use that to calculate the thousandth Fibonacci quantity in fixed time.

&mldr;Assuming we may calculate Φ1000 in fixed time. Which we are able to’t, in actual life.


Alright.

The publish is over; you noticed the trick. “Eigendecomposition,” that is referred to as.

I glossed over a couple of steps – I spent completely no time explaining how I knew the eigenvalues and eigenvectors of this matrix, for instance. I simply asserted that they had been associated to the golden ratio. However in actuality you may clear up for them, or ask a pc to do it for you. It’s fairly mechanical, like matrix inversion – it appears linear algebra is greatest explored with a repl close by.

In any case, I feel that the why of eigendecomposition is extra attention-grabbing than the how.

As for the Fibonacci sequence&mldr; properly, this can be a fairly horrible option to really calculate Fibonacci numbers. Even when we fake that we solely care about numbers that may slot in IEEE 754 double-precision floats, we nonetheless can’t use this method to calculate very many Fibonacci numbers, as a result of the floating-point error provides up too shortly.

But when we solely care about double-precision floats&mldr; properly, there may be yet another Fibonacci implementation to think about. It’s an algorithm that that runs in fixed time, and fixed house, and covers the total gamut of floating-point numbers with out accumulating any error in any respect&mldr;

const fibs = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464];

const fib = (n) => fibs[n];

Nevertheless it’s extra enjoyable to overthink it.

Source Link

What's Your Reaction?
Excited
0
Happy
0
In Love
0
Not Sure
0
Silly
0
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top