Approximating Eigenvalues and Eigenvectors

Section 20 Approximating 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 the power method for?
How does the power method work?
How can we use the inverse power method to approximate any eigenvalue/eigenvector pair?

🔗

Subsection Application: Leslie Matrices and Population Modeling

🔗

The Leslie Matrix (also called the Leslie Model) is a powerful model for describing an age distributed growth of a population that is closed to migration. In a Leslie model, it is usually the case that only one gender (most often female) is considered. As an example, we will later consider a population of sheep that is being grown commercially. A natural question that we will address is how we can harvest the population to build a sustainable environment.

🔗

When working with populations, the matrices we use are often large. For large matrices, using the characteristic polynomial to calculate eigenvalues is too time and resource consuming to be practical, and we generally cannot find the exact values of the eigenvalues. As a result, approximation techniques are very important. In this section we will explore a method for approximating eigenvalues. The eigenvalues of a Leslie matrix are important because they describe the limiting or steady-state behavior of a population. The matrix and model were introduced by Patrick H. Leslie in “On the Use of Matrices in Certain Population Mathematics”, Leslie, P.H., Biometrika, Volume XXXIII, November 1945, pp. 183-212.

🔗

Subsection Introduction

🔗

We have used the characteristic polynomial to find the eigenvalues of a matrix, and for each eigenvalue row reduced a corresponding matrix to find the eigenvectors This method is only practical for small matrices — for more realistic applications approximation techniques are used. We investigate one such technique in this section, the power method.

🔗

Preview Activity 20.1.

Let $A = [\begin{array}{cc} 2 & 6 \\ 5 & 3 \end{array}] .$ Our goal is to find a scalar $λ$ and a nonzero vector $v$ so that $A v = λ v .$

🔗

(a)

If we have no prior knowledge of the eigenvalues and eigenvectors of this matrix, we might just begin with a guess. Let $x_{0} = [1 0]^{T}$ be such a guess for an eigenvector. Calculate $A x_{0} .$ Is $x_{0}$ an eigenvector of $A ?$ Explain.

🔗

(b)

If $x_{0}$ is not a good approximation to an eigenvector of $A,$ then we need to make a better guess. We have little to work with other than just random guessing, but we can use $x_{1} = A x_{0}$ as another guess. We calculated $x_{1}$ in part 1. Is $x_{1}$ an eigenvector for $A ?$ Explain.

🔗

(c)

In parts (a) and (b) you might have noticed that in some sense $x_{1}$ is closer to being an eigenvector of $A$ than $x_{0}$ was. So maybe continuing this process will get us closer to an eigenvector of $A .$ In other words, for each positive integer $k$ we define $x_{k}$ as $A x_{k - 1} .$ Before we proceed, however, we should note that as we calculate the vectors $x_{1},$ $x_{2},$ $x_{3},$ $\dots,$ the entries in the vectors get large very quickly. So it will be useful to scale the entries so that they stay at a reasonable size, which makes it easier to interpret the output. One way to do this is to divide each vector $x_{i}$ by its largest component in absolute value so that all of the entries stay between $- 1$ and $1 .$ ³⁷ So in our example we have $x_{0} = [1 0]^{T},$ $x_{1} = [2 / 5 1]^{T},$ and $x_{2} = [1 25 / 34]^{T} .$ Explain why scaling our vectors will not affect our search for an eigenvector.

🔗

(d)

Use an appropriate technological tool to find the vectors $x_{k}$ up to $k = 10 .$ What do you think the limiting vector $lim_{k \to \infty} x_{k}$ is? Is this limiting vector an eigenvector of $A ?$ If so, what is the corresponding eigenvalue?

🔗

Subsection The Power Method

🔗

While the examples we present in this text are small in order to highlight the concepts, matrices that appear in real life applications are often enormous. For example, in Google's PageRank algorithm that is used to determine relative rankings of the importance of web pages, matrices of staggering size are used (most entries in the matrices are zero, but the size of the matrices is still huge). Finding eigenvalues of such large matrices through the characteristic polynomial is impractical. In fact, finding the roots of all but the smallest degree characteristic polynomials is a very difficult problem. As a result, using the characteristic polynomial to find eigenvalues and then finding eigenvectors is not very practical in general, and it is often a better option to use a numeric approximation method. We will consider one such method in this section, the power method.

🔗

In Preview Activity 20.1, we saw an example of a matrix

A = [\begin{array}{cc} 2 & 6 \\ 5 & 3 \end{array}]

so that the sequence

{x_{k}},

where

x_{k} = A x_{k - 1},

converged to a dominant eigenvector of

A

for an initial guess vector

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

The vectors

x_{i}

for

i

from

1

6

(with scaling) are approximately

\begin{aligned} x_{1} & = [\begin{array}{c} 0.4 \\ 1 \end{array}] & x_{2} & = [\begin{array}{c} 1 \\ 0.7353 \end{array}] & x_{3} & = [\begin{array}{c} 0.8898 \\ 1 \end{array}] \\ x_{4} & = [\begin{array}{c} 1 \\ 0.9575 \end{array}] & x_{5} & = [\begin{array}{c} 0.9838 \\ 1 \end{array}] & x_{6} & = [\begin{array}{c} 1 \\ 0.9939 \end{array}] . \end{aligned}

🔗

Numerically we can see that the sequence

{x_{k}}

approaches the vector

[1 1]^{T},

and Figure 20.1 illustrates this geometrically as well.

🔗

This method of successive approximations

x_{k} = A x_{k - 1}

is called the power method (since we could write

x_{k}

A^{k} x_{0}

). Our task now is to show that this method works in general. In the next activity we restrict our argument to the

2 \times 2

case, and then discuss the general case afterwards.

🔗

Let

A

be an arbitrary

2 \times 2

matrix with two linearly independent eigenvectors

v_{1}

and

v_{2}

and corresponding eigenvalues

λ_{1}

and

λ_{2},

respectively. We will also assume

| λ_{1} | > | λ_{2} | .

