Skip to main content

Section6.6Discrete Dynamical Systems

Objectives
  1. Understand how to convert word problems to matrix equations.
  2. Learn how the eigenvalues and eigenvectors of a matrix A can be used to describe the long-term behaviour of an associated discrete dynamical system.
  3. Recipe:calculate the state v t of a discrete dynamical system at time t .
  4. Picture: dynamics of a discrete dynamical system.
  5. Vocabulary: difference equation, (linear) discrete dynamical system, saddle point, attractor, repeller.

This section and the next are devoted to one common kind of application of eigenvalues: to the study of discrete dynamical systems. The discrete dynamical systems we study are linear discrete dynamical systems.

If f : R n R n is a transformation (not necessarily linear) and ..., v i , v i + 1 , v i + 2 ,... is a sequence of vectors in R n such that v i + 1 = f ( v i ) , then we say that f and the sequence v i , v i + 1 ,... make up a discrete dynamical system. The difference equations we study are special kinds of discrete dynamical system, the kind where f is a linear transformation.

Before giving too many technical definitions, we consider an example:

Example

A truck rental company has locations all over Vancouver, where you can rent moving trucks. You can return them to any other location. For simplicity, pretend that there are three locations, and that every customer returns their truck the next day. Let v t be the vector whose entries x t , y t , z t are the number of trucks in locations 1,2, and 3, respectively. Let A be the matrix whose i , j -entry is the probability that a customer renting a truck from location j returns it to location i . For example, the matrix

A = B .3.4.5.3.4.3.4.2.2 C

encodes a 30% probability that a customer renting from location 3 returns the truck to location 2, and a 40% probability that a truck rented from location 1 gets returned to location 3. The second row (for instance) of the matrix A says:

The number of trucks returned to location 2 will be (on average):

30%ofthetrucksfromlocation140%ofthetrucksfromlocation230%ofthetrucksfromlocation3

Applying this to all three rows, this means

A B x t y t z t C = B .3 x t + .4 y t + .5 z t .3 x t + .4 y t + .3 z t .4 x t + .2 y t + .2 z t C .

Therefore, Av t represents the number of trucks at each location the next day:

Av t = v t + 1 .

This is an example of a linear discrete dynamical system.

Subsection6.6.1Discrete dynamical systems

Suppose that we are studying a system whose state at any given time can be described by a list of numbers: for instance, the numbers of rabbits aged 0,1, and 2 years, respectively, or the number of customers of two different phone companies in Canada. In each case, we can represent the state at time t by a vector v t . We assume that t represents a discrete time quantity: in other words, v t is the state “on day t or “at year t ”. Suppose in addition that the state at time t + 1 is related to the state at time t in a linear way: v t + 1 = Av t for some matrix A . This is the situation we will consider in this section.

Definition

A (first-order homogeneous) matrix difference equation is an equation of the form

v t + 1 = Av t

where A is an n × n matrix. An initial condition is a vector v 0 in R n . Taken together, the difference equation and the initial condition determine a sequence of vectors v 0 , v 1 , v 2 ,... such that v t + 1 = Av t for all t . This is called a (linear) discrete dynamical system.

In other words:

  • v t is the “state at time t ,
  • v t + 1 is the “state at time t + 1, and
  • v t + 1 = Av t means that A is the “change of state matrix.”

Note that

v t = Av t 1 = A 2 v t 2 = ··· = A t v 0 ,

which should hint to you that the long-term behavior of such a system is an eigenvalue problem.

Subsection6.6.2Long-term behaviour

An important question to ask about a dynamical system is: what is its long-term behavior? How many trucks will be at each location after 100 days (assuming no intervention from the business owner)? How many rabbits will there be in 20 years (and how many of them will be adults)? In this subsection, we will address this kind of question.

Example(A Predator–Prey Model)

There is a pond with two species: frogs and midges. The frogs eat the midges. The population is counted once a year. We measure frogs in hundreds (10 2 ), and midges in hundreds of thousands (10 5 ).

