Eigenvalues and Eigenvectors

1 Eigenvalues and EigenvectorsFew concepts to remember from linear algebraLet be an matrix and the linear transformation = Rank: maximum number of linearly independent columns or rows of Range = = } Null = = } eigenvalue problemLet be an matrix: is an eigenvectorof if there exists a scalar such that = where is called an is an eigenvector, then is also an eigenvector. Therefore, we will usually seek for normalized Eigenvectors , so that =1 Note: When using Python, normalize using p= do we find Eigenvalues ?Linear algebra approach: = = Therefore the matrix is singular =0 = is the characteristic polynomial of degree .In most cases, there is no analytical formula for the Eigenvalues of a matrix (Abel proved in 1824 that there can be no formula for the roots of a polynomial of degree 5 or higher) Approximate the Eigenvalues numerically!ExampleNotes:The matrix is singular (det(A)=0), and rank( )=1 The matrix has two distinct real eigenvaluesThe Eigenvectors are linearly independent =2142 2 142 =0 Solution of characteristic polynomial gives.

2 =4, /=0To g e t t h e e i g e n v e c t o r s , w e s o l v e : = 2 (4)142 (4) $ %=00 =122 (0)142 (0) $ %=00 = 12 Diagonalizable MatricesA matrix with linearly independent Eigenvectors is said to be diagonalizable. = . , = / ,.. = ; ,In matrix form: .. = # .. $ = .. #000 000 $This corresponds to a similarity transformation = = % Example =2142 2 142 =0 Solution of characteristic polynomial gives: .=4, /=0To g e t t h e e i g e n v e c t o r s , w e s o l v e : = 2 (4)142 (4) $ %=00 =122 (0)142 (0) $ %=00 = 12 = <. = normalized eigenvector ( =2norm) = = =4000 Notes:The matrix is singular (det(A)=0), and rank( )=1 Since has two linearly independent Eigenvectors , the matrix is full rank, and hence, the matrix is Eigenvalues of the matrix: =3 182 9are .= /= the incorrectstatement:A)Matrix is diagonalizableB)The matrix has only one eigenvalue with multiplicity 2C)Matrix has only one linearly independent eigenvectorD)Matrix is not singularLet s look back at )If a matrix has linearly independent Eigenvectors then is diagonalizable, , = < where the columns of are the linearly independent normalized Eigenvectors of (which guarantees that < exists) and is a diagonal matrix with the Eigenvalues of.

3 2)If a matrix has less then linearly independent Eigenvectors , the matrix is called defective (and therefore not diagonalizable).3)If a symmetricmatrix has distinct Eigenvalues then is symmetric matrix with distinct Eigenvalues is , and , areeigenpairs of = = = 1 = 1 1 = 1 = 1 = 1 1 =0If all Eigenvalues are distinct 0 Hence, 1 =0, , the Eigenvectors are or thogonal (linearly independent), and consequently the matrix is that a diagonalizable matrix does not guarantee distinct things to remember about Eigenvalues : Eigenvalues can have zero value Eigenvalues can be negative Eigenvalues can be real or complex numbers A real matrix can have complex Eigenvalues The Eigenvalues of a matrix are not necessarily unique. In fact, we can define the multiplicity of an eigenvalue . If a matrix has linearly independent Eigenvectors , then the matrix is diagonalizableHow can we get Eigenvalues numerically?Assume that is diagonalizable ( , it has linearly independent Eigenvectors ).

4 We can propose a vector which is a linear combination of these Eigenvectors : = # #+ ' '+ + $ $Then we evaluate : = # #+ ' '+ + $ $And since #= # #we can also write: = # # #+ ' ' '+ + $ $ $where (is the eigenvalue corresponding to eigenvector (and we assume | #|>| '| | )| | $|Power IterationOur goal is to find an eigenvector (of .We w i l l u s e a n i t e r a t i v e p r o c e s s , where we start with an initial vector, where here we assume that it can be written as a linear combination of the Eigenvectors of . *= # #+ ' '+ + $ $And multiply by to get: #= *= # # #+ ' ' '+ + $ $ $ '= #= # #' #+ ' '' '+ + $ $' $ += +%#= # #+ #+ ' '+ '+ + $ $+ $Or += #+ # #+ ' ' #+ '+ + $ $ #+ $Power Iteration B= .B ..+ / / .B /+ + ; ; .B ;Assume that . 0, the ter m ..dominates the others when is very | .>| /, we have C!C"B 1when is large Hence, as increases, Bconverges to a multiple of the first eigenvector ., , limB D #C"#= ..or B.))

