Eigenvalues and Eigenvectors
CS/SE 4X03
Ned Nedialkov McMaster University March 30, 2021
Outline
Introduction Power method Rayleigh quotient
Introduction Power method Rayleigh quotient Introduction
• Given an n × n matrix A, a nonzero vector v is an eigenvector of A if
Av = λv, λ is scalar (1) That is, v does not change direction under the transformation
Av
• We can write (1) as
Av = λv ⇔ Av = λIv ⇔ (A − λI)v = 0
I is the n × n identity matrix
• (A − λI)v = 0 has a nonzero solution v when
det(A − λI) = 0
• det(A − λI) is characteristic polynomial, det(A − λI) = 0 is characteristic equation
Copyright © 2021 N. Nedialkov. All rights reserved. 3/15
Introduction Power method Rayleigh quotient Introduction cont.
Example 1. Consider
Then
1 2 A= 3 −4
1−λ 2 A − λI = 3 −4 − λ
det(A−λI) = (−4−λ)(1−λ)+6 = −4+4λ−λ+λ2 −6 =λ2 +3λ−10=0
hasrootsλ1 =2andλ2 =−5.
Copyright © 2021 N. Nedialkov. All rights reserved. 4/15
Introduction Power method Rayleigh quotient Introduction cont.
Example 1. cont. For λ1 = 2,
1−2 2 −1 2 (A−2I)v= 3 −4−2 v= 3 −6 v=0
has solution v1 = [2, 1]T , and
1 2 2 4 2
Av1 = 3 −4 1 = 2 = 2 1 1+5 2 6 2
For λ1 = −5,
(A+5I)v= 3 −4+5 v= 3 1 v=0
has solution v2 = [1, −3]T , and
1 2 1 −5 1
Av1 = 3 −4 −3 = 15 = −5 −3
Copyright © 2021 N. Nedialkov. All rights reserved. 5/15
Introduction Power method Rayleigh quotient Introduction cont.
Example 2. Example form p. 223–225 of U. Ascher and C. Greig, A First Course in Numerical Methods
• Graph with n nodes, 1, 2, . . . , n, each node corresponds to a webpage
• If node i links to node j, directed edge from i to j 13
4
2
5
6
• Assume j points to Nj pages
E.g. page j = 3 points to N3 = 3 pages 1, 4, 6
Copyright © 2021 N. Nedialkov. All rights reserved. 6/15
Introduction Power method Rayleigh quotient Introduction cont.
Example 2. cont.
• Denote the importance of node (page) i by xi
• j contributes 1 xj to the importance of each page it points to Nj
E.g. page j = 3 contributes 1×3 to each of 1,4, and 6 3
page j = 1 contributes 1×1 to each of 2 and 4 2
• Can be represented as a matrix
123456
1
2
1
3 111
222
3 1
1 a blank denotes 0
4 5 6
2 11
23
1
2 111
232
• Column: out links, row: in links
Copyright © 2021 N. Nedialkov. All rights reserved. 7/15
Introduction Power method Rayleigh quotient Introduction cont.
Example 2. cont. • Then
E.g.
xi= 1xj, i=1,…,n j:j→i Nj
x4= 1×1+ 1×3=1×1+1×3 N1 N3 2 3
• We have n equations. As a system: Ax = x
• Eigenvalue problem!
Copyright © 2021 N. Nedialkov. All rights reserved. 8/15
Introduction Power method Rayleigh quotient Introduction cont.
Example 2. cont.
• Given page i, the number of links to it is << n, total number of
pages. n can be in the billions
• A is very large and sparse
• The sum in each column is 1
• This matrix is column stochastic
• There is a unique largest eigenvalue 1
• Entries in the corresponding eigenvector are positive
• How to find this eigenvector?
Copyright © 2021 N. Nedialkov. All rights reserved. 9/15
Introduction Power method Rayleigh quotient Power method
• Method for finding the largest eigenvalue and corresponding eigenvector
• Denote an eigen pair by (λi, xi)
• Assume λ1 real and |λ1| > |λi| for all i = 2,…,n
• Assume A has n linearly independent eigenvectors
• Anyv∈Rn canbewrittenas
n
v = αjxj, αj scalar
j=1
• Compute Av, A2v, …, Akv
Copyright © 2021 N. Nedialkov. All rights reserved.
10/15
Introduction Power method Rayleigh quotient Power method cont.
We have
nnn
Av = Aαjxj = αj(Axj) = αjλjxj
j=1 j=1 j=1 nnn
A2v = A(Av) = Aαjλjxj = αjλj(Axj) = αjλ2jxj j=1 j=1 j=1
.
nn
Akv = A(Ak−1v) = Aαjλk−1xj = αjλk−1(Axj) jj
n
= α j λ kj x j
j=1
j=1 j=1
Copyright © 2021 N. Nedialkov. All rights reserved.
11/15
Introduction Power method Rayleigh quotient Power method cont.
A k v = λ k1 α 1 x 1 + λ k2 α 2 x 2 + · · · + λ kn α n x n
λ2k λnk
= λ k1 α 1 x 1 + λ α 2 x 2 + · · · + λ α n x n 11
• Since|λ1|>|λj|,λjk →0ask→∞forallj≥2 λ1
• Then
• Akv converges to a multiple of x1, the eigenvector
corresponding to λ1
Copyright © 2021 N. Nedialkov. All rights reserved.
Akv → (λk1α1)x1
12/15
Introduction Power method Rayleigh quotient Power method cont.
• Rate of convergence depends on |λ2|/|λ1| • If |λ1| > 1, Akv ≈ (λk1α1)x1 can overflow • If |λ1| < 1, Akv ≈ (λk1α1)x1 can underflow • How to avoid over/underflow? Normalize
• Compute
◦ start with any v
◦ for k = 1,2,..., until convergence
v=Av
v=v/∥v∥
Copyright © 2021 N. Nedialkov. All rights reserved.
13/15
Introduction Power method Rayleigh quotient Rayleigh quotient
• Rayleigh quotient
μ(v) = vT Av vTv
• If v is an eigenvector
μ(v)= vTAv = vTλv =λ
vTv vTv
• If v is an approximation to an eigenvector μ(v) ≈ λ
Power method
v0 initial guess
for k = 1, 2, . . . until termination
v = Avk−1 v k = v / ∥ v ∥
λ(k) =vTAv 1kk
Copyright © 2021 N. Nedialkov. All rights reserved.
14/15
Introduction Power method Rayleigh quotient Example 2. cont.
• Start with v = (1/6, 1/6, 1/6, 1/6, 1/6, 1/6)T , ∥v∥1 = 1 • v = Av, ∥v∥1 = 1, need to normalize
• The x for the PageRank example is
• Ranking is
0.2174
page 1 2 3 4 5 6 rank 5 3 1 4 6 2
0.0994 0.1615 0.2981
x ≈ 0.1491 0.0745
Copyright © 2021 N. Nedialkov. All rights reserved.
15/15