Linear AlgebraEigenvalues and Eigenvectors5 of 7
Eigenvalues and Eigenvectors · 5

Matrix Powers: Fibonacci and Long-Run Behavior

We want to jump straight to the nnth 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,…\state{0, 1, 1, 2, 3, 5, 8}, \dots, numbered from F0=0\state{F_0 = 0} and F1=1\state{F_1 = 1}, each number is the sum of the two before it, so finding the 100th Fibonacci number F100\state{F_{100}} 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×22 \times 2 matrix.

The Fibonacci Sequence as a Matrix Power
0, 1, 1, 2, 3, 5, 8, 13, 21, …\htmlClass{lc-blue}{0,\, 1,\, 1,\, 2,\, 3,\, 5,\, 8,\, 13,\, 21,\, \dots}
??
F100\htmlClass{lc-blue}{F_{100}}
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]\displaystyle \state{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} \step{\to} \state{\begin{bmatrix} 1 \\ 1 \end{bmatrix}} \step{\to} \state{\begin{bmatrix} 2 \\ 1 \end{bmatrix}} \step{\to} \state{\begin{bmatrix} 3 \\ 2 \end{bmatrix}} \step{\to} \state{\begin{bmatrix} 5 \\ 3 \end{bmatrix}}
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]\displaystyle \begin{aligned} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \state{\begin{bmatrix} 3 \\ 2 \end{bmatrix}} &= \begin{bmatrix} 1(\state{3}) + 1(\state{2}) \\ 1(\state{3}) + 0(\state{2}) \end{bmatrix} \\ &= \state{\begin{bmatrix} 5 \\ 3 \end{bmatrix}} \end{aligned}
Take nn steps with a matrix powerMultiplying the starting vector [10]\state{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} by A=[1110]A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} a total of nn times puts the nnth Fibonacci number in the bottom entry:
[1110]n[10]=[Fn+1Fn]\displaystyle \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \state{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} = \state{\begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix}}

So finding F100\state{F_{100}} comes down to computing [1110]100[10]\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{100} \state{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}.

2

Eigenvalues and Eigenvectors of the Fibonacci Matrix

Writing A100A^{100} 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 AA, where multiplying by AA just scales the vector by a single number λ\lambda:

Av\displaystyle A\vone{v} =λv  ⟹  A2v\displaystyle = \lambda \vone{v} \implies A^2 \vone{v} =λ2v  ⟹  Anv\displaystyle = \lambda^2 \vone{v} \implies A^n \vone{v} =λnv\displaystyle = \lambda^n \vone{v}
Eigenvalues and Eigenvectors of the Fibonacci Matrix
A=[1110]A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}
[10]\htmlClass{lc-blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}
λ=  ?v=  ?\lambda = \;?\quad \htmlClass{lc-green}{v} = \;?
Text solution
Use an eigenvector of the form [λ1]\state{\begin{bmatrix} \lambda \\ 1 \end{bmatrix}} to find the characteristic equationBecause multiplying [λ1]\state{\begin{bmatrix} \lambda \\ 1 \end{bmatrix}} by A=[1110]A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} moves λ\lambda into the bottom entry (multiplying the bottom entry 11 by λ\lambda), the top entry λ\lambda must also get multiplied by λ\lambda to become λ2\lambda^2:
[1110][λ1]=[λ+1λ]=[λ2λ]  ⟹  λ2−λ−1=0\displaystyle \begin{aligned} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \state{\begin{bmatrix} \lambda \\ 1 \end{bmatrix}} &= \state{\begin{bmatrix} \lambda + 1 \\ \lambda \end{bmatrix}} = \state{\begin{bmatrix} \lambda^2 \\ \lambda \end{bmatrix}} \\ &\implies \lambda^2 - \lambda - 1 = 0 \end{aligned}
Solve for the two eigenvaluesApplying the quadratic formula gives the Golden Ratio φ\vone{\varphi} and a second negative eigenvalue ψ\vtwo{\psi}:
λ1=1+52⏟φ≈1.618,λ2=1−52⏟ψ≈−0.618\displaystyle \begin{aligned} \vone{\lambda_1} &= \underbrace{\vone{\frac{1 + \sqrt{5}}{2}}}_{\vone{\varphi \approx 1.618}}, \\ \vtwo{\lambda_2} &= \underbrace{\vtwo{\frac{1 - \sqrt{5}}{2}}}_{\vtwo{\psi \approx -0.618}} \end{aligned}
Write the eigenvectors and their nnth powersPlugging φ\vone{\varphi} and ψ\vtwo{\psi} into [λ1]\state{\begin{bmatrix} \lambda \\ 1 \end{bmatrix}} gives two eigenvectors that AnA^n scales directly by φn\vone{\varphi^n} and ψn\vtwo{\psi^n}:
An[φ1]=φn[φ1],An[ψ1]=ψn[ψ1]\displaystyle \begin{aligned} A^n \vone{\begin{bmatrix} \varphi \\ 1 \end{bmatrix}} &= \vone{\varphi^n} \vone{\begin{bmatrix} \varphi \\ 1 \end{bmatrix}}, \\ A^n \vtwo{\begin{bmatrix} \psi \\ 1 \end{bmatrix}} &= \vtwo{\psi^n} \vtwo{\begin{bmatrix} \psi \\ 1 \end{bmatrix}} \end{aligned}

