Understand how to convert word problems to matrix equations.
Learn how the eigenvalues and eigenvectors of a matrix can be used to describe the long-term behaviour of an associated discrete dynamical system.
Recipe:calculate the state of a discrete dynamical system at time
Picture: dynamics of a discrete dynamical system.
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 is a transformation (not necessarily linear) and is a sequence of vectors in such that then we say that and the sequence make up a discrete dynamical system. The difference equations we study are special kinds of discrete dynamical system, the kind where 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 be the vector whose entries are the number of trucks in locations and respectively. Let be the matrix whose -entry is the probability that a customer renting a truck from location returns it to location For example, the matrix
encodes a probability that a customer renting from location 3 returns the truck to location 2, and a probability that a truck rented from location gets returned to location The second row (for instance) of the matrix says:
The number of trucks returned to location will be (on average):
Applying this to all three rows, this means
Therefore, represents the number of trucks at each location the next day:
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 and years, respectively, or the number of customers of two different phone companies in Canada. In each case, we can represent the state at time by a vector We assume that represents a discrete time quantity: in other words, is the state “on day ” or “at year ”. Suppose in addition that the state at time is related to the state at time in a linear way: for some matrix This is the situation we will consider in this section.
Definition
A (first-order homogeneous) matrix difference equation is an equation of the form
where is an matrix. An initial condition is a vector in Taken together, the difference equation and the initial condition determine a sequence of vectors such that for all This is called a (linear) discrete dynamical system.
In other words:
is the “state at time ”
is the “state at time ” and
means that is the “change of state matrix.”
Note that
which should hint to you that the long-term behavior of such a system is an eigenvalue problem.
A second-order matrix difference equation is one where there are two matrices and and the equation
holds for all An inhomogeneous (first order) matrix difference equation is one where there is a constant vector such that
holds for all We will not consider second- or higher-order or inhomogeneous difference equations, or their associated discrete dynamical systems, in this book.
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.
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 (), and midges in hundreds of thousands ().
If it were not for the frogs, the midge population would increase by each year. We assume that each frog kills midges each year. Equivalently, for each frogs, the number of midges that gets eaten is
The growth of the frog population is constrained by the availability of midges. We assume that on average, for each midges, tadpoles survive to become adult frogs each year. Finally, we need the death rate of the frog population. It is That is, only of the adult frogs this year survive until next year.
We now show how this description leads directly to a difference equation
Let denote the number of frogs (in hundreds) after years have passed, and let denote the number of midges (in hundreds of thousands) after years have passed. Let
Then the text of the problem tells us that
and
This can be written in matrix form:
Write
for later reference.
If is the vector containing the population data for this year (midges and frogs), then is the vector containing the population data for next year, is the vector containing the population for the year after, and so on.
For example, if we calculate that there are frogs and midges in year 0, then we would record this as
We could then calculate
and
This represents frogs and midges in year
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 looks like as
In order to study we start with the observation
This is to say that to get you apply to a total of times.
In Section 6.4 we saw that is troublesome to calculate directly when is large, but it is easier to calculate if we diagonalize: In the case of the frogs and midges:
This allows us to write down a computable formula for
(6.6.1)
For instance, if we continue to suppose that then we calculate
(6.6.2)
In even more direct language, the model predicts that the number of frogs (in hundreds) is given by
and the number of midges (in hundreds of thousands) is given by
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 grows, the quantity tends to whereas grows without bound. This is good news for our frogs and midges, since it we calculate
and similarly for the midges 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
This says that after several years have passed, the ratio of frogs to midges will be approximately 500 frogs for each 100,000 midges, which we can simplify to 1 frog for every 200 midges.
Warning
You can choose any ordering you like for the variables at the start of a question like this. For instance, you can list the midges first and the frogs second, to get the system
This describes the same model, so the formulas you would derive for and 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.
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
and an initial vector then we can write
The situation is simplest when is an eigenvector of with eigenvalue In this case, the multiplication has the effect of stretching by a factor of so that applying times to results in scaling by
provided is an eigenvector with eigenvalue
The next best situation, which is the usual one, is when we can write as a linear combination of eigenvectors of Suppose are eigenvectors of with associated eigenvalues If
for some coefficients then
We can always find ourselves in this situation if is diagonalizable, because we can find an ordered basis for made up of eigenvectors of in this case. We might even be able to write as a linear combination of eigenvectors even if is not diagonalizable, but it's not guaranteed.
From now on, we assume is diagonalizable. Let
be an invertible matrix where the columns are eigenvectors of We want to write
which is the same as solving the system of linear equations
so that we deduce that
Having written as a linear combination of eigenvectors, we can calculate
Recipe: Calculating the state at time for a discrete dynamical system
If and determine a discrete dynamical system and if is diagonalizable, then to calculate the vector
Write
where are eigenvectors of with associated eigenvalues
Then
Relating this procedure to diagonalization
In this case we are taking the vectors and are forming the combination with coefficients
(6.6.3)
You can check that if denotes the diagonal matrix having as diagonal entries, then the vector of coefficients (6.6.3) is calculated as Then to combine with these coefficients, we take the product That is to say:
Example(Frogs and midges, revisited)
We look at the example of frogs and midge again, this time using the eigenvectors of extensively. Remember that
Set We know has eigenvector–eigenvalue pairs
For later use, we set up a little more notation:
Write in terms of eigenvectors of
You can calculate these coefficients in many ways, of course, but one way is to do the multiplication
We now know that
(6.6.4)
which is saying the same thing as
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 grows larger, the coefficient tends to This means that as time goes by, the contribution of to becomes less and less important, and the other summand, explains the long-term behaviour of the model. For example, we can see directly from Equation (6.6.4) that the ratio of (100s of frogs) to (100,000s of midges) tends to as
By moving the initial vector around in the figure above, you can see how the long-term behaviour of the model depends on For example, if lies in the eigenspace for then the sequence is attracted the origin. For any other starting position, the vector has some nonzero component in the -eigenspace, and this component will determine the long-term behaviour, so that 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 to the right has bad consequences for the frogs and midges. If, for example, we move to then
so that applying the recipe gives us
As becomes larger, both and 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 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 can behave, even when we restrict our attention to matrices. The following examples do not cover every possibility, but they should be enough to give you the tools to understand every case.
We have said nothing about cases where one or both eigenvalues of are negative. A negative eigenvalue causes the coefficient of the corresponding eigenvector to switch signs from positive to negative or back again every time is applied.
With the exception that the negative eigenvalue or eigenvalues cause the vectors 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 -matrix with two distinct real eigenvalues
Both of are bigger than but less than In this case, the origin is an attractor, which is to say the sequence will always approach the origin.
One of is greater than and the other is less than In this case, the origin is a saddle point, which is to say the sequence 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 are greater than In this case, the origin is a repeller, which is to say the sequence will always go away from the origin.
Of course, this discussion leaves out a great many special cases. What if or 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
Previously, we saw that magnitude of the eigenvalues, i.e., whether or 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 tends to infinity if the sequence of positive real numbers keeps growing without bound. If is a complex number, then as
If is a real -matrix with non-real eigenvalues, then there are three possibilities for the long-term behaviour of the associated discrete dynamical system.
If then the vectors will spiral inwards, towards the origin, which is an attractor.
If then the vectors will move around the origin in a periodic or quasi-periodic way, neither getting closer or farther away on average.
If then the vectors 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 is diagonalizable.
Even in the 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 is an diagonalizable matrix, then we may find a basis that consists of eigenvectors of with associated eigenvalues Any initial state vector can be written as
and then
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 -matrix to have three non-real eigenvalues.