Module

for

Eigenvalues and Eigenvectors

     

Background

    
We will now review some ideas from linear algebra. Proofs of the theorems are either left as exercises or can be found in any standard text on linear algebra.  We know how to solve n linear equations in n unknowns.  It was assumed that the determinant of the matrix was nonzero and hence that the solution was unique. In the case of a homogeneous system AX = 0, if  [Graphics:Images/EigenvaluesMod_gr_1.gif],  the unique solution is the trivial solution X = 0.  If  [Graphics:Images/EigenvaluesMod_gr_2.gif],  there exist nontrivial solutions to AX = 0. Suppose that  [Graphics:Images/EigenvaluesMod_gr_3.gif],  and consider solutions to the homogeneous linear
system

        [Graphics:Images/EigenvaluesMod_gr_4.gif]     

A homogeneous system of equations always has the trivial solution [Graphics:Images/EigenvaluesMod_gr_5.gif].  Gaussian elimination can be used to obtain the reduced row echelon form which will be used to form a set of relationships between the variables, and a non-trivial solution.  

 

Example 1.  Find the nontrivial solutions to the homogeneous system  
        [Graphics:Images/EigenvaluesMod_gr_6.gif]
Solution 1.

 

 

Background for Eigenvalues and Eigenvectors

Definition (Linearly Independent).  The vectors  [Graphics:Images/EigenvaluesMod_gr_37.gif]  are said to be linearly independent if the equation  

        
[Graphics:Images/EigenvaluesMod_gr_38.gif]

implies that
[Graphics:Images/EigenvaluesMod_gr_39.gif].   If the vectors are not linearly independent they are said to be linearly dependent.  

Two vectors in
[Graphics:Images/EigenvaluesMod_gr_40.gif] are linearly independent if and only if they are not parallel.  Three vectors in [Graphics:Images/EigenvaluesMod_gr_41.gif]  are linearly independent if and only if they do not lie in the same plane.

 

Definition (Linearly Dependent).  The vectors   [Graphics:Images/EigenvaluesMod_gr_42.gif]  are said to be linearly dependent if there exists a set of numbers [Graphics:Images/EigenvaluesMod_gr_43.gif] not all zero, such that

         
[Graphics:Images/EigenvaluesMod_gr_44.gif].

 

Theorem. The vectors  [Graphics:Images/EigenvaluesMod_gr_45.gif]  are linearly dependent if and only if at least one of them is a linear combination of the others.

    A desirable feature for a vector space is the ability to express each vector as s linear combination of vectors chosen from a small subset of vectors.  This motivates the next definition.

 

Definition (Basis).  Suppose that  [Graphics:Images/EigenvaluesMod_gr_46.gif] is a set of  m  vectors in [Graphics:Images/EigenvaluesMod_gr_47.gif].  The set  S i s called a basis for  [Graphics:Images/EigenvaluesMod_gr_48.gif]  if for every vector  [Graphics:Images/EigenvaluesMod_gr_49.gif]  there exists a unique set
of scalars
[Graphics:Images/EigenvaluesMod_gr_50.gif] so that  X  can be expressed as the linear combination  

        
[Graphics:Images/EigenvaluesMod_gr_51.gif]

 

Theorem.  In  [Graphics:Images/EigenvaluesMod_gr_52.gif],  any set of  n  linearly independent vectors forms a basis of  [Graphics:Images/EigenvaluesMod_gr_53.gif].  Each vector  [Graphics:Images/EigenvaluesMod_gr_54.gif]  is uniquely expressed as a linear combination of the basis vectors.

 

Theorem.  Let  [Graphics:Images/EigenvaluesMod_gr_55.gif]  be vectors in  [Graphics:Images/EigenvaluesMod_gr_56.gif].  

(i)    If  m>n,  then the vectors are linearly independent.  

(ii)    If  m=n,  then the vectors are linearly dependent if and only if   [Graphics:Images/EigenvaluesMod_gr_57.gif],  where  [Graphics:Images/EigenvaluesMod_gr_58.gif].  