5 B .How can we now get the Eigenvalues ?If is an eigenvector of such that = then how can we evaluate the corresponding eigenvalue ? = Rayleigh coefficientNormalized Power Iteration =arbitrarynonzerovector = for =1,2,.. B= B<. B= # # &= $& $ $+ % % $& %+ + ' ' $& 'Normalized Power IterationDemo Power Iteration B= .B ..+ / / .B /+ + ; ; .B ;What if the starting vector have no component in the dominant eigenvector $( $=0)? Normalized Power IterationDemo Power Iteration B= .B ..+ / / .B /+ + ; ; .B ;What if the first two largest Eigenvalues (in magnitude) are the same, | $=| %? B= .B ..+ .B / .B / /+ . + ; ; .B ;Potential vector may have no component in the dominant eigenvector "( "=0). This is usually unlikely to happen if is chosen randomly, and in practice not a problem because rounding will usually introduce such of eventual overflow (or underflow): in practice the approximated eigenvector is normalized at each iteration (Normalized Power Iteration) two largest Eigenvalues (in magnitude) may be the same: | "|=| #|.

6 In this case, power iteration will give a vector that is a linear combination of the corresponding Eigenvectors : If signs are the same, the method will converge to correct magnitude of the eigenvalue . If the signs are different, the method will not converge. This is a real problem that cannot be discounted in B= .B ..+ / / .B /+ + ; ; .B ; We c a n s e e f r o m t h e a b o v e t h a t t h e r a t e o f c o n v e r g e n c e d e p e n d s o n t h e ratio C!C", that is: .<B B ..= / .BConvergence and error B= .+ / . / .B /+ &Power method has linear convergence, which is quite slow. PQR P ?S?RA) ) ) ) we want to use the normalized power iteration, starting from T=( ,0). Select the correct statementA)Normalized power iteration will not convergeB)Normalized power iteration will converge to the eigenvector corresponding to the eigenvalue )Normalized power iteration will converge to the eigenvector corresponding to the eigenvalue 4.

7 $ %The matrix =3113has Eigenvalues (4,2) and corresponding Eigenvectors .=(1,1)and /=( 1,1). )IclickerquestionSuppose is an eigenvector of such that = What is an eigenvalue of <.?A) B) C)1/ D) .CE)Can t tell without knowing Inverse Power MethodPreviously we learned that we can use the Power Method to obtain the largest eigenvalue and corresponding eigenvector, by using the update BSuppose there is a single smallest eigenvalue of . With the previous ordering| .|>| /| | V| >| ;|the smallest eigenvalue is ;. When computing the Eigenvalues of the inverse matrix <.,we get the following ordering1 ;>1 ;<. 1 .And hence we can use the Power Method update on the matrix <.to compute the dominant eigenvalue .C$, , <. BIclickerquestionWhich code snippet is the best option to compute the smallest eigenvalue of the matrix ?A)B)D)E) I have no idea! C)Inverse Power MethodNote that the update <. Bcan be instead written as BWhere Bis know and we need to solve for BU.

8 (we are just solving a linear system of equations!). Since the matrix does not change from iteration to the next, we can factorize the matrix once and then perform a series of backward and forward = and = resulting in = Hence we can efficiently solve = B Cost of computing Eigenvalues using inverse power iterationIclickerquestionWhat is the approximated cost of computing the largest eigenvalue using Power Method? A) B) /+ C) /D) V+ /E) IclickerquestionSuppose is an eigenvector of such that = and also is an eigenvector of such that = . What is an eigenvalue of What is an eigenvalue of ( + )<.?A)C /C UC B)C /C UC C)//C UC D)C /C UC E)C /C UC IclickerquestionSuppose is an eigenvector of such that = , but is not the largest or smallest eigenvalue . We want to compute the eigenvalue that is close to a given number . Which of the following modified matrices will give such eigenvalue ?A)( )B)( )<.C)(1 ) D).W E)I still have no clue how to answer to these of a Shifted Inverse MatrixSuppose the eigenpairs , satisfy =.

9 We c a n d e s c r i b e t h e e i g e n v a l u e s f o r t h e s h i f t e d i n v e r s e m a t r i x a s( )<. = = =1 Hence the eigensystemproblem is( )<. =1 Eigenvalues of a Shifted Inverse MatrixWe u s e t h e u p d a t e BTo o b t a i n t h e eigenpair , that satisfy = such that is an eigenvalue close to the number We c a n f a c t o r i z e t h e m a t r i x = such that = and then efficiently solve = B Convergence summaryMethodCostConvergence + / Power Method +1= ' ' #Inverse Power Method +1= )+ ' $ $%#Shifted Inverse Power Method( ) +1= )+ ' / /' $: largest eigenvalue (in magnitude) %: second largest eigenvalue (in magnitude) ': smallest eigenvalue (in magnitude) '-$: second smallest eigenvalue (in magnitude) .: closest eigenvalue to .%: second closest eigenvalue to