We would like to represent this as a matrix equation, and then use eigenvalues to analyze, replacing the recurrence formula with a matrix equation of the form \(\vv_{k+1}=A\vv_k\text{.}\) A sequence of vectors generated in this way is called a linear dynamical system. It is a good model for systems with discrete time evolution (where changes occur in steps, rather than continuously).
without first finding all the intermediate states, so this is a situation where we would like to be able to efficiently compute powers of a matrix. Fortunately, we know how to do this when \(A\) is diagonalizable: \(A^n = PD^nP^{-1}\text{,}\) where \(D\) is a diagonal matrix whose entries are the eigenvalues of \(A\text{,}\) and \(P\) is the matrix of corresponding eigenvectors of \(A\text{.}\)
Let \(\vv_k = \begin{bmatrix}x_k\\ x_{k+1}\end{bmatrix}\text{,}\) for each \(k\geq 0\text{,}\) and let \(A=\begin{bmatrix}0\amp 1\\ a \amp b\end{bmatrix}\text{.}\) Show that
\begin{equation*}
\vv_{k+1}=A\vv_k, \text{ for each } k\geq 0\text{.}
\end{equation*}
Show that if \(\lambda\) is an eigenvalue of \(A\text{,}\) then \(\xx = \begin{bmatrix}1\\ \lambda\\ \lambda^2\end{bmatrix}\) is an associated eigenvector.
Consider the Fibonacci sequence, defined by \(x_0=1, x_1=1\text{,}\) and \(x_{k+2}=x_k+x_{k+1}\text{.}\) Let \(A\) be the matrix associated to this sequence.
State the matrix \(A\text{,}\) and show that \(A\) has eigenvalues \(\lambda_\pm = \frac{1}{2}(1\pm \sqrt{5})\text{,}\) with associated eigenvectors \(\xx_\pm = \begin{bmatrix}1\\ \lambda_\pm\end{bmatrix}\text{.}\)
Let \(P = \begin{bmatrix}1\amp 1\\ \lambda_+ \amp \lambda_-\end{bmatrix}\text{,}\) let \(D = \begin{bmatrix}\lambda_+ \amp 0\\ 0 \amp \lambda_-\end{bmatrix}\text{,}\) and let \(\mathbf{a_0}=\begin{bmatrix}a_0\\a_1\end{bmatrix}=P^{-1}\vv_0\text{,}\) where \(\vv_0=\begin{bmatrix}1\\1\end{bmatrix}\) gives the initial values of the sequence.
By considering the numerical values of the eigenvalues \(\lambda_+\) and \(\lambda_-\text{,}\) explain why we can nonetheless treat the Fibonacci sequence as approximately geometric when \(n\) is large.
(This is true more generally: if a matrix \(A\) has one eigenvalue that is larger in absolute value than all the others, this eigenvalue is called the dominant eigenvalue. If \(A\) is the matrix of some linear recurrence, and \(A\) is diagonalizable, then we can consider the sequence as a sum of geometric sequences that will become approximately geometric in the long run.)
As a more practical example, consider the following (over-simplified) predator-prey system. It is based on an example in Interactive Linear Algebra 1
personal.math.ubc.ca/~tbjw/ila/dds.html
, by Margalit, Rabinoff, and Williams, but adapted to the wildlife here in Lethbridge. An ecosystem contains both coyotes and deer. Initially, there is a population of \(20\) coyotes, and \(500\) deer.
After \(t\) years, the two populations will be given by \(\mathbf{p}_t=A^t\mathbf{p}_0\text{,}\) where \(\mathbf{p}_0=\bbm 500\\20\ebm\) gives the initial populations of the two species. If possible, we would like to be able to find a closed-form formula for \(\mathbf{p}_t\text{,}\) which would allow us to analyze the long-term predictions of our model.
Analyze the eigenvalues of this matrix, and diagonalize. The sympy library won’t be up to the task. Instead, some combination of numpy and scipy, as described by Patrick Walls on his website 2
What if you adjust the parameters? Can you come up with a system where both species flourish? Or one where they both disappear? Or one where the populations oscillate regularly?
Referring to the hint from Part 4.6.4.b, note that the size of the populations will depend on the modulus \(r\) of the eigenvalues. For what values of \(r\) will the populations decline/increase/remain steady?
The answers are, respectively, no, and yes. Can you come up with numbers that are based on a realistic example? What does our model predict in that case? Is it accurate?
A special type of linear dynamical system occurs when the matrix \(A\) is stochastic. A stochastic matrix is one where each entry of the matrix is between \(0\) and \(1\text{,}\) and all of the columns of the matrix sum to \(1\text{.}\)
The reason for these conditions is that the entries of a stochastic matrix represent probabilities; in particular, they are transition probabilities. That is, each number represents the probability of one state changing to another.
If a system can be in one of \(n\) possible states, we represent the system by an \(n\times 1\) vector \(\vv_t\text{,}\) whose entries indicate the probability that the system is in a given state at time \(t\text{.}\) If we know that the system starts out in a particular state, then \(\vv_0\) will have a \(1\) in one of its entries, and \(0\) everywhere else.
A Markov chain is given by such an initial vector, and a stochastic matrix. As an example, we will consider the following scenario, described in the book Shape, by Jordan Ellenberg:
A mosquito is born in a swamp, which we will call Swamp A. There is another nearby swamp, called Swamp B. Observational data suggests that when a mosquito is at Swamp A, there is a 40% chance that it will remain there, and a 60% chance that it will move to Swamp B. When the mosquito is at Swamp B, there is a 70% chance that it will remain, and a 30% chance that it will return to Swamp A.
By diagonalizing the matrix \(M\text{,}\) find a formula for \(\vv_n = M^n\vv_0\text{.}\) Use this to determine the long-term probability that the mosquito will be found in either swamp.
You should have found that one of the eigenvalues of \(M\) was \(\lambda=1\text{.}\) The corresponding eigenvector \(\vv\) satisfies \(M\vv=\vv\text{.}\) When we normalize so that the entires of \(\vv\) sum to 1, we call \(\vv\) a steady-state vector: if our system begins with state \(\vv\text{,}\) it will remain there forever.
Confirm that if the eigenvector \(\vv\) is rescaled so that its entries sum to 1, the resulting values agree with the long-term probabilities found in the previous part. (The system tends toward the steady-state solution, even if it begins in another state.)
A stochastic matrix \(M\) is called regular some power \(M^k\) has all positive entries. It is a theorem that every regular stochastic matrix has a unique steady-state vector. That is, there is a unique vector \(\vv\) whose entries are positive, and sum to 1, such that \(M\vv = \vv\text{.}\)
Prove that every stochastic matrix has 1 as an eigenvalue. (It is also possible to show that 1 is the dominant eigenvalue, but we will not attempt to do so.)
The eigenvalues of \(M\) are the same as the eigenvalues of \(M^T\text{.}\) Since the columns of \(M\) sum to 1, the rows of \(M^T\) sum to 1. Does this suggest a possible eigenvector for \(M^T\text{?}\)
Suppose \(M\xx = \lambda \xx\) for \(\lambda\neq 1\) and some \(\xx\neq \mathbf{0}\text{.}\) The entries of \(\xx\) are not all equal (or \(\xx\) is the eigenvector for \(\lambda =1\)). Let \(x_j\) be the largest entry in \(\xx\text{.}\)
Prove that the product of two \(2\times 2\) stochastic matrices is stochastic. Conclude that if \(M\) is stochastic, so is \(M^k\) for each \(k=1,2,3,\ldots\text{.}\)
We know that 1 is an eigenvalue of \(M^T\text{,}\) with eigenvector \(\xx= \bbm 1/n\\ 1/n\\\vdots \\ 1/n\ebm\) (rescaled so that its entries sum to 1). We want to that the dimension of the 1-eigenspace of \(M^T\) is 1. That is, any \(\yy\) whose entries are not all equal cannot satisfy \(M^T\yy = \yy\text{.}\)
To show this, let \(y_i\) be respectively, the smallest entry in \(\yy\text{.}\) Since the entries of \(\yy\) are not all equal, \(y_i\lt y_k\) for some \(k\text{.}\)
Let \(M\) be a regular stochastic matrix. Prove that for any initial state \(\vv_0\) whose entries sum to 1, the Markov chain \(\vv_n = M^n\vv_0\) satisfies \(\lim_{n\to\infty}\vv_n = \vv\text{.}\) (You may assume that \(\vv_0\) is a linear combination of eigenvectors of \(M\text{,}\) and that \(\abs{\lambda}\lt 1\) for each eigenvalue \(\lambda \neq 1\text{.}\))
