Eigenvalue Decomposition

(1)

Eigenvalue

Decomposition

Wanho Choi (wanochoi.com)

(2)

Eigenvalues & Eigenvectors

Av

_i

=

λ

_i

v

_i

A : n by n matrix

v

_i

: the i-th eigenvector

λ

_i

: the i-th eigenvalue

λ

_i

, v

_i

(

)

: the i-th eigen-pair

(

i : 1, 2, 3, ! , n

)

(3)

Geometrical Meaning

Av

_i

=

λ

_i

v

_i

The transformed vector (Ax) is a scalar multiple of the vector (x).

Ax is parallel to x.

eigen = characteristic

eigenvector : strectching direction eigenvalue: stretching factor

(4)

https://www.youtube.com/watch?v=8UX82qVJzYI

(5)

When A is a symmetric matrix, …

• Two different eigenvectors are orthogonal each other. v_iTAv _j = v_iT

( )

Av _j = v_iT

( )

λ_jv_j = v_iTλ_jv _j = λ_jv_iTv _j v_iTAv _j = v_iTATv _j = v

(

_iTAT

)

v _j = Av

( )

_i T v _j =

( )

λ_iv_i T v _j = λ_iv_iTv _j ⇒ λ_jv_iTv _j = λ_iv_iTv _j ⇔

(

λ_i − λ_j

)

v_iTv _j = 0 ∴v_iT v _j = 0 ∵

(

λ_i ≠ λ_j

)

Av_i = λ_iv_i, Av _j = λ_jv _j

(

λ_i ≠ λ_j, i ≠ j

)

AT = A

(6)

How to calculate eigenvalues

Av

_i

=

λ

_i

v

_i

⇔ A −

(

λ

_i

I

)

v

_i

= 0

⇔ det A −

(

λ

_i

I

)

= 0

λ

_i

: the i-th roots of the n-th order polynomial

(7)

Invertible Matrix Theorem

• The matrix A is invertible

if and only if 0 is not an eigenvalue of A.

Av_i = λ_iv_i If A-1 is exist, then v_i = A-1λ_iv_i. ∴A-1 v_i = 1 λ_i vi ⇔ A-1 = 1 λ1 0 ! 0 0 1 λ₂ ! 0 " " # " 0 0 0 1 λ_n ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥

(8)

Some Useful Properties

• • • • det(A) = λ₁ × λ₂ ×!× λ_n trace(A) = λ₁ + λ₂ +!+ λ_n

rank(A) = the number of non-zero eigenvalues

(9)

Eigenvalue(Spectral) Decomposition

AV= − a1 − − a2 − ! − an − ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ | | | v₁ v₂ ! vn | | | ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥= a₁⋅v₁ a₁⋅v₂ ! a1⋅vn a₂⋅v₁ a₂⋅v₂ ! a2⋅vn ! ! " ! an⋅v1 an⋅v2 ! an⋅vn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ = | | | Av1 Av2 ! Avn | | | ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥= | | | λ1v1 λ2v2 ! λnvn | | | ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥= | | | v1 v2 ! vn | | | ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ λ1 0 ! 0 0 λ₂ ! 0 ! ! " ! 0 0 ! λn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ = VΛ Av_i = λ_iv_i ⇔ AV = VΛ ⇔ A = VΛVT ⇔ A = λ_i i=1 n

∑

v_iv_iT V−1= VT V : orthonormal( ) A = | ! | v₁ ! v_n | ! | ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ λ₁ ! 0 " # " 0 ! λ_n ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ − v₁ − ! " ! − v_n − ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ α 0₀ _β ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ a c b d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ =⎡ a b_{c d} ⎣ ⎢ ⎤ ⎦ ⎥⎡ αa αc_{βb βd} ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = αaa + βbb αac + βbd αac + βbd αcc + βdd ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥=α aa acac cc ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ + β⎡ bb bd_{bd dd} ⎣ ⎢ ⎤ ⎦ ⎥ =α a c ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ a c⎡_⎣ ⎤_{⎦ + β}⎡ b_d ⎣ ⎢ ⎤ ⎦ ⎥ b d⎡_⎣ ⎤_⎦ rotation inverse rotation stretching

(10)

Eigenspace

n unknowns n equations Ax = b VΛVT

(

)

x = b Λ VT x

( )

= VT b Λy = d VTx = y x = Vy linear system

(globally coupled system) eigenvalue decomposition

decoupled n equations in eigenspace

(11)

Eigenvalue Analysis

• It gives the solution of Ax=b, and simplifies the

solution of a certain problem by reducing a coupled system to a collection of scalar problems.

• _{It gives insight into the}_{behavior of evolving}

systems governed by linear equation.

Am = VΛV

(

T

)

m = VΛV

(

T

)

(

VΛVT

)

! VΛV

(

T

)

= VΛVT VΛVT

(

)

! VΛV

(

T

)

= VΛIΛV

(

T

)

! VΛV

(

T

)

= VΛΛV

(

T

)

! VΛV

(

T

)

= VΛ2 VT

(

)

! VΛV

(

T

)

= ! = VΛm VT Ax = b ⇔ VΛV

(

T

)

x = b ⇔ Λ V

( )

Tx = VTb ⇔ Λy = d

(12)

Applications of Eigenvalue Analysis

• Analyzing natural frequency in vibration

• Analyzing stability or convergence in iteration

• Approximation with lower computation

(13)

Applications of Eigenvalue Analysis

• _Analyzing_stability_or_convergence_{in iteration}

• Approximation with lower computation

y_n = 1+ Δt( λ)n y₀ (λ < 0 in this case) : It converges when 1+ Δtλ ≤ 1. ⇔ −1 < 1+ Δtλ < 1 ⇔ − 2 < Δtλ < 0 ∴Δt < −2 λ y_n₊₁ = y_n + Δt ⋅ f (y_n) = y_n + Δt ⋅Ay_n = y_n + Δt ⋅ Λy_n = I + Δt ⋅ Λ( )y_n