Skip to main content
Logo image

Section 5.2 Finding eigenvectors numerically

We have typically found eigenvalues of a square matrix A as the roots of the characteristic polynomial det(AλI)=0 and the associated eigenvectors as the null space Nul(AλI). Unfortunately, this approach is not practical when we are working with large matrices. First, finding the charactertic polynomial of a large matrix requires considerable computation, as does finding the roots of that polynomial. Second, finding the null space of a singular matrix is plagued by numerical problems, as we will see in the preview activity.
For this reason, we will explore a technique called the power method that finds numerical approximations to the eigenvalues and eigenvectors of a square matrix.

Preview Activity 5.2.1.

Let’s recall some earlier observations about eigenvalues and eigenvectors.
  1. How are the eigenvalues and associated eigenvectors of A related to those of A1?
  2. How are the eigenvalues and associated eigenvectors of A related to those of A3I?
  3. If λ is an eigenvalue of A, what can we say about the pivot positions of AλI?
  4. Suppose that A=[0.80.40.20.6]. Explain how we know that 1 is an eigenvalue of A and then explain why the following Sage computation is incorrect.
  5. Suppose that x0=[10], and we define a sequence xk+1=Axk; in other words, xk=Akx0. What happens to xk as k grows increasingly large?
  6. Explain how the eigenvalues of A are responsible for the behavior noted in the previous question.

Subsection 5.2.1 The power method

Our goal is to find a technique that produces numerical approximations to the eigenvalues and associated eigenvectors of a matrix A. We begin by searching for the eigenvalue having the largest absolute value, which is called the dominant eigenvalue. The next two examples demonstrate this technique.

Example 5.2.1.

Let’s begin with the positive stochastic matrix A=[0.70.60.30.4]. We spent quite a bit of time studying this type of matrix in Section 4.5; in particular, we saw that any Markov chain will converge to the unique steady-state vector. Let’s rephrase this statement in terms of the eigenvectors of A.
This matrix has eigenvalues λ1=1 and λ2=0.1 so the dominant eigenvalue is λ1=1. The associated eigenvectors are v1=[21] and v2=[11]. Suppose we begin with the vector
x0=[10]=13v113v2
and find
x1=Ax0=13v113(0.1)v2x2=A2x0=13v113(0.1)2v2x3=A3x0=13v113(0.1)3v2xk=Akx0=13v113(0.1)kv2
and so forth. Notice that the powers 0.1k become increasingly small as k grows so that xk13v1 when k is large. Therefore, the vectors xk become increasingly close to a vector in the eigenspace E1, the eigenspace associated to the dominant eigenvalue. If we did not know the eigenvector v1, we could use a Markov chain in this way to find a basis vector for E1, which, as seen in Section 4.5, is essentially how the Google PageRank algorithm works.

Example 5.2.2.

Let’s now look at the matrix A=[2112], which has eigenvalues λ1=3 and λ2=1. The dominant eigenvalue is λ1=3, and the associated eigenvectors are v1=[11] and v2=[11]. Once again, begin with the vector x0=[10]=12v112v2 so that
x1=Ax0=312v112v2x2=A2x0=3213v112v2x3=A3x0=3313v112v2xk=Akx0=3k13v112v2.
As the figure shows, the vectors xk are stretched by a factor of 3 in the v1 direction and not at all in the v2 direction. Consequently, the vectors xk become increasingly long, but their direction becomes closer to the direction of the eigenvector v1=[11] associated to the dominant eigenvalue.
To find an eigenvector associated to the dominant eigenvalue, we will prevent the length of the vectors xk from growing arbitrarily large by multiplying by an appropriate scaling constant. Here is one way to do this. Given the vector xk, we identify its component having the largest absolute value and call it mk. We then define xk=1mkxk, which means that the component of xk having the largest absolute value is 1.
For example, beginning with x0=[10], we find x1=Ax0=[21]. The component of x1 having the largest absolute value is m1=2 so we multiply by 1m1=12 to obtain x1=[112]. Then x2=Ax1=[522]. Now the component having the largest absolute value is m2=52 so we multiply by 25 to obtain x2=[145].
The resulting sequence of vectors xk is shown in the figure. Notice how the vectors xk now approach the eigenvector v1, which gives us a way to find the eigenvector v=[11]. This is the power method for finding an eigenvector associated to the dominant eigenvalue of a matrix.

Activity 5.2.2.

