Math 2331 - The Characteristic Equation

5.2 The Characteristic Equation Math 2331 – Linear Algebra 5.2 The Characteristic Equation Math 2331, Linear Algebra 1 / 12 5.2 The Characteristic Equation Definition IMT REF Similarity Application 5.2 The Characteristic Equation The Characteristic Equation: Definition and Examples The Invertible Matrix Theorem (continued) Row Reductions and Determinants Similarity Application to Markov Chains Math 2331, Linear Algebra 2 / 12 5.2 The Characteristic Equation Definition IMT REF Similarity Application The Characteristic Equation Ax = λx Find eigenvectors x by solving (A − λI ) x = 0. How Do We Find the Eigenvalues λ? x must be nonzero ⇓ (A − λI ) x = 0 must have nontrivial solutions ⇓ (A − λI ) is not invertible ⇓ det (A − λI ) = 0 (called the characteristic equation) Solve det (A − λI ) = 0 for λ to find the eigenvalues. Characteristic polynomial: det (A − λI ) Characteristic equation: det (A − λI ) = 0 Math 2331, Linear Algebra 3 / 12 5.2 The Characteristic Equation Definition IMT REF Similarity Application The Characteristic Equation: Example Example  Find the eigenvalues of A =  0 1 . −6 5 Solution: Since       0 1 λ 0 −λ 1 A−λI = − = , −6 5 0 λ −6 5 − λ the equation det (A−λI ) = 0 becomes −λ (5 − λ) + 6 = 0 =⇒ λ2 − 5λ + 6 = 0 Factor: (λ − 2) (λ − 3) = 0. So the eigenvalues are 2 and 3. Math 2331, Linear Algebra 4 / 12 5.2 The Characteristic Equation Definition IMT REF Similarity Application The Characteristic Equation: Example Example   1 2 1 Find the eigenvalues of A =  0 −5 0 . 1 8 1 Solution: For a 3 × 3 matrix or larger, recall that a determinant can be computed by cofactor expansion. det (A−λI ) = = (−5 − λ) 1−λ 2 1 0 −5 − λ 0 1 8 1−λ 1−λ 1 1 1−λ h i = (−5 − λ) (1 − λ)2 − 1   = (−5 − λ) 1 − 2λ + λ2 − 1 = − (5 + λ) λ [−2 + λ] = 0 ⇒ λ = −5, 0, 2 Math 2331, Linear Algebra 5 / 12 5.2 The Characteristic Equation Definition IMT REF Similarity Application The Invertible Matrix Theorem - continued Theorem (IMT (cont.)) Let A be an n × n matrix. Then A is invertible if and only if: s. The number 0 is not an eigenvalue of A. t. det A 6= 0 Algebraic Multiplicity The (algebraic) multiplicity of an eigenvalue is its multiplicity as a root of the characteristic equation. Math 2331, Linear Algebra 6 / 12 5.2 The Characteristic Equation Definition IMT REF Similarity Application Row Reductions and Determinants Recall that if B is obtained from A by a sequence of row replacements or interchanges, but without scaling, then det A = (−1)r det B, where r is the number of row interchanges. Suppose the echelon form U is obtained from A by a sequence of row replacements or r interchanges, but without scaling.   u11 u12 u13 · · · u1n  0 u22 u23 · · · u2n     0 u33 · · · u3n  A∼U= 0   .. .. .. ..  ..  . . . . .  0 0 0 0 unn The determinant of A, written det A, is defined as follows:    product of  (−1)r · , when A is invertible pivots in U det A =  0, when A is not invertible Math 2331, Linear Algebra 7 / 12 5.2 The Characteristic Equation Definition IMT REF Similarity Application Row Reductions and Determinants: Example Example   3 2 3 Find the eigenvalues of A =  0 6 10 . 0 0 2 Solution:   3−λ 2 3 0 6−λ 10  det (A − λI ) = det  0 0 2−λ Characteristic equation: ( )( )( eigenvalues: , ) = 0. , Math 2331, Linear Algebra 8 / 12 5.2 The Characteristic Equation Definition IMT REF Similarity Application Row Reductions and Determinants: Example Example Find the characteristic polynomial  2 0  5 3 A=  9 1 1 2 of  0 0 0 0   3 0  5 −1 and then find all the eigenvalues and their algebraic multiplicity. Solution: 2−λ 0 0 0 5 3−λ 0 0 det (A − λI ) = 9 1 3−λ 0 1 2 5 −1 − λ = (2 − λ) (3 − λ) (3 − λ) (−1 − λ) = 0 eigenvalues: , , Math 2331, Linear Algebra 9 / 12 5.2 The Characteristic Equation Definition IMT REF Similarity Application Similarity Numerical methods for finding approximating eigenvalues are based upon Theorem 4 to be described shortly. Similarity For n × n matrices A and B, we say the A is similar to B if there is an invertible matrix P such that P −1 AP = B or equivalently, A = PBP −1 . Theorem (4) If n × n matrices A and B are similar, then they have the same characteristic polynomial and hence the same eigenvalues. Proof: If B = P −1 AP, then     det (B − λI ) = det P −1 AP − P −1 λIP = det P −1 (A − λI ) P = det P −1 · det (A − λI ) · det P = det (A − λI ). Math 2331, Linear Algebra 10 / 12 5.2 The Characteristic Equation Definition IMT REF Similarity Application Application to Markov Chains: Example Example   .95 .90 Consider the migration matrix M = and define .05 .10 xk+1 = Mxk . It can beshown  that x0 , x1 , x2 , . . . converges to a steady state vector x = 1 2 1 2 . Why? The answer lies in examining the corresponding eigenvectors. First we find the eigenvalues:   .95 − λ .90 det (M − λI ) = det = λ2 − 1. 05λ + 0.05 .05 .10 − λ So solve λ2 − 1. 05λ + 0.05 = 0 By factoring λ = 0.05, λ = 1 Math 2331, Linear Algebra 11 / 12 5.2 The Characteristic Equation Definition IMT REF Similarity Application Application to Markov Chains: Example (cont.)   1 The eigenvector corresponding to λ = 1 is v1 = and the 1   −1 eigenvector corresponding to λ = 0.05 is v2 = . 1 Then for a given vector x0 , x0 = c1 v1 + c2 v2 x1 = Mx0 = M (c1 v1 + c2 v2 ) = c1 Mv1 + c2 Mv2 = c1 v1 + c2 (0.05) v2 x2 = Mx1 = M (c1 v1 + c2 (0.05) v2 ) = c1 Mv1 + c2 (0.05) Mv2 = c1 v1 + c2 (0.05)2 v2 xk = c1 v1 + c2 (0.05)k v2   and so lim xk = lim c1 v1 + c2 (0.05)k v2 = c1 v1 k→∞ k→∞  1  and this is the steady state vector 21 when c1 = 12 . and in general 2 Math 2331, Linear Algebra 12 / 12