Proof  Eigenvalues and Eigenvectors  Eigenvalues and Eigenvectors  

 

    Applications of mathematics sometimes encounter the following questions:  What are the singularities of  [Graphics:Images/EigenvaluesMod_gr_59.gif],  where  [Graphics:Images/EigenvaluesMod_gr_60.gif]  is a parameter?  What is the behavior of the sequence of vectors  [Graphics:Images/EigenvaluesMod_gr_61.gif]?  What are the geometric features of a linear transformation?  Solutions for problems in many different disciplines, such as economics, engineering, and physics, can involve ideas related to these equations. The theory of eigenvalues and eigenvectors is powerful enough to help solve these otherwise intractable problems.

    Let  A  be a square matrix of dimension  n × n  and let  X  be a vector of dimension  n.  The product  Y = AX  can be viewed as a linear transformation from  n-dimensional space into itself.  We want to find scalars  [Graphics:Images/EigenvaluesMod_gr_62.gif]  for which there exists a nonzero vector  X  such that

(1)          
[Graphics:Images/EigenvaluesMod_gr_63.gif];  

that is, the linear transformation  T(X) = AX  maps  X  onto the multiple  [Graphics:Images/EigenvaluesMod_gr_64.gif].  When this occurs, we call  X  an eigenvector that corresponds to the eigenvalue  [Graphics:Images/EigenvaluesMod_gr_65.gif], and together they form the eigenpair  [Graphics:Images/EigenvaluesMod_gr_66.gif] for  A.  In general, the scalar  [Graphics:Images/EigenvaluesMod_gr_67.gif]  and vector  X  can involve complex numbers.  For simplicity, most of our illustrations will involve real calculations.  However, the techniques are easily extended to the complex case.  The n × n identity matrix  I  can be used to write equation (1) in the form

(2)        
[Graphics:Images/EigenvaluesMod_gr_68.gif].  

The significance of equation (2) is that the product of the matrix  [Graphics:Images/EigenvaluesMod_gr_69.gif]  and the nonzero vector  X  is the zero vector!  The theorem of homogeneous linear system says that (2) has nontrivial solutions if and only if the matrix  [Graphics:Images/EigenvaluesMod_gr_70.gif]  is singular, that is,

(3)        
[Graphics:Images/EigenvaluesMod_gr_71.gif].  

This determinant can be written in the form  

(4)        
[Graphics:Images/EigenvaluesMod_gr_72.gif]

 

Definition (Characteristic Polynomial).  When the determinant in (4) is expanded, it becomes a polynomial of degree n, which is called the characteristic polynomial   

(5)        
[Graphics:Images/EigenvaluesMod_gr_73.gif]     

Exploration for p([Graphics:Images/EigenvaluesMod_gr_81.gif])

 

    There exist exactly n roots (not necessarily distinct) of a polynomial of degree n.  Each root  [Graphics:Images/EigenvaluesMod_gr_82.gif]  can be substituted into equation (3) to obtain an underdetermined system of equations that has a corresponding nontrivial solution vector X.  If   [Graphics:Images/EigenvaluesMod_gr_83.gif]  is real, a real eigenvector  X  can be constructed. For emphasis, we state the following definitions.

 

Definition (Eigenvalue).  If  A  is and  n × n  real matrix, then its  n  eigenvalues  [Graphics:Images/EigenvaluesMod_gr_84.gif]  are the real and complex roots of the characteristic polynomial  

        
[Graphics:Images/EigenvaluesMod_gr_85.gif].

 

Definition (Eigenvector).  If   [Graphics:Images/EigenvaluesMod_gr_86.gif]  is an eigenvalue of  A  and the nonzero vector  V  has the property that

          
[Graphics:Images/EigenvaluesMod_gr_87.gif]    

then  V  is called an eigenvector of  A  corresponding to the eigenvalue  [Graphics:Images/EigenvaluesMod_gr_88.gif].  Together, this eigenvalue [Graphics:Images/EigenvaluesMod_gr_89.gif] and eigenvector V is called an eigenpair  [Graphics:Images/EigenvaluesMod_gr_90.gif].

    The characteristic polynomial  [Graphics:Images/EigenvaluesMod_gr_91.gif] can be factored in the form

        
[Graphics:Images/EigenvaluesMod_gr_92.gif]  
        
where  [Graphics:Images/EigenvaluesMod_gr_93.gif]  is called the multiplicity of the eigenvalue [Graphics:Images/EigenvaluesMod_gr_94.gif]. The sum of the multiplicities of all eigenvalues is  n;  that is,

        
[Graphics:Images/EigenvaluesMod_gr_95.gif].  

 

The next three results concern the existence of eigenvectors.

 

