Chapter 9 - Generalized Eigenvectors PDF

Preview

Summary

Linear Algebra...

Description

Chapter 9 Generalized Eigenvectors Definition 9.1 A vector vm is a generalized eigenvector of rank m for the square matrix A and associated eigenvector λ if (A − λI)m vm = 0 and (A − λI )i vm 6= 0 ∀ 1 ≤ i ≤ m − 1.       −7 −25 1 1 −10 −25 1 Example 9.2 Let A =  4 13 1, v = 0 and λ = 3. Then (A−3I) =  4 10 1  0 0 2 0 0 0 −1     −10 0 0 −36 and (A − 3I )v =  −4  6= 0R3 . Now, (A − 3I)2 = 0 0 13  and (A − 3I )2 v = 0R3 . Clearly 0 0 0 1 v is a generalized eigenvector of rank 2 (v = v2 ). Example 9.3 Find of rank 2 corresponding to the eigenvalues of λ = 4  a generalized eigenvector  4 0 0 0 1 5 1 0  for the matrix A =  −1 −1 3 0  . 0 0 0 3        x1 x1 0 0 0 0 0  x2   1  x1 + x2 + x3  1 1 0  4   x2     Let v =   x3 ∈ R . Then (A − 4I)v = −1 −1 −1 0   x3 =  −x1 − x2 − x3  and 0 0 0 −1 −x4 x4 x4      0 0 0 0 0 x1       0 0 0 0 x 2   2  0  (A − 4I)2 v =  0 0 0 0   x3 =  0  . Now (A − 4I) v = 0 and (A − 4I)v 6= 0. Thus x4 = 0 0 0 0 1 x4 x4   1 1  and x1 + x2 + x3 6= 0. We can choose x1 = x2 = x3 = 1. Then v2 =  1. 0 92

CHAPTER 9. GENERALIZED EIGENVECTORS

93

Definition 9.4 A chain generated by a generalized eigenvector vm of rank m associated with the eigenvector λ is a set of vectors {v1 , v2 , . . . , vm−1 , vm } defined recursively as vj = (A − λI)vj+1

j = m − 1, m − 2, . . . 1.

A canonical basis is a set of n linearly independent composed entirely of chains. The chains associated with an eigenvalues of multiplicity greater than one are determined as follows: Step 1 Denote the multiplicity of λ as m, and determine the smallest positive integer p for which the rank of (A − λI)P equals n − m, where n denotes the number of rows (or columns) of A. Step 2 For each integer k between 1 and p inclusive, compute the eigenvalue rank number Nk as Nk = rank (A − λI )k−1 − rank (A − λI )k . Each Nk is the number of generalized eigenvectors of rank k that will appear in the canonical basis. Step 3 Determine a generalized eigenvector of rank p, and construct the chain generated by this vector. Each of these vectors is part of the canonical basis. Step 4 Reduce each positive Nk (1 ≤ k ≤ p) by 1. If all the Nk are zero, stop the procedure is completed. If not, continue to step 5. Step 5 Find the highest value of k for which Nk is non zero and determine a generalized eigenvector of that rank which is linearly independent of all previously determined eigenvectors associated with λ. Form the chain generated by this vector and include it in the basis. Return to step 4.   7 1 2 Example 9.5 Find a canonical basis for A =  0 7 1. Clearly, the eigenvalue λ = 7 has 0 0 7   0 1 2 multiplicity 3. Thus n = 3, m = 3 and n − m = 0. Now, (A − 7I) = 0 0 1 , (A − 7I )2 = 0 0 0     0 0 0 0 0 1 0 0 0  and (A − 7I)3 =  0 0 0 has rank zero, so p = 3. Next, 0 0 0 0 0 0 N3 = rank (A − 7I)2 − rank (A − 7I)3 = 1 − 0 = 1. N2 = rank (A − 7I)1 − rank (A − 7I)2 = 2 − 1 = 1.

N1 = rank (A − 7I)0 − rank (A − 7I)1 = rank (I3 ) − rank (A − 7I)1 = 3 − 2 = 1. So, we need to find one generalized eigenvector of rank 1, we need to find one generalized eigenvector of rank 2 and we need to find one generalized eigenvector of rank 3. At this point, we will find a generalized eigenvector of rank 3 and construct the chain generated by this eigenvector. If v = v3 =

94

