EIGENVALUES AND EIGENVECTORS - Number theory

1 Chapter 6 EIGENVALUES MotivationWe motivate the chapter on EIGENVALUES by discussing the equationax2+ 2hxy+by2=c,where not all ofa, h, bare zero. The expressionax2+ 2hxy+by2is calledaquadratic forminxandyand we have the identityax2+ 2hxy+by2= x y a hh b xy =XtAX,whereX= xy andA= a hh b .Ais called the matrix of the now rotate thex, yaxes anticlockwise through radians to newx1, y1axes. The equations describing the rotation of axes are derived asfollows:LetPhave coordinates (x, y) relative to thex, yaxes and coordinates(x1, y1) relative to thex1, y1axes. Then referring to Figure :115116 CHAPTER 6. EIGENVALUES AND EIGENVECTORS - 6? @@@@@@@@I @@@@@@@@R @@@xyx1y1 PQRO Figure : Rotating the ( + )=OP(cos cos sin sin )= (OPcos ) cos (OPsin ) sin =ORcos PRsin =x1cos y1sin.

2 Similarlyy=x1sin +y1cos .We can combine these transformation equations into the single matrixequation: xy = cos sin sin cos x1y1 ,orX=P Y, whereX= xy , Y= x1y1 andP= cos sin sin cos .We note that the columns ofPgive the directions of the positivex1andy1axes. AlsoPis an orthogonal matrix we haveP Pt=I2and soP 1= matrixPhas the special property that detP= matrix of the typeP= cos sin sin cos is called shall show soon that any 2 2 real orthogonal matrix with MOTIVATION117equal to 1 is a rotation can also solve for the new coordinates in terms of the old ones: x1y1 =Y=PtX= cos sin sin cos xy ,sox1=xcos +ysin andy1= xsin +ycos . ThenXtAX= (P Y)tA(P Y) =Yt(PtAP) suppose, as we later show, that it is possible to choose anangle sothatPtAPis a diagonal matrix, say diag( 1, 2).

3 ThenXtAX= x1y1 100 2 x1y1 = 1x21+ 2y21( )and relative to the new axes, the equationax2+ 2hxy+by2=cbecomes 1x21+ 2y21=c, which is quite easy to sketch. This curve is symmetricalabout thex1andy1axes, withP1andP2, the respective columns ofP,giving the directions of the axes of it can be verified thatP1andP2satisfy the equationsAP1= 1P1andAP2= equations force a restriction on 1and 2. For ifP1= u1v1 , thefirst equation becomes a hh b u1v1 = 1 u1v1 or a 1hhb 1 u1v1 = 00 .Hence we are dealing with a homogeneous system of two linear equations intwo unknowns, having a non trivial solution (u1, v1). Hence a 1hhb 1 = , 2satisfies the same equation. In expanded form, 1and 2satisfy 2 (a+b) +ab h2= equation has real roots =a+b p(a+b)2 4(ab h2)2=a+b p(a b)2+ 4h22( )(The roots are distinct ifa6=borh6= 0.)

4 The casea=bandh= 0 needsno investigation, as it gives an equation of a circle.)The equation 2 (a+b) +ab h2= 0 is called theeigenvalue equationof the 6. EIGENVALUES AND Definitions and examplesDEFINITION ( eigenvalue , eigenvector)LetAbe a complexsquare matrix. Then if is a complex Number andXanon zerocom-plex column vector satisfyingAX= X, we callXaneigenvectorofA,while is called aneigenvalueofA. We also say thatXis an eigenvectorcorresponding to the eigenvalue .So in the above exampleP1andP2are EIGENVECTORS corresponding to 1and 2, respectively. We shall give an algorithm which starts from theeigenvalues ofA= a hh b and constructs a rotation matrixPsuch thatPtAPis noted above, if is an eigenvalue of ann nmatrixA, withcorresponding eigenvectorX, then (A In)X= 0, withX6= 0, sodet (A In) = 0 and there are at mostndistinct EIGENVALUES if det (A In) = 0, then (A In)X= 0 has a non trivialsolutionXand so is an eigenvalue ofAwithXa corresponding (Characteristic polynomial, equation)The polynomial det (A In) is called thecharacteristic polynomialofAand is often denoted by chA( ).

5 The equation det (A In) = 0 is calledthecharacteristic equationofA. Hence the EIGENVALUES ofAare the rootsof the characteristic polynomial a 2 2 matrixA= a bc d , it is easily verified that the character-istic polynomial is 2 (traceA) + detA, where traceA=a+dis the sumof the diagonal elements the EIGENVALUES ofA= 2 11 2 and find all The characteristic equation ofAis 2 4 + 3 = 0, or( 1)( 3) = = 1 or 3. The eigenvector equation (A In)X= 0 reduces to 2 11 2 xy = 00 , DEFINITIONS AND EXAMPLES119or(2 )x+y= 0x+ (2 )y= = 1 givesx+y= 0x+y= 0,which has solutionx= y, yarbitrary. Consequently the eigenvectorscorresponding to = 1 are the vectors yy , withy6= = 3 gives x+y= 0x y= 0,which has solutionx=y, yarbitrary.