An eigenvalue whose absolute value is larger than that of any other eigenvalue is called a dominant eigenvalue. Any eigenvector for a dominant eigenvalue is called a dominant eigenvector. Before we show that our method can be used to approximate a dominant eigenvector, we recall that since

v_{1}

and

v_{2}

are eigenvectors corresponding to distinct eigenvalues, then

v_{1}

and

v_{2}

are linearly independent. So there exist scalars

a_{1}

and

a_{2}

such that

x_{0} = a_{1} v_{1} + a_{2} v_{2} .

🔗

We have seen that for each positive integer

k

we can write

x_{n}

\begin{matrix} (20.1) & x_{k} = a_{1} λ_{1}^{k} v_{1} + a_{2} λ_{2}^{k} v_{2} . \end{matrix}

🔗

With this representation of

x_{0}

we can now see why the power method approximates a dominant eigenvector of

A .

🔗

Activity 20.2.

Assume as above that $A$ is an arbitrary $2 \times 2$ matrix with two linearly independent eigenvectors $v_{1}$ and $v_{2}$ and corresponding eigenvalues $λ_{1}$ and $λ_{2},$ respectively. (We are assuming that we don't know these eigenvectors, but we can assume that they exist.) Assume that $λ_{1}$ is the dominant eigenvalue for $A,$ $x_{0}$ is some initial guess to an eigenvector for $A,$ that $x_{0} = a_{1} v_{1} + a_{2} v_{2},$ and that $x_{k} = A x_{k - 1}$ for $k \geq 1 .$

🔗

(a)

We divide both sides of equation (20.1) by $λ_{1}^{k}$ (since $λ_{1}$ is the dominant eigenvalue, we know that $λ_{1}$ is not $0$ ) to obtain

\begin{matrix} (20.2) & \frac{1}{λ_{1}^{k}} x_{k} = a_{1} v_{1} + a_{2} {(\frac{λ_{2}}{λ_{1}})}^{k} v_{2} . \end{matrix}

Recall that $λ_{1}$ is the dominant eigenvalue for $A .$ What happens to ${(\frac{λ_{2}}{λ_{1}})}^{k}$ as $k \to \infty ?$ Explain what happens to the right hand side of equation (20.2) as $k \to \infty .$

🔗

(b)

Explain why the previous result tells us that the vectors $x_{k}$ are approaching a vector in the direction of $v_{1}$ or $- v_{1}$ as $k \to \infty,$ assuming $a_{1} \neq 0 .$ (Why do we need $a_{1} \neq 0 ?$ What happens if $a_{1} = 0 ?$ )

🔗

(c)

What does all of this tell us about the sequence ${x_{k}}$ as $k \to \infty ?$

🔗

The power method is straightforward to implement, but it is not without its drawbacks. We began by assuming that we had a basis of eigenvectors of a matrix

A .

So we are also assuming that

A

is diagonalizable. We also assumed that

A

had a dominant eigenvalue

λ_{1} .

That is, if

A

n \times n

we assume that

A

has eigenvalues

λ_{1},

λ_{2},

\dots,

λ_{n},

not necessarily distinct, with

| λ_{1} | > | λ_{2} | \geq | λ_{3} | \geq \dots \geq | λ_{n} |

🔗

and with

v_{i}

an eigenvector of

A

with eigenvalue

λ_{i} .

We could then write any initial guess

x_{0}

in the form

x_{0} = a_{1} v_{1} + a_{2} v_{2} + \dots + a_{n} v_{n} .

🔗

The initial guess is also called a seed.

🔗

Then

x_{k} = a_{1} λ_{1}^{k} v_{1} + a_{2} λ_{2}^{k} v_{2} + \dots + a_{n} λ_{n}^{k} v_{n}

🔗

and

\begin{matrix} (20.3) & \frac{1}{λ_{1}^{k}} x_{k} = a_{1} v_{1} + a_{2} {(\frac{λ_{2}}{λ_{1}})}^{k} v_{2} + \dots + a_{n} {(\frac{λ_{n}}{λ_{1}})}^{k} v_{n} . \end{matrix}

🔗

Notice that we are not actually calculating the vectors

x_{k}

here — this is a theoretical argument and we don't know

λ_{1}

and are not performing any scaling like we did in Preview Activity 20.1. We are assuming that

λ_{1}

is the dominant eigenvalue of

A,

though, so for each

i

the terms

{(\frac{λ_{i}}{λ_{1}})}^{k}

converge to

0

k

goes to infinity. Thus,

x_{k} \approx λ_{1}^{k} a_{1} v_{1}

🔗

for large values of

k,

which makes the sequence

{x_{k}}

converge to a vector in the direction of a dominant eigenvector

v_{1}

provided

a_{1} \neq 0 .

So we need to be careful enough to choose a seed that has a nonzero component in the direction of

v_{1} .

Of course, we generally don't know that our matrix is diagonalizable before we make these calculations, but for many matrices the sequence

{x_{k}}

will approach a dominant eigenvector.

🔗

The power method approximates a dominant eigenvector, and there are ways that we can approximate the dominant eigenvalue. Exercise 8 presents one way — by keeping track of the components of the

x_{k}

that have the largest absolute values, and the next activity shows another.

🔗

Activity 20.3.

Let $A$ be an $n \times n$ matrix with eigenvalue $λ$ and corresponding eigenvector $v .$

🔗

(a)

Explain why $λ = \frac{λ (v \cdot v)}{v \cdot v} .$

🔗

(b)

Use the result of part (a) to explain why $λ = \frac{(A v) \cdot v}{v \cdot v} .$

🔗

The result of Activity 20.3 is that, when the vectors in the sequence

{x_{k}}

approximate a dominant eigenvector of a matrix

A,

the quotients

\begin{matrix} (20.4) & \frac{(A x_{k}) \cdot x_{k}}{x_{k} \cdot x_{k}} = \frac{x_{k}^{T} A x_{k}}{x_{k}^{T} x_{k}} \end{matrix}

🔗

approximate the dominant eigenvalue of

A .

The quotients in (20.4) are called Rayleigh quotients.

🔗

To summarize, the procedure for applying the power method for approximating a dominant eigenvector and dominant eigenvalue of a matrix

A

is as follows.

Step 1: Select an arbitrary nonzero vector $x_{0}$ as an initial guess to a dominant eigenvector.
Step 2: Let $x_{1} = A x_{0} .$ Let $k = 1 .$
Step 3: To avoid having the magnitudes of successive approximations become excessively large, scale this approximation $x_{k} .$ That is, find the entry $α_{k}$ of $x_{k}$ that is largest in absolute value. Then replace $x_{k}$ by $\frac{1}{α_{k}} x_{k} .$
Step 4: Calculate the Rayleigh quotient $r_{k} = \frac{(A x_{k}) \cdot x_{k}}{x_{k} \cdot x_{k}} .$
Step 5: Let let $x_{k + 1} = A x_{k} .$ Increase $k$ by $1$ and repeat Steps 3 through 5.

🔗

If the sequence

{x_{k}}

converges to a dominant eigenvector of

A,

then the sequence

{r_{k}}

converges to the dominant eigenvalue of

A .

🔗

The power method can be useful for approximating a dominant eigenvector as long as the successive multiplications by

A

are fairly simple — for example, if many entries of

A

are zero.³⁸ The rate of convergence of the sequence

{x_{k}}

depends on the ratio

\frac{λ_{2}}{λ_{1}} .

If this ratio is close to

1,

then it can take many iterations before the power

{(\frac{λ_{2}}{λ_{1}})}^{k}

makes the

v_{2}

term negligible. There are other methods for approximating eigenvalues and eigenvectors, e.g., the QR factorization, that we will not discuss at this point.

🔗

Subsection The Inverse Power Method

🔗

The power method only allows us to approximate the dominant eigenvalue and a dominant eigenvector for a matrix

A .

It is possible to modify this method to approximate other eigenvectors and eigenvalues under certain conditions. We consider an example in the next activity to motivate the general situation.

🔗

Activity 20.4.

Let $A = [\begin{array}{cc} 2 & 6 \\ 5 & 3 \end{array}]$ be the matrix from Preview Activity 20.1. Recall that $8$ is an eigenvalue for $A,$ and a quick calculation can show that $- 3$ is the other eigenvalue of $A .$ Consider the matrix $B = (A - (- 2) I_{2})^{- 1} = \frac{1}{10} [\begin{array}{rr} - 5 & 6 \\ 5 & - 4 \end{array}] .$

🔗

(a)

Show that $\frac{1}{8 - (- 2)}$ and $\frac{1}{- 3 - (- 2)}$ are the eigenvalues of $B .$

🔗

(b)

Recall that $v_{1} = [1 1]^{T}$ is an eigenvector of $A$ corresponding to the eigenvalue $8$ and assume that $v_{2} = [- 6 5]^{T}$ is an eigenvector for $A$ corresponding to the eigenvalue $- 3 .$ Calculate the products $B v_{1}$ and $B v_{2} .$ How do the products relate to the results of part (a)?

🔗

Activity 20.4 provides evidence that we can translate the matrix

A

having a dominant eigenvalue to a different matrix

B

with the same eigenvectors as

A

and with a dominant eigenvalue of our choosing. To see why, let

A

be an

n \times n

matrix with eigenvalues

λ_{1},

λ_{2},

\dots,

λ_{n},

and let

α

be any real number distinct from the eigenvalues. Let

B = (A - α I_{n})^{- 1} .

In our example in Activity 20.4 the numbers

\frac{1}{λ_{1} - α}, \frac{1}{λ_{2} - α}, \frac{1}{λ_{3} - α}, \dots, \frac{1}{λ_{n} - α}

🔗

were the eigenvalues of

B,

and that if

v_{i}

is an eigenvector for

A

corresponding to the eigenvalue

λ_{i},

then

v_{i}

is an eigenvector of

B

corresponding to the eigenvalue

\frac{1}{λ_{i} - α} .

To see why, let

λ

be an eigenvalue of an

n \times n

matrix

A

with corresponding eigenvector

v .

Let

α

be a scalar that is not an eigenvalue of

A,

and let

B = (A - α I_{n})^{- 1} .

Now

\begin{aligned} A v & = λ v \\ A v - α v & = λ v - α v \\ (A - α I_{n}) v & = (λ - α) v \\ \frac{1}{λ - α} v & = (A - α I_{n})^{- 1} v . \end{aligned}

🔗

\frac{1}{λ - α}

is an eigenvalue of

B

with eigenvector

v .

🔗

Now suppose that

A

is an

n \times n

matrix with eigenvalues

λ_{1},

λ_{2},

\dots,

λ_{n},

and that we want to approximate an eigenvector and corresponding eigenvalue

λ_{i}

A .

If we can somehow find a value of

α

so that

| λ_{i} - α | < | λ_{j} - α |

for all

j \neq i,

then

| \frac{1}{λ_{i} - α} | > | \frac{1}{λ_{j} - α} |

for any

j \neq i .

Thus, the matrix

B = (A - α I_{n})^{- 1}

has

\frac{1}{λ_{i} - α}

as its dominant eigenvalue and we can use the power method to approximate an eigenvector and the Rayleigh quotient to approximate the eigenvalue

\frac{1}{λ_{i} - α},

and hence approximate

λ_{i} .

🔗

Activity 20.5.

Let $A = \frac{1}{8} [\begin{array}{crr} 7 & 3 & 3 \\ 30 & 22 & - 10 \\ 15 & - 21 & 11 \end{array}] .$

🔗

(a)

Apply the power method to the matrix $B = (A - I_{3})^{- 1}$ with initial vector $x_{0} = [1 0 0]^{T}$ to fill in Table 20.2 (to four decimal places). Use this information to estimate an eigenvalue for $A$ and a corresponding eigenvector.

Table 20.2. Applying the power method to

(A - I_{3})^{- 1}

$k$	$10$	$15$	$20$
$x_{k}$
$\frac{x_{k}^{T} A x_{k}}{x_{k}^{T} x_{k}}$

🔗

(b)

Applying the power method to the matrix $B = (A - 0 I_{3})^{- 1}$ with initial vector $x_{0} = [1 0 0]^{T}$ yields the information in Table 20.3 (to four decimal places). Use this information to estimate an eigenvalue for $A$ and a corresponding eigenvector.

Table 20.3. Applying the power method to

(A - 0 I_{3})^{- 1}

$k$	$10$	$15$	$20$
$x_{k}$	$[\begin{array}{r} - 0.3344 \\ 0.6677 \\ 1.0000 \end{array}]$	$[\begin{array}{r} - 0.3333 \\ 0.6666 \\ 1.0000 \end{array}]$	$[\begin{array}{r} - 0.3333 \\ 0.6666 \\ 1.0000 \end{array}]$
$\frac{x_{k}^{T} A x_{k}}{x_{k}^{T} x_{k}}$	$- 1.0014$	$- 1.0000$	$- 1.0000$

🔗

(c)

Applying the power method to the matrix $B = (A - 5 I_{3})^{- 1}$ with initial vector $x_{0} = [1 0 0]^{T}$ yields the information in Table 20.4 (to four decimal places). Use this information to estimate an eigenvalue for $A$ and a corresponding eigenvector.

Table 20.4. Applying the power method to

(A - 5 I_{3})^{- 1}

$k$	$10$	$15$	$20$
$x_{k}$	$[\begin{array}{r} 0.0000 \\ 1.0000 \\ - 1.0000 \end{array}]$	$[\begin{array}{r} 0.0000 \\ 1.0000 \\ - 1.0000 \end{array}]$	$[\begin{array}{r} 0.0000 \\ 1.0000 \\ - 1.0000 \end{array}]$
$\frac{x_{k}^{T} A x_{k}}{x_{k}^{T} x_{k}}$	$- 1.0000$	$- 1.0000$	$- 1.0000$

🔗

Subsection Examples

🔗

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

🔗

Example 20.5.

Let $A = [\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array}] .$

