Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Matrix Calculations: Applications of Eigenvalues
and Eigenvectors; Inner Products
H. Geuvers
Institute for Computing and Information Sciences – Intelligent Systems
Radboud University Nijmegen
Version: fall 2014
H. Geuvers
Version: fall 2014
Matrix Calculations
1 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Outline
Applications of Eigenvalues and Eigenvectors
Inner products
H. Geuvers
Version: fall 2014
Matrix Calculations
2 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Political swingers re-re-revisited, part I
• Recall the political transisition matrix
0.8 0.1
P=
=
0.2 0.9
1
10
8 1
2 9
• Eigenvalues λ are obtained via det(P − λ I2 ) = 0:
8
9
( 10
− λ)( 10
− λ) −
1
10
·
2
10
= λ2 −
=
1
2
17
10
±
q
289
100
=
1 17
2 10
1 17
2 10
±
q
9
17
10 λ
+
7
10
=0
• Solutions via “abc”
1
2
17
10
±
q
17 2
10
−
28
10
=
±
3
10
−
280
100
100
1 14
7
• Hence λ = 21 · 20
10 = 1 or λ = 2 · 10 = 10 .
H. Geuvers
Version: fall 2014
Matrix Calculations
4 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Political swingers re-re-revisited, part II
−0.2x + 0.1y = 0
giving (1, 2) as eigenvector
0.2x + −0.1y = 0
0.8 + 0.2
1
1
0.8 0.1
1
• Indeed
=
=
=1
·
0.2 + 1.8
2
2
0.2 0.9
2
λ = 1 solve:
X
λ = 0.7 solve:
0.1x + 0.1y = 0
0.2x + 0.2y = 0
giving (1, −1) as eigenvector
• Check:
0.8 0.1
1
0.8 − 0.1
0.7
1
·
=
=
= 0.7
0.2 0.9
−1
0.2 − 0.9
−0.7
−1
H. Geuvers
Version: fall 2014
Matrix Calculations
X
5 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Political swingers re-re-revisited, part III
• The eigenvalues 1 and 0.7 are different, and indeed the
eigenvectors (1, 2) and (1, −1) are independent
• The coordinate-translation TV ⇒B from the eigenvector basis
V = {(1, 2), (1, −1)} to the standard basis
B = {(1, 0), (0, 1)} consists of the eigenvectors:
1 1
TV ⇒B =
2 −1
• In the reverse direction:
TB⇒V =
H. Geuvers
TV ⇒B
−1
Version: fall 2014
=
1
−1−2
−1 −1
=
−2 1
1
3
Matrix Calculations
1 1
2 −1
6 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Political swingers re-re-revisited, part IV
We explicitly check the diagonalisation equation:
!
!
!
!
1 0
1 1
1 0
1
1
TV ⇒B ·
· TB⇒V =
·
· 13
0 0.7
2 −1
0 0.7
2 −1
!
!
1 0.7
1 1
= 31
·
2 −0.7
2 −1
!
2.4 0.3
= 31
0.6 2.7
!
0.8 0.1
=
0.2 0.9
= P,
H. Geuvers
Version: fall 2014
the original political transition matrix!
Matrix Calculations
7 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Political swingers re-re-revisited, part V
1 0
· T −1 is useful for iteration
0 0.7
1 0
1 0
−1
2
• P = T·
·T ·T ·
· T −1
0
0.7
0
0.7
1 0
1 0
= T·
·
· T −1
0
0.7
0
0.7
2
1
0
= T·
· T −1
0 (0.7)2
n
(1)
0
n
• P = T·
· T −1
0 (0.7)n
1 0
n
• lim P = T ·
· T −1
since lim (0.7)n = 0
n→∞
n→∞
0
0
1 1
1 0
1
1
1
1 1 1
=
= 3
·
·3
2 −1
0 0
2 −1
2 2
This diagonalisation P = T ·
H. Geuvers
Version: fall 2014
Matrix Calculations
8 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Political swingers re-re-revisited, part VI
• In an earlier lecture we wondered how to compute
Pn
100
·
150
• We can now see that in the limit it goes to:
100
lim P ·
=
n→∞
150
n
1 1
100
·
150
2 2
1
250
83 3
1
= 3
=
500
166 23
1
3
(This was already suggested earlier, but now we can calculate it!)
Recall the useful limit result
lim an = 0,
n→∞
H. Geuvers
for |a| < 1.
Version: fall 2014
Matrix Calculations
9 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Rental car returns, part I
• Assume a car rental company with three locations, for picking
up and returning cars, written as P, Q, R
• The weekly distribution history shows:
Location P
60% stay at P
10% go to Q
30% go to R
Location Q
10% go to P
80% stay at Q
10% go to R
Location R
10% go to P
20% go to Q
70% stay at R
H. Geuvers
Version: fall 2014
Matrix Calculations
10 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Rental car returns, part II
Two possible representations of these return distributions
1
As probabilistic transition system
0.6
) GFED
u
?>=<
89:;
@ABC
P eJo J
9 Q
0.1
t
JJ
t
t
JJ 0.1
0.2 ttt
JJ
t
JJ
t
t
JJ
tt
J
tt
0.3
0.1
89:;
. ?>=<
p
R
J
0.1
0.8
0.7
H. Geuvers
Version: fall 2014
Matrix Calculations
11 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Rental car returns, part III
2
As a transition matrix
0.6 0.1 0.1
C = 0.1 0.8 0.2 =
0.3 0.1 0.7
6 1 1
1
1 8 2
10
3 1 7
This matrix C describes what is called a Markov chain:
• all entries are in the unit interval [0, 1] of probabilities
• in each column, the entries add up to 1
H. Geuvers
Version: fall 2014
Matrix Calculations
12 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Rental car returns, part IV
Task:
• Start from the following division of cars:
P = Q = R = 200
ie.
P
200
Q = 200
R
200
• Determine the division of cars after two weeks
• Determine the equilibrium division, reached as the number of
weeks goes to infinity
H. Geuvers
Version: fall 2014
Matrix Calculations
13 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Rental car returns, part V
• After one week we have:
200
C · 200 =
200
6 1 1
200
1
1 8 2 · 200
10
200
3 1 7
160
1200 + 200 + 200
1
= 10 200 + 1600 + 400
= 220
220
600 + 200 + 1400
• After two weeks we have:
160
C · 220 =
220
6 1 1
160
1
· 220
1
8
2
10
220
3 1 7
960 + 220 + 220
140
1
160 + 1760 + 440 = 236
= 10
480 + 220 + 1540
224
H. Geuvers
Version: fall 2014
Matrix Calculations
14 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Rental car returns, part VI
• For the equilibrium we first compute eigenvalues and
eigenvectors of the transition matrix C
• The characteristic polynomial is:
0.6 − λ 0.1
6 − 10λ
0.1 1
1
1
0.1 0.8 − λ 0.2 =
1
8 − 10λ
2
1000 0.3
0.1
0.7
−
λ
3
1
7
−
10λ
h
1
= 1000
(6 − 10λ) (8 − 10λ)(7 − 10λ) − 2
i
−1 (7 − 10λ) − 1 + 3 2 − 1(8 − 10λ)
= ··· h
i
1
= 1000
− 1000λ3 + 2100λ2 − 1400λ + 300
= −λ3 + 2.1λ2 − 1.4λ + 0.3.
H. Geuvers
Version: fall 2014
Matrix Calculations
15 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Rental car returns, part VII
• Next we solve −λ3 + 2.1λ2 − 1.4λ + 0.3 = 0.
• We seek a trivial solution; again λ = 1 works!
• Now we can write
−λ3 + 2.1λ2 − 1.4λ + 0.3 = (λ − 1)(−λ2 + 1.1λ − 0.3)
• We can apply the “abc” formula to the second part:
−1.1±
√
(1.1)2 −4·0.3
−2
=
=
=
√
−1.1± 1.21−1.2
−2
√
−1.1± 0.01
−2
−1.1±0.1
−2
• This yields additional eigenvalues: λ = 0.5 and λ = 0.6.
H. Geuvers
Version: fall 2014
Matrix Calculations
16 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Rental car returns, part VIII
λ = 1 has eigenvector (4, 9, 7); indeed:
4
6 1 1
4
24 + 9 + 7
4
1
1
C · 9 = 10 1 8 2 · 9 = 10 4 + 72 + 14 = 1 9
7
3 1 7
7
12 + 9 + 49
7
λ = 0.6 has eigenvector (0, −1, 1):
6 1 1
0
0
1
1 8 2 · −1 =
C · −1 = 10
3 1 7
1
1
−1 + 1
0
1
= 0.6 −1
−8
+
2
10
−1 + 7
1
λ = 0.5 has eigenvector (−1, −1, 2):
6 1 1
−6 − 1 + 2
−1
−1
−1
1
1
1 8 2·−1 = 10
−1 − 8 + 4 = 0.5 −1
C ·−1 = 10
3 1 7
2
−3 − 1 + 14
2
2
H. Geuvers
Version: fall 2014
Matrix Calculations
17 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Rental car returns, part IX
• Now: eigenvector base V = {(4, 9, 7), (0, −1, 1), (−1, −1, 2)}
and standard base as B = {(1, 0, 0), (0, 1, 0), (0, 0, 1)}.
• Then we can do change-of-coordinates back-and-forth:
TV ⇒B
4 0 −1
= 9 −1 −1
7 1 2
TB⇒V
1
1 1
1
25 −15 5
= 20
−16 4 4
• These translation matrices yield a diagonalisation:
C = TV ⇒B
H. Geuvers
Version: fall 2014
1 0 0
· 0 0.6 0 · TB⇒V
0 0 0.5
Matrix Calculations
18 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Rental car returns, part X
• Thus:
lim C n
n→∞
n
1
0
0
0 · TB⇒V
= lim TV ⇒B · 0 (0.6)n
n→∞
0 0
(0.5)n
1 0 0
4 4 4
1
9 9 9
= TV ⇒B · 0 0 0 · TB⇒V = 20
0 0 0
7 7 7
• Finally, the equilibrium starting from P = Q = R = 200 is:
4 4 4
200
120
1
· 200 = 270 .
9
9
9
20
7 7 7
200
210
H. Geuvers
Version: fall 2014
Matrix Calculations
19 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Length of a vector
• Intuitively, each vector v = (x1 , . . . , xn ) ∈ Rn has a length
(aka. size or norm or Euclidian length), written as kv k
• This kv k is a non-negative real number: kv k ∈ R, kv k ≥ 0
• Some special cases:
• n = 1: so v ∈ R, with kv k = |v |
• n = 2: so v = (x1 , x2 ) ∈ R2 and with Pythagoras:
q
and thus
kv k = x12 + x22
kv k2 = x12 + x22
• n = 3: so v = (x1 , x2 , x3 ) ∈ R3 and also with Pythagoras:
kv k2 = x12 + x22 + x32
and thus
kv k =
q
x12 + x22 + x32
• In general, for v = (x1 , . . . , xn ) ∈ Rn ,
kv k =
H. Geuvers
Version: fall 2014
q
x12 + x22 + · · · + xn2
Matrix Calculations
21 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Distance between points
• Assume now we have two vectors v , w ∈ Rn , written as:
v = (x1 , . . . , xn )
w = (y1 , . . . , yn )
• What is the distance between the endpoints?
• commonly written as d(v , w )
• again, d(v , w ) is a non-negative real
• For n = 2,
d(v , w ) =
q
(x1 − y1 )2 + (x2 − y2 )2 = kv − w k = kw − v k
• This will be used also for other n, so:
d(v , w ) = kv − w k
H. Geuvers
Version: fall 2014
Matrix Calculations
22 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Length is fundamental
• Distance can be obtained from length of vectors
• Interestingly, also angles can be obtained from length!
• Both length of vectors and angles between vectors can de
derived from the notion of inner product
H. Geuvers
Version: fall 2014
Matrix Calculations
23 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Inner product definition
Definition
For vectors v = (x1 , . . . , xn ), w = (y1 , . . . , yn ) ∈ Rn define their
inner product as the real number:
hv , w i = x1 y1 + · · · + xn yn
X
xi yi
=
1≤i≤n
Note: Length kv k can be expressed via inner product:
kv k2 = x12 + · · · + xn2 = hv , v i,
H. Geuvers
Version: fall 2014
so
kv k =
p
hv , v i.
Matrix Calculations
24 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Inner products via matrix transpose
Recall matrix transposition
For an m × n matrix A, the transpose
obtained by mirroring in the diagonal:
T
a11 · · · a1n
..
=
.
am1 · · · amn
AT is the n × m matrix A
a11 · · · am1
..
.
a1n · · · amn
The inner product of v = (x1 , . . . , xn ), w = (y1 , . . . , yn ) ∈ Rn is
then a matrix product:
y1
..
hv , w i = x1 y1 + · · · + xn yn = (x1 · · · xn ) · . = v T · w .
yn
H. Geuvers
Version: fall 2014
Matrix Calculations
25 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Inner products and angles, part I
O
?
0
/
/
_>>
>>
>>
>
/
0
h(1,0),(0,1)i=0
h(1,0),(1,1)i=1
h(1,0),(2,0)i=2
0
/
0
h(1,0),(−1,1)i=−1
0
o
/
h(1,0),(−1,−1)i=−1
/
>>
>>
>>
/
h(1,0),(0,−1)i=0
/
0
h(1,0),(−1,0)i=−1
0>
H. Geuvers
/
0
h(1,0),(1,−1)i=1
Version: fall 2014
Matrix Calculations
26 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Reminder: cosine law
A
b
C•
γ
•c
c
h
d
a
◦
c
c
c
c
c
c
D
c•
B
c 2 = a2 + b 2 − 2ab cos(γ)
Proof: By Pythagoras b 2 = h2 + d 2 and c 2 = h2 + (a − d)2 .
Hence by subtraction:
b 2 −c 2 = d 2 −a2 +2ad−d 2 = −a2 +2ad
and so
c 2 = a2 +b 2 −2ad
Recall cos(γ) = db , so by substituting d = b cos(γ) we are done. H. Geuvers
Version: fall 2014
Matrix Calculations
27 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Inner products and angles, part II
w
0
* c
kw k
c
c d(v , w ) = kv − w k
c
c
c
γ
c
- v
•
◦
kv k
The cosine rule says:
kv − w k2 = kv k2 + kw k2 − 2kv k kw k cos(γ)
That is:
cos(γ) =
kv k2 + kw k2 − kv − w k2
2kv k kw k
Let’s elaborate it . . .
H. Geuvers
Version: fall 2014
Matrix Calculations
28 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Inner products and angles, part III
Starting from the cosine rule:
kv k2 + kw k2 − kv − w k2
2kv k kw k
2
2
x1 + · · · + xn + y12 + · · · + yn2 − (x1 − y1 )2 − · · · − (xn − yn )2
2kv k kw k
2x1 y1 + · · · + 2xn yn
2kv k kw k
x1 y1 + · · · + xn yn
kv k kw k
hv , w i
hv , w i
remember this: cos(γ) =
kv k kw k
kv k kw k
cos(γ) =
=
=
=
=
Thus, anglespbetween vectors are expressible via the inner product
(since kv k =
H. Geuvers
hv , v i).
Version: fall 2014
Matrix Calculations
29 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Recall the cosine function
H. Geuvers
Version: fall 2014
Matrix Calculations
30 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Linear algebra in gaming, part I
• Linear algebra plays an important role in game visualisation
• Here: simple illustration, borrowed from blog.wolfire.com
(More precisely: http://blog.wolfire.com/2009/07/
linear-algebra-for-game-developers-part-2)
• Recall: cosine cos function is positive on angles between -90
and +90 degrees.
H. Geuvers
Version: fall 2014
Matrix Calculations
31 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Linear algebra in gaming, part II
• Consider a guard G and hero H in:
• The guard is at position (1, 1), facing in direction D =
1
,
1
with a 180 degrees field of view
• The hero is at (3, 0). Is he within view?
H. Geuvers
Version: fall 2014
Matrix Calculations
32 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Linear algebra in gaming, part III
3
1
2
−
=
0
1
−1
• The angle γ between D and V must be between -90 and +90!
• The direction vector V is: V =
hD,V i
• Hence we must have: cos(γ) = kDk·kV
k ≥0
• Since kDk ≥ 0 and kV k ≥ 0, it suffices to have: hD, V i ≥ 0
• Well, hD, V i = 1 · 2 + 1 · −1 = 1. Hence H is within sight!
H. Geuvers
Version: fall 2014
Matrix Calculations
33 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Linear algebra in gaming, part IV
• Now what if the guard’s field of view is 60 degrees?
√
• Inbetween -30 and +30 degrees we have cos ≥ 12 3 ∼ 0.87
• The cosine of the actual angle γ between D and V is:
cos(γ) =
hD, V i
1 · 2 + 1 · −1
p
= √
kDk · kV k
12 + 12 · 22 + (−1)2
1
= √ √ ∼ 0.31 < 0.87
2· 5
• H is now out of view! (the angle γ = cos−1 (0.31) = 72 degr.)
H. Geuvers
Version: fall 2014
Matrix Calculations
34 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Inner product for vector spaces in general
Definition
We say that a vector space V has an inner product if there is a
special function:
h−,−i
/R
V ×V
satisfying the following five requirements.
1
hv , v i ≥ 0
2
hv , v i = 0 if and only if v = 0
3
hv , w i = hw , v i
4
hv + v 0 , w i = hv , w i + hv 0 , w i
5
hav , w i = ahv , w i
(similarly in w , by 3)
(and similarly in w , by 3)
Given such inner product, define length, distance and angle:
p
hv , w i
kv k = hv , v i
d(v , w ) = kv − w k
cos(γ) =
.
kv k kw k
H. Geuvers
Version: fall 2014
Matrix Calculations
35 / 36
Applications of Eigenvalues and Eigenvectors
Inner products
Radboud University Nijmegen
Hilbert spaces
• The notion of inner product turns out to be very general and
flexible
• It combines algebra (vectors) and geometry (distance)
• It forms the basis of Hilbert spaces (involving “completeness”)
• Our examples: inner product on Rn
• Many other examples exist, involving for instance distance
between functions
• Important topic in abstract analysis and (quantum mechanics)
• Our main applications: projections and approximations
H. Geuvers
Version: fall 2014
Matrix Calculations
36 / 36
© Copyright 2024 ExpyDoc