6 Consequently the EIGENVECTORS corre-sponding to = 3 are the vectors yy , withy6= next result has wide applicability:THEOREM a 2 2 matrix having distinct EIGENVALUES 1and 2and corresponding eigenvectorsX1andX2. LetPbe the matrixwhose columns areX1andX2, respectively. ThenPis non singular andP 1AP= 100 2 .Proof. SupposeAX1= 1X1andAX2= 2X2. We show that the systemof homogeneous equationsxX1+yX2= 0has only the trivial solution. Then by theorem the matrixP=[X1|X2] is non singular. So assumexX1+yX2= 0.( )ThenA(xX1+yX2) =A0 = 0, sox(AX1) +y(AX2) = 0. Hencex 1X1+y 2X2= 0.( )120 CHAPTER 6. EIGENVALUES AND EIGENVECTORSM ultiplying equation by 1and subtracting from equation gives( 2 1)yX2= 0, as ( 2 1)6= 0 andX26= 0. Then from equation ,xX1= 0and hencex= the equationsAX1= 1X1andAX2= 2X2giveAP=A[X1|X2] = [AX1|AX2] = [ 1X1| 2X2]= [X1|X2] 100 2 =P 100 2 ,soP 1AP= 100 2.

7 EXAMPLE 2 11 2 be the matrix of example ThenX1= 11 andX2= 11 are EIGENVECTORS corresponding to eigenvalues1 and 3, respectively. Hence ifP= 1 11 1 , we haveP 1AP= 1 00 3 .There are two immediate applications of theorem The first is to thecalculation ofAn: IfP 1AP= diag ( 1, 2), thenA=Pdiag ( 1, 2)P 1andAn= P 100 2 P 1 n=P 100 2 nP 1=P n100 n2 P second application is to solving a system of linear differential equationsdxdt=ax+bydydt=cx+dy,whereA= a bc d is a matrix of real or complex numbers andxandyare functions oft. The system can be written in matrix form as X=AX,whereX= xy and X= x y = dxdtdydt . DEFINITIONS AND EXAMPLES121We make the substitutionX=P Y, whereY= x1y1 . Thenx1andy1are also functions oftand X=P Y=AX=A(P Y),so Y= (P 1AP)Y= 100 2 x1= 1x1and y1= differential equations are well known to have the solutionsx1=x1(0)e 1tandy1=y1(0)e 2t, wherex1(0) is the value ofx1whent= 0.

8 [Ifdxdt=kx, wherekis a constant, thenddt e ktx = ke ktx+e ktdxdt= ke ktx+e ktkx= ktxis constant, soe ktx=e k0x(0) =x(0). Hencex=x(0)ekt.]However x1(0)y1(0) =P 1 x(0)y(0) , so this determinesx1(0) andy1(0) interms ofx(0) andy(0). Hence ultimatelyxandyare determined as explicitfunctions oft, using the equationX=P 2 34 5 . Use the eigenvalue method toderive an explicit formula forAnand also solve the system of differentialequationsdxdt= 2x 3ydydt= 4x 5y,givenx= 7 andy= 13 whent= The characteristic polynomial ofAis 2+3 +2 which has distinctroots 1= 1 and 2= 2. We find corresponding eigenvectorsX1= 11 andX2= 34 . Hence ifP= 1 31 4 , we haveP 1AP= diag ( 1, 2).HenceAn= Pdiag ( 1, 2)P 1 n=Pdiag (( 1)n,( 2)n)P 1= 1 31 4 ( 1)n00 ( 2)n 4 3 1 1 122 CHAPTER 6.

9 EIGENVALUES AND EIGENVECTORS = ( 1)n 1 31 4 1 00 2n 4 3 1 1 = ( 1)n 1 3 2n1 4 2n 4 3 1 1 = ( 1)n 4 3 2n 3 + 3 2n4 4 2n 3 + 4 2n .To solve the differential equation system, make the substitutionX=P Y. Thenx=x1+ 3y1, y=x1+ 4y1. The system then becomes x1= x1 y1= 2y1,sox1=x1(0)e t, y1=y1(0)e 2t. Now x1(0)y1(0) =P 1 x(0)y(0) = 4 3 1 1 713 = 116 ,sox1= 11e tandy1= 6e 2t. Hencex= 11e t+ 3(6e 2t) = 11e t+18e 2t, y= 11e t+ 4(6e 2t) = 11e t+ 24e a more complicated example we solve a system ofinhomogeneousrecurrence the system of recurrence relationsxn+1= 2xn yn 1yn+1= xn+ 2yn+ 2,given thatx0= 0 andy0= The system can be written in matrix form asXn+1=AXn+B,whereA= 2 1 1 2 andB= 12 .It is then an easy induction to prove thatXn=AnX0+ (An 1+ +A+I2)B.

10 ( ) DEFINITIONS AND EXAMPLES123 Also it is easy to verify by the eigenvalue method thatAn=12 1 + 3n1 3n1 3n1 + 3n =12U+3n2V,whereU= 1 11 1 andV= 1 1 1 1 . HenceAn 1+ +A+I2=n2U+(3n 1+ + 3 + 1)2V=n2U+(3n 1) equation givesXn= 12U+3n2V 0 1 + n2U+(3n 1)4V 12 ,which simplifies to xnyn = (2n+ 1 3n)/4(2n 5 + 3n)/4 .Hencexn= (2n+ 1 3n)/4 andyn= (2n 5 + 3n) (A I2) 1existed (that is, if det (A I2)6= 0, orequivalently, if 1 is not an eigenvalue ofA), then we could have used theformulaAn 1+ +A+I2= (An I2)(A I2) 1.( )However the EIGENVALUES ofAare 1 and 3 in the above problem, so formula be used discussion of EIGENVALUES and EIGENVECTORS has been limited to 2 2matrices. The discussion is more complicated for matrices of size greaterthan two and is best left to a second course in linear following result is a useful generalization of theorem The readeris referred to [28, page 350] for a ann nmatrix having distinct EIGENVALUES 1.