Introduction to Eigenvalues and Eigenvectors

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 matrix

A,

for some special non-zero vectors

v

the action of

A

v

will be same as scalar multiplication, i.e.,

A v = λ v

for some scalar

λ .

Geometrically, this means that the transformation

T

defined by

T (x) = A x

simply stretches or contracts the vector

v

but does not change its direction. Such a nonzero vector is called an eigenvector of

A,

while the scalar

λ

is called the corresponding eigenvalue of

A .

The eigenvectors of a matrix tell us quite a bit about the transformation the matrix defines.

🔗

Eigenvalues and eigenvectors are used in many applications. Social media like Facebook and Google use eigenvalues to determine the influence of individual members on the network (which can affect advertising) or to rank the importance of web pages. Eigenvalues and eigenvectors appear in quantum physics, where atomic and molecular orbitals can be defined by the eigenvectors of a certain operator. They appear in principal component analysis, used to study large data sets, to diagonalize certain matrices and determine the long term behavior of systems as a result, and in the important singular value decomposition of a matrix. Matrices with real entries can have real or complex eigenvalues, and complex eigenvalues reveal a rotation that is encoded in every real matrix with complex eigenvalues which allows us to better understand certain matrix transformations.

🔗

Definition 9.1.

Let $A$ be an $n \times n$ matrix. A non-zero vector $x$ is an eigenvector (or characteristic vector) of $A$ if there is a scalar $λ$ such that $A x = λ x .$ The scalar $λ$ is an eigenvalue (or characteristic value) of $A .$

🔗

For example,

v = [\begin{matrix} 1 \\ 1 \end{matrix}]

is an eigenvector of

A = [\begin{array}{cc} 2 & 1 \\ 3 & 0 \end{array}]

corresponding to the eigenvalue

λ = 3

because

A v = [\begin{matrix} 3 \\ 3 \end{matrix}],

which is equal to

3 v .

On the other hand,

w = [\begin{matrix} 1 \\ 2 \end{matrix}]

is not an eigenvector of

A = [\begin{array}{cc} 2 & 1 \\ 3 & 0 \end{array}]

because

A w = [\begin{matrix} 4 \\ 3 \end{matrix}],

which is not a multiple of

w .

🔗

Preview Activity 9.1.

🔗

(a)

For each of the following parts, use the definition of an eigenvector to determine whether the given vector $v$ is an eigenvector for the given matrix $A .$ If it is, determine the corresponding eigenvalue.

🔗

(i)

$A = [\begin{array}{cc} 3 & 2 \\ 3 & 8 \end{array}],$ $v = [\begin{array}{r} - 2 \\ 1 \end{array}]$

🔗

(ii)

$A = [\begin{array}{cr} 2 & 0 \\ 0 & - 3 \end{array}],$ $v = [\begin{matrix} 0 \\ 1 \end{matrix}]$

🔗

(iii)

$A = [\begin{array}{cc} 3 & 2 \\ 3 & 8 \end{array}],$ $v = [\begin{matrix} 1 \\ 1 \end{matrix}]$

🔗

(iv)

$A = [\begin{array}{cc} 1 & 2 \\ 2 & 4 \end{array}],$ $v = [\begin{array}{r} - 2 \\ 1 \end{array}]$

🔗

(b)

We now consider how we can find the eigenvectors corresponding to an eigenvalue using the definition. Suppose $A = [\begin{array}{cr} 6 & - 2 \\ 2 & 1 \end{array}] .$ We consider whether we can find eigenvectors corresponding to eigenvalues 3, and 5. Effectively, this will help us determine whether 3 and/or 5 are eigenvalues of $A .$

🔗

(i)

Rewrite the vector equation $A v = 5 v$ where $v = [\begin{matrix} x \\ y \end{matrix}]$ as a vector equation.

🔗

(ii)

After writing $5 v$ as $5 I v$ where $I$ is the identity matrix, rearrange the variables to turn this vector equation into the homogeneous matrix equation $B v = 0$ where $B = [\begin{array}{cr} 1 & - 2 \\ 2 & - 4 \end{array}] .$ If possible, find a non-zero (i.e. a non-trivial) solution to $B v = 0 .$ Explain what this means about 5 being an eigenvalue of $A$ or not.

🔗

(iii)

Similarly, determine whether the vector equation $A v = 3 v$ has non-zero solutions. Using your result, determine whether 3 is an eigenvalue of $A$ or not.

🔗

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 vectors

x

for which

A x

has the same direction as

x .

This will happen when

A x = λ x

🔗

for some scalar

λ .

Of course,

A x = λ x

when

x = 0

for every

A

and every

λ,

but that is uninteresting. So we really want to consider when there is a non-zero vector

x

so that

A x = λ x .

This prompts the definition of eigenvectors and eigenvalues as in Definition 9.1

🔗

In order for a matrix

A

to have an eigenvector, one condition

A

must satisfy is that

A

has to be a square matrix, i.e. an

n \times n

matrix. We will find that each

n \times n

matrix has only finitely many eigenvalues.

🔗

The terms eigenvalue and eigenvector seem to come from Hilbert, using the German “eigen” (roughly translated as “own”, “proper”, or “characteristic”) to emphasize how eigenvectors and eigenvalues are connected to their matrices. To find the eigenvalues and eigenvectors of an

n \times n

matrix

A,

we need to find the solutions to the equation

A x = λ x .

🔗

In Preview Activity 9.1, we considered this equation for

A = [\begin{array}{cr} 6 & - 2 \\ 2 & 1 \end{array}]

