This section is devoted to one common kind of application of eigenvalues: to the study of difference equations, in particular to Markov chains. We will introduce stochastic matrices, which encode this type of difference equation, and will cover in detail the most famous example of a stochastic matrix: the Google Matrix.
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 copies of Prognosis Negative in each of the Red Box kiosks in Atlanta. 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 subsection.
A difference equation is an equation of the form
for an matrix and vectors in
In other words:
Note that
which should hint to you that the long-term behavior of a difference equation is an eigenvalue problem.
We will use the following example in this subsection and the next. Understanding this section amounts to understanding this example.
Red Box has kiosks all over Atlanta where you can rent movies. You can return them to any other kiosk. For simplicity, pretend that there are three kiosks in Atlanta, and that every customer returns their movie the next day. Let be the vector whose entries are the number of copies of Prognosis Negative at kiosks and respectively. Let be the matrix whose -entry is the probability that a customer renting Prognosis Negative from kiosk returns it to kiosk For example, the matrix
encodes a probability that a customer renting from kiosk 3 returns the movie to kiosk 2, and a probability that a movie rented from kiosk gets returned to kiosk The second row (for instance) of the matrix says:
The number of movies returned to kiosk will be (on average):
Applying this to all three rows, this means
Therefore, represents the number of movies in each kiosk the next day:
This system is modeled by a difference equation.
An important question to ask about a difference equation is: what is its long-term behavior? How many movies will be in each kiosk after 100 days? In the next subsection, we will answer this question for a particular type of difference equation.
In this subsection, we discuss difference equations representing probabilities, like the Red Box example. Such systems are called Markov chains. The most important result in this section is the Perron–Frobenius theorem, which describes the long-term behavior of a Markov chain.
A square matrix is stochastic if all of its entries are nonnegative, and the entries of each column sum to
A matrix is positive if all of its entries are positive numbers.
A positive stochastic matrix is a stochastic matrix whose entries are all positive numbers. In particular, no entry is equal to zero. For instance, the first matrix below is a positive stochastic matrix, and the second is not:
Continuing with the Red Box example, the matrix
is a positive stochastic matrix. The fact that the columns sum to says that all of the movies rented from a particular kiosk must be returned to some other kiosk (remember that every customer returns their movie the next day). For instance, the first column says:
Of the movies rented from kiosk
The sum is as all of the movies are returned to one of the three kiosks.
The matrix represents the change of state from one day to the next:
If we sum the entries of we obtain
This says that the total number of copies of Prognosis Negative in the three kiosks does not change from day to day, as we expect.
The fact that the entries of the vectors and sum to the same number is a consequence of the fact that the columns of a stochastic matrix sum to
Let be a stochastic matrix, let be a vector, and let Then the sum of the entries of equals the sum of the entries of
Computing the long-term behavior of a difference equation turns out to be an eigenvalue problem. The eigenvalues of stochastic matrices have very special properties.
Let be a stochastic matrix. Then:
In fact, for a positive stochastic matrix one can show that if is a (real or complex) eigenvalue of then The -eigenspace of a stochastic matrix is very important.
A steady state of a stochastic matrix is an eigenvector with eigenvalue such that the entries are positive and sum to
The Perron–Frobenius theorem describes the long-term behavior of a difference equation represented by a stochastic matrix. Its proof is beyond the scope of this text.
Let be a positive stochastic matrix. Then admits a unique steady state vector which spans the -eigenspace.
Moreover, for any vector with entries summing to some number the iterates
approach as gets large.
Translation: The Perron–Frobenius theorem makes the following assertions:
One should think of a steady state vector as a vector of percentages. For example, if the movies are distributed according to these percentages today, then they will be have the same distribution tomorrow, since And no matter the starting distribution of movies, the long-term distribution will always be the steady state vector.
The sum of the entries of is the total number of things in the system being modeled. The total number does not change, so the long-term state of the system must approach it is a multiple of because it is contained in the -eigenspace, and the entries of sum to
Let be a positive stochastic matrix. Here is how to compute the steady-state vector of
The above recipe is suitable for calculations by hand, but it does not take advantage of the fact that is a stochastic matrix. In practice, it is generally faster to compute a steady state vector by computer as follows:
Let be a positive stochastic matrix. Here is how to approximate the steady-state vector of with a computer.
Continuing with the Red Box example, we can illustrate the Perron–Frobenius theorem explicitly. The matrix
has characteristic polynomial
Notice that is strictly greater in absolute value than the other eigenvalues, and that it has algebraic (hence, geometric) multiplicity We compute eigenvectors for the eigenvalues to be, respectively,
The eigenvector necessarily has positive entries; the steady-state vector is
The eigenvectors form a basis for for any vector in we have
Iterating multiplication by in this way, we have
as This shows that approaches which is an eigenvector with eigenvalue , as guaranteed by the Perron–Frobenius theorem.
What do the above calculations say about the number of copies of Prognosis Negative in the Atlanta Red Box kiosks? Suppose that the kiosks start with 100 copies of the movie, with copies at kiosk 1, copies at kiosk and copies at kiosk Let be the vector describing this state. Then there will be movies in the kiosks the next day, the day after that, and so on. We let
(Of course it does not make sense to have a fractional number of movies; the decimals are included here to illustrate the convergence.) The steady-state vector says that eventually, the movies will be distributed in the kiosks according to the percentages
which agrees with the above table. Moreover, this distribution is independent of the beginning distribution of movies in the kiosks.
Now we turn to visualizing the dynamics of (i.e., repeated multiplication by) the matrix This matrix is diagonalizable; we have for
The matrix leaves the -coordinate unchanged, scales the -coordinate by and scales the -coordinate by Repeated multiplication by makes the - and -coordinates very small, so it “sucks all vectors into the -axis.”
The matrix does the same thing as but with respect to the coordinate system defined by the columns of This means that “sucks all vectors into the -eigenspace”, without changing the sum of the entries of the vectors.
The picture of a positive stochastic matrix is always the same, whether or not it is diagonalizable: all vectors are “sucked into the -eigenspace,” which is a line, without changing the sum of the entries of the vectors. This is the geometric content of the Perron–Frobenius theorem.
Internet searching in the 1990s was very inefficient. Yahoo or AltaVista would scan pages for your search text, and simply list the results with the most occurrences of those words. Not surprisingly, the more unsavory websites soon learned that by putting the words “Alanis Morissette” a million times in their pages, they could show up first every time an angsty teenager tried to find Jagged Little Pill on Napster.
Larry Page and Sergey Brin invented a way to rank pages by importance. They founded Google based on their algorithm. Here is roughly how it works.
Each web page has an associated importance, or rank. This is a positive number. This rank is determined by the following rule.
If a page links to other pages then each page inherits of ’s importance.
In practice, this means:
Alternatively, there is the random surfer interpretation. A “random surfer” just sits at his computer all day, randomly clicking on links. The pages he spends the most time on should be the most important. So, the important (high-ranked) pages are those where a random surfer will end up most often. This measure turns out to be equivalent to the rank.
Consider an internet with pages. The importance matrix is the matrix whose -entry is the importance that page passes to page
Observe that the importance matrix is a stochastic matrix, assuming every page contains a link: if page has links, then the th column contains the number times, and the number zero in the other entries.
Consider the following internet with only four pages. Links are indicated by arrows.
The importance rule says:
In terms of matrices, if is the vector containing the ranks of the pages then
The matrix on the left is the importance matrix, and the final equality expresses the importance rule.
The above example illustrates the key observation.
The rank vector is an eigenvector of the importance matrix with eigenvalue
In light of the key observation, we would like to use the Perron–Frobenius theorem to find the rank vector. Unfortunately, the importance matrix is not always a positive stochastic matrix.
Here is Page and Brin’s solution. First we fix the importance matrix by replacing each zero column with a column of s, where is the number of pages:
The modified importance matrix is always stochastic.
Now we choose a number in called the damping factor. (A typical value is )
Let be the importance matrix for an internet with pages, and let be the modified importance matrix. The Google Matrix is the matrix
In the random surfer interpretation, this matrix says: with probability our surfer will surf to a completely random page; otherwise, he'll click a random link on the current page, unless the current page has no links, in which case he'll surf to a completely random page in either case.
The reader can verify the following important fact.
The Google Matrix is a positive stochastic matrix.
If we declare that the ranks of all of the pages must sum to then we find:
The PageRank vector is the steady state of the Google Matrix.
This exists and has positive entries by the Perron–Frobenius theorem. The hard part is calculating it: in real life, the Google Matrix has zillions of rows.
