Chapter 4 Eigenvector and Eigenvalue

[Def] $A \in {I\!\!R}^{n \times n} , v \ne 0$ If $Av = \lambda v$ , then v is called the eigenvector of A associated with the Eigenvalue $\lambda$.

${\varphi}_{\lambda} = \{ v \vert Av = \lambda v \}$is a subspace of ${I\!\!R}^n$ is called the Eigen Space of A associated with $\lambda$

< Characteristic Polynomial : $det( \lambda I - A) = P (\lambda)$ >

If $\lambda$ is an eigenvalue of A , then

1. $det( \lambda I - A ) = 0$ 2. $( \lambda I - A )$ is singular

$\Rightarrow$ If $\lambda$ is an eigenvalue $\Rightarrow P ( \lambda ) = 0$

$\left \{ \matrix{ {{d x_1 (t)} \over {dt}} = a_{11} x_1 + a_{12} x_2 + \cdots ... ... (t)} \over {dt}} = a_{n1} x_1 + a_{n2} x_2 + \cdots + a_{nn} x_n \cr }\right$ $\Rightarrow {{dx} \over {dt}} = Ax$

The solution is of the form x(t) = f(t) v

$\Rightarrow$ differentiate with respected to t .

$\Rightarrow {x^'} (t) = {f^'} (t) v$