So along either eigenvector line, nn matrix multiplications simplify to a single power of φ\vone{\varphi} or ψ\vtwo{\psi}.

For almost every starting vector v=[x1]\state{v} = \state{\begin{bmatrix} x \\ 1 \end{bmatrix}}, multiplying by AA changes the vector's top-to-bottom ratio at each step, except along the two eigenvector lines at ratios φ≈1.618\vone{\varphi \approx 1.618} and ψ≈−0.618\vtwo{\psi \approx -0.618}, where Av,A2v,A\state{v}, A^2\state{v}, and A3vA^3\state{v} 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\state{F_n} starting from [10]\state{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}, which does not lie on either eigenvector line. Because the two eigenvectors [φ1]\vone{\begin{bmatrix} \varphi \\ 1 \end{bmatrix}} and [ψ1]\vtwo{\begin{bmatrix} \psi \\ 1 \end{bmatrix}} are independent, we can write [10]\state{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} as a combination of them and apply AnA^n to each piece separately.

The Direct Formula for Fibonacci and the Golden Ratio
[φ1]\htmlClass{lc-green}{\begin{bmatrix} \varphi \\ 1 \end{bmatrix}}
[ψ1]\htmlClass{lc-pink}{\begin{bmatrix} \psi \\ 1 \end{bmatrix}}
[10]\htmlClass{lc-blue}{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}
Fn=  ?\htmlClass{lc-blue}{F_n} = \;?
Text solution
Build the starting vector out of the eigenvectorsSubtracting the two eigenvectors cancels the 11s on the bottom and leaves φ−ψ=5\vone{\varphi} - \vtwo{\psi} = \sqrt{5} on top, so dividing by 5\sqrt{5} gives [10]\state{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}:
[10]=15[φ1]−15[ψ1]\displaystyle \state{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} = \vone{\frac{1}{\sqrt{5}}\begin{bmatrix} \varphi \\ 1 \end{bmatrix}} - \vtwo{\frac{1}{\sqrt{5}}\begin{bmatrix} \psi \\ 1 \end{bmatrix}}
Multiply both sides by AnA^nSince each vector on the right is an eigenvector, AnA^n scales the first piece by φn\vone{\varphi^n} and the second piece by ψn\vtwo{\psi^n}:
[Fn+1Fn]=An[10]=15φn[φ1]−15ψn[ψ1]\displaystyle \begin{aligned} \state{\begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix}} &= A^n \state{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} \\ &= \vone{\frac{1}{\sqrt{5}}\varphi^n \begin{bmatrix} \varphi \\ 1 \end{bmatrix}} - \vtwo{\frac{1}{\sqrt{5}}\psi^n \begin{bmatrix} \psi \\ 1 \end{bmatrix}} \end{aligned}
Read the bottom row to get Fn\state{F_n}Both eigenvectors have 11 in the bottom entry, giving the direct formula for the nnth Fibonacci number:
Fn=15φn−15ψn=15(1+52)n−15(1−52)n\displaystyle \begin{aligned} \state{F_n} &= \vone{\frac{1}{\sqrt{5}}\varphi^n} - \vtwo{\frac{1}{\sqrt{5}}\psi^n} \\ &= \vone{\frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^n} \\ &\quad - \vtwo{\frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^n} \end{aligned}
Drop the shrinking term as n→∞n \to \inftyBecause ∣ψ∣≈0.618<1\vtwo{|\psi| \approx 0.618} < 1, ψn→0\vtwo{\psi^n} \to 0 for large nn, leaving only the φn\vone{\varphi^n} term:
[Fn+1Fn]≈15φn[φ1]  ⟹  Fn+1Fn≈φ≈1.618\displaystyle \state{\begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix}} \approx \vone{\frac{1}{\sqrt{5}}\varphi^n \begin{bmatrix} \varphi \\ 1 \end{bmatrix}} \implies \state{\frac{F_{n+1}}{F_n}} \approx \vone{\varphi \approx 1.618}

So the ratio of consecutive Fibonacci numbers approaches the Golden Ratio φ≈1.618\vone{\varphi \approx 1.618} as nn grows. Because the second term 15(−0.618)n\vtwo{\frac{1}{\sqrt{5}}(-0.618)^n} is always smaller than 0.50.5 in absolute value, you can compute Fn\state{F_n} on a calculator just by rounding φn5\vone{\frac{\varphi^n}{\sqrt{5}}} 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\lambda = 1

Next, we want to find what happens after nn 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→∞n \to \infty depends only on how ∣λ∣|\lambda| compares to 11.