🔗

(a)

Approximate the dominant eigenvalue of $A$ accurate to two decimal places using the power method. Use technology as appropriate.

Solution.

We use technology to calculate the scaled vectors $A^{k} x_{0}$ for values of $k$ until the components don't change in the second decimal place. We start with the seed $x_{0} = [1 1 1]^{T} .$ For example, to two decimal places we have $x_{k} = [0.28 0.64 1.00]^{T}$ for $k \geq 20 .$ So we suspect that ${[0.28 0.64 1.00]}^{T}$ is close to a dominant eigenvector for $A .$ For the dominant eigenvalue, we can calculate the Rayleigh quotients $\frac{(A x_{k}) \cdot x_{k}}{x_{k} \cdot x_{k}}$ until they do not change to two decimal places. For $k \geq 4,$ our Rayleigh quotients are all (to two decimal places) equal to $16.12 .$ So we expect that the dominant eigenvalue of $A$ is close to $16.12 .$ Notice that

A [0.28 0.64 1.00]^{T} = [4.56 10.32 16.08]^{T},

which is not far off from $16.12 [0.28 0.64 1.00]^{T} .$

🔗

(b)

Find the characteristic polynomial $p (λ)$ of $A .$ Then find the the root of $p (λ)$ farthest from the origin. Compare to the result of part (a). Use technology as appropriate.