Let’s begin by considering the matrix A=[0.50.20.40.7] and the initial vector x0=[10].
  1. Compute the vector x1=Ax0.
  2. Find m1, the component of x1 that has the largest absolute value. Then form x1=1m1x1. Notice that the component having the largest absolute value of x1 is 1.
  3. Find the vector x2=Ax1. Identify the component m2 of x2 having the largest absolute value. Then form x2=1m2x1 to obtain a vector in which the component with the largest absolute value is 1.
  4. The Sage cell below defines a function that implements the power method. Define the matrix A and initial vector x0 below. The command power(A, x0, N) will print out the multiplier m and the vectors xk for N steps of the power method.
    How does this computation identify an eigenvector of the matrix A?
  5. What is the corresponding eigenvalue of this eigenvector?
  6. How do the values of the multipliers mk tell us the eigenvalue associated to the eigenvector we have found?
  7. Consider now the matrix A=[5.15.73.84.4]. Use the power method to find the dominant eigenvalue of A and an associated eigenvector.
Notice that the power method gives us not only an eigenvector v but also its associated eigenvalue. As in the activity, consider the matrix A=[5.15.73.84.4], which has eigenvector v=[32]. The first component has the largest absolute value so we multiply by 13 to obtain v=[123]. When we multiply by A, we have Av=[1.300.86]. Notice that the first component still has the largest absolute value so that the multiplier m=1.3 is the eigenvalue λ corresponding to the eigenvector. This demonstrates the fact that the multipliers mk approach the eigenvalue λ having the largest absolute value.
Notice that the power method requires us to choose an initial vector x0. For most choices, this method will find the eigenvalue having the largest absolute value. However, an unfortunate choice of x0 may not. For instance, if we had chosen x0=v2 in our example above, the vectors in the sequence xk=Akx0=λ2kv2 will not detect the eigenvector v1. However, it usually happens that our initial guess x0 has some contribution from v1 that enables us to find it.
The power method, as presented here, will fail for certain unlucky matrices. This is examined in Exercise 5.2.4.5 along with a means to improve the power method to work for all matrices.

Subsection 5.2.2 Finding other eigenvalues

The power method gives a technique for finding the dominant eigenvalue of a matrix. We can modify the method to find the other eigenvalues as well.

Activity 5.2.3.

The key to finding the eigenvalue of A having the smallest absolute value is to note that the eigenvectors of A are the same as those of A1.
  1. If v is an eigenvector of A with associated eigenvector λ, explain why v is an eigenvector of A1 with associated eigenvalue λ1.
  2. Explain why the eigenvalue of A having the smallest absolute value is the reciprocal of the dominant eigenvalue of A1.
  3. Explain how to use the power method applied to A1 to find the eigenvalue of A having the smallest absolute value.
  4. If we apply the power method to A1, we begin with an intial vector x0 and generate the sequence xk+1=A1xk. It is not computationally efficient to compute A1, however, so instead we solve the equation Axk+1=xk. Explain why an LU factorization of A is useful for implementing the power method applied to A1.
  5. The following Sage cell defines a command called inverse_power that applies the power method to A1. That is, inverse_power(A, x0, N) prints the vectors xk, where xk+1=A1xk, and multipliers 1mk, which approximate the eigenvalue of A. Use it to find the eigenvalue of A=[5.15.73.84.4] having the smallest absolute value.
  6. The inverse power method only works if A is invertible. If A is not invertible, what is its eigenvalue having the smallest absolute value?
  7. Use the power method and the inverse power method to find the eigenvalues and associated eigenvectors of the matrix A=[0.232.331.161.08].
With the power method and the inverse power method, we can now find the eigenvalues of a matrix A having the largest and smallest absolute values. With one more modification, we can find all the eigenvalues of A.

Activity 5.2.4.