1\htmlClass{lc-mute}{1}
−1\htmlClass{lc-mute}{-1}
∣λ∣>1|\lambda| > 1
0\htmlClass{lc-mute}{0}
5\htmlClass{lc-mute}{5}
(1.618)n\htmlClass{lc-green}{(1.618)^n}
λ=1\lambda = 1
0\htmlClass{lc-mute}{0}
5\htmlClass{lc-mute}{5}
1n1^n
∣λ∣<1|\lambda| < 1
0\htmlClass{lc-mute}{0}
5\htmlClass{lc-mute}{5}
(−0.618)n\htmlClass{lc-pink}{(-0.618)^n}

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.30.20.7]A = \begin{bmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{bmatrix}, where the largest eigenvalue is λ1=1\vone{\lambda_1 = 1}.

Long-Run Behavior and Steady State When λ = 1
X\text{X}
Y\text{Y}
0.80.8
0.20.2
0.30.3
0.70.7
100\htmlClass{lc-blue}{100}
0\htmlClass{lc-blue}{0}
An[1000]=  ?A^n \htmlClass{lc-blue}{\begin{bmatrix} 100 \\ 0 \end{bmatrix}} = \;?
Text solution
Find the eigenvalues and eigenvectors of AASolving det⁡(A−λI)=0\det(A - \lambda I) = 0 gives λ1=1\vone{\lambda_1 = 1} with v1=[32]\vone{v_1 = \begin{bmatrix} 3 \\ 2 \end{bmatrix}} (which scales to [6040]\vone{\begin{bmatrix} 60 \\ 40 \end{bmatrix}} for 100 total customers) and λ2=0.5\vtwo{\lambda_2 = 0.5} with v2=[1−1]\vtwo{v_2 = \begin{bmatrix} 1 \\ -1 \end{bmatrix}}:
A[6040]=1[6040],A[1−1]=0.5[1−1]\displaystyle \begin{aligned} A\vone{\begin{bmatrix} 60 \\ 40 \end{bmatrix}} &= \vone{1}\vone{\begin{bmatrix} 60 \\ 40 \end{bmatrix}}, \\ A\vtwo{\begin{bmatrix} 1 \\ -1 \end{bmatrix}} &= \vtwo{0.5}\vtwo{\begin{bmatrix} 1 \\ -1 \end{bmatrix}} \end{aligned}
Split the starting vector into the steady state and the initial imbalanceStarting with [1000]\state{\begin{bmatrix} 100 \\ 0 \end{bmatrix}} 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:
[1000]=[6040]⏟steady state+40[1−1]⏟initial imbalance\displaystyle \state{\begin{bmatrix} 100 \\ 0 \end{bmatrix}} = \vone{\underbrace{\begin{bmatrix} 60 \\ 40 \end{bmatrix}}_{\text{steady state}}} + \vtwo{\underbrace{40\begin{bmatrix} 1 \\ -1 \end{bmatrix}}_{\text{initial imbalance}}}
Multiply by AnA^n using the eigenvaluesAfter nn months, the [6040]\vone{\begin{bmatrix} 60 \\ 40 \end{bmatrix}} steady state is multiplied by 1n=1\vone{1^n = 1}, while the imbalance is multiplied by (0.5)n\vtwo{(0.5)^n}:
An[1000]=[6040]+(0.5)n⋅40[1−1]\displaystyle A^n \state{\begin{bmatrix} 100 \\ 0 \end{bmatrix}} = \vone{\begin{bmatrix} 60 \\ 40 \end{bmatrix}} + \vtwo{(0.5)^n \cdot 40\begin{bmatrix} 1 \\ -1 \end{bmatrix}}
Let n→∞n \to \infty to find the steady stateSince (0.5)n→0\vtwo{(0.5)^n} \to 0, the imbalance shrinks to 00:
lim⁡n→∞An[1000]=[6040]\displaystyle \lim_{n \to \infty} A^n \state{\begin{bmatrix} 100 \\ 0 \end{bmatrix}} = \vone{\begin{bmatrix} 60 \\ 40 \end{bmatrix}}

So the customer counts go from [8020]\state{\begin{bmatrix} 80 \\ 20 \end{bmatrix}} after 1 month to [7030]\state{\begin{bmatrix} 70 \\ 30 \end{bmatrix}} 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]\vone{\begin{bmatrix} 60 \\ 40 \end{bmatrix}} steady-state part stays fixed while the c2[1−1]\vtwo{c_2\begin{bmatrix} 1 \\ -1 \end{bmatrix}} imbalance is cut in half each month, so every starting split settles to [6040]\vone{\begin{bmatrix} 60 \\ 40 \end{bmatrix}}.

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 AnA^n Using Diagonalization

Up to now, we have found Anv0A^n \state{v_0} for one specific starting vector v0\state{v_0}. When no starting vector is given, or when we want a formula for every entry of the matrix AnA^n itself, we compute the matrix power using diagonalization.

Writing A=PDP−1A = P D P^{-1} with the eigenvectors in PP and the eigenvalues in DD makes AnA^n easy to compute, because every P−1PP^{-1}P pair in the middle cancels out:

An\displaystyle A^n =(PDP−1)(P⏟P−1P=IDP−1)⋯(PDP−1)\displaystyle = (P D \underbrace{P^{-1})(P}_{P^{-1}P = I} D P^{-1}) \cdots (P D P^{-1}) =PDnP−1\displaystyle = P D^n P^{-1}
Formula for Aⁿ Using Diagonalization
A=[0.80.30.20.7]An=[????]\displaystyle \begin{aligned} A &= \begin{bmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{bmatrix} \\ A^n &= \begin{bmatrix} ? & ? \\ ? & ? \end{bmatrix} \end{aligned}
Text solution
Set up PP, DnD^n, and P−1P^{-1} from the eigenvectors and eigenvaluesUsing v1=[32]\vone{v_1 = \begin{bmatrix} 3 \\ 2 \end{bmatrix}} with λ1=1\vone{\lambda_1 = 1} and v2=[1−1]\vtwo{v_2 = \begin{bmatrix} 1 \\ -1 \end{bmatrix}} with λ2=0.5\vtwo{\lambda_2 = 0.5} for A=[0.80.30.20.7]A = \begin{bmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{bmatrix}, build PP, raise the diagonal of DD to the nnth power, and invert PP:
P=[312−1],Dn=[100(0.5)n],P−1=1−5[−1−1−23]=[0.20.20.4−0.6]\displaystyle \begin{aligned} P &= \begin{bmatrix} \vone{3} & \vtwo{1} \\ \vone{2} & \vtwo{-1} \end{bmatrix}, \\ D^n &= \begin{bmatrix} \vone{1} & 0 \\ 0 & \vtwo{(0.5)^n} \end{bmatrix}, \\ P^{-1} &= \frac{1}{-5}\begin{bmatrix} -1 & -1 \\ -2 & 3 \end{bmatrix} \\ &= \begin{bmatrix} 0.2 & 0.2 \\ 0.4 & -0.6 \end{bmatrix} \end{aligned}
Multiply PDnP D^n firstMultiplying PP by the diagonal matrix DnD^n scales the first column of PP by 1\vone{1} and the second column by (0.5)n\vtwo{(0.5)^n}:
PDn=[312−1][100(0.5)n]=[3(0.5)n2−(0.5)n]\displaystyle P D^n = \begin{bmatrix} \vone{3} & \vtwo{1} \\ \vone{2} & \vtwo{-1} \end{bmatrix} \begin{bmatrix} \vone{1} & 0 \\ 0 & \vtwo{(0.5)^n} \end{bmatrix} = \begin{bmatrix} \vone{3} & \vtwo{(0.5)^n} \\ \vone{2} & \vtwo{-(0.5)^n} \end{bmatrix}
Multiply by P−1P^{-1} on the right to get AnA^nMultiplying the two 2×22 \times 2 matrices gives a formula for each entry of AnA^n in terms of nn:
An=[3(0.5)n2−(0.5)n][0.20.20.4−0.6]=[0.6+0.4(0.5)n0.6−0.6(0.5)n0.4−0.4(0.5)n0.4+0.6(0.5)n]\displaystyle \begin{aligned} & A^n \\ &\quad = \begin{bmatrix} \vone{3} & \vtwo{(0.5)^n} \\ \vone{2} & \vtwo{-(0.5)^n} \end{bmatrix} \begin{bmatrix} 0.2 & 0.2 \\ 0.4 & -0.6 \end{bmatrix} \\ &\quad = \begin{bmatrix} \begin{gathered}\vone{0.6} \\ + \vtwo{0.4(0.5)^n}\end{gathered} & \begin{gathered}\vone{0.6} \\ - \vtwo{0.6(0.5)^n}\end{gathered} \\[8pt] \begin{gathered}\vone{0.4} \\ - \vtwo{0.4(0.5)^n}\end{gathered} & \begin{gathered}\vone{0.4} \\ + \vtwo{0.6(0.5)^n}\end{gathered} \end{bmatrix} \end{aligned}
Take the limit as n→∞n \to \inftyLetting (0.5)n→0\vtwo{(0.5)^n} \to 0 in all four entries gives the long-run matrix A∞A^\infty:
A∞=[0.60.60.40.4]\displaystyle A^\infty = \begin{bmatrix} \vone{0.6} & \vone{0.6} \\ \vone{0.4} & \vone{0.4} \end{bmatrix}

So whatever starting vector you multiply by AnA^n, 60%\vone{60\%} of the total ends up in the top entry and 40%\vone{40\%} ends up in the bottom entry in the long run.

Key concepts

Whenever a square matrix AA has as many independent eigenvectors as it has columns (so it is diagonalizable), you can jump straight to step nn without multiplying AA repeatedly.

First check whether your starting vector v0\state{v_0} is already a multiple of a single eigenvector v1\vone{v_1}. If it is, don't split it into pieces or invert a matrix; just scale it directly by λ1n\vone{\lambda_1^n}, such as An[6040]=1n[6040]=[6040]A^n \vone{\begin{bmatrix} 60 \\ 40 \end{bmatrix}} = \vone{1^n} \vone{\begin{bmatrix} 60 \\ 40 \end{bmatrix}} = \vone{\begin{bmatrix} 60 \\ 40 \end{bmatrix}}.

Power times a starting vector (Anv0A^n \state{v_0})

When given a specific starting vector v0\state{v_0}, split it into eigenvectors and scale each piece by λn\lambda^n:

v0=c1v1+c2v2  ⟹  Anv0=c1λ1nv1+c2λ2nv2\displaystyle \begin{aligned} \state{v_0} &= \vone{c_1 v_1} + \vtwo{c_2 v_2} \\ \implies A^n \state{v_0} &= \vone{c_1 \lambda_1^n v_1} + \vtwo{c_2 \lambda_2^n v_2} \end{aligned}

For example, [1000]=[6040]+40[1−1]\state{\begin{bmatrix} 100 \\ 0 \end{bmatrix}} = \vone{\begin{bmatrix} 60 \\ 40 \end{bmatrix}} + \vtwo{40\begin{bmatrix} 1 \\ -1 \end{bmatrix}} gives An[1000]=[6040]+(0.5)n⋅40[1−1]A^n \state{\begin{bmatrix} 100 \\ 0 \end{bmatrix}} = \vone{\begin{bmatrix} 60 \\ 40 \end{bmatrix}} + \vtwo{(0.5)^n \cdot 40\begin{bmatrix} 1 \\ -1 \end{bmatrix}} without needing P−1P^{-1}.

Formula for the whole matrix (AnA^n)

When you need the entries of AnA^n itself in terms of nn, diagonalize and raise only the diagonal entries of DD to the nnth power:

An=PDnP−1=[v1v2][λ1n00λ2n][v1v2]−1\displaystyle A^n = P D^n P^{-1} = \begin{bmatrix} \vone{v_1} & \vtwo{v_2} \end{bmatrix} \begin{bmatrix} \vone{\lambda_1^n} & 0 \\ 0 & \vtwo{\lambda_2^n} \end{bmatrix} \begin{bmatrix} \vone{v_1} & \vtwo{v_2} \end{bmatrix}^{-1}
Long-run behavior (n→∞n \to \infty)

Look at the sizes of the eigenvalues in Anv0=c1λ1nv1+c2λ2nv2A^n \state{v_0} = \vone{c_1 \lambda_1^n v_1} + \vtwo{c_2 \lambda_2^n v_2}:

  • ∣λ∣<1|\lambda| < 1 shrinks to 00: Terms like (0.5)n\vtwo{(0.5)^n} and (−0.618)n\vtwo{(-0.618)^n} go to 00.
  • λ=1\vone{\lambda = 1} stays steady: If λ1=1\vone{\lambda_1 = 1} and every other eigenvalue has ∣λ∣<1|\lambda| < 1, the system settles to the c1v1\vone{c_1 v_1} steady-state vector, such as [6040]\vone{\begin{bmatrix} 60 \\ 40 \end{bmatrix}}.
  • Largest ∣λ∣>1|\lambda| > 1 takes over: When c1≠0\vone{c_1} \neq 0, Anv0≈c1λ1nv1A^n \state{v_0} \approx \vone{c_1 \lambda_1^n v_1} for large nn, so the ratio of the entries of Anv0A^n \state{v_0} approaches the entry ratio of the eigenvector v1\vone{v_1} with the largest eigenvalue (such as Fn+1Fn→φ1=φ\state{\frac{F_{n+1}}{F_n}} \to \vone{\frac{\varphi}{1}} = \vone{\varphi}).
6

Practice

1

A matrix AA has eigenvalues λ1=3\vone{\lambda_1 = 3} with eigenvector v1=[12]\vone{v_1 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}} and λ2=−1\vtwo{\lambda_2 = -1} with eigenvector v2=[1−1]\vtwo{v_2 = \begin{bmatrix} 1 \\ -1 \end{bmatrix}}. By writing the starting vector as a combination of v1\vone{v_1} and v2\vtwo{v_2}, find a formula for An[45]A^n \state{\begin{bmatrix} 4 \\ 5 \end{bmatrix}} and evaluate A10[45]A^{10} \state{\begin{bmatrix} 4 \\ 5 \end{bmatrix}}.

Write [45]=c1[12]+c2[1−1]\state{\begin{bmatrix} 4 \\ 5 \end{bmatrix}} = \vone{c_1 \begin{bmatrix} 1 \\ 2 \end{bmatrix}} + \vtwo{c_2 \begin{bmatrix} 1 \\ -1 \end{bmatrix}}: what happens to c2\vtwo{c_2} when you add the top and bottom equations together?

Adding the two rows of [45]=c1[12]+c2[1−1]\state{\begin{bmatrix} 4 \\ 5 \end{bmatrix}} = \vone{c_1 \begin{bmatrix} 1 \\ 2 \end{bmatrix}} + \vtwo{c_2 \begin{bmatrix} 1 \\ -1 \end{bmatrix}} gives 9=3c19 = 3\vone{c_1}, so c1=3\vone{c_1 = 3} and c2=1\vtwo{c_2 = 1}:
[45]=3[12]+1[1−1]\displaystyle \state{\begin{bmatrix} 4 \\ 5 \end{bmatrix}} = \vone{3\begin{bmatrix} 1 \\ 2 \end{bmatrix}} + \vtwo{1\begin{bmatrix} 1 \\ -1 \end{bmatrix}}
Multiplying by AnA^n scales the first piece by 3n\vone{3^n} and the second by (−1)n\vtwo{(-1)^n}:
An[45]=3(3n)[12]+(−1)n[1−1]=[3n+1+(−1)n2⋅3n+1−(−1)n]\displaystyle \begin{aligned} A^n \state{\begin{bmatrix} 4 \\ 5 \end{bmatrix}} &= \vone{3(3^n)\begin{bmatrix} 1 \\ 2 \end{bmatrix}} + \vtwo{(-1)^n\begin{bmatrix} 1 \\ -1 \end{bmatrix}} \\ &= \begin{bmatrix} \vone{3^{n+1}} + \vtwo{(-1)^n} \\ \vone{2 \cdot 3^{n+1}} - \vtwo{(-1)^n} \end{bmatrix} \end{aligned}
For n=10n = 10, watch out for two common slips: don't drop the factor of c1=3\vone{c_1 = 3} to get 3103^{10} instead of 311\vone{3^{11}} (which gives [59,050118,097]\begin{bmatrix} 59{,}050 \\ 118{,}097 \end{bmatrix}), and remember that (−1)10=+1\vtwo{(-1)^{10}} = +1, not −1-1 (which gives [177,146354,295]\begin{bmatrix} 177{,}146 \\ 354{,}295 \end{bmatrix}):
A10[45]=[311+12⋅311−1]=[177,148354,293]\displaystyle A^{10}\state{\begin{bmatrix} 4 \\ 5 \end{bmatrix}} = \begin{bmatrix} \vone{3^{11}} + \vtwo{1} \\ \vone{2 \cdot 3^{11}} - \vtwo{1} \end{bmatrix} = \begin{bmatrix} 177{,}148 \\ 354{,}293 \end{bmatrix}
2

Two bike-share stations, Uptown and Downtown, trade bikes each day according to A=[0.70.20.30.8]A = \begin{bmatrix} 0.7 & 0.2 \\ 0.3 & 0.8 \end{bmatrix}, which has eigenvalues λ1=1\vone{\lambda_1 = 1} with eigenvector v1=[23]\vone{v_1 = \begin{bmatrix} 2 \\ 3 \end{bmatrix}} and λ2=0.5\vtwo{\lambda_2 = 0.5} with eigenvector v2=[1−1]\vtwo{v_2 = \begin{bmatrix} 1 \\ -1 \end{bmatrix}}. Starting with [8020]\state{\begin{bmatrix} 80 \\ 20 \end{bmatrix}} 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→∞n \to \infty.

The two stations have 80+20=10080 + 20 = 100 bikes in total, and the entries of v1=[23]\vone{v_1 = \begin{bmatrix} 2 \\ 3 \end{bmatrix}} add up to 55: what multiple of v1\vone{v_1} gives the 100-bike steady state?

Scaling v1=[23]\vone{v_1 = \begin{bmatrix} 2 \\ 3 \end{bmatrix}} by 20\vone{20} so its entries add up to 100 gives the steady-state vector [4060]\vone{\begin{bmatrix} 40 \\ 60 \end{bmatrix}}. Be careful not to flip the steady state to [6040]\begin{bmatrix} 60 \\ 40 \end{bmatrix} just because Uptown starts with more bikes (which leads to the wrong 3-day split [62.537.5]\begin{bmatrix} 62.5 \\ 37.5 \end{bmatrix} and long-run split [6040]\begin{bmatrix} 60 \\ 40 \end{bmatrix}):
[8020]=[4060]+40[1−1]  ⟹  An[8020]=[4060]+(0.5)n⋅40[1−1]\displaystyle \begin{aligned} \state{\begin{bmatrix} 80 \\ 20 \end{bmatrix}} &= \vone{\begin{bmatrix} 40 \\ 60 \end{bmatrix}} + \vtwo{40\begin{bmatrix} 1 \\ -1 \end{bmatrix}} \\ \implies A^n\state{\begin{bmatrix} 80 \\ 20 \end{bmatrix}} &= \vone{\begin{bmatrix} 40 \\ 60 \end{bmatrix}} \\ &\quad + \vtwo{(0.5)^n \cdot 40\begin{bmatrix} 1 \\ -1 \end{bmatrix}} \end{aligned}
After n=3n = 3 days, (0.5)3⋅40=5\vtwo{(0.5)^3 \cdot 40 = 5}:
A3[8020]=[40+560−5]=[4555]\displaystyle A^3\state{\begin{bmatrix} 80 \\ 20 \end{bmatrix}} = \begin{bmatrix} \vone{40} + \vtwo{5} \\ \vone{60} - \vtwo{5} \end{bmatrix} = \begin{bmatrix} 45 \\ 55 \end{bmatrix}
As n→∞n \to \infty, (0.5)n→0\vtwo{(0.5)^n} \to 0 and the distribution settles at [4060]\vone{\begin{bmatrix} 40 \\ 60 \end{bmatrix}}.
3

Diagonalize A=[1221]A = \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix} and use An=PDnP−1A^n = P D^n P^{-1} to find a formula for each entry of the matrix AnA^n in terms of nn.