Solution.

The characteristic polynomial of $A$ is

p (λ) = - λ^{3} + 15 λ^{2} + 18 λ = - λ (λ^{2} - 15 λ - 18) .

The quadratic formula gives the nonzero roots of $p (λ)$ as

\frac{15 \pm \sqrt{15^{2} + 4 (18)}}{2} = \frac{15 \pm 3 \sqrt{33}}{2} .

The roots farthest from the origin is approximately $16.12,$ as was also calculated in part (a).

🔗

Example 20.6.

Let $A = [\begin{array}{ccc} 2 & 1 & 0 \\ 1 & 3 & 1 \\ 0 & 1 & 2 \end{array}] .$

🔗

(a)

Use the power method to approximate the dominant eigenvalue and a corresponding eigenvector (using scaling) accurate to two decimal places. Use $x_{0} = [1 1 1]^{T}$ as the seed.

Solution.

We use technology to calculate the scaled vectors $A^{k} x_{0}$ for values of $k$ until the components don't change in the second decimal place. For example, to two decimal places we have $x_{k} = [0.50 1.00 0.50]^{T}$ for $k \geq 4 .$ So we suspect that ${[\frac{1}{2} 1 \frac{1}{2}]}^{T}$ is a dominant eigenvector for $A .$ For the dominant eigenvalue, we can calculate the Rayleigh quotients $\frac{(A x_{k}) \cdot x_{k}}{x_{k} \cdot x_{k}}$ until they do not change to two decimal places. For $k \geq 2,$ our Rayleigh quotients are all (to two decimal places) equal to $4 .$ So we expect that the dominant eigenvalue of $A$ is $4 .$ We could also use the fact that

A {[\frac{1}{2} 1 \frac{1}{2}]}^{T} = [2 4 2]^{T} = 4 {[\frac{1}{2} 1 \frac{1}{2}]}^{T}

to see that ${[\frac{1}{2} 1 \frac{1}{2}]}^{T}$ is a dominant eigenvector for $A$ with eigenvalue $4 .$

🔗

(b)

Determine the exact value of the dominant eigenvalue of $A$ and compare to your result from part (a).

Solution.

Technology shows that the characteristic polynomial of $A - λ I_{3}$ is

p (λ) = - λ^{3} + 7 λ^{2} - 14 λ + 8 = - (λ - 1) (λ - 2) (λ - 4) .

We can see from the characteristic polynomial that $4$ is the dominant eigenvalue of $A .$

🔗

(c)

Approximate the remaining eigenvalues of $A$ using the inverse power method.