and

λ = 5 .

The homogeneous matrix equation we came up with was

[\begin{array}{cr} 1 & - 2 \\ 2 & - 4 \end{array}] x = 0 .

🔗

To see the relationship between this homogeneous matrix equation and the eigenvalue-eigenvector equation better, let us consider the eigenvector equation using matrix algebra:

\begin{aligned} A x & = λ x \\ A x - λ x & = 0 \\ A x - λ I_{n} x & = 0 \\ (A - λ I_{n}) x & = 0, \end{aligned}

🔗

where

I_{n}

is the

n \times n

identity matrix. Notice that this description matches the homogenous equation matrix example above since we simply subtracted 5 from the diagonal terms of the matrix

A .

Hence, to find eigenvalues, we need to find the values of

λ

so that the homogeneous equation

(A - λ I_{n}) x = 0

has non-trivial solutions.

🔗

Activity 9.2.

🔗

(a)

Under what conditions on $A - λ I_{n}$ will the matrix equation $(A - λ I_{n}) x = 0$ have non-trivial solutions? Describe at least two different but equivalent conditions.

🔗

(b)

The real number 0 is an eigenvalue of $A = [\begin{array}{cc} 1 & 2 \\ 2 & 4 \end{array}] .$ Check that your criteria in the previous part agrees with this result.

🔗

(c)

Determine if 5 is an eigenvalue of the matrix $A = [\begin{array}{cc} 1 & 2 \\ 2 & 4 \end{array}]$ using your criterion above.

🔗

(d)

What are the two eigenvalues of the matrix $A = [\begin{array}{cc} 3 & 2 \\ 4 & 5 \end{array}] ?$

🔗

Since an eigenvector of

A

corresponding to eigenvalue

λ

is a non-trivial solution to the homogeneous equation

(A - λ I_{n}) x = 0,

the eigenvalues

λ

which work are those for which the matrix

A - λ I_{n}

has linearly dependent columns, or for which the row echelon form of the matrix

A - λ I_{n}

does not have a pivot in every column. When we need to test if a specific

λ

is an eigenvalue, this method works fine. However, finding which

λ

's will work in general involves row reducing a matrix with

λ

's subtracted on the diagonal algebraically. For certain types of matrices, this method still provides us the eigenvalues quickly. For general matrices though, row reducing algebraically is not efficient. We will later see an algebraic method which uses the determinants to find the eigenvalues.

🔗

Activity 9.3.

🔗

(a)

For $λ$ to be an eigenvalue of $A,$ we noted that $A - λ I_{n}$ must have a non-pivot column. Use this criterion to explain why $A = [\begin{array}{rc} - 2 & 2 \\ 0 & 4 \end{array}]$ has eigenvalues $λ = - 2$ and $λ = 4 .$

🔗

(b)

Determine the eigenvalues of $A = [\begin{array}{ccrc} 3 & 0 & 1 & 0 \\ 0 & 2 & - 1 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 1 \end{array}] .$

🔗

(c)

Generalize your results from the above parts in the form of a theorem in the most general $n \times n$ case.

🔗

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 time

t + 1

in terms of the values at time

t .

For example, the discrete dynamical system

y_{t + 1} = y_{t} + t

🔗

relates the value of

y

at time

t + 1

to the value of

y

at time

t .

This is in contrast with a differential equation¹⁶ such as

\frac{d y}{d t} = y + t,

🔗

which describes the instantaneous rate of change of

y (t)

in terms of

y

and

t .

🔗

Discrete dynamical systems can be used in population modeling to provide a simplified model of predator-prey interactions in biology (see Activity 9.4). Other applications include Markov chains (see Exercise 5), age structured population growth models, distillation of a binary ideal mixture of two liquids, cobweb model in economics concerning the interaction of supply and demand for a single good, queuing theory and traffic flow.

🔗

Eigenvectors can be used to analyze the long-term behavior of dynamical systems.

🔗

Activity 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:

\begin{matrix} (9.1) & \begin{aligned} r_{k + 1} & = & 1.14 r_{k} & - & 0.12 f_{k} \\ f_{k + 1} & = & 0.08 r_{k} & + & 0.86 f_{k} \end{aligned} \end{matrix}

where $r_{i}$ represents the number of rabbits in the area $i$ years after a starting time value, and $f_{i}$ represents the number of foxes in year $i .$ We use $r_{0}, f_{0}$ to denote the initial population values.

🔗

(i)

Suppose $r_{k} = 300$ and $f_{k} = 100$ for one year. Calculate rabbit and fox population values for the next year. In other words, find $r_{k + 1}, f_{k + 1}$ values.

🔗

(ii)

Consider the coefficients of the variables $r_{k}, f_{k}$ in the the system of equations in (9.1). Can you explain the reasoning behind the signs and absolute sizes of the coefficients from the story that it models?

🔗

(iii)

Let $x_{k} = [\begin{matrix} r_{k} \\ f_{k} \end{matrix}] .$ The vector $x_{k}$ is called the state vector of the system at time $k,$ because it describes the state of the whole system at time $k .$ We can rewrite the system of equations in (9.1) as a matrix-vector equation in terms of the state vectors at time $k$ and $k + 1 .$ More specifically, the equation will be of the form

\begin{matrix} (9.2) & x_{k + 1} = A x_{k} \end{matrix}

where $A = [\begin{array}{cr} 1.14 & - 0.12 \\ 0.08 & 0.86 \end{array}] .$ We will call this matrix the transition matrix of the system. Check that $A [\begin{matrix} 300 \\ 100 \end{matrix}]$ gives us the population values you calculated in the first part above.

