Transcript

okay so we start this is the second lecture on eigenvalues so the first lecture was that reached the key equation ax equal lambda X X is the eigenvector and lambdas the eigenvalue now to use that and the the good way to after we found so so job one is to find the eigenvalues and find the eigenvectors now after we found them what do we do with them well the good way to see that is diagonalize the matrix so the matrix is a and I want to show first of all this is like the basic fact this this formula that's that's the key to today's lecture this matrix a I put its eigenvectors in the columns of a matrix s so s will be the eigenvector matrix and i want to look at this magic combination s inverse a s so can i show you how that how that what happens there and notice notice there's an S inverse we have to be able to invert this eigenvector matrix s so for that we need n independent eigenvectors so that's the that's the case okay so suppose we have n linearly independent eigen vectors of a put them in the columns of this matrix s so I'm naturally going to call that the eigenvector matrix because it's got the eigenvectors in its columns and all i want to do is show you what happens when you multiply a times s so a times s so this is a times the matrix with the first eigenvector in this first column the second eigenvector in its second column the nth eigen vector in its nth column and how am I going to do this matrix multiplication well certainly I'll do it a column at a time and what do I get a times the first column gives me the first column of the answer but what is it that's an eigenvector a times x1 is equal to the lambda times the x 1 and that lambdas we'll call lambda 1 of course so that's the first column ax 1 is the same as lambda 1 X 1 IX 2 is lambda 2 X 2 so on along to in the nth column we now have lambda n xn looking good but the next step is even better so for the next step I want to separate out those eigenvalues those those multiplying numbers from the X's so then I'll have just what I want okay so how am I going to separate out so that that number lambda 1 is multiplying the first column so if I want to factor it out of the first column I better put here is going to be X 1 and that's going to multiply this matrix lambda 1 in the first entry in all zeros you see that that that's going to come out right for the first column because we remember how we're going back to that original punchline that if I want a number to multiply X 1 then I can do it by putting X 1 in that column in the first column and putting that number there what am I going to have here I'm going to have lambda what I'm going to have X 1 X 2 xn these are going to be my columns again I'm getting s back again I'm getting s back again but now what's it x on the right its x if I want if I want lambda n xn in the last column how do I do it well the last column here will be I'll take the last column use these coefficients put the lambda end down there and it will multiply that nth column and give me lambda n xn there there you see matrix multiplication just working for us so I started with a s I wrote down what it meant a times each eigenvector that gave me lambda times the eigenvector and then when I peeled off the lambdas they were on the right-hand side so I've got s my matrix back again and this matrix this diagonal matrix the eigen value matrix and I call it capital lambda using capital letters for matrices and lambda to prompt me that it's that it's eigen values that are in there so you see that the eigenvalues are just sitting down that diagonal if I had a column x2 here I would want the lambda 2 in the two tube position in the diagonal position to multiply that X 2 and give me the lambda 2 X 2 that's my formula a s is s lambda okay that's that's the you see it's just a calculation now I mentioned and I have to mention again this business about an independent eigenvectors as it stands this is all fine whether I mean I could be repeating the same eigenvector but I am no interest in that I want to be able to invert s and that's where this comes in this n independent eigenvectors business comes in to tell me that that matrix is invertible so let me on the next board write down what I've got a s equals s lambda and now I can multiply on the left by s inverse so this is really I can do that provided s is invertible provided my assumption of n independent eigenvectors is satisfied and i mentioned at the end of last time and i'll say again that there's a small number of matrices for that don't have n independent eigenvectors so i've got to discuss that that technical point but the great the most matrices that we see have end n independent eigenvectors and we can diagonalize this is diagonalization i could also write it and I often will the other way round if I multiply on the right by s inverse if I took this equation at the top and multiply on the right by s inverse I could I would have a left here now s inverse is coming from the right so can you keep those two straight a multiplies its eigenvectors that's how i keep them straight so a multiplies s a multiplies this and then this s inverse makes the whole thing diagonal and this is another way of saying the same thing putting the S is on the other side of the equation vision a is s lambda s inverse so that's the that's the new factorization that's the replacement for Lu from elimination or QR from gram-schmidt and notice that the matrix so it's it's a matrix times the diagonal matrix times the inverse of the first one it's is that's the combination that we'll see throughout this chapter this this combination with an S and an S inverse okay can I just begin to use that for example what about a squared what are the eigenvalues and eigenvectors of a squared that's a straightforward question with it with an absolutely clean answer so let me let me consider a squared so I start with ax equal lambda X and I'm headed for a squared so let me multiply both sides by a that's one way to get a squared on the left so if I should write these ifs in here if ax equals lambda X then I multiply by a so I get a squared x equals while I'm multiplying by a so that's lambda a X that lambda was a number so I just put it on the left and what do I did tell me how to make that look better what have I got here for if a has the eigenvalue lambda and eigenvector x what's up with a squared a squared X I just multiplied by a but now for a X I'm going to substitute lambda X so I've got lambda squared X so from that simple calculation I my conclusion is that the eigenvalues of a squared are lambda squared and the eigenvectors i always think about both of those what can i say about the eigenvalues they're squared what can I say about the eigenvectors they're the same the same X is in s for a now let me see that also from this formula how can I see what a squared is looking like from this formula so let me that was one way to do it let me do it by just taking a squared from that a squared is s lambda s inverse that's a times s lambda s inverse that's a which is this is the beauty of eigenvalues eigenvectors having that s inverse and s is the identity so i've got s lambda squared s inverse you see what that's telling me it's telling me the same thing that I just learned here but in the in a matrix form it's telling me that the S is the same the eigenvectors are the same but the eigenvalues are squared because this is what's lambda squared that's still diagonal it's got little lambda 1 squared lambda 2 squared down to lambda n squared on that diagonal those are the eigenvalues as we just learned of a squared okay so somehow those eigenvalues and eigenvectors are really giving you a way to to to see what's going on inside a matrix now of course I can continue that for to the case power a to the case power if I multiply if I have K of these together you see how s inverse s will keep canceling in the in the inside I'll have the s outside at the far left and lambda will be in there K times and s inverse so what's that telling me that's telling me that the eigenvalues of a of a to the K power are the K power the eigenvalues of a cubed are the cubes of the eigenvalues of a and the eigenvectors are the same the same okay in other words eigenvalues and eigenvectors give a great way to understand the powers of a matrix if I take this square of a matrix or the hundredth power of a matrix the pivots are all over the place Lu if I multiply lu x lu x lu x lu a hundred times i've got a hundred l use i can't do anything with them but when i multiply s lambda s inverse by itself when I look at the eigenvector picture a hundred times I get a hundred or 99 of these guys cancelling out inside and I get a to the hundredth is s lambda to the hundredth s inverse I mean eigenvalues tell you about powers of a matrix in a way that we had no no way to approach previously for example when does when do the powers of a matrix go to zero I would call that matrix stable maybe so so so I could write down a theorem I'll write it as a theorem just use that word to emphasize that here I'm getting this great fact from this eigenvalue picture okay a to the K approaches zero as K goes as K gets bigger if what what's the how can I tell for a matrix a if its powers go to zero what's somewhere inside that matrix is that information that information is not present in the pivots it's present in the eigenvalues what do I need for the to know that if I take I earn higher powers of a that this matrix gets smaller and smaller well s and s inverse are not moving so it's this guy that has to get small and that's easy too easy to understand the requirement is all eigenvalues so what is a requirement the eigenvalues have to be less than one now I have to write that absolute value because those eigenvalues could be negative they could be complex numbers so I'm taking the absolute value half if all of those are below one that's in fact we practically see why let me just say that I that I operating on one assumption here and I gotta keep remembering that that assumption is still present that assumption was that I had a full set of of n independent eigenvectors if I don't have that then I then this approach is not working so so again a pure eigenvalue approach eigenvector approach needs and independent eigenvectors if we don't have n independent eigenvectors we can't diagonalize the matrix we can't get to a diagonal matrix this this this diagonalization is only possible if s inverse makes sense okay can I can I follow up on that point now so so you see why what we get and and why we want it because we get information about the powers of a matrix just immediately from the eigenvalues okay now let me follow up on this business of which matrices are diagonalizable sorry about that long word so a matrix is sure so here's here's the main point a is sure to be to have n independent eigenvectors and and B now here comes that word diagonalizable if if so we might as well get the nice case out in the open the nice case is when if all the lambdas are different that means that means no repeated eigenvalues okay that's the nice case if my matrix and most Maitre if I do a random matrix in MATLAB and compute its eigenvalues so if I computed if I took I of ran of ten ten gave that MATLAB command the we'd get a random 10 by 10 matrix we would get a list of its ten eigenvalues and they would be different they would be distinct is the best word I would have a random matrix will have ten distinct that 10 by 10 matrix will have ten distinct eigenvalues and if it does the eigenvectors are automatically independent so that's a nice fact I could I'll refer you to the text for the proof that that a is sure to have an independent eigenvectors if the eigenvalues are different if if all the if all eigenvalues are it's just if some lambdas are repeated then I have to look more closely if an eigenvalue is repeated I have to look I have to count at the chick has it got say it's repeated three times so what's a possibility for the so it's so here's here's the repeated possibility and let me emphasize the conclusion that if I have repeated eigenvalues I may or may not I may or may not have have n independent eigenvectors I might I you know this isn't a completely negative case the identity matrix well suppose I take the ten by ten identity matrix what are the eigenvalues of that matrix so just let's take the easiest matrix the identity if I look for its eigenvalues they're all ones so that eigenvalue one is repeated ten times but there's no shortage of eigenvectors for the identity matrix in fact every vector is an eigenvector so i can take ten independent vectors oh well what happens to everything if a is the identity matrix let's just think that one through in our head if a is the identity matrix then it's got plenty of eigenvectors i choose ten independent vectors they're the columns of s and and what do i get from s inverse a s i get i again right if a is the idea and of course that's the correct lambda the matrix was already diagonal so if the matrix is already diagonal then the the lambda is the same as the matrix a diagonal matrix has got its eigenvalues sitting right there in front of you now if it's triangular the eigenvalues are still sitting there but so let's let's take a case where it's triangular suppose a is like 2 1 2 0 so there's a case that's going to be trouble there's a case that's going to be trouble first of all what are the eigen value if we start with a matrix the first thing we do will practically without thinking is compute the eigenvalues and eigenvectors okay so what are the eigenvalues you can tell me right away what they are they're two and two right it's a triangular matrix so when I do this determinant shall I do this determinant of a minus lambda I I'll get this 2 minus lambda 1 0 2 minus lambda right I take that determinant so I make those into vertical bars to mean determinant and what's the determinant to minus lambda square what are the roots lambda equal to twice so the eigenvalues are lambda equals 2 and 2 okay fine now the next step find the eigenvectors so i hope for eigenvectors and what do I find for this guy I can Victor's for this guy when I subtract 2 minus the identity so a minus 2 I as zeros here and I'm looking for the null space what's what are the eigenvectors they're there they're the null space of a minus lambda up the null space is only one dimension this is a case where I don't have enough eigenvectors my algebra simplicity is - I would say when I see when I count how often the eigenvalue is repeated that's the algebraic multiplicity that's the multiplicity how many times is it the root of the polynomial my polynomial is 2 minus lambda square it's a double root so my algebraic multiplicity is 2 but the geometric multiplicity which looks for vectors looks for eigenvectors and which means the null space of this thing and the only eigenvector is 1 0 that's in the null space 0 1 is not in the null space the null space is only one dimensional so there is a matrix my this a or the original a that are not diagonalizable I can't I can't find two independent eigenvectors there's only one okay so that's the case that I'm that's a case that I I'm not really handling for example when I wrote down up here that the powers went to 0 if the eigen guys were below 1 I didn't really handle that case of repeated eigen values because my reasoning was based on this form and this formula is based on n independent eigenvectors ok so just this just to say there are some matrices that we that we don't cover through diagonalization but the great majority we do okay and we're always okay if we have different distinct eigen oh okay that's like the typical case because for each eigen value there's at least one eigenvector the algebraic multiplicity one for every eigenvalue and the geometric multiplicity is 1 there's one eigenvector and they are independent okay okay now let me come back to the important case when when we're okay the important case when we are dying light let me look at so so so a quick let me solve this equation the equation will be each I start with some start with a given vector u0 and then my equation is that every step I multiply what I have by a I then then equation ought to be simple to handle and I'd like to be able to solve how would I find if I start with a vector you know it and I multiply by a a hundred times what if I got what I certainly write down a formula for the answer so what what so u1 is a you know and u2 is what's you to then you to I multiply u2 I get from you one by another multiplying by a so I've been a twice and my formula is you K after K steps I multiplied by a K times the original you know you see what I'm doing the next section is going to solve systems of rental equation I'm going to have derivative this this section is the nice one it's all difference equations I would call that a difference equation it's kinetic first-order I would call that a first-order system because it connects only it only goes up one level and it's a system because these are vectors and that's amazing and the solution is just that okay but that's a nice formula that's like that most compact formula I could ever get you what hundreds would be eighty to one hundred you know but how would I actually find you one hundred how would I find how would I discover what you 100 is let me let me show you how here's the idea if so to solve to really stop shall I say to really to really solve it I would take this initial vector U naught and I would write it as a combination of eigenvectors to really solve right right you not as a combination say certain amount of the first eigen vector plus is certain the second eigenvector plus a certain amount of the last time now multiply by a you want you got to see the magic of eigenvectors working multiplied by a so a you know is what so a times that a times so what I can separate it out into n separate pieces and that's the whole point that each of those pieces is going in its own merry way each of those pieces is an eigenvector and when I multiply by a what is this piece become so that's some amount of the first let's suppose the eigenvectors are normalized to be unit vectors so that says what the eigenvector is and I need some multiple of it to produce you know okay now when I multiply by a what do I get I get c1 which is just a factor times ax 1 but they X 1 is lambda 1 X 1 when I multiply this by a I get C 2 lambda 2 X 2 and here I get C n lambda n and suppose I multiply by a to the hundredth power now can we can we having done it multiplied by a let's multiply by a to the hundredth what happens to this first term when I multiply by a to the 100 it's got that factor lambda to the hundredth that's the key that that's what I mean by going its own merry way if it is pure eigenvector it's exactly in a direction where multiplication by a just brings in a scalar factor lambda one so a hundred times brings in this 100 times a hundred times lambda 200 times lambda n actually what are we seeing here we're seeing this same lambda capital lambda to the hundredth as in the as in the diagonalization and we're seeing the S matrix that matrix s of eigenvector that's what this has got this has got to amount to a lambda to the hundredth power times and s times this vector C that's telling us how much of each one is in the original thing so if I had to really find a hundredth power I would take you not I would expand it as a combination of eigenvectors this is really s the eigenvector matrix times C the coefficient vector and then I would immediately did by inserting these hundreds powers of eigenvalues I'd have the answer so the the up there must be let's see okay it's so yeah so if you 100 is one hundred times you know and you know it is SC then you see this formula is just this formula which is the way I would actually get hold of this of this you 100 which is let me put it here you 100 the way right the way I would actually get hold of that see what what the solution is after a hundred steps would be expand the initial vector into eigenvectors and up and let each eigenvector go its own way multiplying by a hundred by lambda at every step and therefore by lambda to the hundredth power after a hundred steps can I do anything so that's that's the the formulas now let me take an example I'll use the Fibonacci sequence as an example so so Fibonacci example you remember the Fibonacci numbers if we start with 1 and 1 as f naught oh I think I start with 0 that's 0 and 1 be the first so there's F 0 and F 1 first to 7rg numbers and what's the rule for Fibonacci numbers I'm there the Sun the next one is the sum of those so it's 1 the next one is the sum of those so it's 2 the next one is the sum of those so it's 3 well it looks like 1 2 3 4 5 but somehow it's not going to do that way the next one is 5 right 2 or 3 makes 5 the next one is 8 the next one is 13 and the 107 odd number is one that's my question how could I get a formula for the hundredth number and and for example how could I answer the question how fast are they growing how fast are those Fibonacci numbers growing they're certainly growing it's not a stable case whatever the eigenvalues of whatever matrix it is they're not smaller than one these numbers are growing but how fast are they growing the answer is is lies in the eigenvalue so I've got to find the matrix let me write down the Fibonacci rule FK plus 2 is f k plus 1 plus f k right now that's not in my I want to write that as u k plus 1 and a UK but right now what I've got is a single equation not a system and it's second order it's like having a second order differential equation with second derivative I want to get first derivatives here I want to get first difference so the way the way to do it is to effuse UK will be a vector see it a small trick let that UK be a vector F k plus 1 and F K so I'm going to get a 2 by 2 system first order instead of a 1 instead of a scalar system second-order by a simple trick I'm just going to have in an equation FK plus 1 equals FK plus 1 that will be my second equation then this is my system this is my unknown and what's my one-step equation so so now UK plus 1 that's so UK plus 1 is the left side and what have I got here on the right side I've got some matrix multiplying UK can you see that alright if you can see it then you can tell me what the matrix is do you see that I'm taking my system here artificially made it into a system I artificially made the unknown into a vector and now I'm ready to look at and see what the matrix so do you see the left side UK plus 1 is FK + 2 FK plus 1 that's just what I want on the right side this remember this UK here I mean for the moment put it as FK plus 1 FK so what's the matrix well that is a 1 and a 1 and that has a 1 and a 0 there's the matrix you see that that gives me the right hand set so there's the matrix a and this is our friend UK so we've got so that simple trick would change the second order scalar problem to a first order system - but with two unknowns with a matrix and now what do I do well before I even think I find its eigen values and eigen values so what are the eigen values and I that mate that's the Iowa's first let me just like think for a minute it's two by two so this shouldn't be impossible to do let's do it okay so my matrix again is one one one zero it's symmetric by the way so what I will eventually know about symmetric matrices is that the eigenvalues will come out real I won't get any complex numbers here and the eigenvectors once I get those actually will be orthogonal but 2x2 I'm more interested in what the actual numbers are what do I know about those two numbers what should it do you want me to find this determinant of a minus lambda hi sure so it's the determinant of 1 minus lambda 1 1 0 right minus lambda yes okay okay there'll be two eigenvectors well tell me again what i know about the two eigenvalues before I go any further tell me something about these two eigenvalues what are they add up to lambda 1 plus lambda 2 is is the same as the trace down the diagonal of the matrix 1 and 0 is 1 so lambda 1 plus lambda 2 should come out to be 1 and lambda 1 times lambda 2 should come out to be the determinant which is minus 1 so I'm expecting the eigenvalues to head to 1 and to multiply 2 minus 1 but let's just see a happy if I multiply this out I get that times that will be a lambda squared minus lambda minus 1 good lambda squared minus lambda minus 1 actually you see the compare that with the original equation that I started FK plus 2 minus FK plus 1 minus FK is 0 the the recurrent the recursion with that be that the Fibonacci number satisfied is somehow showing up directly here for the eigenvalues when we set that to 0 okay that's all well I would like to be able to factor that that quadratic but I'm better off to use the quadratic formula land that is let's see minus B is 1 plus or minus square root of B squared which is 1 minus 4 times that times that which is plus 4 over 2 so that's the square root of 5 so the eigenvalues are lambda 1 is 1/2 of 1 plus square root of 5 and lambda 2 is 1/2 of 1 minus square root of and sure enough they those add up to 1 and they multiply to give minus 1 okay those are the two I can go how what are those numbers approximately square root of 5 well it's more than 2 what less than 3 it could be nice to know these numbers I think I think that that so that number comes out bigger than 1 right yeah that's right this number comes out bigger than 1 it's about 1.618 not exactly it suppose it's one point just like a face so then what's lambda 2 is lambda 2 positive or negative negative right obviously negative and I knew that so it's minus and they add up to 1 so minus point 6 1 8 I guess ok and some more those are the two eigenvalues one eigenvalue bigger than one one eigenvalue smaller than one that's a great situation to be in of course the eigenvalues are different so there's no doubt whatever is this matrix diagonalizable is this matrix diagonalizable that original matrix a short we've got two distinct eigenvalues and we can find the eigenvectors in a moment but they'll be independent will be diagonalizable and now you can already answer my very first question how faster those Fibonacci numbers increasing how close they're increasing right they're not doubling at every step let's look again these numbers 5 8 13 it's not obvious the next would be 21 34 so to get some idea of what F 100 is can you give me any the crucial number so it these it's approximately what's controlling the growth of these Fibonacci numbers it's the eigen value and which eigen value is controlling that growth the big ones so F 100 will it be approximately some constant C one I guess times this lambda 1 is 1 plus square root of 5 over 2 to the hundredth power and the 200 in other words the eigen value these that the Fibonacci numbers are growing by about that factor you see that we we've got precise information about the about the Fibonacci numbers out of the Idaho okay and again why is that true let me go over to this board so what I'm doing here yeah the original eigen the original initial value is some combination of eigenvectors and then when we start multiple when we start going out the theory of Fibonacci numbers when we start multiplying by a 100 times it's his lambda 1 to the hundredth this term is is the one that's taken over its I mean that's be like one point six to the hundredth power the second term is practically nothing right the point six or minus point 6 to the hundredth power is an extremely small extremely small number so this is is this there were only two terms because we're two by two this number is this piece of it is there but it's it's disappeared where this piece is there and it's growing and controlling everything so so really that we're doing like problems that are revolving we're doing dynamic instead of ax equal B that's a static problem we're now we're doing dynamics a squared a cubed things are evolving in time and the eigenvalues are the crucial numbers okay I guess to complete this I better write down so we should complete the whole process by finding the eigen vectors okay well I have two up in the corner then I have to look at a minus lambda I so a minus lambda I is this 1 minus lambda 1 1 and minus lambda and now can we spot and eigenvector out of that that's s for these two lambdas this matrix is singular I guess the eigenvector 2x2 ought to be or easy so if I know that this matrix is singular then seems to me the eigen vector has to be lambda and one because that multiplication will give me the 0 and this multiplication gives me better give me also 0 do you see why it does this is the minus lambda squared plus lambda plus 1 it's the thing that's 0 because these lambdas are special there's the eigenvector x 1 is lambda 1 1 and X 2 is lambda 2 1 I did that as a little trick that was available in the 2 by 2 case so now I finally have to oh I have to take the initial you know so to complete this example entirely I have to say ok what was you 0 u 0 was F 1 F 2 so u 0 a starting vector f1 f0 and those were 1 and 0 so I have to use that vector so I have to look for from multiple of the first eigenvector and the second to produce u0 the 1 0 which this is what we'll find c1 and c2 and then I'm done so let me in the last five seconds grinding out a formula let me repeat the idea that I really it's the idea that central when things are revolving in time let me come back to this board because the ideas are here when things are evolving in time by a first order system starting from an original unit the key is find the eigenvalues and eigenvectors of a that will tell those eigenvectors are the eigenvalues will already tell you what's happening is the solution blowing up is it going to 0 what's it doing and then to find out exactly a formula you have to take your u0 and write it as a con nation of eigenvectors and then follow each eigenvector separate and that's really what this formula the formula for that that's what the formula for a to the K is doing so remember that formula for a to the K is s lambda to the K s inverse okay that's that's difference equations and you just have to so that the homework will give some examples different from Fibonacci to next time will be differentially you