Chapter 6 Eigenvalues And Eigenvectors - MIT Mathematics
Chapter 6Eigenvalues and Eigenvectors6.1 Introduction to Eigenvalues'1 An eigenvector x lies along the same line as Ax : Ax λx. The eigenvalue is λ.2 If Ax λx then A2 x λ2 x and A 1 x λ 1 x and (A cI)x (λ c)x: the same x.3 If Ax λx then (A λI)x 0 and A λI is singular and det(A λI) 0.n eigenvalues.4 Check λ’s by det A (λ1 )(λ2 ) · · · (λn ) and diagonal sum a11 a22 · · · ann sum of λ’s.5 Projections have λ 1 and 0. Reflections have 1 and 1. Rotations have eiθ and e iθ : complex!&%This chapter enters a new part of linear algebra. The first part was about Ax b:balance and equilibrium and steady state. Now the second part is about change. Timeenters the picture—continuous time in a differential equation du/dt Au or time stepsin a difference equation uk 1 Auk . Those equations are NOT solved by elimination.The key idea is to avoid all the complications presented by the matrix A. Supposethe solution vector u(t) stays in the direction of a fixed vector x. Then we only need tofind the number (changing with time) that multiplies x. A number is easier than a vector.We want “eigenvectors” x that don’t change direction when you multiply by A.A good model comes from the powers A, A2 , A3 , . . . of a matrix. Suppose you needthe hundredth power A100 . Its columns are very close to the eigenvector (.6, .4) : .8 .3A, A , A .2 .723 .70.30.45.55 .650 .525.350 .475 100A .6000 .6000 .4000 .4000 A100 was found by using the eigenvalues of A, not by multiplying 100 matrices. Thoseeigenvalues (here they are λ 1 and 1/2) are a new way to see into the heart of a matrix.288
6.1. Introduction to Eigenvalues289To explain eigenvalues, we first explain eigenvectors. Almost all vectors change direction, when they are multiplied by A. Certain exceptional vectors x are in the samedirection as Ax. Those are the “eigenvectors”. Multiply an eigenvector by A, and thevector Ax is a number λ times the original x.The basic equation is Ax λx. The number λ is an eigenvalue of A.The eigenvalue λ tells whether the special vector x is stretched or shrunk or reversed or leftunchanged—when it is multiplied by A. We may find λ 2 or 12 or 1 or 1. The eigenvalue λ could be zero! Then Ax 0x means that this eigenvector x is in the nullspace.If A is the identity matrix, every vector has Ax x. All vectors are eigenvectors of I.All eigenvalues “lambda” are λ 1. This is unusual to say the least. Most 2 by 2 matriceshave two eigenvector directions and two eigenvalues. We will show that det(A λI) 0.This section will explain how to compute the x’s and λ’s. It can come early in the coursebecause we only need the determinant of a 2 by 2 matrix. Let me use det(A λI) 0 tofind the eigenvalues for this first example, and then derive it properly in equation (3).The matrix A has two eigenvalues λ 1 and λ 1/2. Look at det(A λI): 311.8 .3.8 λ .32A det λ λ (λ 1) λ .2 .7.2.7 λ222Example 1 I factored the quadratic into λ 1 times λ 12 , to see the two eigenvalues λ 1 andλ 12 . For those numbers, the matrix A λI becomes singular (zero determinant). Theeigenvectors x1 and x2 are in the nullspaces of A I and A 12 I.(A I)x1 0 is Ax1 x1 and the first eigenvector is (.6, .4).(A 12 I)x2 0 is Ax2 12 x2 and the second eigenvector is (1, 1): .6.8 .3 .6x1 and Ax1 x1 (Ax x means that λ1 1).4.2 .7 .4 1.8 .31.5x2 and Ax2 (this is 12 x2 so λ2 12 ). 1.2 .7 1 .5If x1 is multiplied again by A, we still get x1 . Every power of A will give An x1 x1 .Multiplying x2 by A gave 12 x2 , and if we multiply again we get ( 12 )2 times x2 .When A is squared, the eigenvectors stay the same. The eigenvalues are squared.This pattern keeps going, because the eigenvectors stay in their own directions (Figure 6.1)and never get mixed. The eigenvectors of A100 are the same x1 and x2 . The eigenvaluesof A100 are 1100 1 and ( 12 )100 very small number.Other vectors do change direction. But all other vectors are combinations of the twoeigenvectors. The first column of A is the combination x1 (.2)x2 : Separate into eigenvectors.8.6.2 x1 (.2)x2 .(1)Then multiply by A.2.4 .2
290Chapter 6. Eigenvalues and EigenvectorsFigure 6.1: The eigenvectors keep their directions. A2 x λ2 x with λ2 12 and (.5)2 .When we multiply separately for x1 and (.2)x2 , A multiplies x2 by its eigenvalue 12 :Multiply each xi by λiA .8.2is 1.6.1.7x1 (.2)x2 .4 .1.32Each eigenvector is multiplied by its eigenvalue, when we multiply by A. At every step 99x1 is unchanged and x2 is multiplied by 12 , so 99 steps give the small number 12 : .8A99.2is really x1 (.2) 1 992 very.6x2 small .4vectorThis is the first column of A100 . The number we originally wrote as .6000 was not exact.We left out (.2)( 12 )99 which wouldn’t show up for 30 decimal places.The eigenvector x1 is a “steady state” that doesn’t change (because λ1 1). Theeigenvector x2 is a “decaying mode” that virtually disappears (because λ2 .5). Thehigher the power of A, the more closely its columns approach the steady state.This particular A is a Markov matrix. Its largest eigenvalue is λ 1. Its eigenvectorx1 (.6, .4) is the steady state—which all columns of Ak will approach. Section 10.3shows how Markov matrices appear when you search with Google.For projection matrices P , we can see when P x is parallel to x. The eigenvectorsfor λ 1 and λ 0 fill the column space and nullspace. The column space doesn’t move(P x x). The nullspace goes to zero (P x 0 x).
2916.1. Introduction to EigenvaluesExample 2The projection matrix P .5.5.5.5 has eigenvalues λ 1 and λ 0.Its eigenvectors are x1 (1, 1) and x2 (1, 1). For those vectors, P x1 x1 (steadystate) and P x2 0 (nullspace). This example illustrates Markov matrices and singularmatrices and (most important) symmetric matrices. All have special λ’s and x’s:1. Markov matrix : Each column of P adds to 1, so λ 1 is an eigenvalue.2. P is singular, so λ 0 is an eigenvalue.3. P is symmetric, so its eigenvectors (1, 1) and (1, 1) are perpendicular.The only eigenvalues of a projection matrix are 0 and 1. The eigenvectors for λ 0 (whichmeans P x 0x) fill up the nullspace. The eigenvectors for λ 1 (which means P x x)fill up the column space. The nullspace is projected to zero. The column space projectsonto itself. The projection keeps the column space and destroys the nullspace: 1202Project each part v projects onto P v . 1202Projections have λ 0 and 1. Permutations have all λ 1. The next matrix R is areflection and at the same time a permutation. R also has special eigenvalues. Example 3The reflection matrix R 01 10 has eigenvalues 1 and 1.The eigenvector (1, 1) is unchanged by R. The second eigenvector is (1, 1)—its signsare reversed by R. A matrix with no negative entries can still have a negative eigenvalue!The eigenvectors for R are the same as for P , because reflection 2(projection) I: 0 1.5 .51 0R 2P I 2 .(2)1 0.5 .50 1When a matrix is shifted by I, each λ is shifted by 1. No change in eigenvectors.Figure 6.2: Projections P have eigenvalues 1 and 0. Reflections R have λ 1 and 1.A typical x changes direction, but an eigenvector stays along the same line.
292Chapter 6. Eigenvalues and EigenvectorsThe Equation for the EigenvaluesFor projection matrices we found λ’s and x’s by geometry: P x x and P x 0.For other matrices we use determinants and linear algebra. This is the key calculationin the chapter—almost every application starts by solving Ax λx.First move λx to the left side. Write the equation Ax λx as (A λI)x 0.The matrix A λI times the eigenvector x is the zero vector. The eigenvectors make upthe nullspace of A λI. When we know an eigenvalue λ, we find an eigenvector bysolving (A λI)x 0.Eigenvalues first. If (A λI)x 0 has a nonzero solution, A λI is not invertible.The determinant of A λI must be zero. This is how to recognize an eigenvalue λ:EigenvaluesThe number λ is an eigenvalue of A if and only if A λI is singular.Equation for the eigenvaluesdet(A λI) 0.(3)This “characteristic polynomial” det(A λI) involves only λ, not x. When A is n by n,equation (3) has degree n. Then A has n eigenvalues (repeats possible!) Each λ leads to x:For each eigenvalue λ solve (A λI)x 0 or Ax λx to find an eigenvector x.Example 4A 1 22 4 is already singular (zero determinant). Find its λ’s and x’s.When A is singular, λ 0 is one of the eigenvalues. The equation Ax 0x hassolutions. They are the eigenvectors for λ 0. But det(A λI) 0 is the way to find allλ’s and x’s. Always subtract λI from A: 1 λ2Subtract λ from the diagonal to find A λI .(4)24 λTake the determinant “ad bc” of this 2 by 2 matrix. From 1 λ times 4 λ,the “ad” part is λ2 5λ 4. The “bc” part, not containing λ, is 2 times 2. 1 λ2det (1 λ)(4 λ) (2)(2) λ2 5λ.(5)24 λSet this determinant λ2 5λ to zero. One solution is λ 0 (as expected, since A issingular). Factoring into λ times λ 5, the other root is λ 5:det(A λI) λ2 5λ 0yields the eigenvaluesλ1 0andλ2 5 .
2936.1. Introduction to EigenvaluesNow find the eigenvectors. Solve (A λI)x 0 separately for λ1 0 and λ2 5: y0y2 yields an eigenvector z0z 1 42 y0y1(A 5I)x yields an eigenvector 2 1 z0z2(A 0I)x 1224for λ1 0for λ2 5.The matrices A 0I and A 5I are singular (because 0 and 5 are eigenvalues). Theeigenvectors (2, 1) and (1, 2) are in the nullspaces: (A λI)x 0 is Ax λx.We need to emphasize: There is nothing exceptional about λ 0. Like every othernumber, zero might be an eigenvalue and it might not. If A is singular, the eigenvectorsfor λ 0 fill the nullspace: Ax 0x 0. If A is invertible, zero is not an eigenvalue.We shift A by a multiple of I to make it singular.In the example, the shifted matrix A 5I is singular and 5 is the other eigenvalue.Summary To solve the eigenvalue problem for an n by n matrix, follow these steps:1.Compute the determinant of A λI. With λ subtracted along the diagonal, thisdeterminant starts with λn or λn . It is a polynomial in λ of degree n.2.Find the roots of this polynomial, by solving det(A λI) 0. The n roots arethe n eigenvalues of A. They make A λI singular.3. For each eigenvalue λ, solve (A λI)x 0 to find an eigenvector x.A note on the eigenvectors of 2 by 2 matrices. When A λI is singular, both rows aremultiples of a vector (a, b). The eigenvector is any multiple of (b, a). The example hadλ 0 : rows of A 0I in the direction (1, 2); eigenvector in the direction (2, 1)λ 5 : rows of A 5I in the direction ( 4, 2); eigenvector in the direction (2, 4).Previously we wrote that last eigenvector as (1, 2). Both (1, 2) and (2, 4) are correct.There is a whole line of eigenvectors—any nonzero multiple of x is as good as x.MATLAB’s eig(A) divides by the length, to make the eigenvector into a unit vector.We must add a warning. Some 2 by 2 matrices have only one line of eigenvectors.This can only happen when two eigenvalues are equal. (On the other hand A I has equaleigenvalues and plenty of eigenvectors.) Without a full set of eigenvectors, we don’t have abasis. We can’t write every v as a combination of eigenvectors. In the language of the nextsection, we can’t diagonalize a matrix without n independent eigenvectors.
294Chapter 6. Eigenvalues and EigenvectorsDeterminant and TraceBad news first: If you add a row of A to another row, or exchange rows, the eigenvaluesusually change. Elimination does not preserve the λ’s. The triangular U has its eigenvaluessitting along the diagonal—they are the pivots. But they are not the eigenvalues of A!Eigenvalues are changed when row 1 is added to row 2: 1 31 3U has λ 0 and λ 1; A has λ 0 and λ 7.0 02 6Good news second: The product λ1 times λ2 and the sum λ1 λ2 can be found quicklyfrom the matrix. For this A, the product is 0 times 7. That agrees with the determinant(which is 0). The sum of eigenvalues is 0 7. That agrees with the sum down the maindiagonal (the trace is 1 6). These quick checks always work:The product of the n eigenvalues equals the determinant.The sum of the n eigenvalues equals the sum of the n diagonal entries.The sum of the entries along the main diagonal is called the trace of A:λ1 λ2 · · · λn trace a11 a22 · · · ann .(6)Those checks are very useful. They are proved in Problems 16–17 and again in the nextsection. They don’t remove the pain of computing λ’s. But when the computation is wrong,they generally tell us so. To compute the correct λ’s, go back to det(A λI) 0.The trace and determinant do tell everything when the matrix is 2 by 2. We never wantto get those wrong! Here trace 3 and det 2, so the eigenvalues are λ 1 and 2 : 1 93 17 3A oror.(7)0 2 2 010 4And here is a question about the best matrices for finding eigenvalues : triangular.Why do the eigenvalues of a triangular matrix lie along its diagonal?Imaginary EigenvaluesOne more bit of news (not too terrible). The eigenvalues might not be real numbers.Example 5 The 90 rotationQ h0 11 0ihas no real eigenvectors. Its eigenvaluesare λ1 i and λ2 i. Then λ1 λ2 trace 0 and λ1 λ2 determinant 1.After a rotation, no real vector Qx stays in the same direction as x (x 0 is useless).There cannot be an eigenvector, unless we go to imaginary numbers. Which we do.
2956.1. Introduction to Eigenvalues To see how i 1 can help, look at Q2 which is I. If Q is rotation through 90 ,then Q2 is rotation through 180 . Its eigenvalues are 1 and 1. (Certainly Ix 1x.)Squaring Q will square each λ, so we must have λ2 1. The eigenvalues of the 90 rotation matrix Q are i and i, because i2 1.Those λ’s come as usual from det(Q λI) 0. This equation gives λ2 1 0.Its roots are i and i. We meet the imaginary number i also in the eigenvectors:Complexeigenvectors 0 110 11 iii and0 110 ii i.11Somehow these complex vectors x1 (1, i) and x2 (i, 1) keep their direction as they arerotated. Don’t ask me how. This example makes the all-important point that real matricescan easily have complex eigenvalues and eigenvectors. The particular eigenvalues i and ialso illustrate two special properties of Q:1. Q is an orthogonal matrix so the absolute value of each λ is λ 1.2. Q is a skew-symmetric matrix so each λ is pure imaginary.A symmetric matrix (S T S) can be compared to a real number. A skew-symmetricmatrix (AT A) can be compared to an imaginary number. An orthogonal matrix(QT Q I) corresponds to a complex number with λ 1. For the eigenvalues of Sand A and Q, those are more than analogies—they are facts to be proved in Section 6.4.The eigenvectors for all these special matrices are perpendicular. Somehow (i, 1) and(1, i) are perpendicular (Chapter 9 explains the dot product of complex vectors).Eigenvalues of AB and A BThe first guess about the eigenvalues of AB is not true. An eigenvalue λ of A times aneigenvalue β of B usually does not give an eigenvalue of AB:ABx Aβx βAx βλx.False proof(8)It seems that β times λ is an eigenvalue. When x is an eigenvector for A and B, thisproof is correct. The mistake is to expect that A and B automatically share the sameeigenvector x. Usually they don’t. Eigenvectors of A are not generally eigenvectors of B.A and B could have all zero eigenvalues while 1 is an eigenvalue of AB:A 0010 and B 0 0;1 0then AB 1000 and A B 0 1.1 0For the same reason, the eigenvalues of A B are generally not λ β. Here λ β 0while A B has eigenvalues 1 and 1. (At least they add to zero.)
296Chapter 6. Eigenvalues and EigenvectorsThe false proof suggests what is true. Suppose x really is an eigenvector for both A andB. Then we do have ABx λβx and BAx λβx. When all n eigenvectors are shared,we can multiply eigenvalues. The test AB BA for shared eigenvectors is important inquantum mechanics—time out to mention this application of linear algebra:A and B share the same n independent eigenvectors if and only if AB BA.Heisenberg’s uncertainty principle In quantum mechanics, the position matrix P andthe momentum matrix Q do not commute. In fact QP P Q I (these are infinitematrices). To have P x 0 at the same time as Qx 0 would require x Ix 0.If we knew the position exactly, we could not also know the momentum exactly.Problem 36 derives Heisenberg’s uncertainty principle kP xk kQxk 12 kxk2 .REVIEW OF THE KEY IDEAS1. Ax λx says that eigenvectors x keep the same direction when multiplied by A.2. Ax λx also says that det(A λI) 0. This determines n eigenvalues.3. The eigenvalues of A2 and A 1 are λ2 and λ 1 , with the same eigenvectors.4. The sum of the λ’s equals the sum down the main diagonal of A (the trace).The product of the λ’s equals the determinant of A.5. Projections P , reflections R, 90 rotations Q have special eigenvalues 1, 0, 1, i, i.Singular matrices have λ 0. Triangular matrices have λ’s on their diagonal.6. Special properties of a matrix lead to special eigenvalues and eigenvectors.That is a major theme of this chapter (it is captured in a table at the very end).WORKED EXAMPLES6.1 AFind the eigenvalues and eigenvectors of A and A2 and A 1 and A 4I: 2 15 4A and A2 . 12 45Check the trace λ1 λ2 4 and the determinant λ1 λ2 3.SolutionA The eigenvalues of A come from det(A λI) 0: 2 12 λ 1det(A λI) λ2 4λ 3 0. 12 12 λThis factors into (λ 1)(λ 3) 0 so the eigenvalues of A are λ1 1 and λ2 3. Forthe trace, the sum 2 2 agrees with 1 3. The determinant 3 agrees with the product λ1 λ2 .
2976.1. Introduction to EigenvaluesThe eigenvectors come separately by solving (A λI)x 0 which is Ax λx: 1 1 x01λ 1: (A I)x gives the eigenvector x1 11 y01λ 3: 1 1 x01(A 3I)x gives the eigenvector x2 1 1 y0 1A2 and A 1 and A 4I keep the same eigenvectors as A. Their eigenvalues are λ2 andλ 1 and λ 4:A2 has eigenvalues 12 1 and 32 9A 1 has11and13A 4I has1 4 53 4 7Notes for later sections: A has orthogonal eigenvectors (Section 6.4 on symmetricmatrices). A can be diagonalized since λ1 6 λ2 (Section 6.2). A is similar to any 2 by 2matrix with eigenvalues 1 and 3 (Section 6.2). A is a positive definite matrix (Section 6.5)since A AT and the λ’s are positive.6.1 BHow can you estimate the eigenvalues of any A? Gershgorin gave this answer.Every eigenvalue of A must be “near” at least one of the entries aii on the main diagonal.For λ to be “near aii ” means that aii λ is no more than the sum Ri of all other aij in that row i of the matrix. Then Ri Σj6 i aij is the radius of a circle centered at aii .Every λ is in the circle around one or more diagonal entries aii : aii λ Ri .Here is the reasoning. If λ is an eigenvalue, then A λI is not invertible. Then A λIcannot be diagonally dominant (see Section 2.5). So at least one diagonal entry aii λis not larger than the sum Ri of all other entries aij (we take absolute values!) in row i.Example 1. Every eigenvalue λ of this A falls into one or both of the Gershgorin circles:The centers are a and d, the radii are R1 b and R2 c . a bFirst circle: λ a b A c dSecond circle: λ d c Those are circles in the complex plane, since λ could certainly be complex.Example 2. All eigenvalues of this A lie in a circle of radius R 3 around one or moreof the diagonal entries d1 , d2 , d3 : d1 1 2 λ d1 1 2 R1 λ d2 2 1 R2A 2 d2 1 1 2 d3 λ d3 1 2 R3You see that “near” means not more than 3 away from d1 or d2 or d3 , for this example.
298Chapter 6. Eigenvalues and EigenvectorsFind the eigenvalues and eigenvectors of this symmetric 3 by 3 matrix S: Symmetric matrix1 10Singular
6.1. Introduction to Eigenvalues 289 To explain eigenvalues, we first explain eigenvectors. Almo st all vectors change di-rection, when they are multiplied by A. Certain exceptional vectors x are in the same direction as Ax. Those are the “eigenvectors” . Multiply an eigenvector by
Part One: Heir of Ash Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 Chapter 24 Chapter 25 Chapter 26 Chapter 27 Chapter 28 Chapter 29 Chapter 30 .
Eigenvalues, Eigenvectors, and Diagonalization 428 12.2Getting Started 12.2.1The Algebraic Eigenvalue Problem * View at edX The algebraic eigenvalue problem is given by Ax lx: where A 2Rn n is a square matrix, l is a scalar, and x is a nonzero ve
Eigenvalues and Eigenvectors Applications Diagonalisation and iteration Radboud University Nijmegen Political swingers, part II So
TO KILL A MOCKINGBIRD. Contents Dedication Epigraph Part One Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Part Two Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18. Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 Chapter 24 Chapter 25 Chapter 26
DEDICATION PART ONE Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 PART TWO Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 .
network analysis and the topic models for text analysis, and our general theory can be . Bai and Silverstein(2006) for detailed book-length accounts of the topic of random matrices. There is a rich recent literature in mathematics on the asymptotic behaviors of eigenvalues and eigenvectors
Theorem 1 If A is symmetric, then any two eigenvectors from different eigenspaces are orthogonal. Proof Let v1 and v2 be eigenvectors corresponding to distinct eigenvalues 1 and 2.Observe that vT 2 Av1 v T 1 A Tv 2 v T 1 Av2 ) vT 2 ( 1v1) v T 1 ( 2v2) ) 1(v1 v2) 2(v1 v
Fedrico Chesani Introduction to Description Logic(s) Some considerations A Description Language DL Extending DL Description Logics Description Logics and SW A simple logic: DL Concept-forming operators Sentences Semantics Entailment Sentences d 1: d 2 Concept d 1 is equivalent to concept d 2, i.e. the individuals that satisfy d 1 are precisely those that satisfy d 2 Example: PhDStudent .
