We want to jump straight to the nth step of a step-by-step sequence without having to calculate every step along the way.
1
The Fibonacci Sequence as a Matrix Power
In the Fibonacci sequence 0,1,1,2,3,5,8,…, numbered from F0=0 and F1=1, each number is the sum of the two before it, so finding the 100th Fibonacci number F100 by hand means computing every Fibonacci number before it. Stacking two consecutive Fibonacci numbers into a column vector turns each step forward into multiplying by a 2×2 matrix.
The Fibonacci Sequence as a Matrix Power
Text solution
Stack two consecutive terms into a column vectorPutting the newest number on top and the older number on the bottom turns each step of the sequence into a new vector:
[10]→[11]→[21]→[32]→[53]
Write the single-step rule as a matrixAdding the old top and bottom gives the new top, and moving the old top down gives the new bottom:
[1110][32]=[1(3)+1(2)1(3)+0(2)]=[53]
Take n steps with a matrix powerMultiplying the starting vector [10] by A=[1110] a total of n times puts the nth Fibonacci number in the bottom entry:
[1110]n[10]=[Fn+1Fn]
So finding F100 comes down to computing [1110]100[10].
2
Eigenvalues and Eigenvectors of the Fibonacci Matrix
Writing A100 still doesn't save any work if we have to multiply the matrix by itself 100 times, because every multiplication mixes the top and bottom entries together. Instead, we look for the eigenvectors of A, where multiplying by A just scales the vector by a single number λ:
Av=λv⟹A2v=λ2v⟹Anv=λnv
Eigenvalues and Eigenvectors of the Fibonacci Matrix
Text solution
Use an eigenvector of the form [λ1] to find the characteristic equationBecause multiplying [λ1] by A=[1110] moves λ into the bottom entry (multiplying the bottom entry 1 by λ), the top entry λ must also get multiplied by λ to become λ2:
[1110][λ1]=[λ+1λ]=[λ2λ]⟹λ2−λ−1=0
Solve for the two eigenvaluesApplying the quadratic formula gives the Golden Ratio φ and a second negative eigenvalue ψ:
λ1λ2=φ≈1.61821+5,=ψ≈−0.61821−5
Write the eigenvectors and their nth powersPlugging φ and ψ into [λ1] gives two eigenvectors that An scales directly by φn and ψn:
An[φ1]An[ψ1]=φn[φ1],=ψn[ψ1]
So along either eigenvector line, n matrix multiplications simplify to a single power of φ or ψ.
For almost every starting vector v=[x1], multiplying by A changes the vector's top-to-bottom ratio at each step, except along the two eigenvector lines at ratios φ≈1.618 and ψ≈−0.618, where Av,A2v, and A3v stay on the same line.
Multiplying by the Fibonacci matrix changes the top-to-bottom ratio of every vector except the ones along two special lines, where the ratio stays the same.
3
The Direct Formula for Fibonacci and the Golden Ratio
Now we want a direct formula for Fn starting from [10], which does not lie on either eigenvector line. Because the two eigenvectors [φ1] and [ψ1] are independent, we can write [10] as a combination of them and apply An to each piece separately.
The Direct Formula for Fibonacci and the Golden Ratio
Text solution
Build the starting vector out of the eigenvectorsSubtracting the two eigenvectors cancels the 1s on the bottom and leaves φ−ψ=5 on top, so dividing by 5 gives [10]:
[10]=51[φ1]−51[ψ1]
Multiply both sides by AnSince each vector on the right is an eigenvector, An scales the first piece by φn and the second piece by ψn:
[Fn+1Fn]=An[10]=51φn[φ1]−51ψn[ψ1]
Read the bottom row to get FnBoth eigenvectors have 1 in the bottom entry, giving the direct formula for the nth Fibonacci number:
Fn=51φn−51ψn=51(21+5)n−51(21−5)n
Drop the shrinking term as n→∞Because ∣ψ∣≈0.618<1,ψn→0 for large n, leaving only the φn term:
[Fn+1Fn]≈51φn[φ1]⟹FnFn+1≈φ≈1.618
So the ratio of consecutive Fibonacci numbers approaches the Golden Ratio φ≈1.618 as n grows. Because the second term 51(−0.618)n is always smaller than 0.5 in absolute value, you can compute Fn on a calculator just by rounding 5φn to the nearest whole number, though for an exact formula you need both terms written out.
4
Long-Run Behavior and Steady State When λ=1
Next, we want to find what happens after n steps and in the long run when a system trades a fixed total back and forth instead of growing forever. When we split a starting vector into eigenvectors, what happens to each piece as n→∞ depends only on how ∣λ∣ compares to 1.
Let's track two streaming services, X and Y, that share 100 customers, who switch between the services each month according to A=[0.80.20.30.7], where the largest eigenvalue is λ1=1.
Long-Run Behavior and Steady State When λ = 1
Text solution
Find the eigenvalues and eigenvectors of ASolving det(A−λI)=0 gives λ1=1 with v1=[32] (which scales to [6040] for 100 total customers) and λ2=0.5 with v2=[1−1]:
A[6040]A[1−1]=1[6040],=0.5[1−1]
Split the starting vector into the steady state and the initial imbalanceStarting with [1000] means service X begins with 40 more customers than its steady-state 60, and service Y begins with 40 fewer than its steady-state 40:
Multiply by An using the eigenvaluesAfter n months, the [6040] steady state is multiplied by 1n=1, while the imbalance is multiplied by (0.5)n:
An[1000]=[6040]+(0.5)n⋅40[1−1]
Let n→∞ to find the steady stateSince (0.5)n→0, the imbalance shrinks to 0:
n→∞limAn[1000]=[6040]
So the customer counts go from [8020] after 1 month to [7030] after 2 months, and eventually settle at 60 customers in X and 40 in Y.
For every initial split of the 100 customers between services X and Y, the [6040] steady-state part stays fixed while the c2[1−1] imbalance is cut in half each month, so every starting split settles to [6040].
No matter how you split the 100 starting customers, the 60-to-40 steady state stays fixed while the imbalance is cut in half each month.
5
Formula for An Using Diagonalization
Up to now, we have found Anv0 for one specific starting vector v0. When no starting vector is given, or when we want a formula for every entry of the matrix An itself, we compute the matrix power using diagonalization.
Writing A=PDP−1 with the eigenvectors in P and the eigenvalues in D makes An easy to compute, because every P−1P pair in the middle cancels out:
An=(PDP−1P=IP−1)(PDP−1)⋯(PDP−1)=PDnP−1
Formula for Aⁿ Using Diagonalization
AAn=[0.80.20.30.7]=[????]
Text solution
Set up P,Dn, and P−1 from the eigenvectors and eigenvaluesUsing v1=[32] with λ1=1 and v2=[1−1] with λ2=0.5 for A=[0.80.20.30.7], build P, raise the diagonal of D to the nth power, and invert P:
Take the limit as n→∞Letting (0.5)n→0 in all four entries gives the long-run matrix A∞:
A∞=[0.60.40.60.4]
So whatever starting vector you multiply by An,60% of the total ends up in the top entry and 40% ends up in the bottom entry in the long run.
Key concepts
Whenever a square matrix A has as many independent eigenvectors as it has columns (so it is diagonalizable), you can jump straight to step n without multiplying A repeatedly.
First check whether your starting vector v0 is already a multiple of a single eigenvector v1. If it is, don't split it into pieces or invert a matrix; just scale it directly by λ1n, such as An[6040]=1n[6040]=[6040].
Power times a starting vector (Anv0)
When given a specific starting vector v0, split it into eigenvectors and scale each piece by λn:
v0⟹Anv0=c1v1+c2v2=c1λ1nv1+c2λ2nv2
For example, [1000]=[6040]+40[1−1] gives An[1000]=[6040]+(0.5)n⋅40[1−1] without needing P−1.
Formula for the whole matrix (An)
When you need the entries of An itself in terms of n, diagonalize and raise only the diagonal entries of D to the nth power:
An=PDnP−1=[v1v2][λ1n00λ2n][v1v2]−1
Long-run behavior (n→∞)
Look at the sizes of the eigenvalues in Anv0=c1λ1nv1+c2λ2nv2:
∣λ∣<1 shrinks to 0: Terms like (0.5)n and (−0.618)n go to 0.
λ=1 stays steady: If λ1=1 and every other eigenvalue has ∣λ∣<1, the system settles to the c1v1 steady-state vector, such as [6040].
Largest ∣λ∣>1 takes over: When c1=0,Anv0≈c1λ1nv1 for large n, so the ratio of the entries of Anv0 approaches the entry ratio of the eigenvector v1 with the largest eigenvalue (such as FnFn+1→1φ=φ).
6
Practice
1
A matrix A has eigenvalues λ1=3 with eigenvector v1=[12] and λ2=−1 with eigenvector v2=[1−1]. By writing the starting vector as a combination of v1 and v2, find a formula for An[45] and evaluate A10[45].
Watch out: don't drop the factor of c1=3 to get 310 instead of 311.Watch out: remember that (−1)10=+1, not −1.
Write [45]=c1[12]+c2[1−1]: what happens to c2 when you add the top and bottom equations together?
Adding the two rows of [45]=c1[12]+c2[1−1] gives 9=3c1, so c1=3 and c2=1:
[45]=3[12]+1[1−1]
Multiplying by An scales the first piece by 3n and the second by (−1)n:
For n=10, watch out for two common slips: don't drop the factor of c1=3 to get 310 instead of 311 (which gives [59,050118,097]), and remember that (−1)10=+1, not −1 (which gives [177,146354,295]):
A10[45]=[311+12⋅311−1]=[177,148354,293]
2
Two bike-share stations, Uptown and Downtown, trade bikes each day according to A=[0.70.30.20.8], which has eigenvalues λ1=1 with eigenvector v1=[23] and λ2=0.5 with eigenvector v2=[1−1]. Starting with [8020] bikes, split the starting vector into the steady-state vector and the initial imbalance, find the bike distribution after 3 days, and find the distribution in the long run as n→∞.
Be careful not to flip the steady state to [6040] just because Uptown starts with more bikes.
The two stations have 80+20=100 bikes in total, and the entries of v1=[23] add up to 5: what multiple of v1 gives the 100-bike steady state?
Scaling v1=[23] by 20 so its entries add up to 100 gives the steady-state vector [4060]. Be careful not to flip the steady state to [6040] just because Uptown starts with more bikes (which leads to the wrong 3-day split [62.537.5] and long-run split [6040]):
As n→∞,(0.5)n→0 and the distribution settles at [4060].
3
Diagonalize A=[1221] and use An=PDnP−1 to find a formula for each entry of the matrix An in terms of n.
After finding λ1,λ2 and building P=[v1v2], multiply PDn first before multiplying by P−1 on the right.
Solving det(A−λI)=(1−λ)2−4=0 gives λ1=3 with v1=[11] and λ2=−1 with v2=[1−1]. When inverting P=[111−1], watch out for the negative determinant det(P)=−1−1=−2; dividing by 2 instead of −2 gives −21[3n+(−1)n3n−(−1)n3n−(−1)n3n+(−1)n] with every sign flipped:
A sequence begins with a0=0,a1=1 and follows the rule an+1=an+2an−1. (a) Write the 2×2 matrix A such that [an+1an]=An[10]. (b) Use an eigenvector of the form [λ1] to find the eigenvalues and eigenvectors of A. (c) Find the direct formula for an and the value that the ratio anan+1 approaches as n→∞.
(a) The top row of A builds an+1 from an and an−1; what does the bottom row do to turn [anan−1] into [an+1an]? (c) Use the bottom entries of [21] and [−11] to cancel to 0 when building [10].
(a) A=[1120].
(b) Multiplying [λ1] by A gives A[λ1]=[λ+2λ]=[λ2λ], so λ2−λ−2=0, which gives λ1=2 with v1=[21] and λ2=−1 with v2=[−11].
(c) Subtracting the two eigenvectors gives [21]−[−11]=[30], so dividing by 3 and multiplying by An gives:
[an+1an]=An[10]=31(2n)[21]−31(−1)n[−11]
Make sure to read the bottom entry for an rather than the top entry (reading the top entry gives an+1=32n+1+(−1)n):
an=32n−(−1)n
Since 2n grows while (−1)n stays at size 1, the ratio anan+1 approaches 2.
5
A matrix A has eigenvalues λ1=2 with eigenvector v1=[31] and λ2=0.4 with eigenvector v2=[12]. (a) If v0=[74], what does the ratio of the top entry to the bottom entry of Anv0 approach as n→∞? (b) Find all nonzero starting vectors v0=[xy] for which Anv0→[00] as n→∞.
Watch out: don't confuse the largest eigenvalue λ1=2 with the entry ratio of its eigenvector v1=[31].
Write Anv0=c1(2n)[31]+c2(0.4)n[12]: which eigenvector sets the long-run ratio of the entries when c1=0, and what must c1 be if the vector shrinks to [00]?
(a) Since [74]=2[31]+1[12], we have An[74]=2(2n)[31]+(0.4)n[12]. As n→∞,(0.4)n→0 and Anv0≈2(2n)[31]. Don't confuse the largest eigenvalue λ1=2 with the entry ratio of its eigenvector v1=[31] (which gives the wrong answer 2): the top-to-bottom entry ratio approaches 13=3.
(b) In Anv0=c1(2n)[31]+c2(0.4)n[12], don't assume that λ1=2>1 makes every nonzero starting vector grow without bound: the vector shrinks to [00] exactly when c1=0, which means v0 is any nonzero multiple of v2:[xy]=c[12] for c=0.