CHAPTER 9. GENERALIZED EIGENVECTORS

 x1  x2, then (A − 7I )3 v = 0, (A − 7I )2 v 6= 0 and (A − 7I)v 6= 0. Clearly x3 6= 0 and we can choose   x3 0 x1 = x2 = 0. Thus v3 =  0. Then 1

     0 1 2 0 2      0 = 1 v2 = (A − 7I)v3 = 0 0 1 0 0 0 1 0      0 1 2 2 1      v1 = (A − 7I)v2 = 0 0 1 1 = 0 . 0 0 0 0 0       2 1   0      0 , 1 , 0 . Thus a canonical basis for A is   1 0 0   4 0  00 0 0

Example 9.6 Determine a canonical basis for A =

2 4 0 0 0 0

1 −1 4 0 0 0

0 0 0 4 0 0

0 0 0 2 4 0

0 0 0 . 0 0 7

λ = 4 has multiplicity 5 and λ = 7 has multiplicity 1. Thus n = 6, m = 5 and n − m = 1. Now    0 0 −2 0 0 0  ! 0 2 1 0 0 0 0 0 −1 0 0 0 0 0 0 0 0 0 0

(A − 4I) =  0 0

0 0 0 0 0

0 0 2 0 0

0 0 , 0 0 3

0 0 0 0 0 0 0 0 0 0 0

2

(A − 4I) =  00 00

0 0 0 0 0

Clearly, (A − 4I )3 has rank 1, thus p = 3. Now

0 0 0 0 0

0 0 0 0 9

3

and (A − 4I ) =

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 27

.

N3 = rank (A − 4I)2 − rank (A − 4I)3 = 2 − 1 = 1. N2 = rank (A − 4I)1 − rank (A − 4I)2 = 4 − 2 = 2. N1 = rank (A − 4I)0 − rank (A − 4I)1 = rank (I6 ) − rank (A − 4I)1 = 6 − 4 = 2. A canonical basis for contains one generalized eigenvector of rank 3, two generalized eigenvectors of rank 2 and one generalized eigenvector of rank 1, all corresponding to λ = 4. Next, we find ! the generalized eigenvector of rank 3 and the chain generated by this eigenvector. Let v3 =

x1 x2 x3 x4 x5 x6

Let v3 =

, then (A − 4I )3 v3 = 0, (A − 4I )2 v3 6= 0 and (A − 4I)v3 6= 0. Clearly, x6 = 0 and x3 6= 0.

0! 0 1 , 0 0 0

then

v2 = (A −



0 0 4I)v3 =  00 0 0

2 0 0 0 0 0

1 −1 0 0 0 0

0 0 0 0 0 0

0 0 0 2 0 0

0 0 0 0 0 3

 

0! 0 1 0 0 0



=



1 −1 0  0 0 0

and

95

CHAPTER 9. GENERALIZED EIGENVECTORS 0 2

v1 = (A − 4I)v2 = 

0 0 0 0 0

0 0 0 0 0

1 −1 0 0 0 0

0 0 0 0 0 0

0 0 0 2 0 0



1 0 −1 0 0  0 0 0 0 0 3 0



=





−2 0  0 . 0 0 0

Next, we reduce each non-zero Nk by 1, obtaining N3 = 0, N2 = 1 and N1 = 1. Next, we will find a generalized eigenvector of rank 2 and the chain generated by this elements and ensure (associated ! with λ = 4) that these eigenvector are linearly independent to the three others. Let w2 = then (A − 4I)2 w2 = 0 and (A − 4I )w2 6= 0. Clearly, y6 = 0 and y3 = 0. Let w2 = 

w1 = (A − 4I)w2 = 

0 0 0 0 0 0

2 0 0 0 0 0

1 −1 0 0 0 0

0 0 0 0 0 0

0 0 0 2 0 0



0 0 0 0 0 3

0! 0 0 0 1 0

=

0! 0 0 , 0 1 0

y1 y2 y3 y4 y5 y6

,

then

0! 0 0 . 2 0 0

Reducing each non zero Nk by 1 again, N3 = N2 = N1 = 0. So, all the necessary basis vectors corresponding to λ = have been found. The one left  is the generalized eigenvector of rank 1  −3only 2 1 0 0 0 z1 !

corresponding to λ = 7. Now (A − 7I) =  We shall choose z1 =

0! 0 0 . 0 0 1

0 −3 −1 0 0 0 0 0 −3 0 0 0  0 0 0 −3 2 0 . 0 0 0 0 −3 0 0 0 0 0 0 0

z2 z3 z4 z5 z6

, then (A − 7I)v1 = 0.

