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 .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.

2 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). 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.

3 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. 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.

4 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( ). 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.

5 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. 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.

6 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 .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.

7 [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. 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.

8 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.( ) 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.

9 ( )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, .. , nand corresponding eigenvectorsX1, .. , Xn. LetPbe the matrixwhose columns are respectivelyX1, .. , Xn. ThenPis non singular andP 1AP= 10 00 2 0 n .124 CHAPTER 6. EIGENVALUES AND EIGENVECTORSA nother useful result which covers the case where there are multiple eigen-values is the following (The reader is referred to [28, pages351 352] for aproof):THEOREM the characteristic polynomial ofAhas the fac-torizationdet ( In A) = ( c1)n1 ( ct)nt,wherec1, .. , ctare the distinct EIGENVALUES ofA. Suppose that fori=1.

10 , t, we have nullity (ciIn A) =ni. For each suchi, choose a basisXi1, .. , Xinifor theeigenspaceN(ciIn A). Then the matrixP= [X11| |X1n1| |Xt1| |Xtnt]is non singular andP 1 APis the following diagonal matrixP 1AP= c1In10 00c2In2 ctInt .(The notation means that on the diagonal there aren1elementsc1, followedbyn2elementsc2,.. ,ntelementsct.) PROBLEMS1. LetA= 4 31 0 . Find an invertible matrixPsuch thatP 1AP=diag (1,3) and hence prove thatAn=3n 12A+3 IfA= , prove thatAntends to a limiting matrix 2/3 2/31/3 1/3 asn . PROBLEMS1253. Solve the system of differential equationsdxdt= 3x 2ydydt= 5x 4y,givenx= 13 andy= 22 whent= 0.[Answer:x= 7et+ 6e 2t, y= 7et+ 15e 2t.]4. Solve the system of recurrence relationsxn+1= 3xn ynyn+1= xn+ 3yn,given thatx0= 1 andy0= 2.[Answer:xn= 2n 1(3 2n), yn= 2n 1(3 + 2n).]5. LetA= a bc d be a real or complex matrix with distinct EIGENVALUES 1, 2and corresponding eigenvectorsX1, X2. Also letP= [X1|X2].