Hint.

Try $α = 0.5$ and $α = 1.8 .$

Solution.

Applying the power method to $B = (A - 0.5 I_{3})^{- 1}$ with seed $x_{0} = [1 1 1]^{T}$ gives $x_{k} \approx [0.50 1.00 0.50]^{T}$ for $k \geq 5,$ with Rayleigh quotients of $2$ (to several decimal places). So $2$ is the dominant eigenvalue of $B .$ But $\frac{1}{λ - 0.5}$ is also the dominant eigenvalue of $B,$ where $λ$ is the corresponding eigenvalue of $A .$ . So to find $λ,$ we note that $\frac{1}{λ - 0.5} = 2$ implies that $λ = 1$ is an eigenvalue of $A .$ Now applying the power method to $B = (A - 1.8 I_{3})^{- 1}$ with seed $x_{0} = [1 1 1]^{T}$ gives $x_{k} \approx [1.00 - 1.00 1.00]^{T}$ for large enough $k,$ with Rayleigh quotients of $5$ (to several decimal places). To find the corresponding eigenvalue $λ$ for $A,$ we note that $\frac{1}{λ - 1.8} = 5,$ or $λ = 2$ is an eigenvalue of $A .$ Admittedly, this method is very limited. Finding good choices for $α$ often depends on having some information about the eigenvalues of $A .$ Choosing $α$ close to an eigenvalue provides the best chance of obtaining that eigenvalue.

🔗

Subsection Summary

The power method is an iterative method that can be used to approximate the dominant eigenvalue of an $n \times n$ matrix $A$ that has $n$ linearly independent eigenvectors and a dominant eigenvalue.
To use the power method we start with a seed $x_{0}$ and then calculate the sequence ${x_{k}}$ of vectors, where $x_{k} = A x_{k - 1} .$ If $x_{0}$ is chosen well, then the sequence ${x_{k}}$ converges to a dominant eigenvector of $A .$
If $A$ is an $n \times n$ matrix with eigenvalues $λ_{1},$ $λ_{2},$ $\dots,$ $λ_{n},$ to approximate an eigenvector of $A$ corresponding to the eigenvalue $λ_{i},$ we apply the power method to the matrix $B = (A - α I_{n})^{- 1},$ where $α$ is not a eigenvalue of $A$ and $| \frac{1}{λ_{i} - α} | > | \frac{1}{λ_{j} - α} |$ for any $j \neq i .$

🔗

Exercises Exercises

🔗

1.

Let $A = [\begin{array}{cc} 1 & 2 \\ 2 & 1 \end{array}] .$ Let $x_{0} = [1 0]^{T} .$

🔗

(a)

Find the eigenvalues and corresponding eigenvectors for $A .$

🔗

(b)

Use appropriate technology to calculate $x_{k} = A^{k} x_{0}$ for $k$ up to 10. Compare to a dominant eigenvector for $A .$

🔗

(c)

Use the eigenvectors from part (b) to approximate the dominant eigenvalue for $A .$ Compare to the exact value of the dominant eigenvalue of $A .$

🔗

(d)

Assume that the other eigenvalue for $A$ is close to $0 .$ Apply the inverse power method and compare the results to the remaining eigenvalue and eigenvectors for $A .$

🔗

2.

Let $A = [\begin{array}{rcc} 1 & 2 & 0 \\ - 2 & 1 & 2 \\ 1 & 3 & 1 \end{array}] .$ Use the power method to approximate a dominant eigenvector for $A .$ Use $x_{0} = [1 1 1]^{T}$ as the seed. Then approximate the dominant eigenvalue of $A .$

🔗

3.

Let $A = [\begin{array}{rr} 3 & - 1 \\ - 1 & 3 \end{array}] .$ Use the power method starting with $x_{0} = [1 1]^{T} .$ Explain why the method fails in this case to approximate a dominant eigenvector, and how you could adjust the seed to make the process work.

🔗

4.

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

🔗

(a)

Find the eigenvalues and an eigenvector for each eigenvalue.

🔗

(b)

Apply the power method with an initial starting vector $x_{0} = [0 1]^{T} .$ What is the resulting sequence?

🔗

(c)

Use equation (20.3) to explain the sequence you found in part (b).

🔗

5.

Let $A = [\begin{array}{cc} 2 & 6 \\ 5 & 3 \end{array}] .$ Fill in the entries in Table 20.7, where $x_{k}$ is the $k$ th approximation to a dominant eigenvector using the power method, starting with the seed $x_{0} = [1 0]^{T} .$ Compare the results of this table to the eigenvalues of $A$ and $lim_{k \to \infty} \frac{x_{k + 1} \cdot x_{k}}{x_{k} \cdot x_{k}} .$ What do you notice?

Table 20.7. Values of the Rayleigh quotient

$v$	$x_{0}$	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$
$\frac{v^{T} A v}{v^{T} v}$
$v$	$x_{6}$	$x_{7}$	$x_{8}$	$x_{9}$	$x_{10}$	$x_{11}$
$\frac{v^{T} A v}{v^{T} v}$

🔗

6.

Let $A = [\begin{array}{cr} 4 & - 5 \\ 2 & 15 \end{array}] .$ The power method will approximate the dominant eigenvalue $λ = 14 .$ In this exercise we explore what happens if we apply the power method to $A^{- 1} .$

🔗

(a)

Apply the power method to $A^{- 1}$ to approximate the dominant eigenvalue of $A^{- 1} .$ Use $[1 1]^{T}$ as the seed. How is this eigenvalue related to an eigenvalue of $A ?$

🔗

(b)

Explain in general why applying the power method to the inverse of an invertible matrix $B$ might give an approximation to an eigenvalue of $B$ of smallest magnitude. When might this not work?

🔗

7.

There are other algebraic methods that do not rely on the determinant of a matrix that can be used to find eigenvalues of a matrix. We examine one such method in this exercise. Let $A$ be any $n \times n$ matrix, and let $v$ be any vector in $R^{n} .$