A complete basis is {v1 , v2 , v3 , w1 , w2 , z1 }.

 3 0 Example 9.7 Find a canonical basis for A =  0 0

Clearly  0 2 0 0  0 0 0 0

Let z1 =

λ = 3has multiplicity 4. Thus n =4, 0 1 0   0 0  0 has rank 2, while (A − 3I)2 =  0 0 −1  0 0 0

2 3 0 0 m 0 0 0 0

 0 1 0 0 . 3 −1 0 3 = 0 0 0 0

and  n − m = 0. Hence (A − 3I) = 0 0  has rank 0. Thus p = 2. Then, 0 0

N2 = rank (A − 3I)1 − rank (A − 3I)2 = 2 − 0 = 2. N1 = rank (A − 3I)0 − rank (A − 3I)1 = rank (I4 ) − rank (A − 4I)1 = 4 − 2 = 2. A canonical basis will contain two generalized eigenvectors of rank 2 and two of rank 1. First,  we  x1 x2   find a generalized eigenvector of rank 2 and the chain generated by this eigenvector. Let v2 =  x3 , x4

CHAPTER 9. GENERALIZED EIGENVECTORS

96

 0 0   , then 2 then (A − 3I ) v2 = 0 and (A − 3I)v2 = 6 0. We can choose v2 = 0 1  0 0 v1 = (A − 3I)v2 =  0 0

    0 1 0 1     0 0  0  0  . = 0 −1 0  −1 0 0 1 0

2 0 0 0

Next, we reduce N1 and N2 by 1, obtaining N1 = N2 = 1. Another   generalized eigenvector of rank 0  1  2 for λ = 3 which is linearly independent of v1 and v2 is w2 =   0 . Now 0  0 0 w1 = (A − 3I)w2 =  0 0

A canonical basis for A is {v1 , v2 , w1 , w2 }.

2 0 0 0

    2 0 0 1     0 0   1  0 . = 0 −1   0  0 0 0 0 0

Lemma 9.8 If vm is a generalized eigenvector of rank m for a matrix A and eigenvalues λ, then vj = (A − λI)vj+1 for j = m − 1, m − 2, . . . , 1 is a generalized eigenvector of rank j corresponding to the same matrix and eigenvalue. Proof. Let vm be a generalized eigenvector of rank m for a matrix A for an eigenvalue λ. Clearly (A − λI)m vm = 0 and (A − λI )i vm 6= 0 for 1 ≤ i ≤ m − 1. Now vj = (A − λI )vj+1 = (A − λI )m−j vm . We want to show that vj has rank j , i.e. we need to show that (A − λI)j vj = 0 and (A − λI)l vj 6= 0 for 1 ≤ l ≤ j − 1. Now (A − λI)j vj = (A − λI )j (A − λI )m−j vm = (A − λI )m vm = 0 and (A − λI )j−1 vj = (A − λI)j−1 (A − λI)m−j vm = (A − λI)m−1 vm = 6 0. 

Theorem 9.9 A chain is a linearly independent set of vectors. Proof. Consider a chain of k-generalized eigenvectors {vk , vk−1 , . . . , v1 }. Clearly (A − λI)j vj = 0 for all 1 ≤ j ≤ k (by the previous result). Now, consider the equation ck vk + ck−1 vk−1 + · · · + c1 v1 = 0.

CHAPTER 9. GENERALIZED EIGENVECTORS

97

If we multiply across by (A − λI)k−1 , we obtain ck (A − λI)k−1 vk + ck−1 (A − λI)k−1 vk−1 + · · · + c1 (A − λI )k−1 v1 = 0. Note, that for each cj (A − λI)k−1 vj where 1 ≤ j ≤ k − 1: cj (A − λI)k−1 vj = cj (A − λI)k−j−1 (A − λI)j vj = cj (A − λI)k−j−1 (0) = 0 since (A−λI)j vj = 0 for all 1 ≤ j ≤ k−1. Consequently ck (A−λI)k−1 vk = 0. Now (A−λI)k−1 vk 6= 0 since vk is a generalized eigenvector of rank k. Therefore, ck (A − λI)k−1 vk = 0 =⇒ ck = 0. The above equation reduces to ck−1 vk−1 + · · · + c1 v1 = 0. If we now multiply across by (A − λI)k−2 , we will obtain that ck−1 = 0. Repeating the same argument (i.e. multiplying across by (A − λI)k−3 , (A − λI)k−4 and so on), we can see that ck = ck−1 = · · · = c1 = 0. Therefore {vk , vk−1 , . . . , v1 } are linearly independent. ...