After finding λ1,λ2\vone{\lambda_1}, \vtwo{\lambda_2} and building P=[v1v2]P = \begin{bmatrix} \vone{v_1} & \vtwo{v_2} \end{bmatrix}, multiply PDnP D^n first before multiplying by P−1P^{-1} on the right.

Solving det⁡(A−λI)=(1−λ)2−4=0\det(A - \lambda I) = (1 - \lambda)^2 - 4 = 0 gives λ1=3\vone{\lambda_1 = 3} with v1=[11]\vone{v_1 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}} and λ2=−1\vtwo{\lambda_2 = -1} with v2=[1−1]\vtwo{v_2 = \begin{bmatrix} 1 \\ -1 \end{bmatrix}}. When inverting P=[111−1]P = \begin{bmatrix} \vone{1} & \vtwo{1} \\ \vone{1} & \vtwo{-1} \end{bmatrix}, watch out for the negative determinant det⁡(P)=−1−1=−2\det(P) = -1 - 1 = -2; dividing by 22 instead of −2-2 gives −12[3n+(−1)n3n−(−1)n3n−(−1)n3n+(−1)n]-\frac{1}{2}\begin{bmatrix} 3^n + (-1)^n & 3^n - (-1)^n \\ 3^n - (-1)^n & 3^n + (-1)^n \end{bmatrix} with every sign flipped:
P=[111−1],Dn=[3n00(−1)n],P−1=1−2[−1−1−11]=12[111−1]\displaystyle \begin{aligned} P &= \begin{bmatrix} \vone{1} & \vtwo{1} \\ \vone{1} & \vtwo{-1} \end{bmatrix}, \\ D^n &= \begin{bmatrix} \vone{3^n} & 0 \\ 0 & \vtwo{(-1)^n} \end{bmatrix}, \\ P^{-1} &= \frac{1}{-2}\begin{bmatrix} -1 & -1 \\ -1 & 1 \end{bmatrix} = \frac{1}{2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \end{aligned}
Multiplying PDnP−1P D^n P^{-1} gives:
An=[3n(−1)n3n−(−1)n]⋅12[111−1]=12[3n+(−1)n3n−(−1)n3n−(−1)n3n+(−1)n]\displaystyle \begin{aligned} A^n &= \begin{bmatrix} \vone{3^n} & \vtwo{(-1)^n} \\ \vone{3^n} & \vtwo{-(-1)^n} \end{bmatrix} \cdot \frac{1}{2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \\ &= \frac{1}{2}\begin{bmatrix} \vone{3^n} + \vtwo{(-1)^n} & \vone{3^n} - \vtwo{(-1)^n} \\ \vone{3^n} - \vtwo{(-1)^n} & \vone{3^n} + \vtwo{(-1)^n} \end{bmatrix} \end{aligned}
4

A sequence begins with a0=0,a1=1\state{a_0 = 0}, \state{a_1 = 1} and follows the rule an+1=an+2an−1\state{a_{n+1}} = \state{a_n} + 2\state{a_{n-1}}. (a) Write the 2×22 \times 2 matrix AA such that [an+1an]=An[10]\state{\begin{bmatrix} a_{n+1} \\ a_n \end{bmatrix}} = A^n \state{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}. (b) Use an eigenvector of the form [λ1]\state{\begin{bmatrix} \lambda \\ 1 \end{bmatrix}} to find the eigenvalues and eigenvectors of AA. (c) Find the direct formula for an\state{a_n} and the value that the ratio an+1an\state{\tfrac{a_{n+1}}{a_n}} approaches as n→∞n \to \infty.

(a) The top row of AA builds an+1\state{a_{n+1}} from an\state{a_n} and an−1\state{a_{n-1}}; what does the bottom row do to turn [anan−1]\state{\begin{bmatrix} a_n \\ a_{n-1} \end{bmatrix}} into [an+1an]\state{\begin{bmatrix} a_{n+1} \\ a_n \end{bmatrix}}? (c) Use the bottom entries of [21]\vone{\begin{bmatrix} 2 \\ 1 \end{bmatrix}} and [−11]\vtwo{\begin{bmatrix} -1 \\ 1 \end{bmatrix}} to cancel to 00 when building [10]\state{\begin{bmatrix} 1 \\ 0 \end{bmatrix}}.

(a) A=[1210]A = \begin{bmatrix} 1 & 2 \\ 1 & 0 \end{bmatrix}.
(b) Multiplying [λ1]\state{\begin{bmatrix} \lambda \\ 1 \end{bmatrix}} by AA gives A[λ1]=[λ+2λ]=[λ2λ]A\state{\begin{bmatrix} \lambda \\ 1 \end{bmatrix}} = \state{\begin{bmatrix} \lambda + 2 \\ \lambda \end{bmatrix}} = \state{\begin{bmatrix} \lambda^2 \\ \lambda \end{bmatrix}}, so λ2−λ−2=0\lambda^2 - \lambda - 2 = 0, which gives λ1=2\vone{\lambda_1 = 2} with v1=[21]\vone{v_1 = \begin{bmatrix} 2 \\ 1 \end{bmatrix}} and λ2=−1\vtwo{\lambda_2 = -1} with v2=[−11]\vtwo{v_2 = \begin{bmatrix} -1 \\ 1 \end{bmatrix}}.
(c) Subtracting the two eigenvectors gives [21]−[−11]=[30]\vone{\begin{bmatrix} 2 \\ 1 \end{bmatrix}} - \vtwo{\begin{bmatrix} -1 \\ 1 \end{bmatrix}} = \begin{bmatrix} 3 \\ 0 \end{bmatrix}, so dividing by 33 and multiplying by AnA^n gives:
[an+1an]=An[10]=13(2n)[21]−13(−1)n[−11]\displaystyle \begin{aligned} \state{\begin{bmatrix} a_{n+1} \\ a_n \end{bmatrix}} &= A^n\state{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} \\ &= \vone{\frac{1}{3}(2^n)\begin{bmatrix} 2 \\ 1 \end{bmatrix}} - \vtwo{\frac{1}{3}(-1)^n\begin{bmatrix} -1 \\ 1 \end{bmatrix}} \end{aligned}
Make sure to read the bottom entry for an\state{a_n} rather than the top entry (reading the top entry gives an+1=2n+1+(−1)n3a_{n+1} = \frac{2^{n+1} + (-1)^n}{3}):
an\displaystyle \state{a_n} =2n−(−1)n3\displaystyle = \frac{\vone{2^n} - \vtwo{(-1)^n}}{3}
Since 2n\vone{2^n} grows while (−1)n\vtwo{(-1)^n} stays at size 11, the ratio an+1an\state{\tfrac{a_{n+1}}{a_n}} approaches 22.
5

A matrix AA has eigenvalues λ1=2\vone{\lambda_1 = 2} with eigenvector v1=[31]\vone{v_1 = \begin{bmatrix} 3 \\ 1 \end{bmatrix}} and λ2=0.4\vtwo{\lambda_2 = 0.4} with eigenvector v2=[12]\vtwo{v_2 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}}. (a) If v0=[74]\state{v_0 = \begin{bmatrix} 7 \\ 4 \end{bmatrix}}, what does the ratio of the top entry to the bottom entry of Anv0A^n \state{v_0} approach as n→∞n \to \infty? (b) Find all nonzero starting vectors v0=[xy]\state{v_0 = \begin{bmatrix} x \\ y \end{bmatrix}} for which Anv0→[00]A^n \state{v_0} \to \begin{bmatrix} 0 \\ 0 \end{bmatrix} as n→∞n \to \infty.

Write Anv0=c1(2n)[31]+c2(0.4)n[12]A^n \state{v_0} = \vone{c_1(2^n)\begin{bmatrix} 3 \\ 1 \end{bmatrix}} + \vtwo{c_2(0.4)^n\begin{bmatrix} 1 \\ 2 \end{bmatrix}}: which eigenvector sets the long-run ratio of the entries when c1≠0\vone{c_1} \neq 0, and what must c1\vone{c_1} be if the vector shrinks to [00]\begin{bmatrix} 0 \\ 0 \end{bmatrix}?

(a) Since [74]=2[31]+1[12]\state{\begin{bmatrix} 7 \\ 4 \end{bmatrix}} = \vone{2\begin{bmatrix} 3 \\ 1 \end{bmatrix}} + \vtwo{1\begin{bmatrix} 1 \\ 2 \end{bmatrix}}, we have An[74]=2(2n)[31]+(0.4)n[12]A^n\state{\begin{bmatrix} 7 \\ 4 \end{bmatrix}} = \vone{2(2^n)\begin{bmatrix} 3 \\ 1 \end{bmatrix}} + \vtwo{(0.4)^n\begin{bmatrix} 1 \\ 2 \end{bmatrix}}. As n→∞n \to \infty, (0.4)n→0\vtwo{(0.4)^n} \to 0 and Anv0≈2(2n)[31]A^n \state{v_0} \approx \vone{2(2^n)\begin{bmatrix} 3 \\ 1 \end{bmatrix}}. Don't confuse the largest eigenvalue λ1=2\vone{\lambda_1 = 2} with the entry ratio of its eigenvector v1=[31]\vone{v_1 = \begin{bmatrix} 3 \\ 1 \end{bmatrix}} (which gives the wrong answer 22): the top-to-bottom entry ratio approaches 31=3\vone{\frac{3}{1}} = 3.
(b) In Anv0=c1(2n)[31]+c2(0.4)n[12]A^n \state{v_0} = \vone{c_1(2^n)\begin{bmatrix} 3 \\ 1 \end{bmatrix}} + \vtwo{c_2(0.4)^n\begin{bmatrix} 1 \\ 2 \end{bmatrix}}, don't assume that λ1=2>1\vone{\lambda_1 = 2} > 1 makes every nonzero starting vector grow without bound: the vector shrinks to [00]\begin{bmatrix} 0 \\ 0 \end{bmatrix} exactly when c1=0\vone{c_1 = 0}, which means v0\state{v_0} is any nonzero multiple of v2\vtwo{v_2}: [xy]=c[12]\state{\begin{bmatrix} x \\ y \end{bmatrix}} = \vtwo{c\begin{bmatrix} 1 \\ 2 \end{bmatrix}} for c≠0\vtwo{c} \neq 0.