🔗

(a)

Explain why the vectors

v, A v, A^{2} v, \dots, A^{n} v

are linearly dependent.

🔗

(b)

Let $c_{0},$ $c_{1},$ $\dots,$ $c_{n}$ be scalars, not all 0, so that

c_{0} v + c_{1} A v + c_{2} A^{2} v + \dots + c_{n} A^{n} v = 0 .

Explain why there must be a smallest positive integer $k$ so that there are scalars $a_{0},$ $a_{1},$ $\dots,$ $a_{k}$ with $a_{k} \neq 0 .$ such that

a_{0} v + a_{1} A v + a_{2} A^{2} v + \dots + a_{k} A^{k} v = 0 .

Hint.

Proceed down the list $c_{n - 1},$ $c_{n - 2},$ etc., until you reach a weight that is non-zero.

🔗

(c)

Let

q (t) = a_{0} + a_{1} t + a_{2} t^{2} + \dots + a_{k} t^{k} .

Then

q (A) = a_{0} + a_{1} A + a_{2} A^{2} + \dots + a_{k} A^{k}

and

\begin{aligned} q (A) v & = (a_{0} + a_{1} A + a_{2} A^{2} + \dots + a_{k} A^{k}) v \\ = a_{0} v + a_{1} A v + a_{2} A^{2} v + \dots + a_{k} A^{k} v \\ = 0 . \end{aligned}

Suppose the polynomial $q (t)$ has a linear factor, say $q (t) = (t - λ) Q (t)$ for some degree $k - 1$ polynomial $Q (t) .$ Explain why, if $Q (A) v$ is non-zero, $λ$ is an eigenvalue of $A$ with eigenvector $Q (A) v .$

🔗

(d)

This method allows us to find certain eigenvalues and eigenvectors, the roots of the polynomial $q (t) .$ Any other eigenvector must lie outside the eigenspaces we have already found, so repeating the process with a vector $v$ not in any of the known eigenspaces will produce different eigenvalues and eigenvectors. Let $A = [\begin{array}{ccr} 2 & 2 & - 1 \\ 2 & 2 & 2 \\ 0 & 0 & 6 \end{array}] .$

🔗

(i)

Find the polynomial $q (t) .$ Use $v = [1 1 1]^{T} .$

🔗

(ii)

Find all of the roots of $q (t) .$

🔗

(iii)

For each root $λ$ of $q (t),$ find the polynomial $Q (t)$ and use this polynomial to determine an eigenvector of $A .$ Verify your work.

🔗

8.

We have seen that the Rayleigh quotients approximate the dominant eigenvalue of a matrix $A .$ As an alternative to using Rayleigh quotients, we can keep track of the scaling factors. Recall that the scaling in the power method can be used to make the magnitudes of the successive approximations smaller and easier to work with. Let $A$ be an $n \times n$ matrix and begin with a non-zero seed $v_{0} .$ We now want to keep track of the scaling factors, so let $α_{0}$ be the component of $v_{0}$ with largest absolute value and let $x_{0} = \frac{1}{α_{0}} v_{0} .$ For $k \geq 0,$ let $v_{k} = A x_{k - 1},$ let $α_{k}$ be the component of $v_{k}$ with largest absolute value and let $x_{k} = \frac{1}{α_{k}} v_{k} .$

🔗

(a)

Let $A = [\begin{array}{rc} 0 & 1 \\ - 8 & 6 \end{array}] .$ Use $x_{0} = [1 1]^{T}$ as the seed and calculate $α_{k}$ for $k$ from $1$ to $10 .$ Compare to the dominant eigenvalue of $A .$

🔗

(b)

Assume that for large $k$ the vectors $x_{k}$ approach a dominant eigenvector with dominant eigenvalue $λ .$ Show now in general that the sequence of scaling factors $α_{k}$ approaches $λ .$

🔗

9.

Let $A$ be an $n \times n$ matrix and let $α$ be a scalar that is not an eigenvalue of $A .$ Suppose that $x$ is an eigenvector of $B = (A - α I_{n})^{- 1}$ with eigenvalue $β .$ Find an eigenvalue of $A$ in terms of $β$ and $α$ with corresponding eigenvector $x .$

🔗

10.

Label each of the following statements as True or False. Provide justification for your response.

🔗

(a) True/False.

The largest eigenvalue of a matrix is a dominant eigenvalue.

🔗

(b) True/False.

If an $n \times n$ matrix $A$ has $n$ linearly independent eigenvectors and a dominant eigenvalue, then the sequence ${A^{k} x_{0}}$ converges to a dominant eigenvector of $A$ for any initial vector $x_{0} .$

🔗

(c) True/False.

If $λ$ is an eigenvalue of an $n \times n$ matrix $A$ and $α$ is not an eigenvalue of $A,$ then $λ - α$ is an eigenvalue of $A - α I_{n} .$

🔗

(d) True/False.

Every square matrix has a dominant eigenvalue.

🔗

Subsection Project: Managing a Sheep Herd

🔗

Sheep farming is a significant industry in New Zealand. New Zealand is reported to have the highest density of sheep in the world. Sheep can begin to reproduce after one year, and give birth only once per year. Table 20.8 gives Birth and Survival Rates for Female New Zealand Sheep (from G. Caughley, “Parameters for Seasonally Breeding Populations,” Ecology, 48, (1967), 834-839). Since sheep hardly ever live past 12 years, we will only consider the population through 12 years.

🔗

Table 20.8. New Zealand female sheep data by age group

Age (years)	Birth Rate	Survival Rate
0-1	0.000	0.845
1-2	0.045	0.975
2-3	0.391	0.965
3-4	0.472	0.950
4-5	0.484	0.926
5-6	0.546	0.895
6-7	0.543	0.850
7-8	0.502	0.786
8-9	0.468	0.691
9-10	0.459	0.561
10-11	0.433	0.370
11-12	0.421	0.000

🔗