If it were not for the frogs, the midge population would increase by 30% each year. We assume that each frog kills 500 midges each year. Equivalently, for each 100 frogs, the number of midges that gets eaten is ( 0.5 ) × 100,000.

The growth of the frog population is constrained by the availability of midges. We assume that on average, for each 100,000 midges, 10 = 0.1 × 100 tadpoles survive to become adult frogs each year. Finally, we need the death rate of the frog population. It is 30%. That is, only 70% of the adult frogs this year survive until next year.

We now show how this description leads directly to a difference equation

Let f t denote the number of frogs (in hundreds) after t years have passed, and let m t denote the number of midges (in hundreds of thousands) after t years have passed. Let

v t = N f t m t O .

Then the text of the problem tells us that

f t + 1 = 0.7 f t + 0.1 m t

and

m t + 1 = 0.5 f t + 1.3 m t .

This can be written in matrix form:

v t + 1 = N 0.70.1 0.51.3 O v t .

Write

A = N 0.70.1 0.51.3 O

for later reference.

If v 0 is the vector containing the population data for this year (midges and frogs), then v 1 = Av 0 is the vector containing the population data for next year, v 2 = Av 1 is the vector containing the population for the year after, and so on.

For example, if we calculate that there are 700 frogs and 9 × 10 5 midges in year 0, then we would record this as

v 0 = N 79 O .

We could then calculate

v 1 = N 0.70.1 0.51.3 ON 79 O = N 5.88.2 O

and

v 2 = N 0.70.1 0.51.3 ON 5.88.2 O = N 4.887.76 O .

This represents 488 frogs and 776,000 midges in year 2.

There are many questions one can ask about the model we have constructed. Let us concentrate here on questions about long-term behaviour of the model. That is, what happens in our model after a large number of years? In mathematical notation, we want to know what v t looks like as t →∞ .

In order to study v t , we start with the observation

v t = Av t 1 = AAv t 2 = ··· = t times J ML K AA ... Av 0 .

This is to say that to get v t , you apply A to v 0 a total of t times.

In Section 6.4 we saw that A t is troublesome to calculate directly when t is large, but it is easier to calculate if we diagonalize: A = CDC 1 . In the case of the frogs and midges:

N 0.70.1 0.51.3 O = A = CDC 1 = N 1151 ON 1.2000.8 ON 0.250.251.25 0.25 O .

This allows us to write down a computable formula for v t :

v t = CD t C 1 v 0 . (6.6.1)

For instance, if we continue to suppose that v 0 = N 79 O , then we calculate

v t = N f t m t O = N 1151 ON 1.2 t 000.8 t ON 0.250.251.25 0.25 ON 79 O == N 1151 ON 1.2 t 000.8 t ON 0.56.5 O = N 1151 ON ( 1.2 ) t ( 0.5 )( 0.8 ) t ( 6.5 ) O == N 1 ( 1.2 ) t ( 0.5 )+ 1 ( 0.8 ) t ( 6.5 ) 5 ( 1.2 ) t ( 0.5 )+ 1 ( 0.8 ) t ( 6.5 ) O . (6.6.2)

Simply, the model predicts that the number of frogs (in hundreds) is given by

f t = 1 ( 1.2 ) t ( 0.5 )+ 1 ( 0.8 ) t ( 6.5 )

and the number of midges (in hundreds of thousands) is given by

m t = 5 ( 1.2 ) t ( 0.5 )+ 1 ( 0.8 ) t ( 6.5 ) .

What we asked about the system was the long-term behaviour. From this point of view, the information in equation (6.6.2) was more than we needed. We know from calculus that as t grows, the quantity ( 0.8 ) t tends to 0, whereas ( 1.2 ) t grows without bound. This is good news for our frogs and midges, since it we calculate

lim t →∞ f t = lim t →∞ 1 ( 1.2 ) t ( 0.5 )+ lim t →∞ 1 ( 0.8 ) t ( 6.5 )= + 0

and similarly for the midges lim t →∞ m t = , so the model predicts that both frogs and midges will thrive.

