chapter3

Chapter 3 Eigenvalues and Eigenvectors In this chapter we begin our study of the most important, and certainly the most dominant aspect, of matrix theory. Called spectral theory, it allows usto give fundamental structure theorems for matrices and to develop power tools for comparing and computing w i t hm a t r i c e s . W eb e g i nw i t has t u d y of norms on matrices. 3.1 Matrix Norms We know Mnis a vector space. It is most useful to apply a metric on this vector space. The reasons are manifold, ranging from general information ofa metrized system to perturbation theory where the “smallness” of a matrixmust be measured. For that reason we de fine metrics called matrix norms that are regular norms with one additional property pertaining to the matrix product. Definition 3.1.1. LetA∈M n.R e c a l l t h a t a norm ,,·,,o na n yv e c t o r space sati fies the properties: (i),A,≥0a n d |A,=0i fa n do n l yi f A=0 (ii),cA,=|c|,A,forc∈R (iii),A+B,≤, A,+,B,. There is a true vector product on Mndefined by matrix multiplication. In this connection we say that the norm is submultiplicative if (iv),AB,≤, A,,B, 95 96 CHAPTER 3. EIGENVALUES AND EIGENVECTORS In the case that the norm ,·,satifies all four properties (i) - (iv) we call it amatrix norm . Here are a few simple consequences for matrix norms. The proofs are straightforward. Proposition 3.1.1. Let,·,be a matrix norm on Mn, and suppose that A∈Mn.T h e n (a),A,2≤,A,2,,Ap,≤, A,p,p=2,3,. . . (b) If A2=Athen,A,≥1 (c) If Ais invertible, then ,A−1,≥,I, ,A, (d),I,≥1. Proof. The proof of (a) is a consequence of induction. Supposing that A2=A,we have by the submultiplicativity property that ,A,=EEA2EE≤ ,A,2. Hence ,A,≥ 1, and therefore (b) follows. If Ais invertible, we apply the submultiplicativity again to obtain ,I,=EEAA−1EE≤,A,EEA−1EE, whence (c) follows. Finally, (d) follows because I2=Iand (b) applies. Matrices for which A2=Aare called idempotent . Idempotent matrices turn up in most unlikely places and are useful for applications. Examples. We can easily apply standard vector space type norms, i.e. f1, f2,a n df∞to matrices. Indeed, an n×nmatrix can clearly be viewed as an element of Cn2w i t ht h ec o o r d i n a t es t a c k e di nr o w so f nnumbers each. The trick is usually to verify the submultiplicativity condition (iv).1.f 1.D efine ,A,1=3 i,j|aij| The usual norm conditions (i)—(iii) hold. To show submultiplicativity we write ,AB,1=3 ijeeeee3 kaikbkjeeeee ≤3 ij3 k|aik|bkj| ≤3 ijkm|aik||bmj|=3 i,k|aik|3 mj|bmj| =,A,1,B,1. 3.1. MATRIX NORMS 97 Thus,A,1is a matrix norm. 2.f2.D efine ,A,2= 3 i,ja2 ij 1/2 conditions (i)—(iii) clearly hold. ,A,2is also a matrix norm as we see by application of the Cauchy—Schwartz inequality. We have ,AB,2 2=3 ijX3 kaikbkj~2 ≤3 i,jX3 ka2 ik~X3 mb2 jm~ = 3 i,k|aik|2  3 j,m|bjm|2  =,A,2 2,B,2 2. This norm has three common names: The (a) Frobenius norm, (b) Schur norm, and (c) Hilbert—Schmidt norm. It has considerable importance inmatrix theory. 3.f ∞.D efine for A∈Mn(R) ,A,∞=s u p i,j|aij|=m a x i,j|aij|. Note that if J=[11 11],,J,∞=1 . A l s o J2=2J.T h u s,J2,=2,J,=1W≤ ,J,2.S o,A,∞is not a matrix norm, though it is a vector space norm. We can make it into a matrix norm by ,A,=n,A,∞. Note |||AB|||=nmax i,jeeeee3 kaikbkjeeeee ≤nmax ijnmax k|aik||bkj| ≤n2max i,k|aik|max k,j|bkj| =|||A||| ||| B|||. 98 CHAPTER 3. EIGENVALUES AND EIGENVECTORS In the inequalities above we use the fundamental inequality 3 k|ckdk|≤max k|dk|3 k|ck| (See Exercise 4.) While these norms have some use in general matrix theory, most of the widely applicable norms are those that are subordinate to vectornorms in the manner de fined below. Definition 3.1.2. Let,·,be a vector norm on R n(orCn). For A∈Mn(R) (orMn(C)) we de fine the norm ,A,onMnby ,A,=m a x ,x,=1,Ax,. (T) and call ,A,the norm subordinate to the vector norm. Note the use of the same notation for both the vector and subordinate norms. Theorem 3.1.1. The subordinate norm is a matrix norm and ,Ax,≤ ,A,,x,. Proof. We need to verify conditions (i)—(iv). Conditions (i) and (ii) are obvious and are left to the reader . To show (iii), we have ,A+B,=m a x ,x,=1,(A+B)x,≤max ,x,=1(,Ax,+,Bx,) ≤max ,x,=1,Ax,+m a x ,x,=1,Bx, =,A,+,B,. Note that ,Ax,=,x,Awx ,x,W ≤,A,,x, sinceEEEx ,x,EEE= 1. Finally, it follows that for any x∈R n ,ABx,≤, A,,Bx,≤, A,,B,,x, and therefore ,AB,≤, A,,B,. Corollary 3.1.1. (i),I,=1. 3.2. CONVERGENCE AND PERTURBATION THEORY 99 (ii) If Ais invertible, then ,A−1,≥(,A,)−1. Proof. For (i) we have ,I,=m a x ,x,=1,Ix,=m a x ,x,=1,x,=1. To prove (ii) begin with A−1A=I. Then by the submultiplicativity and (i) 1=,I,≤, A−1,,A, and so,A−1,≥1/,A,. There are many results connected with matrix norms and eigenvectors that we shall explore before long. The relation between the norm of the matrixand its inverse is important in computational linear algebra. The quantity ,A −1,,A,thecondition number of the matrix A. When it is very large, the solution of the linear system Ax=bby general methods such as Gaussian elimination may produce results with considerable error. The conditionn u m b e r ,t h e r e f o r e ,t i p so ffinvestigators to this possibility. Naturally enough t h ec o n d i t i o nn u m b e rm a yb ed i fficult to compute accurately in exactly these circumstances. Alternative and very approximate methods are often used as reliable substitutes for the condition number. A special type of matrix, one for which ,Ax,=,x,for every x∈C, is called an isometry . Such matrices which do not “stretch” any vectors have remarkable spectral properties and play an important roll in spectraltheory. 3.2 Convergence and perturbation theory It will often be necessary to compare o ne matrix with another matrix that isnearby in some sense. When a matrix norm at is hand it is possible to measure the proximity of two matrices by computing the norm of their difference. This is just as we do for numbers. We begin with this study by showing that if the norm of a matrix is less than one, then its di fference with the identity is invertible. Again, this is just as with numbers; that is,if|r|<1, 1 1−ris defined. Let us assume R∈Mnand,, is some norm on Mn. We want to show that if ,R,<1t h e n( I−R)−1exists. Toward this end we prove the following lemma. 100 CHAPTER 3. EIGENVALUES AND EIGENVECTORS Lemma 3.2.1. For every R∈Mn (I−R)(I+R+R2+···+Rn)=I−Rn+1. Proof. This result for matrices is the direct analog of the result for numbers (1−r)(1+r+r2+···+rn)=1−rn+1, also often written as 1+ r+r2+···+rn= 1−rn+1 1−r. We prove the result inductively. If n=1t h er e s u l tf o l l o w sf r o m direct computation, ( I−R)(I+R)=I−R2. Assume the result holds up ton−1. Then (I−R)(I+R+R2+···+Rn−1+Rn)=(I−R)(I+R+···+Rn−1) +(I−R)Rn =(I−Rn)+Rn−Rn+1=I−Rn+1 by our inductive hypothesis. This calculation completes the induction, and hence the proof. Remark 3.2.1. Sometimes the proof is presented in a “quasi-inductive” manner. That is, you will see (I−R)(I+R+R2+···+Rn)=(I+R+R2+···+Rn) −(R+R2+···+Rn+1)(∗) =I−Rn+1 This is usually considered acceptable b ecause the correct induction is trans- parent in the calculation. Below we will show that if ,R,=λ<1, then ( I+R+R2+···)= (I−R)−1.I t w o u l d b e incorrect to apply the obvious fact that ,Rn+1,< λn+1→∞ to draw the conclusion from the equality ( ∗)a b o v ew i t h o u t first establishing convergence of the series∞ 0Rk. A crucial step in showing that an in finite series is convergent is showing that its partial sums satisfy the Cauchy criterion:∞ k=1akconverges if and only if for each ε>0,there exists an integer Nsuch that if m, n > N, theneen k=m+1akee<ε.(See Appendix A.) There is just one more aspect of this problem. While it is easyto establishe the Cauchy criterion for our present situation, we still need toresolve the situation between norm convergence andpointwise convergence . We need to conclude that if ,R,<1t h e nl i m n→∞Rn=0,and by this expression we mean that ( Rn)ij→0 for all 1 ≤i, j≤n. 3.2. CONVERGENCE AND PERTURBATION THEORY 101 Lemma 3.2.2. Suppose that the norm ,·,is a subordinate norm on Mn andR∈Mn. (i) If,R,<ε, then there is a constant Msuch that |pij|<Mε. (ii) If limn→∞,Rn,=0,t h e n limn→∞Rn=0. Proof. (i) If,R,<6, if follows that ,Rx,<6for each vector x,a n db y selecting the standard vectors ejin turn, it follows that from which it follows that,r∗j,<6,w h e r e r∗jdenotes the jthcolumn of R.By Theorem 1.6.2 all norms are equivalent. It follows that there is a fixed constant Mindependent of6andRsuch that |rij|<M6. (ii) Suppose for some increasing subsequence of powers nk→∞ it happens thateee(Rnk)ijeee≥r.Select the standard unit vector e j.A little computation shows that ,Rnkej,≥r,whence,Rnk,≥r, contradicting the known limit limn→∞,Rn,= 0. The conclusion lim n→∞Rn=0f o l l o w s . Lemma 3.2.3. Suppose that the norm ,·,is a subordinate norm on Mn. If,R,=λ<1,t h e n I+R+R2+···+Rk+···converges. Proof. LetPn=I+R+···+Rn. To show convergence we establish that {Pn}is a Cauchy sequence. For n>m we have Pn−Pm=n3 k=m+1Rk Hence ,Pn−Pm,=EEEEEn3 k=m+1RkEEEEE ≤n3 k=m+1,Rk, ≤n3 k=m+1,R,k =n3 m+1λk=λm+1n−m−13 j=0λj ≤λm+1(1−λ)−1→0 102 CHAPTER 3. EIGENVALUES AND EIGENVECTORS where in the second last step we used the inequality, which is valid for 0≤λ≤1.n−m−1 0λj≤∞ 0λj<(1−λ)−1. We conclude by Lemma 3.2.2 that the individual matrix entries of the parital sums converge and thus the series itself converges. Note that this result is independent of the particular norm. In practice it isoften necessary to select a convenient norm to actually carry out or verifyparticular computations are valid. In the theorem below we complete theanalysis of the matrix version of the geometric series, stating that when thenorm of a matrix is less than one, the geometric series based on that matrix converges and the inverse of the di fference with the identity exists. Theorem 3.2.1. IfR∈M n(F)and,R,<1for some norm, then (I−R)−1 exists and (I−R)−1=I+R+R2+···=∞3 k=0Rk. Proof. Apply the two previous lemmas. T h ep e r t u r b a t i o nr e s u l ta l l u d e dt oa b o v ec a nn o wb es t a t e da n de a s i l y proved. In words this result states that i fw eb e g i nw i t ha ni n v e r t i b l em a t r i x and additively perturb it by a su fficiently small amount the result remains invertible. Overall, this is the first of a series of results where what is proved is that some property of a matrix is preserved under additive perturbations. Corollary 3.2.1. IfA, B∈MnandAis invertible, then A+λBis invert- ible for su fficiently small |λ|(inRorC). Proof. A sa b o v ew ea s s u m et h a t ,·,is a norm on Mn(F). It is any easy computation to see that A+λB=A(I+λA−1B). Selectλsufficiently small so that ,λA−1B,=|λ|,A−1B,<1. Then by the theorem above, I+λA−1Bis invertible. Therefore (A+λB)−1=(I+λA−1B)−1A−1 and the result follows. 3.3. EIGENVECTORS AND EIGENVALUES 103 Another way of stating this is to say that if A, B∈MnandAhas a nonzero determinant, then for su fficiently small λthe matrix A+λBalso has a nonzero determinant. This corollary can be applied directly to the identitymatrix itself being perturbed by a rank one matrix. In this case the λcan be speci fied in terms of the two vectors comprising the matrix. (Recall Theorem 2.3.1(8).) Corollary 3.2.2. Letx, y∈R nsatisfy |x, yX|=|λ|<1.T h e n I+xyTis invertible and (I+xyT)−1=I−xyT(1 +λ)−1. Proof. We have that ( I+xyT)−1exists by selecting a norm ,·,consistent with the inner product ·,·X.( F o re x a m p l e ,t a k e ,A,=s u p ,x,2=1,Ax,2,w h e r e ,·,2is the Euclidean norm.) It is easy to see that ( xyT)k=λk−1xyT. Therefore (I+xyT)−1=I−xyT+(xyT)2−(xyT)3+··· =I−xyT+λxyT−λ2xyT+··· =I−xyTXn3 k=0(−λ)k~ . Thus (I+xyT)−1=I−xyT(1 +λ)−1 and the result is proved. In words we conclude that the perturbation of the identity by a small rank 1m a t r i xh a sa computable inverse. 3.3 Eigenvectors and Eigenvalues Throughout this section we will consider only matrices A∈Mn(C)o rMn(R). Furthermore, we suppress the field designation unless it is relevant. Definition 3.3.1. IfA∈Mnandx∈CnorRn.I f t h e r e i s a c o n s t a n t λ∈Cand a vector xW=0f o rw h i c h Ax=λx 104 CHAPTER 3. EIGENVALUES AND EIGENVECTORS we callλaneigenvalue ofAandxits corresponding eigenvector .A l - ternatively, we call xthe eigenvector pertaining to the eigenvalue λ,a n d vice-versa. Definition 3.3.2. ForA∈Mn,d efine (1)σ(A)={λ|Ax=λxhas a solution for a nonzero vector x}.σ(A)i s called the spectrum ofA. (2)ρ(A)= s u p λ∈σ(A)|λ|p or equivalently max λ∈σ(A)|λ|Q .ρ(A)i sc a l l e dt h e spectral radius . Example 3.3.1. LetA=[21 12]. Then λ= 1 is an eigenvalue of Awith eigenvector x=[−1,1]T.A l s oλ= 3 is an eigenvalue of Awith eigenvector x=( 1,1)T. The spectrum of Aisσ(A)={1,3}and the spectral radius of Aisρ(A)=3 . Example 3.3.2. The 3 ×3m a t r i x B= −30 6 −12 9 26 4−4−9 has eigenvalues: −1,−3,1. Pertaining to the eigenvalues are the eigenvectors    3 11   ↔1,   1 10   ↔− 3   3 −2 2   ↔− 1 The characteristic polynomial To say that Ax=λxhas a nontrivial solution ( xW=0 )f o rs o m e λ∈Cis the same as the assertion that ( A−λI)x= 0 has a nontrivial solution. This means that det(A−λI)=0 or what is more commonly written det(λI−A)=0 . From the original de finition (De finition 2.5.1) the determinant is sum of products of individual matrix entries. Therefore, det( λI−A)m u s tb ea polynomial in λ.T h i sm a k e st h ed e finition: 3.3. EIGENVECTORS AND EIGENVALUES 105 Definition 3.3.3. LetA∈Mn. The determinant pA(λ)=d e t (λI−A) is called the characteristic polynomial ofA. Its zeros1are the called theeigenvalues ofA.T h e s e t σ(A) of all eigenvalues of Ais called the spectrum ofA. A simple consequence of the nature of the determinant of det( λI−A)i s the following. Proposition 3.3.1. IfA∈Mn,t h e n pA(λ)has degree exactly n. See Appendix A for basic information on solving polynomials equations p(λ) = 0. We may note that even though A∈Mn(C)h a s n2entries in its de finition, its spectrum is completely determined by the ncoefficients of pA(λ). Procedure. The basic procedure of determining eigenvalues and eigenvec- tors is this: (1) Solve det( λI−A) = 0 for the eigenvalues λand (2) for any given eigenvalue λsolve the system ( A−λI)x= 0 for the pertaining eigenvector(s). Though this procedure is not practical in general it can beeffective for small sized matrices, and for matrices with special structures. Theorem 3.3.1. LetA∈M n.The set of eigenvectors pertaining to any particular eigenvalue is a subspace of the given vector space Cn. Proof. Letλ∈σ(A).The set of eigenvectors pertaining to λis the null space of ( A−λI).The proof is complete by application of Theorem 2.3.1 that states the null space of any matrix is a subspace of the underlying vector space. In light of this theorem the following de finition makes sense and is a most important concept in the study of eigenvalues and eigenvectors. Definition 3.3.4. LetA∈Mnand letλ∈σ(A). The null space of (A−λI)i sc a l l e dt h e eigenspace ofApertaining to λ. Theorem 3.3.2. LetA∈Mn.T h e n (i) Eigenvectors pertaining to di fferent eigenvalues are linearly indepen- dent. 1The zeros of a polynomial (or more generally a function) p(λ) are the solutions to the equation p(λ)=0 . As o l u t i o nt o p(λ)=0i sa l s oc a l l e da root of the equation. 106 CHAPTER 3. EIGENVALUES AND EIGENVECTORS (ii) Suppose λ∈σ(A)with eigenvector xis different from the set of eigenvalues {µ1,...,µ k}⊂σ(A)andVµis the span of the pertaining eigenspaces. Then x/∈Vµ. Proof. (i) Let µ,λ∈σ(A)w i t h µW=λpertaining eigenvectors xandy resepectively. Suppose these vectors are linearly dependent; that is, y=cx. Then µy=µcx=cµx =cAx=A(cx) =Ay =λy This is a contradiction, and (i) is proved. (ii) Suppose the contrary holds, namely that x∈Vµ.T h e n x=a1y1+···+ akymwhere {y1,···,ym}are linearly independent vectors of Vµ.E a c h o f the vectors yiis an eigenvector, we know. Assume the pertaining eigenvalues denoted by µji.T h a ti st os a y , Ayi=µjiyi,for each i=1,...,m . Then λx=Ax=A(a1y1+···+amym) =a1µj1y1+···+akµjmym IfλW=0w eh a v e x=a1y1+···+amym=a1µj1 λy1+···+akµjm λym We know by the previous part of this result that at least two of the co- efficients aimust be nonzero. (Why?) Thus we have two di fferent rep- resentations of the same vector by linearly independent vectors, which is impossible. On the other hand, if λ=0t h e n a1µ1y1+···+akµkyk=0 , which is also impossible. Thus, (ii) is proved. The examples below will illustrate the spectra of various matrices. Example 3.3.1. LetA=Jab cdo .T h e n pA(λ)i sg i v e nb y pA(λ)=d e t (λI−A)=d e t}λ−a−b −cλ−d] =(λ−a)(λ−d)−bc =λ2−(a+d)λ+ad−bc. 3.3. EIGENVECTORS AND EIGENVALUES 107 The eigenvalues are the roots of pA(λ)=0 λ=a+d±0 (a+d)2−4(ad−bc) 2 =a+d±0 (a−d)2+4bc 2. For this quadratic there are three possibilities: (a) Two real rootsc 9different values equal values (b) Two complex roots Here are three 2 ×2 examples that illustrate each possibility. The reader should compute the characteristic polynomials to verify these computation. B1=}1−1 1−1] .Then pB1(λ)=λ2λ=0,0 B2=}0−1 10] .Then pB2(λ)=λ2+1λ=±i B3=}01 10] .Then pB3(λ)=λ2−1λ=±1. Example 3.3.2. Consider the rotation in the x, z-plane through an angle θ B= cosθ0−sinθ 01 0 sinθ0c o sθ  The characteristic polynomial is given by pB(λ)=d e t λ 100 010001 − cosθ0−sinθ 01 0 sinθ0c o sθ   =−1+( 1+2c o s θ)λ−(1 + 2 cos θ)λ 2+λ3 The eigenvalues are 1 ,cosθ+√ cos2θ−1,cosθ−√ cos2θ−1.Whenθ is not equal to an even multiple of π, exactly two of the roots are complex numbers. In fact, they are complex conjugate pairs, which can also be written as cos θ+isinθ,cosθ−isinθ. The magnitude of each eigenvalue 108 CHAPTER 3. EIGENVALUES AND EIGENVECTORS is 1, which means all three eigenvalues lie on the unit circle in the complex plane. An interesting observation is that the characteristic polynomial andhence the eigenvalues are the same regardless of which pair of axes ( x-z, x-y,o ry-z) is selected for the rotation. Matrices of the form Bare actually called rotations. In two dimensions the counter-clockwise rotations through the angle θare given by B θ=}cosθ−sinθ sinθcosθ] The eigenvalues for all θis not equal to an even multiple of πare±i.( S e e Exercise 2.) Example 3.3.3. IfTis upper triangular with diag T=[t11,t22,... ,t nn]. ThenλI−Tis upper triangular with diag[ λ−t11,λ−t22,... ,λ−tnn]. Thus the determinant of λI−Tgives the characteristic polynomial of Tto be pT(λ)=n i=1(λ−tii) The eigenvalues of Tare the diagonal elements of T. By expanding this product we see that pT(λ)=λn−(Σtii)λn−1+ lower order terms. The constant term of pT(λ)i s(−1)nn i=1tii=(−1)ndetT.W ed e fine trT=n3 i=1tii and call it the trace ofT. The same statements apply to lower triangular matrices. Moreover, the trace de finition applies to all matrices, not just to triangular ones, and the result will be the same. Example 3.3.4. Suppose that Ais rank 1. Then there are two vectors w,z∈Cnfor which A=wzT. Tofind the spectrum of Awe consider the equation Ax=λx 3.3. EIGENVECTORS AND EIGENVALUES 109 or z,xXw=λx. From this we see that x=wis an eigenvector with eigenvalue z,wX.I f z⊥x, x is an eigenvector pertaining to the eigenvalue 0. Therefore, σA={z,wX,0}. T h ec h a r a c t e r i s t i cp o l y n o m i a li s pλ(λ)=(λ−z,wX)λn−1. Ifwandzare orthogonal then pA(λ)=λn. Ifwandzare not orthogonal though there are just two eigenvalues, we say that 0 is an eigenvalue of multiplicity n−1, the order of the factor ( λ−0). Alsoz,wXhas multiplicity 1. This is the subject of the next section. For instance, suppose w=( 1,−1,2) and z=( 0,1,−3). Then spectrum of the matrix A=wzTis given by σ(A)={−7,0}. The eigenvalue pertain- ing toλ=−7i swand we may take x=( 0,3,1) and ( c,3,1), for any c∈C, to be eigenvectors pertaining to λ=0 . N o t et h a t {w,(0,3,1),(1,3,1)}form ab a s i sf o r R3. To complete our discussion of characteristic polynomials we prove a re- sult that every nthdegree polynomial with lead coe fficient one is the char- acteristic polynomial of some matrix. You will note the similarity of thisresult and the analogous result for di fferential systems. Theorem 3.3.3. Every polynomial of n thdegree with lead coe fficient 1, that is q(λ)=λn+b1λn−1+···+bn−1λ+bn is the characteristic polynomial of some matrix. Proof. We consider the n×nmatrix B= 01 0 ··· 0 00 1 0 ...... −b n−bn−1 −b1  110 CHAPTER 3. EIGENVALUES AND EIGENVECTORS ThenλI−Bhas the form λI−B= λ−10 ··· 0 0λ−10 ... λ... b nbn−1 λ+b1  Now expand in minors across the bottom row to get det (λI−B)= b n(−1)n+1det −10 ··· 0 λ−10 λ...  +bn−1(−1)n+2det λ0··· 0 0−10 ...λ... +··· +b1(−1)n+ndet λ−10 ··· 0λ−1 ... λ...  =bn(−1)n+1(−1)n−1+bn−1(−1)n+2λ(−1)n−2+··· +(λ+b1)(−1)n+nλn−1 =bn+bn−1λ+···+b1λn−1+λn which is what we set out to prove. (The reader should check carefully the term with bn−2to fully understand the nature of this proof.) Multiplicity LetA∈Mn(C). Since pA(λ) is a polynomial of degree exactly n,i tm u s t have exactly neigenvectors (i.e. roots) λ1,λ2,... ,λncounted according to multiplicity. Recall that the multiplicity of an eigenvalue is the number oftimes the monomial ( λ−λ i) is repeated in the factorization of pA(λ). For example the multiplicity of the root 2 in the polynomial ( λ−2)3(λ−5) is 3. Suppose µ1,... ,µ kare the distinct eigenvalues with multiplicities m1,m2,... ,m krespectively. Then the characteristic polynomial can be 3.3. EIGENVECTORS AND EIGENVALUES 111 rewritten as pA(λ)=d e t (λI−A)=n 1(λ−λi) =k 1(λ−µi)mi. More precisely, the multiplicities m1,m2,... ,m kare called the algebraic multiplicities of the respective eigenvalues. This factorization will be very useful later. We know that for each eigenvalue λof any multiplicity m,t h e r em u s t be at least oneeigenvector pertaining to λ. What is desired, but not always possible, is to findµlinearly independent eigenvectors corresponding to the eigenvalue λof multiplicity m. This state of a ffairs makes matrix theory at once much more challenging but also much more interesting. Example 3.3.3. For the matrix A= 20 0 07 41 4√ 3 01 4√ 35 4  the characteristic polynomial is det(λI−A)=pA(λ)=λ3−5λ2+8λ− 4,which can be factored as pA(λ)=(λ−1) (λ−2)2We see that the eigenvalues are 1, 2, and 2. So, th e multiplicity of the eigenvalue λ=1 is 1, and the multiplicity of the eigenvalue λ=2i s2 . T h ee i g e n s p a c e pertaining to the eigenvalue λ= 1 is generated by the vector 0 −1 3√ 3 1 , and the dimension of this eigenspace is one. The eigenspace pertaining to λ=2i sg e n e r a t e db y 1 00 and 0 1 1 3√ 3 .(That is, these two vectors form a basis of the eigenspace.) To summarize, for the given matrix there is one eigenvector for the eigenvalue λ= 1, and there are two linearly independent eigenvectors for the eigenvalue λ= 2. The dimension of the eigenspace pertaining to λ= 1 is one, and the dimension of the eigenspace pertaining toλ=2i st w o . Now contrast the above example where the eigenvectors span the space C3 and the next example where we have an eigenvalue of multiplicity three but the eigenspace is of dimension one. 112 CHAPTER 3. EIGENVALUES AND EIGENVECTORS Example 3.3.4. Consider the matrix A= 2−10 020 102  The characteristic polynomial is given by ( λ−2)3.Hence the eigenvalue λ= 2 has multiplicity three. The eigenspace pertaining to λ=2i sg e n e r - ated by the single vector [0 ,0,1]TTo see this we solve (A−2I)x=  2−10 020102 −2 100 010001  x = 0−10 000100 x=0 The row reduced echelon form for 0−10 000 100 is 100 010 000 .F r o m this it is apparent that we may take x 3=t,but that x1=x2=0.Now assign t= 1 to obtain the generating vector [0 ,0,1]T.This type of example and its consequences seriously complexi fies the study of matrices. Symmetric Functions Definition 3.3.5. Letnbe a positive integer and Λ={λ1,λ2,... ,λn}be given numbers. Suppose that kis a positive integer with 1 ≤k≤n.T h e kthelementary symmetric function on theΛis defined by Sk(λ1,... ,λn)=3 1≤i1<···<ik≤nk j=1λij. It is easy to see that S1(λ1,... ,λn)=n3 1λi Sn(λ1,... ,λn)=n 1λi. 3.3. EIGENVECTORS AND EIGENVALUES 113 For a given matrix A∈Mnthere are nsymmetric functions de fined with respect to its eigenvalues Λ={λ1,λ2,... ,λn}. The symmetric functions are sometimes called the invariants of matrices as they are invariant undersimilarity transformations that will be in Section 3.5. They also furnishdirectly the coe fficients of the characteristic polynomial. Thus specifying thensymmetric functions of an n×nmatrix is su fficient to determine its eigenvalues. Theorem 3.3.4. LetA∈M nhave symmetric functions Sk,k=1,2, ..., n . Then det(λI−A)=n i=1(λ−λi)=λn+n3 k=1(−1)kSkλn−k. Proof. The proof is a consequence of actually expanding the productn i=1(λ− λi). Each term in the expansion has exactly nterms multiplied together that are combinations of the factor λand the−λI is. For example, for the power λn−kthe coefficient is obtained by computing the total number of products ofk“different”−1λI is.( T h e t e r m d i fferent is in quotes because it refers to different indices not actual values.) Co l l e c t i n ga l lt h e s et e r m si sa c c o m - plished by addition. Now the number of ways we can obtain products ofthese kdifferent (−1)λ I isis easily seen to be the number of sequences in the set{1≤i1<···<ik≤n}. The sum of these is clearly ( −1)kSk,w i t ht h e (−1)kfactor being the collected product of k−1’s. Two of the symmetric functions are familiar. In the following we restate this using familiar terms. Theorem 3.3.5. LetA∈Mn(C).T h e n pA(λ)=d e t (λI−A)=n3 k=0pkλn−k where p0=1 and (i)p1=−tr(A)=−n3 1aii (ii) pn=−detA. (iii) pk=(−1)kSk,for1<k<n . 114 CHAPTER 3. EIGENVALUES AND EIGENVECTORS Proof. Note that pA(0) =−det(A)=pn. This gives (ii). To establish (i), we consider det λ·a 11−a12 ...−a1n −a21λ−a22 −a2n ...... −an1 ... λ−ann . Clearly the productn 1(λ−aii) is one of the selections of products in the calculation process. In every other product there must be no more than n−2 diagonal terms. Hence pA(λ)=d e t (λI−A)=n 1(λ−aii)+pn−2(λ), where pn−2(λ) is a polynomial of degree n−2. The coe fficient ofλn−1is −n 1aiiby the Theorem 3.3.4, and this is (i). As a final note, observe that the characteristic polynomial is de fined by knowing the nsymmetric functions. However, the matrix itself has n2en- tries. Therefore, one may expect that knowing the only characteristic poly- nomial of a matrix is insu fficient to characterize it. This is correct. Many matrices having rather di fferent properties can have the same characteristic polynomial. 3.4 The Hamilton-Cayley Theorem The Hamilton-Cayley Theorem opens the doors to a finer analysis of a ma- trix through the use of polynomials, which in turn is an important tool of spectral analysis. The results states that any square matrix satis fies its own charactertic polynomial, that is pA(A)=0 . T h ep r o o fi sn o td i fficult, but we need some preliminary results about fac toring matrix-valued polynomials. Preceding that we need to consider matrix polynomials in some detail. Matrix polynomials One of the very important results of matrix theory is the Hamilton-Cayleytheorem which states that a matrix satis fies its only characteristic equation. This implies we need the notion of a matrix polynomial. It is an easy idea 3.4. THE HAMILTON-CAYLEY THEOREM 115 – just replace the coe fficients of any polynomial by matrices – but it bears some important consequences. Definition 3.4.1. LetA0,A1,... ,A mbe square n×nmatrices. We can define the polynomial with matrix coe fficients A(λ)=A0λm+A1λm−1+···+Am−1λ+Am. Thedegree ofA(λ)i sm,p r o v i d e d A0W=0 . A(λ) is called regular if det A0W= 0. In this case we can construct an equivalent monic2polynomial. ˜A(λ)=A−1 0A(λ)=A−1 0A0λm+A−1 0A1λm−1+···+A−1 0Am =Iλm+˜A1λm−1+···+˜Am. The algebra of matrix polynomials mim ics the normal polynomial algebra. Let A(λ)=m3 0Aiλm−kB(λ)=m3 0Biλm−k. (1)Addition: A(λ)±B(λ)=m3 0(Ak±Bk)λm−k. (2)Multiplication: A(λ)B(λ)=m3 i=0λmwm3 k=0AiBm−iW The termm k=0AiBm−iis called the Cauchy product of the sequences. Note that the matrices Ajalways multiply on the left of the Bk. (3)Division: LetA(λ)a n d B(λ)b et w om a t r i xp o l y n o m i a l so fd e g r e e m(as above) and suppose B(λ) is regular, i.e. det B0W=0 . W es a y thatQr(λ)a n d Rr(λ)a r eright quotient andremainder ofA(λ)u p o n division by B(λ)i f A(λ)=Qr(λ)B(λ)+Rr(λ)( 1 ) 2Recall that a monic polynomial is a polynomial where coe ffic i e n to ft h eh i g h e s tp o w e r is one. For matrix polynomials the corresponding coe fficient is I, the identity matrix. 116 CHAPTER 3. EIGENVALUES AND EIGENVECTORS i ft h ed e g r e eo f Rr(λ)i slessthan that of B(λ). Similarly Qf(λ)a n d Rf(λ) are respectively the leftquotient andremainder ofA(λ)u p o n division by B(λ)i f A(λ)=B(λ)Qf(λ)+Rf(λ)( 2 ) i ft h ed e g r e eo f Rf(λ)i slessthan that of B(λ). I nt h ec a s e( 1 )w es e e A(λ)B−1(λ)=Qr(λ)+Rr(λ)B−1(λ), (3) which looks much likea b=q+r b, a way to write the quotient and remainder of a divided by bwhen aandbare numbers. Also, the form (3) may not properly exist for all λ. Lemma 3.4.1. LetBi∈Mn(C),i =0,... , n with B0nonsingular. Then the polynomial B(λ)=B0λn+B1λn−1+···+Bn is invertible for su fficiently large |λ|. Proof. We factor B(λ)a s B(λ)= B0λnD I+B−1 0B1λ−1+···+B−1 0Bnλ−ni =B0λnJ I+λ−1D B−1 0B1+···+B−1 0Bnλ1−nio Forλ>1, the norm of the term B−1 0B1+···+B−1 0Bnλ1−nis bounded by EEB−1 0B1+···+B−1 0Bnλ1−nEE≤EEB−1 0B1EE+EEB−1 0B2EE|λ|−1+···EEB−1 0BnEE|λ|1−n ≤p 1+|λ|−1+···+|λ|1−nQ max 1≤i≤nEEB−1 0BiEE ≤1 1−|λ|−1max 1≤i≤nEEB−1 0BiEE Thus the conditions of our perturbation theorem hold and for su fficiently large |λ|,it followsEEλ−1D B−1 0B1+···+B−1 0Bnλ1−niEE<1.Hence I+λ−1D B−1 0B1+···+B−1 0Bnλ1−ni is invertible and therefore B(λ) is also invertible. 3.4. THE HAMILTON-CAYLEY THEOREM 117 Theorem 3.4.1. LetA(λ)andB(λ)be matrix polynomials in Mn(C)or (Mn(R)). Then both left and right division of A(λ)byB(λ)is possible and the respective quotients an d remainders are unique. Proof. We proceed by induction on deg B, and clearly if deg B=0t h er e s u l t holds. If deg B=p> degA(λ)=mthen the result follows simply. For, takeQr(λ)=0a n d Rr(λ)=A(λ). The conditions of right division are met. Now suppose that p≤m. It is easy to see that A(λ)=A0λm+A1λm−1+···+Am−1λ+Am =A0B−1 0λm−pB(λ)−p3 j=1A0B−1 0Bjλm−j+m3 j=1Ajλm−j =Q1(λ)B(λ)+A1(λ) where deg A1(λ)<degA(λ). Our inductive hypothesis assumed the division was possible for matrix polynomials A(λ)o fd e g r e e <p.T h e r e f o r e , A1(λ)= Q2(λ)B() + R(λ), where the degree of B(λ)<p . Finally, with Q(λ)= Q(λ)+Q2(λ), there results A(λ)=Q(λ)B() +R(λ). To establish uniqueness we assume two right divisors and quotients have been determined. Thus A=Qr1(λ)B(λ)+Rr1(λ) A=Qr2(λ)B(λ)+Rr2(λ) Subtract to get 0=( Qr1(λ)−Qr2(λ))B(λ)+Rr1(λ)−Rr2(λ). IfQr1(λ)−Qr2(λ)W= 0, we know the degree of ( Qr1(λ)−Qr2(λ))B(λ)i s greater than the degree of R1(λ)−R2(λ). This contradiction implies that Qr1(λ)−Qr2(λ)=0 ,w h i c hi nt u r ni m p l i e st h a t Rr1(λ)−Rr2(λ)=0 . H e n c e the decomposition is unique. Hamilton-Cayley Theorem Let B(λ)=B0λm+B1λm−1+···+Bm−1λ+Bm with B0W= 0. We can also, write B(λ)=m i=0λm−iBi. Both versions are the same. However, when A∈Mn(F), there are two possible evaluations of B(A). 118 CHAPTER 3. EIGENVALUES AND EIGENVECTORS Definition 3.4.2. LetB(λ),A∈Mn(C)( o r Mn(R)) and B(λ)=B0λm+ B1λm−1+···+Bm−1λ+Bm.D efine B(A)=B0Am+B1Am−1+···+Bm “right value” B(A)=AmB0+Am−1B1+···+Bm “left value” The generalized B´ ezout theorem gives the remainder of B(λ)d i v i d e db y λI−A.I nf a c t ,w eh a v e Theorem 3.4.2 (Generalized B´ ezout Theorem). The right division of B(λ)byλI−Ahas remainder Rr(λ)=B(A) Similarly, the left division of B(λ)by(λI−A)has remainder Rf(λ)=B(A). Proof. In the case deg B(λ)=1 ,w eh a v e B0λ+B1=B0(λI−A)+B0A+B1. The remainder Rr(λ)=B0A+B1=B(A). Assume the result holds for all polynomials up to degree p−1. We have B(λ)=B0λp+B1λp−1+···+Bp =B0λp−1(λI−A)+B0Aλp−1+B1λp−1+··· =B0λp−1(λI−A)+B1(λ) where deg B1(λ)≤p−1. By induction B(λ)=B0λp−1(λI−A)+Qr(λ)(λI−A)+B1(A) B1(A)=( B0A+B1)Ap−1+B2Ap−2+···+Bp−1A+Bp=B(A). This proves the result. Corollary 3.4.1. (λI−A)divides B(λ)if and only if B(A)=0 (resp B(A)=0 ). Combining the B´ ezout result and the adjoint formulation of the matrix inverse, we can establish the important Hamilton-Cayley theorem. Theorem 3.4.3 (Hamilton-Cayley). LetA∈Mn(C)(orMn(R))w i t h characteristic polynomial pA(λ).T h e n pA(A)=0 . 3.4. THE HAMILTON-CAYLEY THEOREM 119 Proof. Recall the adjoint formulation of the inverse as ˆC=1 det·CCT ij=C−1. Now let B=adj(A−λI). Then B(λI−A)=d e t (λI−A)I (λI−A)B=d e t (λI−A)I. These equations show that p(λ)I=d e t (λI−A)Iis divisible on the right andthe left by ( λI−A) without remainder. It follows from the generalized B´ezout theorem that this is possible only if pA(A)=0 . LetA∈Mn(C).Now that we know any Asatisfies its characteristic polynomial, we might also ask if there are polynomials of lower degree that it also satis fies. In particular, we will study the so-called minimal polynomial that a matrix satis fies. The nature of this polynomial will shed considerable light on the fundamental structure of A. For example, both matrices below have the same characteristic polynomial P(λ)=(λ−2)3. A= 200 020002 andB= 210 021002  Henceλ= 2 is an eigenvalue of multiplicity three. However, Asatifies the much simpler first degree polynomial ( λ−2) while there is no polynomial of degree less that three that Bsatisfies. By this time you recognize that Ahas three linearly independent eigenvectors, while Bhas only one eigenvector. We will take this subject up in a later chapter. Biographies Arthur Cayley (1821-1895), one of the most proli fic mathematicians of his era and of all time, born in Richmond, Surrey, and studied mathematics atCambridge. For four years he taught at Cambridge having won a Fellowshipand, during this period, he published 28 papers in the Cambridge Mathe-matical Journal. A Cambridge fellowship had a limited tenure so Cayley had to find a profession. He chose law and was admitted to the bar in 1849. He spent 14 years as a lawyer, but Cayley always considered it as a meansto make money so that he could pursue mathematics. During these 14 yearsas a lawyer Cayley published about 250 mathematical papers! Part of thattime he worked in collaboration with James Joseph Sylvester 3(1814- 3In 1841 he went to the United States to become professor at the University of Virginia, but just four years later resigned and returned to England. He took to teaching private 120 CHAPTER 3. EIGENVALUES AND EIGENVECTORS 1897), another lawyer. Together, but not in collaboration, they founded the algebraic theory of invariants 1843. In 1863 Cayley was appointed Sadleirian professor of Pure Mathemat- ics at Cambridge. This involved a very large decrease in income. However Cayley was very happy to devote himself entirely to mathematics. He pub-lished over 900 papers and notes covering nearly every aspect of modernmathematics. The most important of his work is in developing the algebra of matrices, work in non-Euclidean geometry and n-dimensional geometry. Importantly, he also clari fied many of the theorems of algebraic geometry that had previ- ously been only hinted at, and he was among the first to realize how many different areas of mathematics were linked together by group theory. As early as 1849 Cayley wrote a paper l inking his ideas on permutations with Cauchy’s. In 1854 Cayley wrote two papers which are remarkable forthe insight they have of abstract groups. At that time the only knowngroups were groups of permutations and even this was a radically new area, yet Cayley de fines an abstract group and gives a table to display the group multiplication. Cayley developed the theory of algebraic invariance, and his develop- ment of n-dimensional geometry has been applied in physics to the study of the space-time continuum. His work on matrices served as a founda- tion for quantum mechanics, which was developed by Werner Heisenberg in1925. Cayley also suggested that Euclidean and non-Euclidean geometryare special types of geometry. He united projective geometry and metricalgeometry which is dependent on sizes of angles and lengths of lines. Heinrich Weber (1842-1913) was born and educated in Heidelberg, where he became professor 1869. He then taught at a number of institutions inGermany and Switzerland. His main work was in algebra and number theory. He is best known for his outstanding text Lehrbuch der Algebra published in 1895. Weber worked hard to connect the various theories even fundamental concepts such as a fie l da n dag r o u p ,w h i c hw e r es e e na st o o l sa n dn o t properly developed as theories in his Die partiellen Di fferentialgleichungen der mathematischen Physik 1900-01, which was essentially a reworking of a book of the same title based on lectures given by Bernhard Riemann and pupils and had among them Florence Nightingale. By 1850 he became a barrister, and by 1855 returned to an academic life at the Royal Military Academy in Woolwich, London. Hereturned to the US again in 1877 to become prof essor at the new Johns Hopkins University, but returned to England once again in 1877. Sylvester coined the term ‘matrix’ in 1850. 3.4. THE HAMILTON-CAYLEY THEOREM 121 written by Karl Hattendor ff. Etienne B´ ezout (1730-1783) was a mathematician who represents a char- acteristic aspect of the subject at that time. One of the many successful textbook projects produced in the 18thcentury was B´ ezout’s Cours de math- ematique ,as i xv o l u m ew o r kt h a t first appeared in 1764-1769, which was almost immediately issued in a new e dition of 1770-1772, and which boasted many versions in French and other languages. (The first American textbook in analytic geometry, incidentally, was derived in 1826 from B´ ezout’s Cours .) It was through such compilations, rather than through the original works of the authors themselves, that the mathematical advances of Euler and d’Alembert became widely known. B´ ezout’s name is familiar today in con- nection with the use of determinants in algebraic elimination. In a memoirof the Paris Academy for 1764, and more extensively in a treatise of 1779entitled Theorie generale des equations algebriques ,B ´ezout gave arti ficial rules, similar to Cramer’s, for solving nsimultaneous linear equations in n unknowns. He is best known for an extension of these to a system of equa- tions in one or more unknowns in which it is required to find the condition on the coe fficients necessary for the equations to have a common solution. To take a very simple case, one might ask for the condition that the equa-tions a 1x+b1y+c1=0 , a2x+b2y+c2=0 , a3x+bay+c3=0h a v ea common solution. The necessary condition is that the eliminant a special case of the “Bezoutiant,” should be 0. Somewhat more complicated eliminants arise when conditions are sought for two polynomial equations of unequal degree to have a common solution.B´ezout also was the first one to give a satisfactory proof of the theorem, known to Maclaurin and Cramer, that two algebraic curves of degrees mand nrespectively intersect in general in m·npoints; hence, this is often called B´ezout’s theorem. Euler also had contributed to the theory of elimination, but less extensively than did B´ ezout. Taken from A History of Mathematics by Carl Boyer 122 CHAPTER 3. EIGENVALUES AND EIGENVECTORS William Rowen Hamilton Born Aug. 3/4, 1805, Dublin, Ire. and died Sept. 2, 1865, Dublin Irish mathematician and astronomer who developed the theory of quater- nions, a landmark in the development of algebra, and discovered the phe-nomenon of conical refraction. His uni fication of dynamics and optics, more- over, has had lasting in fluence on mathematical physics, even though the full signi ficance of his work was not fully appreciated until after the rise of quantum mechanics. Like his English contemporaries Thomas Babington Macaulay and John Stuart Mill, Hamilton showed unusual intellect as a child. Before the age of three his parents sent him to live with his father’s brother, James, a learned clergyman and schoolmaster at an Anglican school at Trim, a small town near Dublin, where he remained until 1823, when he entered Trinity College, Dublin. Within a few months of his arrival at his uncle’s he couldread English easily and was advanced in arithmetic; at five he could translate Latin, Greek, and Hebrew and recite Homer, Milton and Dryden. Beforehis 12th birthday he had compiled a grammar of Syriac, and by the age of 14 he had su fficient mastery of the Persian language to compose a welcome to the Persian ambassador on his visit to Dublin. Hamilton became interested in mathematics after a meeting in 1820 with Zerah Colburn, an American who cou ld calculate mentally with aston- ishing speed. Having read the El´ements d’alg` ebre of Alexis—Claude Clairaut and Isaac Newton’s Principia ,Hamilton h a di m m e r s e dh i m s e l fi nt h e five volumes of Pierre—Simon Laplace’s Trait´ ed em ´ ecanique c´ eleste (1798-1827; Celestial Mechanics ) by the time he was 16. His detection of a flaw in Laplace’s reasoning brought him to the attention of John Brinkley, pro-fessor of astronomy at Trinity College. When Hamilton was 17, he sent Brinkley, then president of the Royal Irish Academy, an original memoir about geometrical optics. Brinkley, in forwarding the memoir to the Acad- emy, is said to have remarked: “This young man, I do not say will be , but is,t h e first mathematician of his age.” In 1823 Hamilton entered Trinity College, from which he obtained the highest honours in both classics and m athematics. Meanwhile, he continued his research in optics and in April 1827 submitted this “theory of Systems of Rays” to the Academy. The paper tr ansformed geometrical optics into a new mathematical science by establishing one uniform method for thesolution of all problems in that field.Hamilton started from the principle, originated by the 17th-century French mathematician Pierre de Fermat, thatlight takes the shortest possible time in going from one point to another, whether the path is straight or is bent by refraction. Hamilton ’s key idea 3.5. SIMILARITY 123 was to consider the time (or a related quantity called the “action”) as a function of the end points between which the light passes and to show thatthis quantity varied when the coordinates of the end points varied, accordingto a law that he called the law of varying action. He showed that the entiretheory of systems of rays is reducible to the study of this characteristic function. Shortly after - Hamilton submitted his paper and while still an under- graduate, Trinity College elected h im to the post of Andrews professor of astronomy and royal astronomer of Ireland, to succeed Brinkley, who hadbeen made bishop. Thus an undergraduate (not quite 22 years old) becameex officio an examiner of graduates who were candidates for the Bishop Law Prize in mathematics. The electors’ object was to provide Hamilton with a research post free from heavy teachi ng duties. Accordingly, in October 1827Hamilton took up residence next to Dunsink Observatory, 5 miles (8 km) from Dublin, where he lived for the rest of his life. He proved to be anunsuccessful observer, but large audiences were attracted by the distinctlyliterary flavour of his lectures on astronomy. Throughout his life Hamilton was attracted to literature and considered the poet William Wordsworth among his fiends, although Wordsworth advised him to write mathematics rather than poetry. With eigenvalues we are able to begin spectral analysis. That part is the derivation of the various normal forms for matrices. We begin with a relatively weak form of the Jordan form, which is coming up. First of all, as you have seen diagona l matrices furnish the easiest form for matrix analysis. Also, linear systems are very simple to solve for diagonalmatrices. The next simplest class of matrices are the triangular matrices.We begin with the following result based on the idea of similarity. 3.5 Similarity Definition 3.5.1. Am a t r i x B∈Mnis said to be similar toA∈Mnif there exists a nonsingular matrix S∈Mnsuch that B=S−1AS. The transformation A→S1ASis called a similarity transformation .S o m e - times we write A∼B. Note that similarity is an equivalence relation: (i) A∼A reflexivity (ii) B∼A⇒A∼B symmetry (iii) B∼AandA∼C⇒B∼Ctransitivity 124 CHAPTER 3. EIGENVALUES AND EIGENVECTORS Theorem 3.5.1. Similar matrices have the same characteristic polynomial. Proof. We suppose A, B,a n d S∈Mnwith Sinvertible and B=S−1AS. Then λI−B=λI−S−1AS =λS−1IS−S−1AS =S−1(λI−A)S. Hence det(λI−B)=d e t ( S−1(λI−A)S) =d e t ( S−1)d e t (λI−A)d e tS =d e t (λI−A) because 1 = det I=d e t ( SS−1)=d e t SdetS−1. A simple consequence of Theorem 3.5.1 and Corollary 2.3.1 follows. Corollary 3.5.1. IfAandBare in Mnand if AandBare similar, then they have the same eigenvalues counted ac cording to multiplicity, and there- f o r et h es a m er a n k . We remark that even though [00 00]a n d[0100] have the same eigenvalues, 0 and 0, they are not similar. Hence the converse is not true. Another immediate corollary of Theorem 3.5.1 can be expressed in terms of the invariance of the trace and determinant of similarity transformations , that is functions on Mn(F)d efined for any invertible matrix SbyTS(A)= S−1AS. Note that such transformations are linear mappings from Mn(F)→ Mn(F). We shall see how important are those properties of matrices that are invariant (i.e. do not change) under similarity transformations. Corollary 3.5.2. IfA, B∈Mnare similar, then they have the same trace and same determinant. That is, tr(A) = tr(B) anddetA=d e t B. Theorem 3.5.2. IfA∈Mn,t h e n Ais similar to a triangular matrix. Proof. The following sketch shows the first two steps of the proof. A formal induction can be applied to achieve the full result. Letλ1be an eigenvalue of Awith eigenvector u1. Select a basis , say S1,o fCnand arrange these vectors into columns of the matrix P1,w i t h u1 3.5. SIMILARITY 125 in the first column. De fineB1=P−1 1AP1.T h e n B1is the representation of Ain the new basis and so B1= λα 1...αn−1 0 ... A2 0 where A 2is (n−1)×(n−1) because Au1=λ1u1. Remembering that B1is the representation of Ain the basis S1,t h e n[ u1]S1=e1and hence B1e1=λe1=λ1[1,0,... , 0]T.B y similarity, the characteristic polynomial of B1i st h es a m ea st h a to f A, but more importantly (using expansion by minors down the first column) det(λI−B1)=(λ−λ1)d e t (λIn−1−A2). Now select an eigenvalue λ2ofA2and pertaining eigenvector v2∈Cn;s o A2v2=λ2v2.N o t et h a t λ2is also an eigenvalue of A. With this vector we define ˆu1= 1 0 ... 0 ˆu2= 0 v2 . Select a basis of Cn−1,w i t h v2selected first and create the matrix P2with this basis as columns P2= 10 ... 0 0 ...P 2 0 . It is an easy matter to see that P 2is invertible and B2=P−1 2B1P2 = λ 1∗... ... ∗ 0λ2∗...∗ 00 A3 ...... 00 . Of course, B 2∼B1, and by the transitivity of similarity B2∼A.C o n - tinue this process, deriving ultimately the triangular matrix Bn∼Bn−1and hence Bn∼A. This completes the proof. 126 CHAPTER 3. EIGENVALUES AND EIGENVECTORS Definition 3.5.2. We say that A∈Mnisdiagonalizable ifAis similar to a diagonal matrix. Suppose P∈Mnis nonsingular and D∈Mnis a diagonal matrix. Let A=PDP−1. Suppose the columns of Pare the vectors v1,v2,... ,v n.T h e n Avj=PDP−1vj =PDe j=λjPej=λjvj whereλjis the jthdiagonal element of D,a n d ejis the jthstandard vector. Similarly, if u1,... ,u narenlinearly independent vectors of Apertain- ing to eigenvalues λ1,λ2,... ,λn,t h e nw i t h Q, the matrix with columns u1...u n,w eh a v e AQ=QD where D= λ 1 λ2s ... s λn . Therefore Q−1AQ=D. We have thus established the Theorem 3.5.3. LetA∈Mn.T h e n Ais diagonalizable if and only if A hasnlinearly independent eigenvectors. As a practical measure, the conditions of this theorem are remarkably difficult to verify. Example 3.5.1. The matrix A=[01 00]i snotdiagonalizable. Solution. F i r s tw en o t et h a tt h es p e c t r u m σ(A)={0}.S o l v i n g Ax=0 we see that x=c(1,0)Tis the only solution. That is to say, there are not twolinearly independent eigenvectors. hence the result. 3.5. SIMILARITY 127 Corollary 3.5.3. IfA∈Mnis diagonalizable and Bis similar to A,t h e n Bis diagonalizable. Proof. The proof follows directly from transitivity of similarity. However, more directly, suppose that B∼AandSis the invertible matrix such that B=SAS−1Then BS=SA.I fuis an eigenvector of Awith eigenvalue λ, then SAu =λSuand therefore BSu =λSu. This is valid for each eigenvec- tor. We see that if u1,...,u nare the eigenvalues of A,t h e n Su1,...,Su n are the eigenvalues of B. The similarity matrix converts the eigenvectors of one matrix to the eigenvectors of the transformed matrix. In light of these remarks, we see that similarity transforms preserve com-pletely the dimension of eigenspaces. It is just as signi ficant to note that if a similarity transformation diagonalizes a given matrix A,t h es i m i l a r i t y matrix must consist of the eigenvectors of A. Corollary 3.5.4. LetA∈M nbe nonzero and nilpotent. Then Ais not diagonalizable. Proof. Suppose A∼T,w h e r e Tis triangular. Since Ais nilpotent (i.e.( Am= 0),Tis nilpotent, as well. Therefore the diagonal entries of Tare zero. The spectrum of Tand hence Ais zero, it’s null space has dimension n.T h e r e - fore, by Theorem 2.3.3(f), its rank is zero. Therefore T= 0, and hence A= 0. The result is proved. Alternatively, if the nilpotent matrix Ais similar to a diagonal matrix with zero diagonal entries, then Ai ss i m i l a rt ot h ez e r om a t r i x . T h u s Ais itself the zero matrix. From the obvious fact that the power of a similarity trans- formations is the similarity transformation of the power of a matrix, that is(SAS −1)m=SAmS−1(see Exercise 26), we have Corollary 3.5.5. Suppose A∈Mn(C)is diagonalizable. (i) Then Amis diagonalizable for every positive integer m. (ii) If p(·)is any polynomial, then p(A)is diagonalizable. Corollary 3.5.6. If all the eigenvalues of A∈Mn(C)are distinct, then A is diagonalizable. Proposition 3.5.1. LetA∈Mn(C)andε>0. Then for any matrix norm ,·,there is a matrix Bwith norm ,B,<εfor which A+Bis diagonalizable and for each λ∈σ(A)there is a µ∈σ(B)for which |λ−µ|<ε. 128 CHAPTER 3. EIGENVALUES AND EIGENVECTORS Proof. First triangularize AtoTby a similarity transformation, T=SAS−1. Now add to Tany diagonal matrix Dso that the resulting triangular ma- trixT+Dhas all distinct values. Moreover this can be accomplished by a diagonal matrix of arbitrarily small norm for any matrix norm. Then wehave S −1(T+D)S=S−1TS+S−1DS =A+B where B:=S−1DS. Now by the submultiplicative property of matrix norms ,B,≤EES−1DSEE≤EES−1EE,D,,S,. Thus to obtain the estimate ,B,<ε, it is sufficient to take ,D,≤6 ,S−1,,S,, which is possible as established above. Since the spectrum σ(A+B)o fA+Bhasndistinct values, it follows that A+Bis diagonalizable. There are many, many results on diagonalizable and non-diagonalizable ma- trices. Here is an interesting class o f nondiagonalizable matrices we will encounter later. Proposition 3.5.2. pro Every matrix of the form A=λI+N where Nis nilpotent and is not zero is not diagonalizable. An important subclass has the form: A= λ1 λ1s λ1 s...1 λ “Jordan block”. Eigenvectors Once an eigenvalue is determined, it is a relatively simple matter to find the pertaining eigenvectors. Just solve the homogeneous system ( λI−A)x=0 . Eigenvectors have a more complex structure and their study merits ourattention. Facts (1)σ(A)=σ(A T) including mutliplicities. 3.5. SIMILARITY 129 (2)σ(A)=σ(A∗), including multiplicities. Proof. det(λI−A)=d e t ( ( λI−A)T)=d e t (λI−AT). Similarly for A∗. Definition 3.5.3. The linear space spanned by all the eigenvectors per- taining to an eigenvalue λis called the eigenspace corresponding to the eigenvalue λ. For any A∈Mnany subspace V∈Cnfor which AV⊂V is called an invariant subspace ofA. The determination of invariant sub- spaces for linear transformations has been an important question for decades. Example 3.5.2. For any upper triangular matrix Tthe spaces Vj=S(e1,e2,... ,e j), j=1,... ,n are invariant. Example 3.5.3. Given A∈Mn, with eigenvalue λ. The eigenspace cor- responding to λand all of its subspaces are invariant subspaces. Corollary to this, the null space N(A)= {x|Ax=0}is an invariant subspace of A corresponding to the eigenvalue λ=0 . Definition 3.5.4. LetA∈Mnwith eigenvalue λ. The dimension of the eigenspace corresponding to λis called the geometric multiplicity ofλ.T h e multiplicity of λas a zero of the characteristic polynomial pA(λ)i sc a l l e d thealgebraic multiplicity . Theorem 3.5.4. IfA∈Mnandλ0is an eigenvalue of Awith geometric and algebraic multiplicities mgandma, respectively. Then mg≤ma. Proof. Letu1...u mgbe linearly independent eigenvectors pertaining to λ0. LetSbe a matrix consisting of a basis of Cnwith u1...u mgselected among them and placed in the firstmgcolumns. Then B=S−1AS= λ0I...∗............ 0...B  where I=Img. It is easy to see that pB(λ)=pA(λ)=(λ−λ0)mgp0B(λ), whence the algebraic multiplicity ma≥mg. 130 CHAPTER 3. EIGENVALUES AND EIGENVECTORS Example 3.5.4. ForA=[01 00], the algebraic multiplicity of ais 2, while the geometric multiplicity of 0 is 1. Hence, the equality mg=mais not possible, in general. Theorem 3.5.5. IfA∈Mnand for each eigenvalue µ∈σ(A),mg(µ)= ma(µ),t h e n Ais diagonalizable. The converse is also true. Proof. Extend the argument given in the theorem just above. Alternatively, we can see that Amust have nlinearly independent eigenvalues, which follows from the Lemma 3.5.1. IfA∈MnandµW=λare eigenvalues with eigenspaces Eµ andEλrespectively. Then EµandEλare linearly independent. Proof. Suppose u∈Eµc a nb ee x p r e s s e da s u=k3 cjvj where, of course uW=0a n d vjW=0,j=1,... ,k where v1...v k∈Eλ.T h e n Au=AΣcjvj ⇒ µu=λΣcjvj ⇒ u=λ µΣcjvj,ifµW=0. Sinceλ/µW= 1, we have a contradiction. If µ=0 ,t h e n Σcjvj=0a n dt h i s implies u= 0. In either case we have a contradiction, the result is therefore proved. While both AandAThave the same eigenvalues, counted even with multiplicities, the eigenspaces can be very much di fferent. Consider the example where A=}11 02] and AT=}10 12] . The eigenvalue λ= 1 has eigenvector u=[1 0]f o rAandJ1 −1o forAT. A new concept of left eigenvector yield some interesting results. Definition 3.5.5. We sayλis aleft eigenvector ofA∈Mnif there is a vector y∈Cnfor which y∗A=λy∗ 3.6. EQUIVALENT NORMS AND CONVERGENT MATRICES 131 or inRnifyTA=λyT. Taking adjoints the two sides of this equality become (y∗A)∗=A∗y (λy∗)∗=¯λy. Putting these lines together A∗y=¯λyand hence ¯λis an eigenvalue of A∗. Here’s the big result. Theorem 3.5.6. LetA∈Mn(C)with eigenvalues λand eigenvector u. Letu, v be left eigenvectors pertaining to µ,λ, respectively. If µW=λ,v∗u= u, vX=0. Proof. We have v∗u=1 µv∗Aµ=λ µv∗u. Assuming µW= 0 we have a contradiction. If µ=0 ,a r g u ea s v∗u=1 λv∗Au= µ λc∗u= 0, which was to be proved. The result is proved. Note that left eigenvectors of Aare (right) eigenvectors of A∗(ATin the real case). 3.6 Equivalent norms and convergent matrices Equivalent norms S of a rw eh a v ed e fined a number of di fferent norms. Just what “di fferent” m e a n si ss u b j e c tt od i fferent interpretations. For example, we might agree that different means that the two norms have a di fferent value for some matrix A. On the other hand if we have two matrix norms ,·,aand,·,b, we might be prepared to say that if for two positive constants mM > 0 0<m≤,A,a ,A,b≤M for all A∈Mn(F) then these norms are not really so di fferent but rather are equivalent be- cause “small” in one norm implies “small” in the other and the same for“large.” Indeed, when two norms satisfy the condition above we will callthem equivalent. The remarkable fact is that all subordinate norms on afinite dimensional space are equivalent. This is a direct consequence of the similar result for vector norms. We state it below but leave the details of the proof to the reader. 132 CHAPTER 3. EIGENVALUES AND EIGENVECTORS Theorem 3.6.1. Any two matrix norms, ,·,aand,·,b,o n Mn(C)are equivalent in the sense that ther e exist two positive constants mM > 0 0<m≤,A,a ,A,b≤M for all A∈Mn(F) We have already proved one convergence result about the invertibility of I−Awhen,A,<1. A deeper version of this result can be proved based on a new matrix norm. This result has important consequences in general matrix theory and particularly in com putational matrix theory. It is most important in applications, where having ρ(A)<1 can yield the same results as having ,A,<1. Lemma 3.6.1. Let,·,be a matrix norm that is subordinate to the vector norm (on Cn),·,. Then for each A∈Mn ρ(A)≤,A,. Note: We use the same notation for both vector and matrix norms. Proof. Letλ∈σ(A). Then with corresponding eigenvector xλwe have Axλ=λxλ.N o r m a l i z i n g xλso that,xλ,=1 ,w eh a v e ,A,=m a x ,x,=1,Ax,≥ ,Axλ,=|λ|,xλ,=|λ|.H e n c e ,A,≥ max λ∈σ(A)|λ|=ρ(A). Theorem 3.6.2. For each A∈Mnandε>0there is a vector norm ,·, onCnfor which the subordinate matrix norm ,·,satisfies ρ(A)≤,A,≤ρ(A)+ε. Proof. The proof follows in a series of simple steps, the first of which is interesting in its own right. First we know that Ais similar to a triangular matrix B–from a previous theorem B=SAS−1=Λ+U whereΛis the diagonal part of BandUis strictly upper triangular part of B,w i t hz e r o s filled in elsewhere. 3.6. EQUIVALENT NORMS AND CONVERGENT MATRICES 133 Note that the diagonal of Bisthe spectrum of Band hence that of A. This is important. Now select a δ>0 and form the diagonal matrix D= 1 δ−1s ... s δ1−n . A brief computation reveals that C=DBD−1=DSAS−1D−1 =D(Λ+U)D−1 =Λ+DUD−1=Λ+V where V=DUD−1and more speci fically vij=δj−iuijforj>i and of courseΛis a diagonal matrix with the spectrum of Afor the diagonal ele- ments. In this way we see that for δsmall enough we have arranged that Ais similar to the diagonal matrix of its spectral elements plus a small triangular perturbation. We now de fine the new vector norm on Cnby ,x,A=(DS)∗(DS)x, xX1/2. We recognise this to be a norm from a previous result. Now compute the matrix norm ,A,A=m a x ,x,A=1,Ax,A. Thus ,Ax,2 A=DSAx,DSAx X =CDSx,CDSx X ≤,C,2 2,DSx,2 =,C∗C,2,x,2 A. From C=Λ+V, it follows that C∗C=Λ∗Λ+Λ∗V+V∗Λ+V∗V. Because the last three terms have a δpmultiplier for various positive powers p,w ec a nm a k et h et e r m s Λ∗V+V∗Λ+V∗Vsmall in anynorm by taking δsufficiently small. Also the diagonal elements of Λ∗Λhave the form |λi|2λi∈S(A). 134 CHAPTER 3. EIGENVALUES AND EIGENVECTORS Talkingδsufficiently small so that each of ,Λ∗V,2,,V∗Λ,2and,V∗V,2is less than 6/3. With ,x,2 A=1a sr e q u i r e d ,w eh a v e ,Ax,A≤(ρ(A)+ε),x,A and we know already that ,A,A≥ρ(A). An important corollary places a lower bound on vector norms is given below. Corollary 3.6.1. For any A∈Mn ρ(A)= i n f ,,(m a x ,x,=1,Ax,) where the in fimum is taken over all vector norms. Convergent matrices Definition 3.6.1. We say that a matrix A∈Mn(F)f o r F=RorCis convergent if lim m→∞Am=0 ←the zero matrix. That is, for each 1 ≤i, j≤nthelimm→∞(Am)ij=0 . T h i si ss o m e t i m e s called pointwise convergence. Theorem 3.6.3. The following three statements are equivalent: (a)Ais convergent. (b) lim n→∞,Am,=0,f o rs o m em a t r i xn o r m . (c)ρ(A)<1. Proof. These results follow substantially from previously proven results. However, for completeness, assume (a) holds. Then lim n→∞max ij|(An)ij|=0 or what is the same we have lim n→∞,An,∞=0 3.6. EQUIVALENT NORMS AND CONVERGENT MATRICES 135 which is (b). Now suppose that (b) holds. If ρ(A)≥1t h e r ei sav e c t o r xfor which ,Anx,=,ρ(A),n,x,.T h e r e f o r e ,An,≥1, which contradicts (b). Thus (c) holds. Next if (c) holds we can apply the above theorem toestablish that there is a norm for which ,A,<1. Hence (b) follows. Finally, we know that ,A m,∞≤M,Am, (T) whence lim n→∞Am=0 . ( T h a ti s( a ) ≡(b)). In sum we have shown that (a) ≡(b) and (b) ≡(c). To establish ( T)w en e e dt h ef o l l o w i n g . Theorem 3.6.4. If,, and,·,Iare two vector norms on Cnthen there are constants mandMso that m,x,I≤,x,<M,x,I for all x∈Cn. This result carries over to matrix norms subordinate to vector norms by simple inheritance. To prove this result we use compactness ideas. Supposethere is a sequence of vectors x jfor which 1≤,xj,<1 j,xj,I and for which the components of xjare bounded in modulus. By compact- ness there is a convergent subsequence of the xj,f o rw h i c hl i m xj=xW=0 . But,x,I<∞. Hence,x,= 0, a contradiction. Here is the new and improved version of our previous result. Theorem 3.6.5. Ifρ(A)<1then (I−A)−1exists and (I−A)−1=I+A+A2+···. Proof. Select a matrix norm ,·,for which ,A,<1. Apply previous calcu- lations. We know that every matrix can be triangularized and “almost” di- agonalized we may ask if we can eliminate altogether the o ff-diagonal terms. The answer is unfortunately no. But we can resolve the diagonal question completely. 136 CHAPTER 3. EIGENVALUES AND EIGENVECTORS 3.7 Exercises 1. Suppose that U∈Mnis orthogonal and let ,·,be a matrix norm. Show that ,U,≥1. 2. In two dimensions the counter-clockwise rotations through the angle θare given by Bθ=}cosθ−sinθ sinθcosθ] Find the eigenvalues and eigenvectors for all θ. (Note the two special cases,θis not equal to an even multiple of πandθ=0 . 3. Given two matrices A, B∈Mn(C). De fine the commutant ofAand Bby [A, B]−AB−BA. Prove that tr[ A, B]=0 . 4. Given two finite sequences {ck}n k=1and{dk}n k=1.Prove that k|ckdk|≤ max k|dk| k|ck|. 5. Verify that a matrix norm which is subordinate to a vector norm sat- isfies norm conditions (i) and (ii). 6. Let A∈Mn(C).Show that the matrix norm subordinate to the vector norm ,·,∞is given by ,A,∞=m a x i,ri(A),1 where as usual ri(A)d e n o t e st h e ithrow of the matrix Aand,·,1is thef1norm. 7. The Hilbert matrix, Hnof order nis defined by hij=1 i+j−11≤i, j≤n 8. Show that ,Hn,1<lnn. 9. Show that ,Hn,∞=1 . 10. Show that ,Hn,2∼n1 2. 11. Show that the spectral radius of Hnis bounded by 1. 12. Show that for each ε>0 there exists an integer Nsuch that if n>N there is a vector x∈Rnwith,x,2=1 such that ,Hnx,2<ε. 3.7. EXERCISES 137 13. Same as the previous question except that you need to show that N=! 1 ε1/2 +1w i l lw o r k . 14. Show that the matrix A= 110 031 1−12 is not diagonalizable.Let A∈Mn(C). 15. We know that the characteristic polynomial of a matrix A∈M12(C) is equal to pA(λ)=(λ−1)12−1.Show that Ais not similar to the identity matrix. 16. We know that the spectrum of A∈M3(C)i sσ(A)={1,1,−2}and the corresponding eigenvectors are {[1,2,1]T,[2,1,−1]T,[1,1,2]T}. (i) Is it possible to determine A? Why or why not? If so, prove it. If not show two di fferent matrices with the given spectrum and eigenvectors. (ii) Is Adiagonalizable? 17. Prove that if A∈Mn(C) is diagonalizable then for each λ∈σ(A), the algebraic and geometric multiplicities are equal. That is, ma(λ)= mg(λ). 18. Show that B−1(λ)e x i s t sf o r |λ|sufficiently large. 19. We say that a matrix A∈Mn(R) is row stochastic if all its entries are non negative and the sum of the entries of each row is one. (i) Prove that 1 ∈σ(A). (ii) Prove that ρ(A)=1 . 20. We say that A, B∈Mn(C)a r e quasi -commutative if the spectrum of AB−BAis just zero, i.e. σ(AB−BA)={0}. 21. Prove that if ABis nilpotent then so is BA. 22. A matrix A∈Mn(C) has a square root if there is a matrix B∈Mn(C) such that B2=A.Show that if Ais diagonalizable then it has a square root. 23. Prove that every matrix that commutes with every diagonal matrix is itself diagonal. 138 CHAPTER 3. EIGENVALUES AND EIGENVECTORS 24. Suppose that if A∈Mn(C) is diagonalizable and for each λ∈σ(A), |λ|<1.Prove directly from similarity ideas that lim n→∞An= 0.(That is, do not apply the more general theorem from the lecture notes.) 25. We say that Aisright quasi- invertible if there exists a matrix B∈ Mn(C) such that AB∼D,w h e r e Dis a diagonal matrix with diagonal entries nonzero. Similarly, we say that Aisleft quasi- invertible if there exists a matrix B∈Mn(C) such that BA∼D,w h e r e Dis a diagonal matrix with diagonal entries nonzero. (i) Show that if Aisright quasi- invertible then it is invertible. (ii) Show that if Aisright quasi- invertible then it is left quasi- invertible. (iii) Prove that quasi- invertibility is not an equivalence relation. (Hint. How do we usually show that an assertion is false?) 26. Suppose that A, S∈Mn,w i t h Sinvertible, and mis a positive integer. Show that ( SAS−1)m=SAmS−1. 27. Consider the rotation  10 0 0c o sθ−sinθ 0s i nθcosθ  Show that the eigenvalues are the same as for the rotation  cosθ0−sinθ 01 0 sinθ0c o sθ  See Example 2 of section 3.2. 28. Let A∈Mn(C). De fineeA=∞ n=0An n!. (i) Prove that exists. (ii) Suppose that A, B∈Mn(C). Is eA+B=eAeB?I f n o t , w h e n i s i t true? 29. Suppose that A, B∈Mn(C). We say A`Bif [A, B]=0 ,w h e r e [·,·] is the commutant. Prove or disprove that “ `” is an equivalence relation. Answer the same question in the case of quasi-commutivity.(See Exercise 20 30. Let u, v∈C n.Find ( I+uv∗)m. 3.8. APPENDIX A 139 31. De fine the function fonMm×n(C)b y f(A)=r a n k A, and suppose that,·,is any matrix norm. Prove the following. (1) If for any matrix Afor which f(A)=nshow that fis continuous in ,·,.T h a t is, for every ε>0t h e n f(B)=nfor every matrix Bwith,BA,<ε. is continuous in an ε-neighborhood of A.T h a t i s , f o r a n y Bwith ,A−B,<ε,t h e n f(B)=f(A). (This deviates slightly from the usual de finition of continuity because the function fis integer valued.) (2) If f(A)<n,t h e n fis not continuous in every ε-neighborhood of A. 3.8 Appendix A It is desired to solve the equation p(λ)=0f o rc o e fficients in p0,...,p n∈C orR. The basic theorem on this subject is called the Fundamental Theo- rem of Algebra (FTA), whose importance is manifest by its hundreds ofapplications. Concommitant with the FTA is the notion of reducible andirreducible factors. Theorem 3.8.1 (Theorem Fundamental Theorem of Algebra). Given any polynomial p(λ)=p 0λn+p1λn−1+···+pnwith coefficients in p0,...,p n∈ C. There is at least one solution λ∈Cto the equation p(λ)=0 . Though proving this result would take us too far a field of our subject, we remarks that the simplest proof of this result no doubt comes as a di-rect application of Liouville’s Theorem, a result in complex analysis. As a corollary to the FTA, we have that there are exactly nsolutions to p(λ)=0 when counted with multiplicitiy. Proved originally by Gauss, the proof ofthis theorem eluded mathematicians for many years. Let us assume thatp 0= 1 to make the factorization simpler to write. Thus p(λ)=k i=1(λ−λi)mi(4) . As we know, in the case that the coe fficients p0,...,p nare real, there may be complex solutions. As is easy to prove, complex solutions must come in complex conjugate pairs. For if λ=r+isis a solution p(r+is)=(r+is)n+p1(r+is)n−1+···pn−1(r+is)+pn=0 Because the coe fficients are real, the real and imaginary parts of the powers (r+is)jremain respectively real or imaginary upon multiplication by pj. 140 CHAPTER 3. EIGENVALUES AND EIGENVECTORS Thus p(r+is)=R e ( r+is)n+p1Re (r+is)n−1+···pn−1Re (r+is)+pn +ip Im (r+is)n+p1Im (r+is)n−1+···pn−1Im (r+is)+pnQ =0 Hence the real and imaginary parts are each zero. Since Re ( r−is)j= Re (r+is)jand Im ( r−is)j=−Im (r+is)jit follows that p(r−is)=0 . In the case that the coe fficients are real it may be of interest to note what statement of factorization analogous to (4) above. To this end we need the de finition Definition 3.8.1. The real polynomial x2+bx+cis called irreducible if it has no real zeros. In general, any polynomial that cannot be factored over the underlying field is called irreducible. Irreducible polynomials have played a very impor- tant role in fields such as abstract algebra and number theory. Indeed, they were central in early attempts to prove Fermat’s last theorem and also so but more indirectly to the acutal proof. Our attention here is restricted to thefieldsCandR. Theorem 3.8.2. Letp(λ)=λn+p1λn−1+···+pnwith coefficients in p0,...,p n∈R.T h e n p(λ)can be factored as a product of linear factors pertaining to real zeros of p(λ)=0 and irreducible quadratic factors. Proof. The proof is an easy application of the FTA and the observation above. If λk=r+isis a zero of p(λ), then so also is ¯λk=r−is.T h e r e f o r e the product ( λ−λk)D λ−¯λki =λ2−2λr+r2+s2is an irreducible quadratic. Combine such terms with the linear factors generated from the real zeros,and use (4). Remark 3.8.1. It is worth noting that there are nohigher order irreducible factors with real coe fficients. Even though there are certainly higher order polynomials with complex roots, they can always factored as products of either real linear or real quadratic f actors. Proving this without the FTA may prove challenging. 3.9. APPENDIX B 141 3.9 Appendix B 3.9.1 In finite Series Definition 3.9.1. Aninfiniteseries, denoted by a0+a1+a2+··· is a sequence {un},w h e r e unis defined by un=a0+a1+···+an If the sequence {un}converges to some limit A,w es a yt h a tt h ei n finite series converges to Aand use the notation a0+a1+a2+···=A We also say that the sum of the in finite series is A.I f {un}diverges, the infinite series a0+a1+a2+···is said to be divergent. The sequence {un}is called the sequence ofpartial sums, and the se- quence {an}is called the sequence ofterms of the in finite series a0+a1+ a2+···. Let us now return to the formula 1+r+r2+···+rn=1−rn+1 1−r where rW= 1. Since the sequence {rn+1}converges (and, in fact, to 0) if and only if−1<r< 1( o r |r|<1),rbeing different from 1, the in finite series 1+r+r2+··· converges to (1 −r)−1if and only if |r|<1. This in finite series is called the geometric series with ratio r. Definition 3.9.2. Geometric Series with Ratio r 1+r+r2+···=1 1−r,if|r|<1 and diverges if |r|≥1. Multiplying both sides by ryields the following. 142 CHAPTER 3. EIGENVALUES AND EIGENVECTORS Definition 3.9.3. If|r|<1, then r+r2+r3+···=r 1−r Example 3.9.1. Investigate the convergence of each of the following in fi- nite series. If it converges, determine its limit (sum).a. 1− 1 2+1 4−1 8+··· b. 1 +2 3+4 9+8 27+··· c.3 4+9 16+27 64+··· Solution A careful study reveals that each in finite series is a geometric series. In fact, the ratios are, respectively, (a) −1 2,( b )2 3,a n d( c )3 4.S i n c e they are all of absolute value less than 1, they all converge. In fact, we have:a. 1− 1 2+1 4−1 8+···=1 1−(−1 2)=2 3 b. 1 +2 3+4 9+8 27+···=1 1−2 3=3 1=3 c.3 4+9 16+27 64+···=3 4 1−3 4=3 4·4 1=3 Since an in finite series is de fined as a sequence of partial sums, the prop- erties of sequences carry over to in finite series. The following two properties are especially important. 1. Uniqueness of Limit Ifa0+a1+a2+···converges, then it converges to a unique limit. This property explains the notation a0+a1+a2+···=A where Ais the limit of the in finite series. Because of this notation, we often say that the in finite series sums to A,o rt h e sum oftheinfinitely many terms a0,a1,a2,... isA. We remark, however, that the order of the terms cannot be changed arbitrarily in general. Definition 3.9.4. 2. Sum of In finite Series If a0+a1+a2+···=Aandb0+b1+b2+···=B,t h e n (a0+b0)+(a1+b1)+(a2+b2)+··· =(a0+a1+a2+···) +(b0+b1+b2+···) =A+B This property follows from the observation that (a0+b0)+(a1+b1)+···+(an+bn)=( a0+a1+···+an) +(b0+b1+···+bn) converges to A+B. Another property is 3.9. APPENDIX B 143 Definition 3.9.5. 3. Constant Multiple of In finite Series Ifa0+a1+ a2+···=Aandcis a constant, then ca0+ca1+ca2+···=cA Example 3.9.2. Determine the sums of the following convergent in finite series.a. 5 3·2+13 9·4+35 27·8+··· b.1 3·2+1 9·2+1 27·2+· Solution a. By the Sum Property, the sum of the first in finite series is w1 3+1 2W +w1 9+1 4W +w1 27+1 8W +··· =w1 3+1 9+1 27+···W +w1 2+1 4+1 8+···W =1 3 1−1 3+1 2 1−1 2=1 2+1=3 2 b. By the Constant-Multiple Property, the sum of the second in finite series is 1 2w1 3+1 9+1 27+···W =1 2·1 3 1−1 3=1 2·1 2=1 4 Another type of in finite series can be illustrated by using Taylor poly- nomial extrapolation as follows. Example 3.9.3. In extrapolating the value of ln 2, the nth-degree Taylor polynomial Pn(x)o fl n ( 1+ x)a tx= 0 was evaluated at x=1i nE x a m p l e 4 of Section 12.3. Interpret ln 2 as the sum of an in finite series whose nth partial sum is Pn(1). Solution We have seen in Example 3 of Section 12.3 that Pn(x)=x−1 2x2+1 3x3−···+(−1)n−11 nxn so that Pn(1) = 1−1 2+1 3−···+(−1)n−11 n,a n di ti st h e nth partial sum of the in finite series 1−1 2+1 3−1 4+··· Since {Pn(1)}converges to ln 2 (see Example 4in Section 12.3), we have ln 2 = 1−1 2+1 3−1 4−··· 144 CHAPTER 3. EIGENVALUES AND EIGENVECTORS It should be noted that the terms of the in finite series in the preceding example alternate in sign. In general, an in finite series of this type always converges. Alternating Series Test Leta0≥a1≥···≥0. If anap- proaches 0, then the in finite series a0−a1+a2−a3+··· converges to some limit A,w h e r e0 <A<a 0. The condition that the term antends to zero is essential in the above Alternating Series Test. In fact, if the terms do not tend to zero, the corre-sponding in finite series, alternating or not, must diverge. Divergence Test Ifa ndoes not approach zero as n→+∞, then the in finite series a0+a1+a2+··· diverges. Example 3.9.4. Determine the convergence or divergence of the following infinite series. a. 1−1 3+1 5−1 7+··· b.−2 3+4 5−6 7+··· Solution a. This series is an alternating series with 1>1 3>1 5>···>0 and with the terms approaching 0. In fact, the general ( nth) term is (−1)n1 2n+1 Hence, by the Alternating Series Test, the in finite series 1 −1 3+1 5−1 7+··· converges. b. Let a1=−2 3,a2=4 5,a3=−6 7,... . It is clear that andoes not approach 0, and it follows from the Divergence Test that the in finite series is divergent. [The nth term is ( −1)n2n/(2n+ 1).] Note, however, that the terms do alternate in sign. 3.9. APPENDIX B 145 Another useful tool for testing convergence or divergence of an in finite series is the Ratio Test, to be discussed below. Recall that the geometric series 1+r+r2+··· where the nth term is an=rn,c o n v e r g e si f |r|<1 and diverges otherwise. Note also that the ratio of two consecutive terms is an+1 an=rn+1 rn=r Hence, the geometric series converges if and only if this ratio is of absolute value less than 1. In general, it is possible to draw a similar conclusion if thesequence of the absolute values of the ratios of consecutive terms converges. Ratio Test Suppose that the sequence {|a n+1|/|an|} converges to some limit R. Then, the in finite series a0+a1+ a2+···converges if R< 1 and diverges if R> 1. Example 3.9.5. In each of the following, determine all values of rfor which the in finite series converges. a. 1 + r+r2 2!+r3 3!+··· b. 1 + 2 r+3r3+4r3+··· Solution a. The nth term is an=rn/n!, so that an+1 an=rn+1 (n+1 ) !·n! rn=r n+1 For each value of r,w eh a v e |an+1| |an|=1 n+1|r|→0<1 Hence, by the Ratio Test, the in finite series converges for all values of r. b. Let an=(n+1 )rn. Then, |an+1| |an|=(n+2 )|r|n+1 (n+1 )|r|n=n+2 n+1|r|→|r| Hence, the Ratio Test says that the in finite series converges if |r|<1a n d diverges if |r|>1. For |r|=1 ,w eh a v e |an|=n+1, which does not converge to 0, so that the corresponding in finite series must be divergent as a result of applying the Divergence Test. Sometimes it is possible to compare the partial sums of an in finite series with certain integrals, as illustrated in the following example. 146 CHAPTER 3. EIGENVALUES AND EIGENVECTORS Example 3.9.6. Show that 1+1 2+···+1/nis larger than the de fine integral$n+1 1dx/x , and conclude that the in finite series 1 +1 2+1 3+···diverges. Solution Consider the function f(x)=1 /x. Then, the de finite integral 8n+1 1dx x=l n ( n+1 )−ln 1 = ln( n+1 ) is the area under the graph of the function y=f(x) between x=1a n d x=n+ 1. On the other hand, the sum 1+1 2+···+1 n=[f(1) + f(2) + ···+f(n)]∆x where∆x= 1, is the sum of the areas of nrectangles with base ∆x=1a n d heights f(1),... ,f (n), consecutively, as shown in Figure 12.5. Since the union of these rectangles covers the region bounded by the curve y=f(x), thex-axis, and the vertical lines x=1a n d x=n+1 ,w eh a v e : 1+1 2+···+1 n>8n+1 1dx x=l n ( n+1 ) Now recall that ln( n+ 1) approaches ∞asnapproaches ∞. Hence, the sequence of partial sums of the in finite series 1+1 2+1 3+··· must be divergent. The above in finite series is called the harmonic series. It diverges “to infinity” in the sense that its sequence of partial sums becomes arbitrarily large for all large values of n.I f a n i n finite series diverges to in finity, we also say that it sums toinfinity and use the notation “= ∞” accordingly. We have TheHarmonic Series is defined by 1+1 2+1 3+···=∞