High School
SAT
ACT
University
MCAT
LSAT
DAT
Wize University Linear Algebra Textbook > Eigenvalues and Eigenvectors (Spectral Theory)

Linear Dynamical Systems

Markov Chains (Random Walks)Previous Section
Basics of Differential EquationsNext Section
Popular Courses
Find My Course
0:00 / 0:00

Linear Dynamical Systems and Recurrence Relations

A linear dynamical system in two variables is given by:
{xn+1=axn+bynyn+1=cxn+dyn\left\{ \begin{array}{l} x_{n+1}=\colorOne a x_n+ \colorOne b y_n\\ y_{n+1}=\colorOne cx_n+ \colorOne d y_n \end{array} \right.
Letting v⃗n=[xnyn]\vec v_n=\begin{bmatrix} x_n\\ y_n \end{bmatrix} and A=[abcd]A=\begin{bmatrix} \colorOne a& \colorOne b\\ \colorOne c& \colorOne d \end{bmatrix}, the system can be expressed in matrix form as:
v⃗n+1=Av⃗n\boxed{\quad \vec{v}_{n+1}=A\vec{v}_n \quad}
Notice the pattern as we find each successive state vector:
v⃗1=Av⃗0v⃗2=Av⃗1=A(Av⃗0)=A2v⃗0v⃗3=Av⃗2=A(A2v⃗0)=A3v⃗0⋮v⃗n=Av⃗n−1=A(An−1v⃗0)=Anv⃗0\begin{array}{llllllll} \vec v_1 &=& A\vec v_0\\[0.5em] \vec v_2 &=& A\vec v_1 &=& A(A\vec v_0) &=& A^2 \vec v_0\\[0.5em] \vec v_3 &=& A\vec v_2 &=& A(A^2\vec v_0) &=& A^3 \vec v_0\\[0.5em] \vdots\\[0.5em] \colorTwo{\bm{\vec v_n }}&=& A\vec v_{n-1} &=& A(A^{n-1}\vec v_0) &=& \colorTwo{\bm{A^n \vec v_0}}\\[0.5em] \end{array}
Therefore, we can always find v⃗n\vec v_n by calculating:
v⃗n=Anv⃗0or:   v⃗n=PDnP−1v⃗0\boxed{\quad \begin{aligned} \vec v_n &= \colorOne{A^n}\vec v_0\\[0.5em] \text{or:}\ \ \ \vec v_n &= \colorOne{PD^nP^{-1}}\vec v_0 \end{aligned} \quad}

PAGE BREAK
Steps
Here is how we will find a solution v⃗n\vec v_nto the dynamical system v⃗n+1=Av⃗n\vec v_{n+1}=A\vec v_n given initial conditions x0x_0 and y0y_0:
  1. Diagonalize AA by finding PP and DD such that D=P−1APD = P^{-1}AP.
  2. Use the matrix power formula: An=PDnP−1A^n=PD^nP^{−1}.
  3. Simplify the expression v⃗n=Anv⃗0\vec v_n=A^n \vec v_0 , where v⃗0=[x0y0]\vec v_0= \begin{bmatrix} x_0 \\ y_0 \end{bmatrix}.
PAGE BREAK

Recurrence Relations

A recurrence relation defines elements of a sequence based on previous elements:
xn+2=cxn+dxn+1,x0=a,  x1=b\colorTwo{x_{n+2} = c x_n + d x_{n+1}}, \quad \colorFive{x_0=a,\ \ x_1=b}
We can treat recurrence relations of this form as linear dynamical systems by setting yn=xn+1\boxed{\colorOne{y_n=x_{n+1}}}.
Note: The initial condition can be written as:
v⃗0=[x0y0]=[x0x1]=[ab]\colorFive{\vec v_0 } = \begin{bmatrix} x_{0}\\ \colorOne{y_{0}}\\ \end{bmatrix} = \begin{bmatrix} x_{0}\\ \colorOne{x_{1}}\\ \end{bmatrix} = \begin{bmatrix} \colorFive a\\ \colorFive b\\ \end{bmatrix}
Wize Tip
To set up a dynamical system, start by writing {xn+1=…yn+1=…\left\{ \begin{array}{l} x_{n+1}= \dots\\ y_{n+1}= \dots \end{array} \right. and go from there!

{xn+1=ynyn+1=xn+2  ⟹  {xn+1=0xn+1ynyn+1=cxn+dxn+1  ⟹  {xn+1=0xn+1ynyn+1=cxn+dyn  ⟹  [xn+1yn+1]⏟v⃗n+1=[01cd]⏟A[xnyn]⏟v⃗n\begin{aligned} & \left\{ \begin{array}{l} \colorOne{x_{n+1} = y_n}\\ y_{n+1}= \colorTwo{x_{n+2}} \end{array} \right.\\[2em] \quad \implies \quad &\left\{ \begin{array}{l} x_{n+1} = 0x_n + 1y_n\\ y_{n+1} = \colorTwo{c x_n + d x_{n+1}} \end{array} \right.\\[2em] \quad \implies \quad &\left\{ \begin{array}{l} x_{n+1} = 0x_n + 1y_n\\ y_{n+1} = \colorTwo{c x_n + d}\colorOne{y_n} \end{array} \right.\\[2em] \quad \implies \quad &\underbrace{ \begin{bmatrix} x_{n+1}\\ y_{n+1}\\ \end{bmatrix}}_{\normalsize \vec v_{n+1}} = \underbrace{ \begin{bmatrix} 0 & 1\\ c & d \end{bmatrix}}_{\normalsize A} \underbrace{ \begin{bmatrix} x_{n}\\ y_{n}\\ \end{bmatrix}}_{\normalsize \vec v_{n}} \end{aligned}
PAGE BREAK
Example
Rewrite the following recurrence relation as a linear dynamical system:
xn+2=−2xn+1+xn,x0=2,  x1=3{x_{n+2} = -2x_{n+1} + x_n}, \quad x_0 = 2, \ \ x_1=3
Let yn=xn+1y_n = x_{n+1}. Then {xn+1=yn=0xn+1yn=0xn+1ynyn+1=xn+2=1xn−2xn+1=1xn−2yn  ⟹  A=[011−2]\left\{ \begin{array}{lcrclcl} x_{n+1} &=& y_n &=& 0x_n + 1 y_n &=& 0x_n + 1 y_n\\[0.5em] y_{n+1} &=& x_{n+2} &=& 1 x_n -2 x_{n+1} &=& 1 x_n -2 y_n \end{array} \right. \quad\implies\quad A= \begin{bmatrix} 0 & 1\\ 1 & -2 \end{bmatrix}.
The initial condition is v⃗0=[x0y0]=[x0x1]=[23]\vec v_0 = \begin{bmatrix} x_{0}\\ y_{0}\\ \end{bmatrix} = \begin{bmatrix} x_{0}\\ x_1\\ \end{bmatrix} = \begin{bmatrix} 2\\ 3\\ \end{bmatrix}.
Putting it all together, we obtain the matrix equation v⃗n=Anv⃗0\vec v_{n} = A^n \vec v_0.
Now we can solve this linear dynamical system using the same steps as before!
0:00 / 0:00

Example: Linear Dynamical Systems

Consider the linear dynamical system given by
xn+1=2xn+ynyn+1=xn+2yn\begin{array}{l}x_{n+1}=2x_n+y_n\\y_{n+1}=x_n+2y_n\end{array}
with initial conditions x0=1x_0 = 1, y0=2y_0 = 2. Find solutions to this system for general nn and for n=3n = 3.
The matrix representing this system is A=[2112]A=\begin{bmatrix}2 & 1\\1 & 2\end{bmatrix}.
Writing v⃗n=[xnyn]\vec v_n = \begin{bmatrix} x_n\\ y_n\\ \end{bmatrix} , we have the system v⃗n+1=Av⃗n\vec v_{n+1} = A \vec v_n with initial condition v⃗0=[12]\vec v_0 = \begin{bmatrix} 1\\ 2\\ \end{bmatrix} .
In order to find the eigenvalues of AA, we solve the following equation:
0=det(λI−A)=det[λ−2−1−1λ−2]=(λ−2)2−(−1)2=λ2−4λ+4−1=λ2−4λ+3=(λ−1)(λ−3)\begin{aligned} 0={\rm det}(\lambda I-A)={\rm det}\begin{bmatrix}\lambda-2&-1\\-1&\lambda-2\end{bmatrix} &=(\lambda-2)^2-(-1)^ 2\\[0.5em] &=\lambda^2-4\lambda+4-1\\[0.5em] &=\lambda^2-4\lambda+3\\[0.5em] &=(\lambda-1)(\lambda-3) \end{aligned}
Then the eigenvalues are λ1=1\lambda_1 = 1 and λ2=3\lambda_2=3, giving D=[λ100λ2]=[1003]D=\begin{bmatrix} \colorOne{\lambda_1} & 0\\0 & \colorTwo{\lambda_2}\end{bmatrix} = \begin{bmatrix} \colorOne1 & 0\\ 0 & \colorTwo 3 \end{bmatrix}.
Now let's find the corresponding eigenvectors.
For λ1=1\colorOne{\lambda_1 = 1}, we need to solve the homogeneous equation (I−A)X=0(I - A)X=0:
[−1−1−1−1]R2−R1→R2→[−1−100]\left[\begin{array}{rr} -1&-1\\ -1&-1 \end{array}\right] \underrightarrow{R_2-R_1\to R_2} \left[\begin{array}{rr} -1&-1\\ 0&0 \end{array}\right]
From here it is clear that the solution is any vector of the form [−tt]=t[−11]\begin{bmatrix}-t\\t\end{bmatrix}=t\begin{bmatrix}-1\\1\end{bmatrix}.
This gives the basic eigenvector for λ1=1\colorOne{\lambda_1 = 1} as x⃗1=[−11]\colorOne{ \vec x_1 = \begin{bmatrix} -1\\ 1 \end{bmatrix} }.
For λ2=3\colorTwo{\lambda_2 = 3}, we need to solve the homogeneous equation (3I−A)X=0(3I - A)X=0:
[1−1−11]R2+R1→R2→[1−100]\left[\begin{array}{rr} 1&-1\\ -1&1 \end{array}\right] \underrightarrow{R_2+R_1\to R_2} \left[\begin{array}{rr} 1&-1\\ 0&0 \end{array}\right]
From here it is clear that the solution is any vector of the form [tt]=t[11]\begin{bmatrix}t\\t\end{bmatrix}=t\begin{bmatrix}1\\1\end{bmatrix}.
This gives the basic eigenvector for λ2=3\colorTwo{\lambda_2 = 3} as x⃗2=[11]\colorTwo{\vec x_2 = \begin{bmatrix} 1\\ 1 \end{bmatrix}}.
Then the matrix PP is given by P=[x⃗1x⃗2]=[−1111]P=\begin{bmatrix} \colorOne{\vec x_1}& \colorTwo{\vec x_2} \end{bmatrix} = \begin{bmatrix} \colorOne{-1}&\colorTwo 1\\ \colorOne 1&\colorTwo 1 \end{bmatrix}.
Now we can compute P−1=−12[1−1−1−1]=12[−1111]P^{-1} =-\dfrac{1}{2}\begin{bmatrix}1&-1\\-1&-1\end{bmatrix} =\dfrac{1}{2}\begin{bmatrix}-1&1\\1&1\end{bmatrix}.
Recalling that the initial condition is v⃗0=[12]\vec v_0 = \begin{bmatrix} 1\\ 2 \end{bmatrix} , we can write the formula v⃗n=Anv⃗0\vec v_n = A^n \vec v_0:
v⃗n=PDnP−1v⃗0[xnyn]=[−1111][1003]n12[−1111][12]=[−1111][1003n]⏟12[−1111][12]=  [−13n13n]12[−1111][12]=12[1+3n−1+3n−1+3n1+3n][12]=12[−1+3⋅3n1+3⋅3n]=12[−1+3n+11+3n+1]\begin{array}{ccl} \vec v_n &=& PD^nP^{-1} \vec v_0 \\[0.5em] \begin{bmatrix}x_n\\y_n\end{bmatrix} &=& \begin{bmatrix}-1&1\\1&1\end{bmatrix} \begin{bmatrix}1 & 0\\0 & 3\end{bmatrix}^n \dfrac{1}{2} \begin{bmatrix}-1&1\\1&1\end{bmatrix} \begin{bmatrix}1\\2\end{bmatrix}\\[1.8em] &=& \underbrace{ \begin{bmatrix}-1&1\\1&1\end{bmatrix} \begin{bmatrix}1 & 0\\0 & 3^n\end{bmatrix}} \dfrac{1}{2}\begin{bmatrix}-1&1\\1&1\end{bmatrix} \begin{bmatrix}1\\2\end{bmatrix}\\[1.8em] &=& \quad\ \ \begin{bmatrix}-1&3^n\\1&3^n\end{bmatrix} \dfrac{1}{2}\begin{bmatrix}-1&1\\1&1\end{bmatrix} \begin{bmatrix}1\\2\end{bmatrix}\\[1.8em] &=& \dfrac{1}{2} \begin{bmatrix}1+3^n&-1+3^n\\-1+3^n&1+3^n\end{bmatrix} \begin{bmatrix}1\\2\end{bmatrix}\\[1.8em] &=& \dfrac{1}{2} \begin{bmatrix} -1+3\cdot3^{n}\\ 1+3\cdot3^{n} \end{bmatrix}\\[1.8em] &=& \boxed{ \dfrac{1}{2} \begin{bmatrix}-1+3^{n+1}\\1+3^{n+1}\end{bmatrix}} \end{array}
For n=4n = 4 specifically, we have the solution:
[x4y4]=12[−1+811+81]=[4041]\begin{bmatrix}x_4\\y_4\end{bmatrix} =\dfrac{1}{2} \begin{bmatrix} -1+81\\ 1+81 \end{bmatrix} = \boxed{ \begin{bmatrix} 40\\ 41 \end{bmatrix}}

Practice: Recurrence Relations

Suppose a sequence is defined rescursively as:
xn+2=4xn,x0=1,  x1=4x_{n+2} = 4x_n, \quad x_0 =1,\ \ x_1 =4
Compute x20x_{20} by converting the recurrence to a linear dynamical system.
Extra Practice
Linear Dynamical Systems
Consider the linear dynamical system defined by A=[1211],v⃗0=[11]A=\left[\begin{array}{rr}1&2\\1&1\end{array}\right],\vec v_0=\left[\begin{array}{r}1\\1\end{array}\right]
Give a general formula for v⃗n\vec v_n , as well as a simpler formula for v⃗n\vec v_n that is valid when n is large.
Linear Dynamical Systems
Example: Linear Dynamical Systems
Consider the linear dynamical system given by
xn+1=2xn+ynyn+1=xn+2yn\begin{array}{l}x_{n+1}=2x_n+y_n\\y_{n+1}=x_n+2y_n\end{array}
Linear Dynamical Systems
Practice: Recurrence Relations
Suppose a sequence is defined rescursively as:
xn+2=4xn,x0=1,  x1=4x_{n+2} = 4x_n, \quad x_0 =1,\ \ x_1 =4
19.4F_Final_Builder_Ch_12.7_Dynamical_Systems_$\tkcth{eg12}$_$\key{Final}$_Builder_$\tkcth{12.7.}\tkcf{12}$_
The following system of equations define a dynamic system between the variables x(t)x(t) and y(t)y(t):
x(t+1)=5x(t)+6y(t)y(t+1)=−2x(t)−2y(t) \begin{array}{ll} x(t+1) & = \quad 5x(t) + 6 y(t) \\[15pt] % y(t+1) & = \quad -2x(t) -2 y(t) \end{array}
If x⃗(0)=[10]\vx(0) = \colvec{1}{0}, find the general solution x⃗(t)\vx(t) for the state of the system at any time tt.
19.4F_Final_Builder_Ch_12.7_Dynamical_Systems_$\tkcth{eg4}$_$\key{Final}$_Builder_$\tkcth{12.7.}\tkcf{4}$_
As the previous activity illustrates, computing A‾t ξ⃗\A^t \, \vXi is relatively simple, when the vector is an eigenvector.
Once you've seen an example like this, it's not hard to see that, in general, if ξ⃗\vXi is an eigenvector of the matrix A‾\A, with eigenvalue λ\lambda, then:
A‾t ξ⃗  =  λt ξ⃗ \A^{\bct{t}} \, \vXi \; = \; \lambda^{\bct{t}} \, \vXi
19.4F_Final_Builder_Ch_12.7_Dynamical_Systems_$\tkcth{eg3}$_$\key{Final}$_Builder_$\tkcth{12.7.}\tkcf{3}$_
Although the recursive relationship x⃗(t+1)=A‾  x⃗(t)\vx(t+1) = \A \; \vx(t) is not complicated, computing the vector x⃗(t)\vx(t) at a general time tt isn't very practical, as it would require the computation of a general power on a matrix, i.e.:
x⃗(t)=A‾t  x⃗(0) \vx(t) = \A^t \; \vx(0)
And, in general, A‾t x⃗(0)\A^t \, \vx(0) is not easy to compute (especially for large n×nn\times n matrices!). However, if the vector x⃗ (0)\vx\,(0) were an eigenvector of A‾\A, then the computation would be relatively simple.
19.4F_Final_Builder_Ch_12.6_Dynamical_Systems_$\tkcth{eg2}$_$\key{Final}$_Builder_$\tkcth{12.7.}\tkcf{2}$_
Given the dynamic system defined by x⃗(t+1)=A‾  x⃗(t)\vx(t+1) = \A \;\vx(t), the initial condition x⃗(0)=[1−1]\vx(0) = \colvec{1}{-1} and the matrix
A‾=[1−111], \A = \sm{1}{-1}{1}{1},
find x⃗(3)\vx(3).
19.4F_Final_Builder_Ch_12.7_Dynamical_Systems_$\tkcth{eg11}$_$\key{Final}$_Builder_$\tkcth{12.7.}\tkcf{11}$_
The number of students who enrol in Math 133 and Linear Algebra 2 in a given semester is a function of the number of first year students currently enrolled in Math 133 f(t)f(t) and the number of second year students who already took Math 133 s(t)s(t), according to the following simplified model:
90%90\% of first year students who took Math 133 this semester will take Linear Algebra 2 next semester (the rest will have to repeat Math 133);
10%10\% of second year students who took Linear Algebra 2 will have to take it again;
19.4F_Final_Builder_Ch_12.7_Dynamical_Systems_$\tkcth{eg10}$_$\key{Final}$_Builder_$\tkcth{12.7.}\tkcf{10}$_
The number of students who enrol in Math 133 and Linear Algebra 2 in a given semester is a function of the number of first year students currently enrolled in Math 133 f(t)f(t) and the number of second year students who already took Math 133 s(t)s(t), according to the following simplified model:
90%90\% of first year students who took Math 133 this semester will take Linear Algebra 2 next semester (the rest will have to repeat Math 133);
10%10\% of second year students who took Linear Algebra 2 will have to take it again;