The model can also be used to predict the ratio of frogs to midges. This is a standard kind of limit calculation

lim t →∞ f t m t = lim t →∞ 1 ( 1.2 ) t ( 0.5 )+ 1 ( 0.8 ) t ( 6.5 ) 5 ( 1.2 ) t ( 0.5 )+ 1 ( 0.8 ) t ( 6.5 )= 1 5.

This says that after several years have passed, the ratio of frogs to midges will be approximately 100 frogs for each 500,000 midges, which we can simplify to 1 frog for every 5,000 midges.

Warning

You can choose either ordering for the variables at the start of a question like this. You can list the midges first and the frogs second, to get the system

v t = N m t f t O , A = N 1.3 0.50.10.7 O .

This describes the same model, so the formulas you would derive for m t and f t would be the same.

It is extremely important to keep the same order throughout, however. Do not mix up the order by writing frogs first sometimes and midges first other times. This will lead to nonsense.

Similarly, in problems with more than two variables, you can choose any order for the variables when you work it out. The important thing is to be consistent throughout the problem.

Writing the vectors in terms of eigenvectors

An analysis such as we did for the system of frogs and midges can be simplified and made more conceptual by concentrating on the role of eigenvectors in the story. Concentrating on eigenvectors can also make the process of diagonalization less mysterious.

Suppose we have a discrete dynamical system

v t + 1 = Av t

and an initial vector v 0 , then we can write

v 1 = Av 0 , v 2 = Av 1 = A ( Av 0 )= A 2 v 0 ,..., v t = t times J ML K A ... Av 0 = A t v 0 .

The situation is simplest when v 0 is an eigenvector of A , with eigenvalue λ . In this case, the multiplication Av 0 has the effect of stretching v 0 by a factor of λ , so that applying A t times to v 0 results in scaling v 0 by t times J ML K λλ ... λ = λ t .

A t v 0 = λ t v 0

provided v 0 is an eigenvector with eigenvalue λ .

The next best situation, which is the usual one, is when we can write v 0 as a linear combination of eigenvectors of A . Suppose w 1 ,..., w j are eigenvectors of A with associated eigenvalues λ 1 ,..., λ j . If

v 0 = c 1 w 1 + ··· + c j w j

for some coefficients c 1 ,..., c j then

A t v 0 = c 1 A t w 1 + ··· + c j A t w j = c 1 λ t 1 w 1 + ··· + c j λ tj w j .

We can always find ourselves in this situation if A is diagonalizable, because we can find an ordered basis for R n made up of eigenvectors of A in this case. We might even be able to write v as a linear combination of eigenvectors even if A is not diagonalizable, but it's not guaranteed.

From now on, we assume A is diagonalizable. Let

C = B ||| w 1 w 2 ... w n ||| C

be an invertible matrix where the columns are eigenvectors of A . We want to write

v 0 = c 1 w 1 + ··· + c n w n ,

which is the same as solving the system of linear equations

v 0 = C DHHF c 1 c 2 ... c n EIIG

so that we deduce that

C 1 v 0 = DHHF c 1 c 2 ... c n EIIG .

Having written v as a linear combination of eigenvectors, we can calculate v t :

v t = λ t 1 c 1 w 1 + λ t 2 c 2 w 2 + ··· + λ tn c n w n .
Recipe: Calculating v t , the state at time t , for a discrete dynamical system

If A and v 0 determine a discrete dynamical system v t = A t v 0 , and if A is diagonalizable, then to calculate the vector v t

  • Write
    v 0 = c 1 w 1 + c 2 w 2 + ··· + c n w n
    where w 1 , w 2 ,..., w n are eigenvectors of A with associated eigenvalues λ 1 , λ 2 ,..., λ n .
  • Then
    v t = c 1 λ t 1 w 1 + c 2 λ t 2 w 2 + ··· + c n λ tn w n .
Relating this procedure to diagonalization

In this case we are taking the vectors w 1 , w 2 ,..., w n and are forming the combination with coefficients