🔗

(iv)

The transition matrix will help us simplify calculations of the population values. Note that equation (9.2) implies that $x_{1} = A x_{0},$ $x_{2} = A x_{1},$ $x_{3} = A x_{2},$ and so on. This is a recursive method to find the population values as each year's population values depend on the previous year's population values. Using this approach, calculate $x_{k}$ for $k$ values up to 5 corresponding to the following three different initial rabbit-fox population values (all in thousands):

r_{0} = 300, f_{0} = 100

r_{0} = 100, f_{0} = 200

r_{0} = 1200, f_{0} = 750

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?

🔗

A dynamical system is a system of variables whose values change with time. In Activity 9.4, we considered the discrete dynamical system modeling the rabbit and fox population in an area, which is an example of a predator-prey system. The system was given by the equations from (9.1), where

r_{i}

represented the number of rabbits in the area

i

years after a starting time value, and

f_{i}

represented the number of foxes in year

i .

In this notation,

r_{0}, f_{0}

corresponded to the initial population values.

🔗

As we saw in Activity 9.4, if we define the state vector as

x_{k} = [\begin{matrix} r_{k} \\ f_{k} \end{matrix}],

the system of equations representing the dynamical system can be expressed as

\begin{matrix} (9.3) & x_{k + 1} = A x_{k} \end{matrix}

🔗

where

A = [\begin{array}{cr} 1.14 & - 0.12 \\ 0.08 & 0.86 \end{array}]

represents the transition matrix. Note that equation (9.3) encodes infinitely many equations including

x_{1} = A x_{0},

x_{2} = A x_{1},

x_{3} = A x_{2},

and so on. This is a recursive formula for the population values as each year's population values are expressed in terms of the previous year's population values. If we want to calculate

x_{10},

this formula requires first finding the population values for years 1-9. However, we can obtain a non-recursive formula using matrix algebra. If we substitute

x_{1} = A x_{0}

into

x_{2} = A x_{1}

and simplify, we find that

x_{2} = A x_{1} = A (A x_{0}) = A^{2} x_{0} .

🔗

Similarly, substituting

x_{2} = A^{2} x_{1}

into the formula for

x_{3}

gives

x_{3} = A x_{2} = A (A^{2} x_{0}) = A^{3} x_{0} .

🔗

This process can be continued inductively to show that

\begin{matrix} (9.4) & x_{k} = A^{k} x_{0} \end{matrix}

🔗

for every

k

value. So to find the population values at any year

k,

we only need to know the initial state vector

x_{0} .

🔗

Activity 9.5.

In this activity the matrix $A$ is the transition matrix for the rabbit and fox population model,

A = [\begin{array}{cr} 1.14 & - 0.12 \\ 0.08 & 0.86 \end{array}] .

🔗

(a)

Suppose that the initial state vector $x_{0}$ is an eigenvector of $A$ corresponding to eigenvalue $λ .$ In this case, explain why $x_{1} = λ x_{0}$ and $x_{2} = λ^{2} x_{0} .$ Find the formula for $x_{k}$ in terms of $λ, k$ and $x_{0}$ by applying equation (9.3) iteratively.

🔗

(b)

The initial state vector $x_{0} = [\begin{matrix} 300 \\ 100 \end{matrix}]$ is an eigenvector of $A .$ Find the corresponding eigenvalue and, using your formula from (a) for $x_{k}$ in terms of $λ, k$ and $x_{0},$ find the state vector $x_{k}$ in this case.

🔗

(c)

The initial state vector $x_{0} = [\begin{matrix} 100 \\ 200 \end{matrix}]$ is an eigenvector of $A .$ Find the corresponding eigenvalue and, using your formula from (a) for $x_{k}$ in terms of $λ, k$ and $x_{0},$ find the state vector $x_{k}$ in this case.

🔗

(d)

Consider now an initial state vector of the form $x_{0} = a v_{0} + b w_{0}$ where $a, b$ are constants, $v_{0}$ is an eigenvector corresponding to eigenvalue $λ_{1}$ and $w_{0}$ corresponding to eigenvalue $λ_{2}$ ( $v_{0}$ and $w_{0}$ are not necessarily the eigenvectors from parts (b) and (c)). Use matrix algebra and equation (9.4) to explain why $x_{k} = a λ_{1}^{k} v_{0} + b λ_{2}^{k} w_{0} .$

🔗

(e)

Express the initial state vector $x_{0} = [\begin{matrix} 1200 \\ 750 \end{matrix}]$ as a linear combination of the eigenvectors $v_{0} = [\begin{matrix} 300 \\ 100 \end{matrix}], w_{0} = [\begin{matrix} 100 \\ 200 \end{matrix}]$ and use your result from the previous part to find a formula for $x_{k} .$ What happens to the population values as $k \to \infty ?$

🔗

As you discovered in Activity 9.5, we can use linearly independent eigenvectors of the transition matrix to find a closed formula for the state vector of a dynamical system, as long as the initial state vector can be expressed as a linear combination of the eigenvectors.

🔗

Subsection Examples

🔗

What follows are worked examples that use the concepts from this section.

🔗

Example 9.2.

Let $A = [\begin{array}{cc} 1 & 2 \\ 2 & 4 \end{array}] .$

🔗

(a)

Find all of the eigenvalues of $A .$

Solution.

Recall that a scalar $λ$ is a eigenvalue for $A$ if there is a nonzero vector $x$ such that $A x = λ x$ or $(A - λ I_{2}) x = 0 .$ For this matrix $A,$ we have

