Section 9 Introduction to Eigenvalues and Eigenvectors
Focus Questions
By the end of this section, you should be able to give precise and thorough answers to the questions listed below. You may want to keep these questions in mind to focus your thoughts as you complete the section.
What is an eigenvalue of a matrix?
What is an eigenvector of a matrix?
How do we find eigenvectors of a matrix corresponding to an eigenvalue?
How can the action of a matrix on an eigenvector be visualized?
Why do we study eigenvalues and eigenvectors?
What are discrete dynamical systems and how do we analyze the long-term behavior in them?
Subsection Application: The Google PageRank Algorithm
The World Wide Web is a vast collection of information, searchable via search engines. A search engine looks for pages that are of interest to the user. In order to be effective, a search engine needs to be able to identify those pages that are relevant to the search criteria provided by the user. This involves determining the relative importance of different web pages by ranking the results of thousands or millions of pages fitting the search criteria. For Google, the PageRank algorithm is their method and is βthe heart of our softwareβ as they say. It is this PageRank algorithm that we will learn about later in this section. Eigenvalues and eigenvectors play an important role in this algorithm.Subsection Introduction
Given a matrixDefinition 9.1.
Let
Preview Activity 9.1.
(a)
For each of the following parts, use the definition of an eigenvector to determine whether the given vector
(i)
(ii)
(iii)
(iv)
(b)
We now consider how we can find the eigenvectors corresponding to an eigenvalue using the definition. Suppose
(i)
Rewrite the vector equation
(ii)
After writing
(iii)
Similarly, determine whether the vector equation
Subsection Eigenvalues and Eigenvectors
Eigenvectors are especially useful in understanding the long-term behavior of dynamical systems, an example of which we will see shortly. The long-term behavior of a dynamical system is quite simple when the initial state vector is an eigenvector and this fact helps us analyze the system in general. To find eigenvectors, we are interested in determining the vectorsActivity 9.2.
(a)
Under what conditions on
(b)
The real number 0 is an eigenvalue of
(c)
Determine if 5 is an eigenvalue of the matrix
(d)
What are the two eigenvalues of the matrix
Activity 9.3.
(a)
For
(b)
Determine the eigenvalues of
(c)
Generalize your results from the above parts in the form of a theorem in the most general
Subsection Dynamical Systems
One real-life application of eigenvalues and eigenvectors is in analyzing the long-term behavior of discrete dynamical systems. A dynamical system is a system of variables whose values change with time. In discrete systems, the change is described by defining the values of the variables at timeActivity 9.4.
(a)
Consider a discrete dynamical system providing a simplified model of predator-prey interactions in biology, such as the system describing the populations of rabbits and foxes in a certain area. Suppose, for example, for a specific area the model is given by the following equations:
where
(i)
Suppose
(ii)
Consider the coefficients of the variables
(iii)
Let
where
(iv)
The transition matrix will help us simplify calculations of the population values. Note that equation (9.2) implies that
Can you guess the long-term behavior of the population values in each case? Are they both increasing? Decreasing? One increasing, one decreasing? How do the rabbit and fox populations compare?
Activity 9.5.
In this activity the matrix
(a)
Suppose that the initial state vector
(b)
The initial state vector
(c)
The initial state vector
(d)
Consider now an initial state vector of the form
(e)
Express the initial state vector
Subsection Examples
What follows are worked examples that use the concepts from this section.Example 9.2.
Let
(a)
Find all of the eigenvalues of
Solution.
Recall that a scalar
To solve the homogeneous system
Next we replace row two with
There will be a nontrivial solution to
Applying a little algebra shows that
So the eigenvalues of
(b)
Find a corresponding eigenvector for each eigenvalue found in part (a).
Solution.
Recall that an eigenvector for the eigenvalue
-
When
Technology shows that the reduced row echelon form of
isIf
then implies that is free and Choosing gives us the eigenvector As a check, note that -
When
Technology shows that the reduced row echelon form of
isIf
then implies that is free and Choosing gives us the eigenvector As a check, note that
Example 9.3.
Accurately predicting the weather has long been an important task. Meteorologists use science, mathematics, and technology to construct models that help us understand weather patterns. These models are very sophisticated, but we will consider only a simple model. Suppose, for example, we want to learn something about whether it will be wet or dry in Grand Rapids, Michigan. To do this, we might begin by collecting some data about weather conditions in Grand Rapids and then use that to make predictions. Information taken over the course of 2017 from the National Weather Service Climate Data shows that if it was dry (meaning no measurable precipitation, either rain or snow) on a given day in Grand Rapids, it would be dry the next day with a probability of 64% and wet with a probability of 36%. Similarly, if it was wet on a given day it would be dry the next day with a probability of 47% and dry with a probability of 53%. Assuming that this pattern is one that continues in the long run, we can develop a mathematical model to make predictions about the weather.
This data tells us how the weather transitions from one day to the next, and we can succinctly represent this data in a transition matrix:
Whether it is dry or wet on a given day is called the state of that day. So our transition matrix tells us about the transition between states. Notice that if
(a)
Calculate
Solution.
Here we have
This output tells us the different probabilities of whether it will be dry or wet the day following a dry day.
(b)
Calculate
Solution.
Here we have
This output tells us the different probabilities of whether it will be dry or wet the day following a wet day.
(c)
Calculate
Solution.
Here we have
This output tells us there is a 52% chance of it being dry and a 48% chance of it being wet following a day when there is a 30% chance of it being dry and a 70% chance of it being wet.
(d)
We can use the transition matrix to build a chain of probability vectors. We begin with an initial state, say it is dry on a given day. This initial state is represented by the initial state vector
This output vector tells us that the next day will be dry with a 64% probability and wet with a 36% probability. For each
Thus we create a sequence of vectors that tell us the probabilities of it being dry or wet on subsequent days. The vector
for
(i)
Starting with
Solution.
Technology shows that
We can see that our vectors
(ii)
What does the result of the previous part tell us about eigenvalues of
Solution.
Since our sequence seems to be converging to a vector
(iii)
Rewrite
We do this so we can use exact arithmetic. Let
Solution.
A matrix vector multiplication shows that
In other words,
so these fractions give the same results we obtained with our sequence of vectors
This is an example of a Markov process. Markov processes (named after Andrei Andreevich Markov) are widely used to model phenomena in biology, chemistry, business, physics, engineering, the social sciences, and much more. More specifically,
Definition 9.4.
A Markov process is a process in which the probability of the system being in a given state depends only on the previous state.
If
the total number of observations remains fixed (this is reflected in the fact that the sum of the entries in each column of the matrix
is 1), andno observation is lost (this means the entries in the matrix
cannot be negative).
Subsection Summary
We learned about eigenvalues and eigenvectors of a matrix in this section.A scalar
is an eigenvalue (or characteristic value) of a square matrix if there is a non-zero vector so thatA non-zero vector
is an eigenvector (or characteristic vector) of a square matrix if there is a scalar so thatTo find the eigenvectors of an
matrix corresponding to an eigenvalue we determine the non-trivial solutions to where is the identity matrix.We study eigenvectors and eigenvalues because the eigenvectors tell us quite a bit about the transformation corresponding to the matrix. These eigenvectors arise in many applications in physics, chemistry, statistics, economics, biology, sociology and other areas, and help understand the long-term behavior of dynamical systems.
-
A dynamical system is a system of variables whose values change with time. In linear dynamical systems, the change in the state vector from one time period to the next is expressed by matrix multiplication by the transition matrix
The eigenvectors of provide us a simple method to express the state vector at any given time period in terms of the initial state vector. Specifically, if the initial state vector is where are eigenvectors corresponding to eigenvalues we have
Exercises Exercises
1.
For each of the following matrix-vector pairs, determine whether the given vector is an eigenvector of the matrix.
(a)
(b)
(c)
2.
For each of the following matrix-eigenvalue pairs, determine an eigenvector of
(a)
(b)
(c)
(d)
3.
For each of the following matrix-
(a)
(b)
(c)
(d)
4.
For a matrix
(a)
(b)
(c)
5.
In this problem we consider a discrete dynamical system that forms what is called a Markov chain (see Definition 9.4) which models the number of students attending and skipping a linear algebra class in a semester. Assume the course starts with 1,000,000 students on day 0. For any given class day, 90% of the students who attend a class attend the next class (and 10% of these students skip next class) while only 30% of those absent are there the next time (and 70% of these students continue skipping class).
(a)
We know that there will be 900,000 students in class on the second day and 100,000 students skipping class. On the third day, 90% of the 900,000 students (attenders) and 30% of the 100,000 students (skippers) will come back to class. Therefore, 840,000 students will attend class on the third day. On the other hand, 10% of 900,000 students and 70% of 100,000 students skip class on the third day, for a total of 160,000 students skipping class. We can use variables to represent these numbers. Let
(b)
Find a linear expression for
(c)
Let
6.
Label each of the following statements as True or False. Provide justification for your response.
(a) True/False.
The number 0 cannot be an eigenvalue.
(b) True/False.
The
(c) True/False.
If
(d) True/False.
If
(e) True/False.
If
(f) True/False.
If
(g) True/False.
A projection matrix satisfies
(h) True/False.
If
(i) True/False.
If
(j) True/False.
If
(k) True/False.
A matrix
Subsection Project: Understanding the PageRank Algorithm
Sergey Brin and Lawrence Page, the founders of Google, decided that the importance of a web page can be judged by the number of links to it as well as the importance of those pages. It is this idea that leads to the PageRank algorithm.β17β Google uses this algorithm (and others) to order search engine results. According to Google:β18βPageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites.To rank how βimportantβ a website is, we need to make some assumptions. We assume that a person visits a page and then surfs the web by selecting a link from that page β all links on a given page are assigned the same probability of being chosen. As an example, assume a small set of seven pages 1, 2, 3, 4, 5, 6, and 7 with links between the pages given by the arrows as shown in Figure 9.5.β19β So, for example, there is a hyperlink from page 4 to page 3, but no hyperlink in the opposite direction. If a web surfer starts on page 5, then there is probability of
Definition 9.6.
A stochastic matrix is a matrix in which entries are nonnegative and the sum of the entries in every column is one.
Project Activity 9.6.
Use appropriate technology to do the following. Choose several different initial state vectors geogebra.org/m/b3dybnux
.
The importance of a webpage may be measured by the relative size of the corresponding entry in the steady-state vector for an appropriately chosen Markov chain.
Project Activity 9.7.
Show that the limiting vector you found in Project Activity 9.6 is an eigenvector of
Project Activity 9.8.
(a)
Determine the transition matrix for our seven page internet with this adjustment.
(b)
Approximate the steady-state vector for this adjusted matrix so that the entries are accurate to four decimal places. Use any appropriate technology to row reduce matrices.
(c)
According to this adjusted model, which web page is now the most important? Why? Does this seem reasonable? Why?
Project Activity 9.9.
(a)
Explain why
is the transition matrix for this five page internet. (Keep in mind the adjustment we made for dangling pages.)
(b)
Start with different initial state vectors geogebra.org/m/b3dybnux
.
Definition 9.8.
A stochastic matrix is regular if its transition matrix
Theorem 9.9.
Assume
exists and is a stochastic matrix.-
For any vector
for the same vector
The columns of
are the same vectorThe vector
is the unique eigenvector of whose entries sum to 1.If
is an eigenvalue of not equal to 1, then
Project Activity 9.10.
Return to the seven page internet in Figure 9.5.
(a)
Find the Google matrix
(b)
Approximate, to four decimal places, the steady-state vector for this internet.
(c)
What is the relative rank of each page in this internet, and approximately what percentage of time does a random user spend on each page.
ams.org/samplings/feature-column/fcarc-pagerank
and faculty.winthrop.edu/polaskit/spring11/math550/chapter.pdf
.