As sheep reproduce, they add to the 0-1 sheep (lamb) population. The potential to produce offspring is called fecundity (derived from the word fecund which generally refers to reproductive ability) and determines how many lamb are added to the population. Let

F_{k}

(the fecundity rate) be the rate at which females in age class

k

give birth to female offspring. Not all members of a given age group survive to the next age groups, so let

s_{k}

be the fraction of individuals that survives from age group

k

to age group

k + 1 .

With these ideas in mind, we can create a life cycle chart as in Figure 20.9 that illustrates how the population of sheep changes on a farm (for the sake of space, we illustrate with four age classes).

🔗
Figure 20.9. Life cycle with four age classes.

🔗

To model the sheep population, we need a few variables. Let

n_{1}^{(0)}

be the number of sheep in age group 0-1,

n_{2}^{(0)}

the number in age group 1-2,

n_{3}

the number in age group 2-3 and, in general,

n_{k}^{(0)}

the number of sheep in age group

(k - 1)

k

at some initial time (time

0

), and let

x_{0} = {[n_{1}^{(0)} n_{2}^{(0)} n_{3}^{(0)} \dots n_{12}^{(0)}]}^{T} .

🔗

We wish to determine the populations in the different groups after one year. Let

x_{1} = {[n_{1}^{(1)} n_{2}^{(1)} n_{3}^{(1)} \dots n_{12}^{(1)}]}^{T},

🔗

where

n_{1}^{(1)}

denotes the number of sheep in age group 0-1,

n_{2}^{(1)}

the number of sheep in age group 1-2 and, in general,

n_{k}^{(1)}

the number of tilapia in age group

(k - 1)

k

after one year.

🔗

Project Activity 20.6.

Table 20.8 shows that, on average, each female in age group 1-2 produces $0.045$ female offspring in a year. Since there are $n_{2}$ females in age group 1-2, the lamb population increases by $0.045 n_{2}$ in a year.

🔗

(a)

Continue this analysis to explain why

\begin{aligned} n_{1}^{(1)} & = 0.045 n_{2} + 0.391 n_{3} + 0.472 n_{4} + 0.484 n_{5} + 0.546 n_{6} + 0.543 n_{7} \\ + 0.502 n_{8} + 0.468 n_{9} + 0.459 n_{10} + 0.433 n_{11} + 0.421 n_{12} . \end{aligned}

🔗

(b)

Explain why $n_{2}^{(1)} = 0.845 n_{1} .$

🔗

(c)

Now explain why

\begin{matrix} (20.5) & x_{1} = L x_{0}, \end{matrix}

where $L$ is the matrix

\begin{matrix} (20.6) & [\begin{array}{cccccccccccc} 0 & 0.045 & 0.391 & 0.472 & 0.484 & 0.546 & 0.543 & 0.502 & 0.468 & 0.459 & 0.433 & 0.421 \\ 0.845 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.975 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.965 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.950 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.926 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0.895 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0.850 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.786 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.691 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.561 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.370 & 0 \end{array}] . \end{matrix}

🔗

Notice that our matrix

L

has the form

[\begin{array}{cccccc} F_{1} & F_{2} & F_{3} & \dots & F_{n - 1} & F_{n} \\ s_{1} & 0 & 0 & \dots & 0 & 0 \\ 0 & s_{2} & 0 & \dots & 0 & 0 \\ 0 & 0 & s_{3} & \dots & 0 & 0 \\ ⋱ \\ 0 & 0 & 0 & \dots & s_{n - 1} & 0 \end{array}] .

🔗

Such a matrix is called a Leslie matrix.

🔗

Leslie matrices have certain useful properties, and one eigenvalue of a Leslie matrix can tell us a lot about the long-term behavior of the situation being modeled. You can take these properties as fact unless otherwise directed.

A Leslie matrix $L$ has a unique positive eigenvalue $λ_{1}$ with a corresponding eigenvector $v_{1}$ whose entries are all positive.
If $λ_{i}$ ( $i > 1$ ) is any other eigenvalue (real or complex) of $L,$ then $| λ_{i} | \leq λ_{1} .$ If $λ_{1}$ is the largest magnitude eigenvalue of a matrix $L,$ we call $λ_{1}$ a dominant eigenvalue of $L .$
If any two successive entries in the first row of $L$ are both positive, then $| λ_{i} | < λ_{1}$ for every $i > 1 .$ In this case we say that $λ_{1}$ is a strictly dominant eigenvalue of $L .$ In a Leslie model, this happens when the females in two successive age classes are fertile, which is almost always the case.
If $λ_{1}$ is a strictly dominant eigenvalue, then $x_{k}$ is approximately a scalar multiple of $v_{1}$ for large values of $k,$ regardless of the initial state $x_{0} .$ In other words, large state vectors are close to eigenvectors for $λ_{1} .$

🔗

We can use these properties to determine the long-term behavior of the sheep herd.

🔗

Project Activity 20.7.

Assume that $L$ is defined by (20.6), and let

x_{m} = {[n_{1}^{(m)} n_{2}^{(m)} n_{3}^{(m)} \dots n_{12}^{(m)}]}^{T},

where $n_{1}^{(m)}$ denotes the number of sheep in age group 0-1, $n_{2}^{(m)}$ the number of sheep in age group 1-2 and, in general, $n_{k}^{(m)}$ the number of sheep in age group $(k - 1)$ - $k$ after $k$ years.

🔗

(a)

Assume that $x_{0} = {[100 100 100 \dots 100]}^{T} .$ Use appropriate technology to calculate $x_{22},$ $x_{23},$ $x_{24},$ and $x_{25} .$ Round to the nearest whole number. What do you notice about the sheep population? You may use the GeoGebra applet at geogebra.org/m/yqss88xq.