A - λ I_{2} = [\begin{array}{cc} 1 - λ & 2 \\ 2 & 4 - λ \end{array}] .

To solve the homogeneous system $(A - λ I_{2}) x = 0,$ we row reduce $A - λ I_{2} .$ To do this, we first interchange rows to get the following matrix that is row equivalent to $A - λ I_{2}$ (we do this to ensure that we have a nonzero entry in the first row and column)

[\begin{array}{cc} 2 & 4 - λ \\ 1 - λ & 2 \end{array}] .

Next we replace row two with $\frac{1}{2} (1 - λ)$ times row one minus row two to obtain the row equivalent matrix

[\begin{array}{cc} 2 & 4 - λ \\ 0 & \frac{1}{2} (4 - λ) (1 - λ) - 2 \end{array}] .

There will be a nontrivial solution to $(A - λ I_{2}) x = 0$ if there is a row of zeros in this row echelon form. Thus, we look for values of $λ$ that make

\frac{1}{2} (4 - λ) (1 - λ) - 2 = 0 .

Applying a little algebra shows that

\begin{aligned} \frac{1}{2} (4 - λ) (1 - λ) - 2 & = 0 \\ (4 - λ) (1 - λ) - 4 & = 0 \\ λ^{2} - 5 λ & = 0 \\ λ (λ - 5) & = 0 . \end{aligned}

So the eigenvalues of $A$ are $λ = 0$ and $λ = 5 .$

🔗

(b)

Find a corresponding eigenvector for each eigenvalue found in part (a).

Solution.

Recall that an eigenvector for the eigenvalue $λ$ is a nonzero vector $x$ such that $(A - λ I_{2}) x = 0 .$ We consider each eigenvalue in turn.

When $λ = 0,$

$A - 0 I_{2} = A = [\begin{array}{cc} 1 & 2 \\ 2 & 4 \end{array}] .$

Technology shows that the reduced row echelon form of $A$ is

$[\begin{array}{cc} 1 & 2 \\ 0 & 0 \end{array}] .$

If $x = [\begin{matrix} x_{1} \\ x_{2} \end{matrix}],$ then $A x = 0$ implies that $x_{2}$ is free and $x_{1} = - 2 x_{2} .$ Choosing $x_{2} = 1$ gives us the eigenvector $[\begin{array}{r} - 2 \\ 1 \end{array}] .$ As a check, note that

$[\begin{array}{cc} 1 & 2 \\ 2 & 4 \end{array}] [\begin{array}{r} - 2 \\ 1 \end{array}] = [\begin{matrix} 0 \\ 0 \end{matrix}] .$
When $λ = 5,$

$A - 5 I_{2} = [\begin{array}{rr} - 4 & 2 \\ 2 & - 1 \end{array}] .$

Technology shows that the reduced row echelon form of $A - 5 I_{2}$ is

$[\begin{array}{cr} 1 & - \frac{1}{2} \\ 0 & 0 \end{array}] .$

If $x = [\begin{matrix} x_{1} \\ x_{2} \end{matrix}],$ then $(A - 5 I_{2}) x = 0$ implies that $x_{2}$ is free and $x_{1} = \frac{1}{2} x_{2} .$ Choosing $x_{2} = 2$ gives us the eigenvector $[\begin{matrix} 1 \\ 2 \end{matrix}] .$ As a check, note that

$[\begin{array}{cr} 1 & - \frac{1}{2} \\ 0 & 0 \end{array}] [\begin{matrix} 1 \\ 2 \end{matrix}] = [\begin{matrix} 0 \\ 0 \end{matrix}] .$

🔗

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:

\begin{matrix} (9.5) & T = [\begin{array}{cc} 0.64 & 0.47 \\ 0.36 & 0.53 \end{array}] . \end{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 $T = [t_{i j}],$ then the probability of moving from state $j$ to state $i$ is given by $t_{i j} .$ We can represent a state by a vector: the vector $[\begin{matrix} 1 \\ 0 \end{matrix}]$ represents the dry state and the vector $[\begin{matrix} 0 \\ 1 \end{matrix}]$ represents the wet state.

🔗

(a)

Calculate $T [\begin{matrix} 1 \\ 0 \end{matrix}] .$ Interpret the meaning of this output.

Solution.

Here we have

T [\begin{matrix} 1 \\ 0 \end{matrix}] = [\begin{array}{cc} 0.64 & 0.47 \\ 0.36 & 0.53 \end{array}] [\begin{matrix} 1 \\ 0 \end{matrix}] = [\begin{matrix} 0.64 \\ 0.36 \end{matrix}] .

This output tells us the different probabilities of whether it will be dry or wet the day following a dry day.

🔗

(b)

Calculate $T [\begin{matrix} 0 \\ 1 \end{matrix}] .$ Interpret the meaning of this output.

Solution.

Here we have

T [\begin{matrix} 0 \\ 1 \end{matrix}] = [\begin{array}{cc} 0.64 & 0.47 \\ 0.36 & 0.53 \end{array}] [\begin{matrix} 0 \\ 1 \end{matrix}] = [\begin{matrix} 0.47 \\ 0.53 \end{matrix}] .

This output tells us the different probabilities of whether it will be dry or wet the day following a wet day.

🔗

(c)

Calculate $T [\begin{matrix} 0.3 \\ 0.7 \end{matrix}] .$ Interpret the meaning of this output.

Solution.

Here we have

T [\begin{matrix} 0.3 \\ 0.7 \end{matrix}] = [\begin{array}{cc} 0.64 & 0.47 \\ 0.36 & 0.53 \end{array}] [\begin{matrix} 0.3 \\ 0.7 \end{matrix}] \approx [\begin{matrix} 0.52 \\ 0.48 \end{matrix}] .

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 $x_{0} = [\begin{matrix} 1 \\ 0 \end{matrix}] .$ The probabilities that it will be dry or wet the following day are given by the vector

x_{1} = T x_{0} = [\begin{matrix} 0.64 \\ 0.36 \end{matrix}] .

This output vector tells us that the next day will be dry with a 64% probability and wet with a 36% probability. For each $k \geq 1,$ we let

\begin{matrix} (9.6) & x_{k} = T x_{k - 1} . \end{matrix}

Thus we create a sequence of vectors that tell us the probabilities of it being dry or wet on subsequent days. The vector $x_{k}$ is called the state vector of the system at time $k,$ because it describes the state of the whole system at time $k .$ We can rewrite the system of equations in (9.1) as a matrix-vector equation in terms of the state vectors at time $k$ and $k + 1 .$ More specifically, the equation will be of the form

\begin{matrix} (9.7) & x_{k + 1} = T x_{k} \end{matrix}

for $k \geq 0 .$

🔗

(i)

Starting with $x_{0} = [\begin{matrix} 1 \\ 0 \end{matrix}],$ use appropriate technology to calculate $x_{k}$ for $k$ values up to 10. Round to three decimal places. What do you notice about the entries?

Solution.

Technology shows that

\begin{array}{ll} x_{1} = [\begin{array}{c} 0.640 \\ 0.360 \end{array}] & x_{2} = [\begin{array}{c} 0.579 \\ 0.421 \end{array}] \\ x_{3} = [\begin{array}{c} 0.568 \\ 0.432 \end{array}] & x_{4} = [\begin{array}{c} 0.567 \\ 0.433 \end{array}] \\ x_{5} = [\begin{array}{c} 0.566 \\ 0.434 \end{array}] & x_{6} = [\begin{array}{c} 0.566 \\ 0.434 \end{array}] \\ x_{7} = [\begin{array}{c} 0.566 \\ 0.434 \end{array}] & x_{8} = [\begin{array}{c} 0.566 \\ 0.434 \end{array}] \\ x_{9} = [\begin{array}{c} 0.566 \\ 0.434 \end{array}] & x_{10} = [\begin{array}{c} 0.566 \\ 0.434 \end{array}] . \end{array}

We can see that our vectors $x_{k}$ are essentially the same as we let $k$ increase.

🔗

(ii)

What does the result of the previous part tell us about eigenvalues of $T ?$ Explain.

Solution.

Since our sequence seems to be converging to a vector $x$ satisfying $T x = x,$ we conclude that 1 is an eigenvalue of $T .$

🔗

(iii)

Rewrite $T$ as

T = [\begin{array}{cc} \frac{64}{100} & \frac{47}{100} \\ \frac{36}{100} & \frac{53}{100} \end{array}] .

We do this so we can use exact arithmetic. Let $x = [\begin{matrix} \frac{47}{83} \\ \frac{36}{83} \end{matrix}] .$ What is $T x ?$ (Use exact arithmetic, no decimals.) Explain how $x$ is related to the previous two parts of this problem. What does the vector $x$ tells us about weather in Grand Rapids?

Solution.

A matrix vector multiplication shows that

T x = [\begin{array}{cc} \frac{64}{100} & \frac{47}{100} \\ \frac{36}{100} & \frac{53}{100} \end{array}] [\begin{matrix} \frac{47}{83} \\ \frac{36}{83} \end{matrix}] = [\begin{matrix} \frac{47}{83} \\ \frac{36}{83} \end{matrix}] .

In other words, $x$ is an eigenvector for $T$ with eigenvalue 1. Notice that

\frac{47}{83} \approx 0.566 and \frac{36}{83} \approx 0.434,

so these fractions give the same results we obtained with our sequence of vectors $x_{k} .$ These vectors provide a steady-state vector for Grand Rapids weather. In other words, if there is a $56.6 %$ chance of it being dry on a given day in Grand Rapids, then there is a $56.6 %$ chance it will be dry again the next day.

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 $x_{0}$ is a vector which represents the initial state of a Markov process, then there is a matrix $T$ (the transition matrix) such that the state of the system after one iteration is given by the vector $T x_{0} .$ This produces a chain of state vectors $T x_{0},$ $T^{2} x_{0},$ $T^{3} x_{0},$ etc., where the state of the system after $n$ iterations is given by $T^{n} x_{0} .$ Such a chain of vectors is called a Markov chain. A Markov process is characterized by two properties:

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 $T$ is 1), and
no observation is lost (this means the entries in the matrix $T$ 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 $A$ if there is a non-zero vector $x$ so that $A x = λ x .$
A non-zero vector $x$ is an eigenvector (or characteristic vector) of a square matrix $A$ if there is a scalar $λ$ so that $A x = λ x .$
To find the eigenvectors of an $n \times n$ matrix $A$ corresponding to an eigenvalue $λ,$ we determine the non-trivial solutions to $(A - λ I_{n}) x = 0$ where $I_{n}$ is the $n \times n$ 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 $A .$ The eigenvectors of $A$ 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 $x_{0} = a v_{0} + b w_{0}$ where $v_{0}, w_{0}$ are eigenvectors corresponding to eigenvalues $λ_{1}, λ_{2},$ we have

$x_{k} = A^{k} x_{0} = λ_{1}^{k} a v_{0} + λ_{2}^{k} b w_{0} .$

🔗

Exercises Exercises

🔗

1.

For each of the following matrix-vector pairs, determine whether the given vector is an eigenvector of the matrix.

🔗

(a)

$A = [\begin{array}{cc} 1 & 2 \\ 4 & 3 \end{array}],$ $v = [\begin{array}{r} 1 \\ - 1 \end{array}]$

🔗

(b)

$A = [\begin{array}{cc} 1 & 2 \\ 0 & 3 \end{array}],$ $v = [\begin{array}{r} 1 \\ 1 \end{array}]$

🔗

(c)

$A = [\begin{array}{rcc} 2 & 1 & 0 \\ 0 & 1 & 0 \\ - 1 & 0 & 1 \end{array}],$ $v = [\begin{array}{r} - 1 \\ 0 \\ 1 \end{array}]$

🔗

2.

For each of the following matrix-eigenvalue pairs, determine an eigenvector of $A$ for the given eigenvalue.

🔗

(a)

$A = [\begin{array}{rc} 1 & 2 \\ - 1 & 4 \end{array}],$ $λ = 3$

🔗

(b)

$A = [\begin{array}{cc} 1 & 4 \\ 1 & 1 \end{array}],$ $λ = 3$

🔗

(c)

$A = [\begin{array}{rcc} - 1 & 4 & 1 \\ 3 & 3 & 0 \\ 0 & 0 & 1 \end{array}],$ $λ = 5$

🔗

(d)

$A = [\begin{array}{cccc} 4 & 0 & 0 & 0 \\ 0 & 2 & 0 & 2 \\ 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 \end{array}],$ $λ = 4$

🔗

3.

For each of the following matrix- $λ$ pairs, determine whether the given $λ$ will work as an eigenvalue. You do not need to find an eigenvector as long you can justify if $λ$ is a valid eigenvalue or not.

🔗

(a)

$A = [\begin{array}{cc} 4 & 3 \\ 4 & 8 \end{array}],$ $λ = 2$

🔗

(b)

$A = [\begin{array}{cr} 4 & - 2 \\ 2 & - 1 \end{array}],$ $λ = 0$

🔗

(c)

$A = [\begin{array}{rc} 1 & 2 \\ - 1 & 4 \end{array}],$ $λ = - 1$

🔗

(d)

$A = [\begin{array}{rr} 0 & - 2 \\ - 1 & 1 \end{array}],$ $λ = - 2$

🔗

4.

For a matrix $A$ with eigenvector $v_{1} = [\begin{matrix} 1 \\ 1 \end{matrix}]$ with eigenvalue $λ_{1} = 2,$ and eigenvector $v_{2} = [\begin{matrix} 1 \\ 2 \end{matrix}]$ with eigenvalue $λ_{2} = - 1,$ determine the value of the following expressions using matrix-vector product properties:

🔗

(a)

$A (2 v_{1} + 3 v_{2})$

🔗

(b)

$A (A (v_{1} + 2 v_{2}))$

🔗

(c)

$A^{20} (4 v_{1} - 2 v_{2})$

🔗

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 $a_{n}$ represent the number of students attending class $n$ days after first day. So $a_{0} = 1, 000, 000, a_{1} = 900, 000, a_{2} = 840, 000 .$ Let $s_{n}$ represent the students skipping class. So $s_{0} = 0, s_{1} = 100, 000, s_{2} = 160, 000 .$ Find $a_{3}, s_{3}, a_{4}, s_{4} .$

🔗

(b)

Find a linear expression for $a_{k + 1}$ in terms of the previous day values, $a_{k}$ and $s_{k},$ using the story given in the problem. Similarly, express $s_{k + 1}$ in terms of $a_{k}$ and $s_{k} .$

🔗

(c)

Let $b_{k}$ represent the state vector: $x_{k} = [\begin{matrix} a_{k} \\ s_{k} \end{matrix}] .$ It describes the state of the whole system (students attending class and skipping class) in one vector. For example, $x_{0} = [\begin{matrix} 1, 000, 000 \\ 0 \end{matrix}]$ is the initial state. The state next day is $x_{1} = [\begin{matrix} 900, 000 \\ 100, 000 \end{matrix}] .$ Using your answer to the previous part, find a matrix $A$ which describes how the system changes from one day to the other so that $x_{k + 1} = A x_{k} .$

🔗

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 $0$ vector cannot be an eigenvector.

🔗

(c) True/False.

If $v$ is an eigenvector of $A,$ then so is $2 v .$

🔗

(d) True/False.

If $v$ is an eigenvector of $A,$ then it is also an eigenvector of $A^{2} .$

🔗

(e) True/False.

If $v$ and $u$ are eigenvectors of $A$ with the same eigenvalue, then $v + u$ is also an eigenvector with the same eigenvalue.

🔗

(f) True/False.

If $λ$ is an eigenvalue of $A,$ then $λ^{2}$ is an eigenvalue of $A^{2} .$

🔗

(g) True/False.

A projection matrix satisfies $P^{2} = P .$ If $P$ is a projection matrix, then the eigenvalues of $P$ can only be 0 and 1.

🔗

(h) True/False.

If $λ$ is an eigenvalue of an $n \times n$ matrix $A,$ then $1 + λ$ is an eigenvalue of $I_{n} + A .$

🔗

(i) True/False.

If $λ$ is an eigenvalue of two matrices $A$ and $B$ of the same size, then $λ$ is an eigenvalue of $A + B .$

🔗

(j) True/False.

If $v$ is an eigenvector of two matrices $A$ and $B$ of the same size, then it is also an eigenvector of $A + B .$

🔗

(k) True/False.

A matrix $A$ has 0 as an eigenvalue if and only if $A$ has linearly dependent columns.

🔗

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.¹⁷ Google uses this algorithm (and others) to order search engine results. According to Google:¹⁸

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.¹⁹ 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

\frac{1}{2}

that this person will surf to page 6 and a probability of

\frac{1}{2}

that the surfer will move to page 4. If there is no link leaving a page, as in the case of page 3, then the probability of remaining there is 1.

🔗

To rank pages, we need to know how likely it is that a surfer will land on a given page. In our seven page example, a person can land on page 3 from page 4 with a probability of

\frac{1}{2}

or from page 6 with a probability of

\frac{1}{3} .

If there is a link from a page we assume that the surfer leaves the page, and if there are no links from a page then the surfer stays on that page. We also assume that the surfer does not use the “Back” key. This information for our seven page internet example can be summarized in a transition matrix

T

whose

i, j

th entry is the probability that a surfer lands on page

i

from page

j .

T = [\begin{array}{ccccccc} 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & \frac{1}{2} & 0 & \frac{1}{3} & 0 \\ 0 & \frac{1}{2} & 0 & 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{3} & 1 \\ 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{3} & 0 \end{array}] .

🔗

Let us assume in our seven page internet that a user starts on page 6. That is, the probability that the user is initially on page 6 is 1, and so the probability that the user is on some other page is 0. This information can be encapsulated in a state vector

x_{0} = {[0 0 0 0 0 1 0]}^{T} .

🔗

Since there are links from page 6 to pages 3, 5, and 7, there is a

\frac{1}{3}

probability that the surfer will next move to one of these pages. That means that at the next step, the state vector

x_{1}

for this user will be

x_{1} = {[0 0 \frac{1}{3} 0 \frac{1}{3} 0 \frac{1}{3}]}^{T} .

🔗

Note that

x_{1} = T x_{0} .

🔗

As the user continues to surf the internet, the probabilities that the surfer is on a given page after the second, third, and fourth steps are given in the state vectors

x_{2} = T x_{1} = T^{2} x_{0}, x_{3} = T x_{2} = T^{3} x_{0}, x_{4} = T x_{3} = T^{4} x_{0} .

🔗

In general, the probabilities that the surfer is on a given page after the

n

th step is given by the state vector

x_{n} = T x_{n - 1} = T^{n} x_{0} .

🔗

This example illustrates the general nature of what is called a Markov process (see Definition 9.4). The two properties of the transition matrix

T

make

T

a special kind of matrix.

🔗

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.

🔗

In a Markov process, each generation depends only on the preceding generation and there may be a limiting value as we let the process continue indefinitely. We can test to see if that happens for this Markov process defined by

T

by doing some experimentation.

🔗

Project Activity 9.6.

Use appropriate technology to do the following. Choose several different initial state vectors $x_{0}$ and calculate the vectors in the sequence ${T^{n} x_{0}}$ for large values of $n .$ (Note that, as state vectors, the entries of $x_{0}$ cannot be negative and the sum of the entries of $x_{0}$ must be $1 .$ ) Explain the behavior of the sequence ${x_{n}}$ as $n$ gets large. Do you notice anything strange? What aspects of our seven page internet do you think explain this behavior? Clearly communicate all of the experimentation that you do. You may use the GeoGebra applet at geogebra.org/m/b3dybnux.

🔗

If there is a limit of the sequence

{T^{n} x_{0}}

(in other words, if there is a vector

v

such that

v = lim_{n \to \infty} T^{n} x_{0}

), we call this limit a steady-state or equilibrium vector. Such a steady-state vector has another important property. Since

T

is independent of

n

we have

\begin{matrix} (9.8) & T v = T (lim_{n \to \infty} T^{n} x_{0}) = lim_{n \to \infty} T^{n + 1} x_{0} = v . \end{matrix}

🔗

Equation (9.8) shows that a steady state vector

v

is an eigenvector for

T

with eigenvalue 1. We can interpret the steady-state vector for

T

in an important way. Let

t_{j}

be the fraction of time we spend on page

j

and let

l_{j}

be the number of links on page

j .

Then the fraction of the time that we end up on page

i

coming from page

j

\frac{t_{j}}{l_{j}} .

If we sum over all the pages linked to page

i

we have that

t_{i} = \sum \frac{t_{j}}{l_{j}} .

🔗

Notice that this is essentially the same process we used to obtain

x_{n}

from

x_{n - 1},

and so we can interpret the steady-state vector

v

as telling us what fraction of a random web surfer's time was spent at each web page. If we assume that the time spent at a web page is a measure of its importance, then the steady-state vector tells us the relative importance of each web page. So this steady-state vector provides the page rankings for us. In other words,

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 $T$ with eigenvalue 1.

🔗

Project Activity 9.6 illustrates one problem with our seven page internet. The steady-state vector shows that page 3 is the only important page, but that hardly seems reasonable in the example since there are other pages that must have some importance. The problem is that page 3 is a “dangling” page and does not lead anywhere. Once a surfer reaches that page, they are stuck there, overemphasizing its importance. So this dangling page acts like a sink, ultimately drawing all surfers to it. To adjust for dangling pages, we make the assumption that if a surfer reaches a dangling page (one with no links emanating from it), the surfer will jump to any page on the web with equal probability. So in our seven page example, once a surfer reaches page 3 the surfer will jump to any page on the web with probability

\frac{1}{7} .

🔗

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?

🔗

There is one more issue to address before we can consider ourselves ready to rank web pages. Consider the example of the five page internet shown in Figure 9.7.

🔗

Project Activity 9.9.

🔗

(a)

Explain why

[\begin{array}{ccccc} 0 & 0 & 1 & \frac{1}{2} & \frac{1}{5} \\ 1 & 0 & 0 & 0 & \frac{1}{5} \\ 0 & 1 & 0 & 0 & \frac{1}{5} \\ 0 & 0 & 0 & 0 & \frac{1}{5} \\ 0 & 0 & 0 & \frac{1}{2} & \frac{1}{5} \end{array}] .

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 $x_{0}$ and determine if there is a limit to the Markov chain. Explain. You may use the GeoGebra applet at geogebra.org/m/b3dybnux.

🔗

Project Activity 9.9 shows that it is possible to construct an internet so that the corresponding Markov chain does not have a limit, even after adjusting for dangling pages. This is a significant problem if we want to provide a relative ranking of all web pages regardless of where a surfer starts. To fix this problem we need to make one final adjustment to arrive at a type of transition matrix that always provides a limit for our Markov chain.

🔗

Definition 9.8.

A stochastic matrix is regular if its transition matrix $T$ has the property that for some power $k,$ all the entries of $T^{k}$ are positive.

🔗

Note that the transition matrix from Project Activity 9.9 is not regular. Regular matrices have some especially nice properties, as the following theorem describes. We will not prove this theorem, but use it in the remainder of this project. The theorem shows that if we have a regular transition matrix, then there will a limit of the state vectors

x_{n},

and that this limit has a very interesting property.

🔗

Theorem 9.9.

Assume $n \geq 2$ and that $T$ is a regular $n \times n$ stochastic matrix.

$lim_{k \to \infty} T^{k}$ exists and is a stochastic matrix.
For any vector $x,$

$lim_{k \to \infty} T^{k} x = c$

for the same vector $c .$
The columns of $lim_{k \to \infty} T^{k}$ are the same vector $c .$
The vector $c$ is the unique eigenvector of $T$ whose entries sum to 1.
If $λ$ is an eigenvalue of $T$ not equal to 1, then $| λ | < 1 .$

🔗

Having a regular transition matrix

T

ensures that there is always the same limit

v

to the sequence

T^{k} x_{0}

for any starting vector

x_{0} .

As mentioned before, the entries in

v = lim_{n \to \infty} T^{n} x_{0}

can be interpreted as telling us what fraction of the random surfer's time was spent at each webpage. If we interpret the amount of time a surfer spends at a page as a measure of the page's importance, then this steady-state vector

v

provides a ranking of the relative importance of each page in the web. This is the essence of Google's PageRank.

🔗

To make our final adjustment in the transition matrix to be sure that we obtain a regular matrix, we need to deal with the problems of “loops” in our internet. Loops, as illustrated in Project Activity 9.9, can act as sinks just like the dangling pages we saw earlier and condemn a user that enters such a loop to spend his/her time only on those pages in the loop. Quite boring! To account for this problem, we make a second adjustment.

🔗

Let

p

be a number between 0 and 1 (Google supposedly uses

p = 0.85

). Suppose a surfer is on page

i .

We assume with probability

p

that the surfer will chose any link on page

i

with equal probability. We make the additional assumption with probability

1 - p

that the surfer will select with equal probability any page on the web.

🔗

T

is a transition matrix, incorporating the method we used to deal with dangling pages, then the adjusted transition matrix

G

(the Google matrix) is

G = p T + (1 - p) Q,

🔗

where

Q

is the matrix all of whose entries are

\frac{1}{n},

where

n

is the number of pages in the internet (

n = 7

in our seven page example). Since all of the entries of

G

are positive,

G

is a regular stochastic matrix.

🔗

Project Activity 9.10.

Return to the seven page internet in Figure 9.5.

🔗

(a)

Find the Google matrix $G$ for this internet.

🔗

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

🔗

We conclude with two observations. Consider the role of the parameter

p

in our final adjustment. Notice that if

p = 1,

then

G = T

and we have the original hyperlink structure of the web. However, if

p = 0,

then

G = \frac{1}{n} I_{n},

where

I_{n}

is the

n \times n

identity matrix with

n

as the number of pages in the web. In this case, every page is linked to every other page and a random surfer spends equal time on any page. Here we have lost all of the character of the linked structure of the web. Choosing

p

close to 1 retains much of the original hyperlink structure of the web.

🔗

Finally, the matrices that model the web are HUGE, and so the methods we used in this project to approximate the steady-state vectors are not practical. There are many methods for approximating eigenvectors that are often used in these situations, some of which we discuss in a later section.

A differential equation is an equation that involves one or more derivatives of a function.

Information for this project was taken from the websites ams.org/samplings/feature-column/fcarc-pagerank and faculty.winthrop.edu/polaskit/spring11/math550/chapter.pdf.

web.archive.org/web/20111104131332/http://www.google.com/competition/howgooglesearchworks.html

The Internet is very large and has upwards of 25 billion pages. This would leave us with an enormous transition matrix, even though most of its entries are 0. In fact, studies show that web pages have an average of about 10 links, so on average all but 10 entries of each column are 0. Working with such a large matrix is beyond what we want to do in this project, so we will just amuse ourselves with small examples that illustrate the general points.