Database Reference
In-Depth Information
Recall from
Example 11.2
that the true principal eigenvector is 7. Power iteration will in-
troduce small errors due either to limited precision, as was the case here, or due to the fact
that we stop the iteration before reaching the exact value of the eigenvector. When we com-
puted PageRank, the small inaccuracies did not matter, but when we try to compute all ei-
genpairs, inaccuracies accumulate if we are not careful.
□
To find the second eigenpair we create a new matrix
M
∗
=
M
− λ
1
xx
T
. Then, use power
iteration on
M
∗
to compute its largest eigenvalue. The obtained
x
∗
and λ
∗
correspond to the
second largest eigenvalue and the corresponding eigenvector of matrix
M
.
Intuitively, what we have done is eliminate the influence of a given eigenvector by set-
ting its associated eigenvalue to zero. The formal justification is the following two obser-
vations. If
M
∗
=
M
− λ
xx
T
, where
x
and λ are the eigenpair with the largest eigenvalue, then:
(1)
x
is also an eigenvector of
M
∗
, and its corresponding eigenvalue is 0. In proof, observe
that
M
∗
x
= (
M
− λ
xx
T
)
x
=
M
x
− λ
xx
T
x
=
M
x
− λ
x
= 0
At the next-to-last step we use the fact that
x
T
x
= 1 because
x
is a unit vector.
(2) Conversely, if
v
and λ
v
are an eigenpair of
M
other than the first eigenpair (
x
, λ), then
they are also an eigenpair of
M
∗
.
Proof
:
M
∗
v
= (
M
∗
)
T
v
= (
M
− λ
xx
T
)
T
v
=
M
T
v
− λ
x
(
x
T
v
) =
M
T
v
= λ
v
v
This sequence of equalities needs the following justifications:
(a)
M
and
M
T
have the same set of eigenvalues and eigenvectors. Note that if
M
is
symmetric, then
M
=
M
T
; but even if
M
is not symmetric, the statement is true,
although we do not prove it here.
(b) The eigenvectors of a matrix are
orthogonal
. That is, the dot product of any two
distinct eigenvectors of a matrix is 0. We do not prove this statement here.
EXAMPLE
11.4 Continuing
Example 11.3
, we compute
We may find the second eigenpair by processing the matrix above as we did the original
matrix
M
.
□