We can use the third and fourth properties of Leslie matrices to better understand the long-term behavior of the sheep population. Since successive entries in the first row of the Leslie matrix in (20.6) are positive, our Leslie matrix has a strictly dominant eigenvalue $λ_{1} .$ Given the dimensions of our Leslie matrix, finding this dominant eigenvalue through algebraic means is not feasible. Use the power method to approximate the dominant eigenvalue $λ_{1}$ of the Leslie matrix in (20.6) to five decimal places. Explain your process. Then explain how this dominant eigenvalue tells us that, unchecked, the sheep population grows at a rate that is roughly exponential. What is the growth rate of this exponential growth? You may use the GeoGebra applet at geogebra.org/m/yqss88xq.

🔗

Project Activity 20.7 indicates that, unchecked, the sheep population will grow without bound, roughly exponentially with ratio equal to the dominant eigenvalue of our Leslie matrix

L .

Of course, a sheep farmer cannot provide the physical environment or the resources to support an unlimited population of sheep. In addition, most sheep farmers cannot support themselves only by shearing sheep for the wool. Consequently, some harvesting of the sheep population each year for meat and skin is necessary. A sustainable harvesting policy allows for the regular harvesting of some sheep while maintaining the population at a stable level. It is necessary for the farmer to find an optimal harvesting rate to attain this stable population and the following activity leads us through an analysis of how such a harvesting rate can be determined.

🔗

Project Activity 20.8.

The Leslie model can be modified to consider harvesting. It is possible to harvest different age groups at different rates, and to harvest only some age groups and not others. In the case of sheep, it might make sense to only harvest from the youngest population since lamb is more desirable than mutton and the lamb population grows the fastest. Assume that this is our harvesting strategy and that we harvest our sheep from only the youngest age group at the start of each year. Let $h$ be the fraction of sheep we harvest from the youngest age group each year after considering growth.

🔗

(a)

If we begin with an initial population $x_{0},$ then the state vector after births and expected deaths is $L x_{0} .$ Now we harvest. Explain why if we harvest a fraction $h$ from the youngest age group after considering growth, then the state vector after 1 year will be

x_{1} = L x_{0} - H L x_{0},

where

H = [\begin{array}{cccccccccccc} h & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}] .

🔗

(b)

Our goal is to find a harvesting rate that will lead to a steady state in which the sheep population remains the same each year. In other words, we want to find a value of $h,$ if one exists, that satisfies

\begin{matrix} (20.7) & x = L x - H L x . \end{matrix}

Show that (20.7) is equivalent to the matrix equation

\begin{matrix} (20.8) & x = (I_{12} - H) L x . \end{matrix}

🔗

(c)

Use appropriate technology to experiment numerically with different values of $h$ to find the value you think gives the best uniform harvest rate. Explain your reasoning. You may use the GeoGebra applet at geogebra.org/m/yqss88xq.

🔗

(d)

Now we will use some algebra to find an equation that explicitly gives us the harvest rate in the general setting. This will take a bit of work, but none of it is too difficult. To simplify our work but yet illustrate the overall idea, let us consider the general $4 \times 4$ case with arbitrary Leslie matrix

L = [\begin{array}{cccc} F_{1} & F_{2} & F_{3} & F_{4} \\ s_{1} & 0 & 0 & 0 \\ 0 & s_{2} & 0 & 0 \\ 0 & 0 & s_{3} & 0 \end{array}] .

Recall that we want to find a value of $h$ that satisfies (20.8) with $H = [\begin{array}{cccc} h & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array}] .$ Let $x = [x_{1} x_{2} x_{3} x_{4}]^{T} .$

🔗

(i)

Calculate the matrix product $(I_{4} - H) L .$ Explain why this product is again a Leslie matrix and why $(I_{4} - H) L$ will have a dominant eigenvalue of 1.

🔗

(ii)

Now calculate $(I_{4} - H) L x$ and set it equal to $x .$ Write down the resulting system of 4 equations that must be satisfied. Be sure that your first equation is

\begin{matrix} (20.9) & x_{1} = (1 - h) F_{1} x_{1} + (1 - h) F_{2} x_{2} + (1 - h) F_{3} x_{3} + (1 - h) F_{4} x_{4} . \end{matrix}

🔗

(iii)

Equation (20.9) as written depends on the entries of the vector $x,$ but we should be able to arrive at a result that is independent of $x .$ To see how we do this, we assume the population of the youngest group is never 0, so we can divide both sides of (20.9) by $x_{1}$ to obtain

\begin{matrix} (20.10) & 1 = (1 - h) F_{1} + (1 - h) F_{2} \frac{x_{2}}{x_{1}} + (1 - h) F_{3} \frac{x_{3}}{x_{1}} + (1 - h) F_{4} \frac{x_{4}}{x_{1}} . \end{matrix}

Now we need to write the fractions $\frac{x_{2}}{x_{1}},$ $\frac{x_{3}}{x_{1}},$ and $\frac{x_{4}}{x_{1}}$ so that they do not involve the $x_{i} .$ Use the remaining equations in your system to show that

\begin{aligned} \frac{x_{2}}{x_{1}} & = s_{1} \\ \frac{x_{3}}{x_{1}} & = s_{1} s_{2} \\ \frac{x_{4}}{x_{1}} & = s_{1} s_{2} s_{3} . \end{aligned}

🔗

(iv)

Now conclude that the harvesting value $h$ must satisfy the equation

\begin{matrix} (20.11) & 1 = (1 - h) [F_{1} + F_{2} s_{1} + F_{3} s_{1} s_{2} + F_{4} s_{1} s_{2} s_{3}] . \end{matrix}

The value $R = F_{1} + F_{2} s_{1} + F_{3} s_{1} s_{2} + F_{4} s_{1} s_{2} s_{3}$ is called the net reproduction rate of the population and turns out to be the average number of daughters born to a female in her expected lifetime.

🔗

(e)

Extend (20.11) to the 12 age group case of the sheep herd. Calculate the value of $R$ for this sheep herd and then find the value of $h .$ Compare this $h$ to the value you obtained through experimentation earlier. Find the fraction of the lambs that should be harvested each year and explain what the stable population state vector $x$ tells us about the sheep population for this harvesting policy.

There are several other ways to scale, but we won't consider them here.

A matrix in which most entries are zero is called a sparse matrix.