Remember that the absolute value of a number tells us how far that number is from 0 on the real number line. We may therefore think of the inverse power method as telling us the eigenvalue closest to 0.
  1. If v is an eigenvector of A with associated eigenvalue λ, explain why v is an eigenvector of AsI where s is some scalar.
  2. What is the eigenvalue of AsI associated to the eigenvector v?
  3. Explain why the eigenvalue of A closest to s is the eigenvalue of AsI closest to 0.
  4. Explain why applying the inverse power method to AsI gives the eigenvalue of A closest to s.
  5. Consider the matrix A=[3.61.64.07.61.62.24.44.13.94.39.00.67.64.10.65.0]. If we use the power method and inverse power method, we find two eigenvalues, λ1=16.35 and λ2=0.75. Viewing these eigenvalues on a number line, we know that the other eigenvalues lie in the range between λ1 and λ1, as shaded in Figure 5.2.3.
    Figure 5.2.3. The range of eigenvalues of A.
    The Sage cell below has a function find_closest_eigenvalue(A, s, x, N) that implements N steps of the inverse power method using the matrix AsI and an initial vector x. This function prints approximations to the eigenvalue of A closest to s and its associated eigenvector. By trying different values of s in the shaded regions of the number line shown in Figure 5.2.3, find the other two eigenvalues of A.
  6. Write a list of the four eigenvalues of A in increasing order.
There are some restrictions on the matrices to which this technique applies as we have assumed that the eigenvalues of A are real and distinct. If A has repeated or complex eigenvalues, this technique will need to be modified, as explored in some of the exercises.

Subsection 5.2.3 Summary

We have explored the power method as a tool for numerically approximating the eigenvalues and eigenvectors of a matrix.
  • After choosing an initial vector x0, we define the sequence xk+1=Axk. As k grows larger, the direction of the vectors xk closely approximates the direction of the eigenspace corresponding to the eigenvalue λ1 having the largest absolute value.
  • We normalize the vectors xk by multiplying by 1mk, where mk is the component having the largest absolute value. In this way, the vectors xk approach an eigenvector associated to λ1, and the multipliers mk approach the eigenvalue λ1.
  • To find the eigenvalue having the smallest absolute value, we apply the power method using the matrix A1.
  • To find the eigenvalue closest to some number s, we apply the power method using the matrix (AsI)1.

Exercises 5.2.4 Exercises

This Sage cell has the commands power, inverse_power, and find_closest_eigenvalue that we have developed in this section. After evaluating this cell, these commands will be available in any other cell on this page.

1.

Suppose that A is a matrix having eigenvalues 3, 0.2, 1, and 4.
  1. What are the eigenvalues of A1?
  2. What are the eigenvalues of A+7I?

2.

Use the commands power, inverse_power, and find_closest_eigenvalue to approximate the eigenvalues and associated eigenvectors of the following matrices.
  1. A=[2282].
  2. A=[0.60.70.50.2].
  3. A=[1.916.013.027.02.420.34.617.70.5111.71.413.12.115.36.920.5].

3.

Use the techniques we have seen in this section to find the eigenvalues of the matrix
A=[14.69.014.15.813.027.84.216.00.921.35.53.43.43.31.125.411.315.44.720.333.714.822.59.726.6].

4.

Consider the matrix A=[0140].
  1. Describe what happens if we apply the power method and the inverse power method using the initial vector x0=[10].
  2. Find the eigenvalues of this matrix and explain this observed behavior.
  3. How can we apply the techniques of this section to find the eigenvalues of A?

5.

We have seen that the matrix A=[1221] has eigenvalues λ1=3 and λ2=1 and associated eigenvectors v1=[11] and v2=[11].
  1. Describe what happens when we apply the inverse power method using the initial vector x0=[10].
  2. Explain why this is happening and provide a contrast with how the power method usually works.
  3. How can we modify the power method to give the dominant eigenvalue in this case?

6.

Suppose that A is a 2×2 matrix with eigenvalues 4 and 3 and that B is a 2×2 matrix with eigenvalues 4 and 1. If we apply the power method to find the dominant eigenvalue of these matrices to the same degree of accuracy, which matrix will require more steps in the algorithm? Explain your response.

7.

Suppose that we apply the power method to the matrix A with an initial vector x0 and find the eigenvalue λ=3 and eigenvector v. Suppose that we then apply the power method again with a different initial vector and find the same eigenvalue λ=3 but a different eigenvector w. What can we conclude about the matrix A in this case?

8.

The power method we have developed only works if the matrix has real eigenvalues. Suppose that A is a 2×2 matrix that has a complex eigenvalue λ=2+3i. What would happen if we apply the power method to A?

9.

Consider the matrix A=[1101].
  1. Find the eigenvalues and associated eigenvectors of A.
  2. Make a prediction about what happens if we apply the power method and the inverse power method to find eigenvalues of A.
  3. Verify your prediction using Sage.
You have attempted 1 of 1 activities on this page.