DHHF λ t 1 c 1 λ t 2 c 2 ... λ tn c n EIIG . (6.6.3)

You can check that if D denotes the diagonal matrix having λ 1 , λ 2 ,..., λ n as diagonal entries, then the vector of coefficients (6.6.3) is calculated as D t C 1 v 0 . Then to combine w 1 , w 2 ,..., w n with these coefficients, we take the product CD t C 1 . That is to say:

v t = CD t C 1 v 0 = λ t 1 c 1 w 1 + λ t 2 c 2 w 2 + ··· + λ tn c n w n .
Example(Frogs and midges, revisited)

We look at the example of frogs and midge again, this time using the eigenvectors of A extensively. Remember that

v t + 1 = Av t , A = N 0.70.1 0.51.3 O .

Set v 0 = N 79 O . We know A has eigenvector–eigenvalue pairs

w 1 = N 15 O , λ 1 = 1.2; w 2 = N 11 O , λ 2 = 0.8.

For later use, we set up a little more notation:

v t = N f t m t O , C = N 1151 O , D = N 1.2000.8 O .

Write v 0 in terms of eigenvectors of A :

N 79 O =( 0.5 ) N 15 O +( 6.5 ) N 11 O .

You can calculate these coefficients in many ways, of course, but one way is to do the multiplication

C 1 v 0 = N 0.56.5 O .

We now know that

v t =( 1.2 ) t ( 0.5 ) N 15 O +( 0.8 ) t ( 6.5 ) N 11 O , (6.6.4)

which is saying the same thing as

v t = CD t C 1 v 0

in different notation. You can check by expanding out that (6.6.4) gives the same information as (6.6.2).

Equation (6.6.4) is particularly useful for understanding the long-term behaviour of the model. As t grows larger, the coefficient ( 0.8 ) t tends to 0. This means that as time goes by, the contribution of ( 0.8 ) t ( 6.5 ) N 11 O to v t becomes less and less important, and the other summand, ( 1.2 ) t ( 0.5 ) N 51 O explains the long-term behaviour of the model. For example, we can see directly from Equation (6.6.4) that the ratio of f t (100s of frogs) to m t (100,000s of midges) tends to 1:5 as t →∞ .

Figure10A plot of the number of frogs and midges in each year after year 0. The x -coordinate denotes 100s of frogs, and the y -coordinate denotes 100,000s of midges.

By moving the initial vector around in the figure above, you can see how the long-term behaviour of the model depends on v 0 . For example, if v 0 lies in the eigenspace for 0.8, then the sequence v 0 , Av 0 , A 2 v 0 ,... is attracted the origin. For any other starting position, the vector v 0 has some nonzero component in the 1.2 -eigenspace, and this component will determine the long-term behaviour, so that v 0 , Av 0 , A 2 v 0 ,... is eventually repelled by the origin. In a circumstance like this, where the origin attracts along some directions and repels along others, the origin is said to be a saddle point.

As a real-world matter, however, observe that moving v 0 to the right has bad consequences for the frogs and midges. If, for example, we move v 0 to v 0 = N 85 O , then

v 0 = 0.75 N 15 O + 7.25 N 11 O

so that applying the recipe gives us

N f t m t O = v t =( 0.75 )( 1.2 ) t N 15 O +( 7.25 )( 0.8 ) t N 11 O .

As t becomes larger, both f t and m t tend to −∞ . This is an abstract mathematical statement, and does not make sense for the frogs and midges. In the real world, as soon as the number of midges reaches 0, the ecosystem will collapse and the frogs and midges will all die.

Various kinds of long-term behaviour

There is considerable diversity in how discrete dynamial systems specified by v t + 1 = Av t can behave, even when we restrict our attention to 2 × 2 matrices. The following examples do not cover every possibility, but they should be enough to give you the tools to understand every case.

Possibly negative eigenvalues

We have said nothing about cases where one or both eigenvalues of A are negative. A negative eigenvalue λ 1 < 0 causes the coefficient of the corresponding eigenvector to switch signs from positive to negative or back again every time A is applied.