Theorem (Corresponding Eigenvectors).  Suppose that  A  is and  n × n  square matrix.    
(a)     For each distinct eigenvalue  [Graphics:Images/EigenvaluesMod_gr_96.gif]  there exists at least one eigenvector  V  corresponding to  [Graphics:Images/EigenvaluesMod_gr_97.gif].
(b)     If  
[Graphics:Images/EigenvaluesMod_gr_98.gif]  has multiplicity  r,  then there exist at most  r  linearly independent eigenvectors  [Graphics:Images/EigenvaluesMod_gr_99.gif]  that correspond to  [Graphics:Images/EigenvaluesMod_gr_100.gif].

 

Theorem (Linearly Independent Eigenvectors).  Suppose that  A  is and  n × n  square matrix.  If the eigenvalues [Graphics:Images/EigenvaluesMod_gr_101.gif] are distinct and  [Graphics:Images/EigenvaluesMod_gr_102.gif]  are the k eigenpairs, then  [Graphics:Images/EigenvaluesMod_gr_103.gif] is a set of  k linearly independent vectors.

 

Theorem (Complete Set of Eigenvectors).  Suppose that  A  is and  n × n  square matrix.  If the eigenvalues of  A  are all distinct, then there exist  n  nearly independent eigenvectors  [Graphics:Images/EigenvaluesMod_gr_104.gif].  

Proof  Eigenvalues and Eigenvectors  Eigenvalues and Eigenvectors  

 

    Finding eigenpairs by hand computations is usually done in the following manner.  The eigenvalue  [Graphics:Images/EigenvaluesMod_gr_105.gif]  of multiplicity  r  is substituted into the equation

        [Graphics:Images/EigenvaluesMod_gr_106.gif].  

Then Gaussian elimination can be performed to obtain the row reduced echelon form, which will involve  
n-k  equations in  n  unknowns, where  [Graphics:Images/EigenvaluesMod_gr_107.gif].  Hence there are  k  free variables to choose. The free variables can be selected in a judicious manner to produce  k  linearly independent solution vectors [Graphics:Images/EigenvaluesMod_gr_108.gif] that correspond to  [Graphics:Images/EigenvaluesMod_gr_109.gif].

 

Computer Programs  Eigenvalues and Eigenvectors  Eigenvalues and Eigenvectors  

[Graphics:Images/EigenvaluesMod_gr_110.gif]

Example 2.  Find the eigenvalues and eigenvectors of the matrix  [Graphics:Images/EigenvaluesMod_gr_111.gif].
Solution 2.

 

 

Free Variables

    When the linear system is underdetermined, we needed to introduce free variables in the proper location. The following subroutine will rearrange the equations and introduce free variables in the location they are needed.  Then all that is needed to do is find the row reduced echelon form a second time.  This is done at the end of the next example.

[Graphics:Images/EigenvaluesMod_gr_138.gif]

Example 3.  Find the eigenvalues and eigenvectors of the matrix  [Graphics:Images/EigenvaluesMod_gr_139.gif].  
Solution 3.

 

Example 4.  Find the eigenvalues and eigenvectors of the matrix  [Graphics:Images/EigenvaluesMod_gr_180.gif].
Solution 4.

 

Example 5.  Find the eigenvalues and eigenvectors of the matrix  [Graphics:Images/EigenvaluesMod_gr_214.gif].
Solution 5.

 

Example 6.  Find the eigenvalues and eigenvectors of the matrix  [Graphics:Images/EigenvaluesMod_gr_246.gif].  
Solution 6.

 

Example 7.  Find the eigenvalues and eigenvectors of the matrix  [Graphics:Images/EigenvaluesMod_gr_289.gif].  
Solution 7.

 

Example 8.  Find the eigenvalues and eigenvectors of the matrix  [Graphics:Images/EigenvaluesMod_gr_331.gif].
Solution 8.

 

Example 9.   Find the eigenvalues and eigenvectors of the matrix  [Graphics:Images/EigenvaluesMod_gr_337.gif].
Solution 9.

 

Example 10. Find the eigenvalues of the matrix   [Graphics:Images/EigenvaluesMod_gr_348.gif].
Solution 10.

 

Example 11.  Find the eigenvalues of the following matrix  A.
Solution 11.

 

Research Experience for Undergraduates

Eigenvalues and Eigenvectors  Eigenvalues and Eigenvectors  Internet hyperlinks to web sites and a bibliography of articles.  

 

Download this Mathematica Notebook Eigenvalues and Eigenvectors

 

Return to Numerical Methods - Numerical Analysis

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(c) John H. Mathews 2004