Our goal is to find a technique that produces numerical approximations to the eigenvalues and associated eigenvectors of a matrix
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
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
This matrix has eigenvalues and so the dominant eigenvalue is The associated eigenvectors are and Suppose we begin with the vector
and find
and so forth. Notice that the powers
become increasingly small as
grows so that
when
is large. Therefore, the vectors
become increasingly close to a vector in the eigenspace
the eigenspace associated to the dominant eigenvalue. If we did not know the eigenvector
we could use a Markov chain in this way to find a basis vector for
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 which has eigenvalues and The dominant eigenvalue is and the associated eigenvectors are and Once again, begin with the vector so that
As the figure shows, the vectors
are stretched by a factor of
in the
direction and not at all in the
direction. Consequently, the vectors
become increasingly long, but their direction becomes closer to the direction of the eigenvector
associated to the dominant eigenvalue.
To find an eigenvector associated to the dominant eigenvalue, we will prevent the length of the vectors
from growing arbitrarily large by multiplying by an appropriate scaling constant. Here is one way to do this. Given the vector
we identify its component having the largest absolute value and call it
We then define
which means that the component of
having the largest absolute value is
For example, beginning with
we find
The component of
having the largest absolute value is
so we multiply by
to obtain
Then
Now the component having the largest absolute value is
so we multiply by
to obtain
The resulting sequence of vectors
is shown in the figure. Notice how the vectors
now approach the eigenvector
which gives us a way to find the eigenvector
This is the
power method for finding an eigenvector associated to the dominant eigenvalue of a matrix.
Notice that the power method gives us not only an eigenvector
but also its associated eigenvalue. As in the activity, consider the matrix
which has eigenvector
The first component has the largest absolute value so we multiply by
to obtain
When we multiply by
we have
Notice that the first component still has the largest absolute value so that the multiplier
is the eigenvalue
corresponding to the eigenvector. This demonstrates the fact that the multipliers
approach the eigenvalue
having the largest absolute value.
Notice that the power method requires us to choose an initial vector
For most choices, this method will find the eigenvalue having the largest absolute value. However, an unfortunate choice of
may not. For instance, if we had chosen
in our example above, the vectors in the sequence
will not detect the eigenvector
However, it usually happens that our initial guess
has some contribution from
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.