Worksheet: linear dynamical systems

Worksheet 4.5 Worksheet: linear dynamical systems
A4 US

Suppose we have a sequence

(x_{n})

defined by a linear recurrence of length

k,

as in Worksheet 2.5:

x_{n + k} = a_{0} x_{k} + a_{1} x_{k + 1} + \dots + a_{k - 1} x_{n - k + 1} .

🔗

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

v_{k + 1} = A v_{k} .

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).

🔗

To determine the long term evolution of the system, we would like to be able to compute

v_{n} = A^{n} v_{0}

🔗

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} = P D^{n} P^{- 1},

where

D

is a diagonal matrix whose entries are the eigenvalues of

A,

and

P

is the matrix of corresponding eigenvectors of

A .

🔗

1.

🔗

Consider a recurrence of length 2, of the form

x_{k + 2} = a x_{k} + b x_{k + 1} .

🔗

(a)

🔗

According to Worksheet 2.5, what is the polynomial associated to this recurrence?

🔗

(b)

🔗

Let

v_{k} = [\begin{matrix} x_{k} \\ x_{k + 1} \end{matrix}],

for each

k \geq 0,

and let

A = [\begin{matrix} 0 & 1 \\ a & b \end{matrix}] .

Show that

v_{k + 1} = A v_{k}, for each k \geq 0 .

🔗

(c)

🔗

Compute the characteristic polynomial of

A .

What do you observe?

🔗

2.

🔗

For a recurrence of length 3, given by

x_{k + 3} = a x_{k} + b x_{k + 1} + c x_{k + 2} :

🔗

(a)

🔗

Determine a matrix

A

such that

v_{k + 1} = A v_{k},

where

v_{k} = [\begin{matrix} x_{k} \\ x_{k + 1} \\ x_{k + 2} \end{matrix}] .

🔗

(b)

🔗

Compute the characteristic polynomial of

A,

and compare it to the associated polynomial of the recurrence.

🔗

(c)

🔗

Show that if

λ

is an eigenvalue of

A,

then

x = [\begin{matrix} 1 \\ λ \\ λ^{2} \end{matrix}]

is an associated eigenvector.

🔗

3.

🔗

Consider the Fibonacci sequence, defined by

x_{0} = 1, x_{1} = 1,

and

x_{k + 2} = x_{k} + x_{k + 1} .

Let

A

be the matrix associated to this sequence.

🔗

(a)

🔗

State the matrix

A,

and show that

A

has eigenvalues

λ_{\pm} = \frac{1}{2} (1 \pm \sqrt{5}),

with associated eigenvectors

x_{\pm} = [\begin{matrix} 1 \\ λ_{\pm} \end{matrix}] .

🔗

(b)

🔗

Let

P = [\begin{matrix} 1 & 1 \\ λ_{+} & λ_{-} \end{matrix}],

let

D = [\begin{matrix} λ_{+} & 0 \\ 0 & λ_{-} \end{matrix}],

and let

a_{0} = [\begin{matrix} a_{0} \\ a_{1} \end{matrix}] = P^{- 1} v_{0},

where

v_{0} = [\begin{matrix} 1 \\ 1 \end{matrix}]

gives the initial values of the sequence.

🔗

Show that

\begin{aligned} v_{n} & = P D^{n} P^{- 1} v_{0} \\ = a_{0} λ_{+}^{n} x_{+} + a_{1} λ_{-}^{n} x_{-} . \end{aligned}

🔗

(c)

🔗

Note that Part 4.5.3.b tells us that although the Fibonacci sequence is not a geometric sequence, it is the sum of two geometric sequences!

🔗

By considering the numerical values of the eigenvalues

λ_{+}

and

λ_{-},

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.)

🔗

4.

🔗

As a more practical example, consider the following (over-simplified) predator-prey system. It is based on an example in Interactive Linear Algebra ¹, 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.

🔗

We assume the following:

the share of the deer population eaten by a typical coyote in a year is $10$ deer
in the absence of the coyotes, the deer population would increase by $50$ % per year
$20$ % of the coyote population dies each year of natural causes
the growth rate of the coyote population depends on the number of deer: for each 100 deer, $10$ coyote pups will survive to adulthood.

🔗

If we let

d_{t}

denote the number of deer after

t

years, and

c_{t}

the number of coyotes, then we have

\begin{aligned} d_{t + 1} & = 1.5 d_{t} - 10 c_{t} \\ c_{t + 1} & = 0.1 d_{t} + 0.8 c_{t}, \end{aligned}

🔗

or, in matrix form,

p_{t + 1} = A p_{t},

🔗

where

p_{t} = [\begin{matrix} d_{t} \\ c_{t} \end{matrix}]

and

A = [\begin{matrix} 1.5 & - 10 \\ 0.1 & 0.8 \end{matrix}] .

🔗

After

t

years, the two populations will be given by

p_{t} = A^{t} p_{0},

where

p_{0} = [\begin{matrix} 500 \\ 20 \end{matrix}]

gives the initial populations of the two species. If possible, we would like to be able to find a closed-form formula for

p_{t},

which would allow us to analyze the long-term predictions of our model.

🔗

(a)

🔗

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 ², will be needed.

🔗

(b)

🔗

The eigenvalues turn out to be complex! What does that tell you about the nature of the system? What is the long-term behaviour of this system?

🔗

(c)

🔗

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?

🔗

(d)

🔗

You may have read this while wondering, “Does Sean actually know anything about ecology and population dynamics? Did he just make up those numbers?”

🔗

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?

🔗

5.

🔗

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,

and all of the columns of the matrix sum to

1 .

🔗

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

v_{t},

whose entries indicate the probability that the system is in a given state at time

t .

If we know that the system starts out in a particular state, then

v_{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.

🔗