because f^' (t) v = A f(t) v $\Rightarrow {f^'}(t) v = f(t) Av$ $\Rightarrow Av = {{{f^'} (t)} \over {f(t)}} v$

Let ${{{f^'} (t)} \over {f(t)}} = \lambda \Rightarrow f(t) = c e^{\lambda t}$

$\Rightarrow Av = \lambda v \par\Rightarrow Av = c e^{\lambda t} v$

1. Power Method ( Find MAX. eigenvalue ) 2. Inverse Power Method ( Find MIN. eigenvalue) 3. Shift Inverse Power Method ( Find the eigenvalue close to fixed u )

Power Method :

If ${\lambda}_1 , {\lambda}_2 , \cdots , {\lambda}_n$ are eigenvalue of A with $\vert {\lambda}_1 \vert > \vert {\lambda}_1 \vert \geq \vert {\lambda}_3 \vert \geq \cdots \geq \vert {\lambda}_n \vert$ and $v_1 , v_2 , \cdots , v_n$ are eigenvectors and linear indep. associated with ${\lambda}_1 , {\lambda}_2 , \cdots , {\lambda}_n$ respectively .

STEP : Let q be any vector in ${I\!\!R}^n$ consider the sequence $q , Aq , A^2 q , \cdots , A^n q$

because $\{ v_1 , v_2 , \cdots , v_n \}$ form a basis of ${I\!\!R}^n$

$\Rightarrow q = c_1 v_1 + c_2 v_2 + \cdots + c_n v_n$

W.l.o.G. ( Without loss of Generality )

We may assume

$q = v_1 + v_2 + \cdots + v_n$ $\Rightarrow$ $Aq = A ( v_1 + v_2 + \cdots + v_n )$ = ${\lambda}_1 v_1 + {\lambda}_2 v_2 + \cdots + {\lambda}_n v_n$

$\Rightarrow$ A² q = ${\lambda}^2_1 v_1 + {\lambda}^2_2 v_2 + \cdots + {\lambda}^2_n v_n$

In general ,

Aⁿ q = ${\lambda}^n_1 v_1 + {\lambda}^n_2 v_2 + \cdots + {\lambda}^n_n v_n$ =
${\lambda}^n_1 ( v_1 + {( {{\lambda}_2} \over {{\lambda}_1} )}^n v_2 + \cdots + {({ {{\lambda}_n} \over {{\lambda}_1} })}^n v_n)$

$\Rightarrow$ ${ {A^n q} \over {\lambda}^n_1}$ = $v_1 + {( { {{\lambda}_2} \over {{\lambda}_1} } )}^n v_2$ + $\cdots$ + ${( { {{\lambda}_n} \over {{\lmbda}_1} } )}^n v_n$
= $v_1 + \varepsilon ({ {{\lambda}_2} \over {{\lambda}_1} })$

Aⁿ q = ${\lambda}^n_1 ( v_1 + \varepsilon ({ {{\lambda}_2} \over {{\lambda}_1} }))$where $\varepsilon ({{{\lambda}_2} \over {{\lambda}_1}}) \rightarrow 0$ when $n \rightarrow \infty$

Let $\phi (x)$ be a linear functional [ for example : $\phi (x) = {\Vert x \Vert}_{\infty}$]

${ {\phi( {\lambda}^{n+1}_1 ( v_1 + \varepsilon ({ {{\lambda}_2} \over {{\lam... ...\lambda}^n_1 ( v_1 + \varepsilon ({ {{\lambda}_2} \over {{\lambda}_1} }) ) }}$= ${\lambda}_1 {{\phi ( v_1 + \varepsilon ({{{\lambda}_2} \over {{\lambda}_1}}) ) } \over {\phi ( v_1 + \varepsilon ({{{\lambda}_2} \over {{\lambda}_1}}) ) }}$= ${\lambda}_1$

Example : 4.3.5

A = $\left [ \matrix{ 9 & 1 \cr 1 & 2 \cr } \right ]$ , q₀ = ${\left [ \matrix{ 1 & 1 \cr } \right ]}^T$

[Sol]

STEP 1. Find a sequence $q_0 , A q_0 , \cdots , A^n q_0$A q₀ = $\left [ \matrix{ 9 & 1 \cr 1 & 2 \cr } \right ]$ $\left [ \matrix{ 1 \cr 1 \cr } \right ]$ = $\left [ \matrix{ 10 \cr 3 \cr } \right ]$ = q₁

STEP 2. $\phi (x)$ = ${\Vert x \Vert}_{\infty}$ $\Rightarrow$ ${\left \Vert \matrix{ \left [ \matrix{ 10 \cr 3 \cr } \right ] \cr } \right \Vert }_{\infty}$ = 10 = ${\sigma}_1$

$\Rightarrow$ ${\~ g}_1$ = ${ 1 \over {10}}$ $\left [ \matrix{ 10 \cr 3 \cr } \right ]$ = $\left [ \matrix{ 1 \cr { 3 \over {10} } \cr } \right ]$

STEP 3. repeat STEP 2.

A² q₀ $\Rightarrow$ A (A q₀) = A q₂ = $10 A {\~ q}_1$

consider $A {\~ q}_1$ = $\left [ \matrix{ 9 & 1 \cr 1 & 2 \cr } \right ]$ $\left [ \matrix{ 1 \cr { 3 \over {10} } \cr } \right ]$ = $\left [ \matrix{ 9.3 \cr 1.6 \cr } \right ]$ = q₂

${\~ q}_2$ = ${{q_2} \over {\Vert q_2 \Vert}_{\infty}}$ = $\left [ \matrix{ 1 \cr {{1.6} \over {9.3}} } \right ]$

By Table 4.1 ( P213 )
Eigenvalue : 9.140055
Eigenvector : ( 1 , 0.140055 )

${{A^n q_0} \over {\lambda}^n_1}$ = $u_1 + \varepsilon ({ {{\lambda}_2} \over {{\lambda}_1} })$

$\Rightarrow$ Aⁿ q₀ = ${\lambda}^n_1 ( u_1 + \varesilon ( { ({ {{\lambda}_2} \over {{\lambda}_1} }) }^n )$

${\sigma}_j \rightarrow {\lambda}_1$ , when $j \rightarrow \infty$

${\sigma}_1 = {\Vert A q_0 \Vert}_{\infty}$

${\sigma}_2 = {\Vert A {\~ q_1} \Vert}_{\infty}$

$~~~~~~~~~~~~~~\vdots$

${\sigma}_n$ = ${\Vert A {{\~ q}_n-1} \Vert}_{\infty}$ = ${{\vert {\lambda}^n_1 \vert {\Vert u_1 + \varepsilon {( {{{\lambda}_2} \over {... ...\varepsilon {( {{{\lambda}_2} \over {{\lambda}_1}} )}^{n-1} \Vert}_{\infty}} }$ $\rightarrow {\lambda}_1$

[Thm] If a is nonsingular , if $\lambda$ is an Eigenvalue of A , then ${\lambda}^{-1}$ isi an Eigenvalue of A^-1 .

<Proof> If $\lambda$ is an Eigenvalue of A

$\Rightarrow Ax = \lambda x \par\Rightarrow x = A^{-1} \lambda x = \lambda (A^{-1} x) \par\Rightarrow {\lambda}^{-1} x = A^{-1} x$

Inverse Power Method :

( For finding the smallest Eigenvlaue of A )

1. If $\vert {\lambda}_1 \vert \geq \vert {\lambda}_2 \vert \geq \cdots \geq \vert {\lambda}_{n-1} \vert \geq \vert {\lambda}_n \vert$2. and $v_1 , v_2 , \cdots , v_n$ are L.I. Eigenvectors . 3. A is nonsingular .

$\Rightarrow {\vert {\lambda}^{-1}_n \vert} > {\vert {\lambda}^{-1}_{n-1} \vert}... ...rt {\lambda}^{-1}_{n-2} \vert} \geq \cdots \geq {\vert {\lambda}^{-1}_1 \vert}$

apply Power Method to A^-1

$\Rightarrow$ ${\lambda}^{-1}_n$ can be found by regular Power Method on A^-1

Shift Inverse Power Method :

[Thm] If $\lambda$ is an Eigenvalue of A , then $\lambda - u$ is an Eigenvalue of (A - uI) .

<Proof> because $Ax = \lambda x$

$\Rightarrow ( A - uI ) x = Ax - ux = \lambda x - ux = ( \lambda - u ) x$

so $\lambda - u$ is an Eigenvalue of ( A - uI )

1. Given $\varepsilon > 0$

s.t. $\vert {\lambda}_j - u \vert < \varepsilon$ , and $\vert {\lambda}_k - u \vert > \varepsilon$ for all $k \ne j$2. $v_1 , \cdots , v_n$ L.I. Eigenvectors 3. A^-1 exists

Example : ${\lambda}_1 = 1 , {\lambda}_2 = 1.3 , {\lambda}_3 = 2$ are Eigenvalue of A

[Sol] Let u = 1.2 , consider $\vert {\lambda}_i - u \vert \par\Rightarrow \vert {\lambda}_1 - u \vert , \ver... ...a}_2 - u \vert , \vert {\lambda}_3 - u \vert \par\Rightarrow 0.2 , 0.1 , 0.8 ,$ are Eigenvalues of ( A - uI )

1. If ${\lambda}_1 , {\lambda}_2 , \cdots , {\lambda}_n$ are Eigenvalues of A ,

then ${\lambda}_1 - u , {\lambda}_2 - u , \cdots , {\lambda}_n - u$ are Eigenvalues of A - uI2. If $\vert {\lambda}_j - u \vert$ are the smallest Eigenvalue of A - uI ,

then Apply the inverse Power Method on (A - uI) ,

we can find ${\lambda}_j - u$ ( $\Rightarrow {\lambda}_i$ can be fonud )

Issue :

1. Power Method : find MAX. Eigenvalue and Eigenvector 2. Inverse Power Method : find MIN. Eigenvalue and Eigenvector 3. Shift Inverse Power Method : find the Eigenvalue colse to fixed u