With the exception that the negative eigenvalue or eigenvalues cause the vectors v 0 , v 1 , v 2 ,... to “jump” back and forth, the analysis of discrete dynamical systems with negative eigenvalues is very similar to that of positive eigenvalues.

There are three main cases for a 2 × 2 -matrix A with two distinct real eigenvalues λ 1 , λ 2

  • Both of | λ 1 | , | λ 2 | are bigger than 0 but less than 1. In this case, the origin is an attractor, which is to say the sequence v 0 , v 1 , v 2 ,... will always approach the origin.
  • One of | λ 1 | , | λ 2 | is greater than 1, and the other is less than 1. In this case, the origin is a saddle point, which is to say the sequence v 0 , v 1 , v 2 ,... can go towards the origin for a time, before heading away again (unless it approaches exactly along the eigenspace for the eigenvalue of smaller magnitude).
  • Both of | λ 1 | , | λ 2 | are greater than 1. In this case, the origin is a repeller, which is to say the sequence v 0 , v 1 , v 2 ,... will always go away from the origin.

Of course, this discussion leaves out a great many special cases. What if | λ 1 | = 1, or λ 2 = 0? There are too many of these for it to be helpful for us to cover them all, but by use of the recipe and a little calculus, you can study almost all of them. The only case you might not be equipped to handle is that of a non-diagonalizable matrix A .

Subsection6.6.3Discrete dynamical systems with complex eigenvalues

It can happen that a real matrix A has complex eigenvalues. The associated dynamical systems show spiralling behaviour.

Previously, we saw that magnitude of the eigenvalues, i.e., whether | λ | < 1 or | λ | > 1, had a big effect on the long-term behaviour of the model. The case of complex eigenvalues is the same, with the important modification that we use the complex absolute value to measure the magnitude of the eigenvalues. This is discussed more fully in note.

We say that a sequence of complex numbers ( z 1 , z 2 ,... ) tends to infinity if the sequence ( | z 1 | , | z 2 | ,... ) of positive real numbers keeps growing without bound. If z is a complex number, then as t →∞

z t tendsto A inBnityif | z | > 10if | z | < 1.

If A is a real 2 × 2 -matrix with non-real eigenvalues, λ 1 , λ 2 = λ 1 , then there are three possibilities for the long-term behaviour of the associated discrete dynamical system.

  • If | λ 1 | = | λ 2 | < 1, then the vectors v 0 , v 1 , v 2 ,... will spiral inwards, towards the origin, which is an attractor.
  • If | λ 1 | = | λ 2 | = 1, then the vectors v 0 , v 1 , v 2 ,... will move around the origin in a periodic or quasi-periodic way, neither getting closer or farther away on average.
  • If | λ 1 | = | λ 2 | > 1, then the vectors v 0 , v 1 , v 2 ,... will spiral outwards, away from the origin, which is a repeller.

Subsection6.6.4Discrete dynamical systems in more than 2 dimensions

The basic principles for discrete dynamical systems in more than 2 dimensions remain the same as in 2 dimensions. As before, we will concentrate on the case where A is diagonalizable.

Even in the 3 × 3 case, there are many possibilities for how a discrete dynamical system can behave. It would not be helpful to list every possibility here.

In general, if A is an n × n diagonalizable matrix, then we may find a basis w 1 ,..., w n that consists of eigenvectors of A , with associated eigenvalues λ 1 ,..., λ n . Any initial state vector v 0 can be written as

v 0 = c 1 w 1 + c 2 w 2 + ··· + c n w n

and then

v t = A t v 0 = λ t 1 c 1 w 1 + λ t 2 c 2 w 2 + ··· + λ tn c n w n .

Questions about the long-term behaviour can then be answered by using limit arguments from calculus.

Note

We observe that for a matrix with real-number entries, non-real eigenvalues come in conjugate pairs. It is not possible for a real-number 3 × 3 -matrix to have three non-real eigenvalues.