OOPS - algebra-7

[0:08]OK, here is linear algebra, lecture 7. I�ve been talking about vector spaces, and especially, the nullspace of a matrix, and column space of a matrix. What�s in those spaces? Now I want to actually describe them. How do you describe all the vectors that are in those spaces? How do you compute these things?

[0:41]So this is the turning thing the idea, the definition, into an algorithm. What�s the algorithm for solving Ax = 0? So that�s the nullspace that I�m interested in. So can I take a particular matrix A, and describe the natural algorithm that I�m now executing for that matrix.

[1:07]Here we go� So, let me take the matrix as an example. So we are definitely talking rectangular matrices in this chapter. So I�ll have 4 columns, and 3 rows. (2, 4, 6, 8), and (3, 6, 8, 10) OK�

[1:36]If I just look at those columns and rows, well I noticed right away, that the column-2 is a multiple of column-1. It�s in the same direction as column-1; it�s not independent. I only expect to discover that in a process. Actually with rows I notice that: that row pluses this row gives us a third row. So the third row is not independent.

[2:09]So, all that should come out of elimination. So now what am I� My algorithm is elimination, but extended it now to the rectangular case, where we have to continue even if there�s 0�s in the pivot position, we go on�.

[2:32]OK. Let me execute elimination for that matrix. My goal is always to� Well I�m doing the elimination; I�m not changing the nullspace, that�s very important, right? I�m solving Ax = 0, by elimination. And when I do these operations that you already know, when I subtract a multiple of one equation from another equation, I�m not changing the solutions. So I�m not changing the nullspace.

[3:04]Actually I am changing the column space as you see. So, yes, pay attention to what does this elimination leaves unchanged, and the answer is: the solution to the system is not changed, because I �m doing the same thing; I�m doing the legitimate operations on the equations. Of course on the right-hand side, it�s always 0, and I don�t plan to write 0�s all the time.

[3:30]OK. So, I�m really just working on the left side, but the right side is keeping up, always 0. OK, so what�s the elimination? Well, you know where the first pivot is, and you know what to do with it.

[3:47]Can I just take the first step below here? So, that pivot row is fine, I take 2 times that row away from this one and I get 0, 0 � that�s the same thing, no difficulty, 2*2�s away from the 6, leaves me with a 2, 2*2�s away from the 8 leaves me with a 4. And now 3 of those away from here, 0, again another 0, 3*2�s away from that is a 2, 3*2�s away from that 10 is a 4. OK

[4:23]That�s the first stage of elimination. I�ve got the first column straight. So, of course I move onto the second column. I look in that position, I see a 0. I look below it, hoping for a non-zero, that I can do a row exchange, but it�s 0 below.

[4:48]So, that�s telling me that that column is, well what it�s really gonna be telling me is that column is a combination of the earlier columns� That second column is dependent on the earlier column.

[5:04]But I don�t stop the think here. That column has nothing to do. I go on to the next. So, here�s the next pivot. So there�s the first pivot, and there�s the second pivot.

[5:19]Can I just keep this elimination going downward? So, the next step keeps the first row, keeps the second row, with its pivot, so I�ve got my 2 pivots, and does the elimination to clear out the columns below that pivot. So actually you�ve see the multiplier is 1, it subtract the row-2 from row-3, and produces a row of 0.

[5:53]OK. That� I would call that matrix U, right. That�s our upper� Well I can�t quite say upper triangular, maybe� Upper� I don�t know, upper something. It�s got� It�s in this so-called ECHELON form. The word echelon means like stair case form. The non-zeros come in that stair case form, if there was another pivot here, then the stair case would include that.

[6:33]But, here�s the case where we have 2 pivots only. OK. So actually we�ve already discovered the most important number of this matrix, the number of pivots, is 2. That number we will call the RANK of the matrix. So let me put immediately. The rank of A, so I�m telling you what this word rank means, in the algorithm, it�s equal to THE NUMBER OF PIVOTS, and in this case, 2.

[7:15]OK. For me, that number 2 is the crucial number. OK, now I go to� You remember, I�m always solving Ax = 0. But now I can solve Ux = 0, right, same solution, same nullspace. OK.

[7:30]So I could stop here. Why don�t I stop here and do the back substitution? So now I have to ask you, how do I describe those solutions? There are solutions, right � to Ax = 0. I knew there would be, I had 3 equations and 4 unknowns, I certainly expect some solutions. Now I want to see what are they.

[7:56]OK. Here�s the critical step, I� And I refer to it up here, as separating out the pivot variables, the pivot columns, which is these 2. Here I have 2 PIVOT COLUMNS. Those are� Obviously, they are the columns with the pivots. So I have 2 pivot columns.

[8:23]And I have, the other columns, I�ll call free� These are FREE COLUMNS. OK. Why do I use those words? Why do I use that word free? Because now I want to find the solutions to, Ux = 0. Here�s the way I do it. These free columns� I can assign any number, freely, to those� to the variables x2, and x4 � the ones that multiply column 2 and 4.

[9:07]So, I can assign anything I like, to x2 and x4. And then, I can solve the equations for x1, and x3. Let me say that again: if I� Let me assign�

[9:24]So, one particular x is to assign, say the value 1, to x2, and 0 to x4. That was a free choice, but it�s a convenient choice. OK. Now I want to solve Ux = 0, and find number 1, and 3, complete the solution.

[9:48]OK. Can I write it down� Let�s see� Shall we just remember what Ux = 0 represents? What are my equations? That first equation is x1 +... I�m just saying what are these matrices meaning, that�s the first equation, and the second equation was 2x3 + 4x4 = 0; those are my 2 equations. OK.

[10:17]OK. Now the point is I can find x1 and x3, by back substitution. So we�re building up what we already know. The new thing is that they were some variables that I could give any numbers to. And I�m systematically gonna make a choice like this: 1, and 0.

[10:39]Now what is x3? And let us go backwards, back up by look at the last equation; x3 is 0 from the last equation. Because x4� we�ve set x4 to 0, and then we get x3 is 0. OK.

[11:00]Now we set x2 to be 1, so what is x1? -2, right? So then I have -2 + 2, 0 and 0, correctly giving 0. There�s a vector in the nullspace. There�s a solution to Ax = 0. In fact, what solution is that? That simply says -2 times the first column + 1 times the second column, is the 0 column.

[11:29]Of course, that�s right. -2 of that column plus 1 of that, or -2 of that plus 1 of that. That solution is� That�s just what we saw immediately that the second column is twice as big as the first column.

[11:45]OK. Tell me some more vectors in the nullspace. I found one; tell me how to get a bunch more, immediately out of that one. Just take multiples of it. Any multiple of� I can multiply this by anything. I might as well call I could say c, some multiple of this. So, let me...

[12:12]So, x could be any multiple of this one. OK, that�s� that describes now a line, an infinitely long line in 4-dimensional space. But � which is in the nullspace � is that the whole nullspace? No I�ve got 2 free variables here. I made this choice 1 and 0, for the free variables, but I could have made another choice.

[12:42]Let me make other choice 0 and 1. You see my system. So, let me repeat my system: this is the algorithm that you� just were in to do. Do elimination; decide which are the pivot columns, and which are the free columns that tell you that variables 1 and 3 are pivot variables; 2 and 4 are free variables.

[13:11]Then those free variables� You assign them� You give one of them the value 1, and the other is the value of 0. In this case, we had a 1 and a 0, and complete the solution. And you do, you give the other one, the value 1 and 0. And now, complete the solution. So, let�s complete that solution.

[13:34]I�m looking for a vector in the nullspace. And it�s absolutely gonna be different from this guy, because� because any multiple of that 0 is never gonna give a 1. So I have somebody new in the nullspace, and let me finish it out.

[13:48]What�s x3 here? So we�re going by back substitution, looking at this equation� Now, x4 � we�ve changed; we�re doing the other possibility where x2 is 0, and x4 is 1. So x3 will happen to be -2. And now what do I get for that first equation?

[14:12]Ah, x1, let�s see. 2x3 is -4, plus 2� Do I get a 2 there? Perhaps, yes! 2 for x1, -4, and 2, OK! That�s in the nullspace. What is that say, about the columns? That says that 2 of this column, -2 of this column, plus this column gives 0, which is does. 2 of that minus 2 of that, and 1 of that gives us 0 column.

[14:49]OK. Now I found another vector in the nullspace. Now, we�re ready to tell me the whole nullspace. What are all the solutions to Ax = 0? I�ve got this guy. And when I have him, what else is going into the nullspace along with that?

[15:12]These are my 2 special solutions. I call them special� I just invented that name, special solutions. What�s special about them is the special numbers I gave to the free variables, the values 0�s and 1�s for the free variables.

[15:31]I could have given the variables any values, and got vectors in a nullspace. But this was a good way to be sure I got everybody.

[15:41]OK, so, once I had him, I also have any multiple, right? So, I could take any multiple of that, and it�s in the nullspace. And now what else � I left a little space for what? A plus sign! I can take any combination! Here�s a line of vectors in the nullspace, a bunch of solutions. Would rather I say in the nullspace, or would rather I say OK, I�m solving Ax = 0? Well really I�m solving Ux = 0.

[16:21]Well, OK, let me put in that crucial plus sign, I�m taking all the combinations of my 2 special solutions. That�s my conclusion now. The nullspace contains exactly all the combinations of the special solutions. And how many special solutions are there? There�s 1 for every free variable. And how many free variables are there?

[16:55]Oh, I mean we can see all the whole picture now. If the rank r was 2, this is THE NUMBER OF PIVOT VARIABLES, right, because this counts the pivot. So how many free variables? Well, you know it�s 2, right?

[17:17]What is that in� for a matrix that�s m rows, n columns, n variables that means, with rank r, how many free variables have we get left? If r of the variables are pivot variables, we have n � r, in this case, 4 � 2, FREE VARIABLES.

[17:46]Do you see that�? First of all, we get to seen the answers here, we get r pivot variables, so there really were r equations here, there looks like 3 equations, but there are really only 2 independent equations. And, there were n � r variables that we could choose freely, and we gave those special 0, 1 values and we got the special solution.

[18:22]OK, That� We could stop at that point, that gives you a complete algorithm for finding all the solutions to Ax = 0. OK. Again, you do elimination, going on when a column... when there�s nothing to be done on columns, you just continue.

[18:53]That this number r, the number of the pivot is crucial� and it leaves n � r free variables, which you give value 0 and 1 to. I would like to take one more step. I would like to clean up this matrix even more. So now I�m gonna go to� this is in its� this is in echelon form, upper triangular if you like.

[19:22]I want to go one more step to make it as good as it can be. OK. So, now I�m gonna speak about the reduced row echelon form.

[19:34]OK. So, now I�m gonna speak about the matrix R, which is the REDUCED ROW ECHELON FORM. So what does that mean? That means I just� I can work harder on you. So, let me start� Let me suppose I got as far as U, which was good. Notice how that rows of 0�s appeared. I didn�t comment on that. But I should have. That row of 0 appeared because row-3 was a combination of rows 1 and 2.

[20:25]And elimination discovered that fact. When we get a row of 0�s, that�s telling us that the original row that was there, was a combination of other rows, and elimination knocked it out.

[20:45]OK, so we got this far. Now how can I clean that up further? I can do elimination upwards. I can get 0 above the pivots. So, this reduced row echelon form has 0�s ABOVE AND BELOW THE PIVOTS.

[21:12]So, let me do that. So now I�ll subtract 1 of this from the row above. That will leave a 0, and a -2 in there, and that�s good. OK. And I can clean it up even one more step, I can make pivots� The pivots, I�m gonna make it equal to 1!

[21:38]Because I can divide the equation-2, by the pivot, that won�t change the solutions. So, let me do that, and then I really� I�m ready to start. (1, 2, 0, -2), (0, 0, 1, 2) �I divided the second equation by 2, because now I have a 1 in that pivot, and 0�s below.

[22:08]OK, this is my matrix R. I guess I�m hoping that you could now execute the whole algorithm. MATLAB will do it, immediately with the command rref � Reduced Row Echelon Form of A. So if I input that original matrix A, and then I type that command, press return, that matrix will appear.

[22:48]That�s the reduced row echelon form, and it�s got all the information as clear as can be. What information has it got? Well of course it immediately tells me the pivot rows, the pivot rows � 1 and 2, pivot columns � 1 and 3. And in fact, It�s got the identity matrix in there, right? It�s got 0�s above and below the pivot. And the pivots are 1. So it�s got� So notice the 2 by 2 identity matrix, that setting in the pivot rows and pivot columns.

[23:36]It�s I IN THE PIVOT ROWS AND COLUMNS. It�s got 0 rows below. They�re always indicating that the original rows were combinations of other rows. So we really only have 2 rows there. And now it also�

[24:07]So there�s the identity, now it also got it�s free columns, and� They�re cleaned up as much as possible. Actually it�s now so cleaned up that the special solutions; I can read off, you remember I went through the steps of computing this� doing back substitution.

[24:36]Let me� Instead of that system, let me take this improved system. So I�m gonna use these numbers, right? In these equations what did I do? I divided this equation by 2, and oh, yeah, I subtracted 2 of this, which knocked out this guy and made that a minus sign. Is that what� That�s now� I�ve now written Rx = 0.

[25:13]I guess I�m hoping everybody in this room understand, the solutions to the original Ax = 0� the midway, halfway Ux = 0, and final the Rx = 0, are all the same. Because going from one of those to anther one, I didn�t messed up. I just multiply the equations and subtract from other equations which I�m allowed to do�

[25:43]OK. But my point is that now, if I do these free variables, and back substitution, it�s just� the numbers are there! When I let x� So, in this guy, I let x2 be 1, and x4 be 0. I guess what I�m seeing here. Let me sort of separate this out here. I�m seeing in the pivot columns� If I put the pivot columns here I�m seeing those. And in the free columns, I�m seeing� What I�m seeing in the free columns? It�s 2, 3 in that first three column, the x2 column, and a -2, 2, in the fourth column, the other free column.

[26:39]And the row of 0�s below, which of course has no� That equation is 0 equals 0, that�s satisfied. Here is my point. That when I do back substitution, these numbers are exactly what shows up� Oh, their signs get switched!

[27:01]I was going to say those numbers 2, -2, 0, 2, Can I just circle� This is the free part of the matrix. This is the identity part. This is the free part � maybe I�ll call it F. This of course, I call I, because this is the identity.

[27:21]The free part, I mean I�m just doing back substitution, and those free numbers will show up with a minus sign, because they pop on to the other side of the equation. So I see -2, 0, and I see 2, -2.

[27:42]Can I� So that wasn�t magic, it had to happen. Let me show you clearly why it happened. OK.

[27:51]This is what I�m interested in here. And now let me just like do it for� Let�s suppose� we�ve got to... Let�s suppose we�ve got the system already in rref form. So, my matrix R is� What does it look like? Let me pretend that the pivot columns come first, and whatever in the free column. And there might be some 0�s below. There�s the typical, pretty typical, reduced echelon form.

[28:53]You see what�s typical. It�s got� This is r by r. This is r pivot rows; this is r pivot columns, and here are, n � r free columns. OK. Tell me what are the special solutions? What�s x, if I want to solve Rx = 0? In fact, let me� I�m really going to do the whole� This is now block matrices. I might as well do all the special solutions at once.

[29:44]So I want to solve Rx = 0. And I�ll have some special solutions. Let me� Actually, can I do them all at once? I�m gonna create a NULLSPACE MATRIX. OK. Its columns are SPECIAL SOLUTIONS. I make it sound harder. It�s gonna be totally easy. N will be this nullspace matrix. I want RN to be the 0 matrix. These columns of N� it gets multiplied by R and gives 0 columns. So, what N will do the job?

[30:45]Let me put� I�m gonna put the identity in the free variable part, and then �F will show up in the pivot variables. Just the way I did in that example. There we had the identity and F, and in the special solution. So, these columns are� There�s the matrix of special solutions.

[31:11]And actually� so there is a MATLAB command, or a teaching code command, null� N equal� So this is the � produces the nullbases; the nullspace matrix; null of A. And there it is.

[31:35]And how does that command actually work. It uses MATLAB to compute R, then it picks it out, the pivot variables, the free variable� puts 1�s and 0�s in for the free variables, and copies out the pivot variables. It does back substitution, but back substitution for this system. It�s totally simple. What is this system?

[32:04]Rx = 0. So this is R; it�s (I F). And x is the pivot variables, and the free variables, and it suppose to give us a 0. So, what is that mean? That means that the pivot variables plus F times the free variables, give 0.

[32:32]So, let me put F times the free variable on the other side. I get �F times the free variables. There�s my equation as simple as it can be. That�s what back substitutions come to when I reduce and reduce and reduce this system, to the best form.

[32:55]OK. And then if the free variables� I make this special choice of the identity then the pivot variables are �F. OK. Can I do another example? Could you do another example? Let me just put another example matrix and let�s go through this algorithm once more.

[33:22]Here we go. Here�s the blackboard for another matrix. OK. So I�ll call the matrix A again, but let me make it� Yeah, how big shall we make it this time? Ah, why don�t I do this? It�s just for a heck of it, let me take the transpose of A, and see what happens to that.

[33:54](2, 4, 6, 8), and (3, 6, 8, 10)... Before we do the calculations, tell me what�s coming. How many pivot variables do you expect here? How many columns are going to have pivots? How many� We have 3 columns in that matrix. But are we going to have 3 pivots?

[34:30]No, because this third column is the sum of the first 2 columns. I�m totally expecting that these will be pivot columns. Because there, independent, but this third guy, this third column, which is depend on the first 2, is gonna be a free column.

[34:57]Elimination better discover that. And elimination will also straight out the rows. We�ll also identify some dependent rows and independent rows. What�s the row reduced echelon form for this? Let�s just do this�

[35:16]OK. So, that�s the first pivot. 2 times that away from that gives me a row of 0�s. 2 times that away from that gives me a (0, 2, 2). And 2 times that away from that gives me a (0, 4, 4). OK?

[35:38]First column is straight, first variables is a pivot variable, no problem. On to the second column, I looked at the second pivot; it�s a 0. I looked below it. There is a 2. OK I do a row exchange. So this 0 is now there; I now have a perfectly good pivot, and I use it.

[36:03]OK, and I subtract 2 of that row away from this row, all right if I do it like that� I�ve got to the form U now. This was my A; now there is my U. I can see now� I have to stop, right? I would go on to the third column � I should have tried. I quit but without trying, I shouldn�t have done that.

[36:31]On to the third column, looked at the pivot position, it�s got a 0 in it. Look below, all 0�s. Now I�m entitled to stop.

[36:40]OK. So the rank is 2, AGAIN! What about the nullspace? How many special solutions are there this time? How many special solutions for this matrix? I�ve got� And which are the free variables, what are the pivot variables, and so on? Pivot columns, I�ve got 2 pivot columns, and that�s no accident. The number of pivot columns for a matrix A � that�s a great fact� that the numbers of pivot columns for A and A^T are the same. And I have a free column, there is the free column, 1 free column, because the count is 3 � 2. 3 � 2 gives me 1 free column. OK.

[37:43]So now, let me solve what�s in the nullspace. OK. So how do I� Let�s see, these vectors have length 3; they only have 3 components. I�m making too much space for the� to write x. X is just got 3 components. And what are they?

[38:08]I�m looking for the nullspace. OK. So how do I start? I give the free variables some convenient value. And what�s that? I set it to 1. I set the free variable to 1. If I set the free variable to 0, and solve the pivot variables, I got all 0�s, no progress.

[38:38]But by setting the free variable to 1, you�ll see what my 2 equations now are� Shall I � My equation is x1 + 2x2 + 3x3 = 0, that�s my first equation. And my second equation is now 2x2 + 2x3 = 0. And OK. So if that 3 is 1, x2 is -1, and if x3 is 1, and x2 is -1, then maybe x1 is -1.

[39:17]And actually I go back to check now. I don�t like� I did a quick calculation mentally. Can I mentally do a quick check? That matrix that solution x says that - this column � this column + this column is the 0 column. And it is. Minus that minus that plus that is 0. So that�s in the nullspace. And now you can tell me what else is in the nullspace.

[39:45]What�s the whole nullspace now? It�s I multiply by c, right. The whole nullspace is a line. So that is the description. If I ask you on the homework or quiz or the final, what� give me describe� tell me the nullspace, find the nullspace of this matrix, you could take those steps. And that�s the inter I�m looking for.

[40:16]And I�m looking for that c too, because that�s telling me that you�re remembering that it�s a whole space, not just one vector. Later I will ask you for the bases for the nullspace then I just want this vector.

[40:31]But if I ask for the whole nullspace, then this is the whole line through that vector. OK. Now one more natural thing to do with this example, right, is keep going to the reduced matrix R. So can I push onwards to R. That should be quick, but let�s just practice. Let me keep going to R, so what do I do here?

[40:48]I subtract I clear out above the pivot, so I subtract that from that. That�s 1, 0, 1 in the last� Right? When I subtract this row from this, it produces the 0 above this pivot. And now I want that pivot to be a 1. So, for the R matrix, I�ll divide this equation by 2, and of course, these 0�s are great, they don�t change� There�s R. That�s R! You see what R is? You see the identity matrix setting up here; you see the free part F, the F part here; and you see the 0�s below.

[41:43]This is I, F, 0, 0. And, what�s the X? The X has the identity� Well it�s only the single number 1, but it�s the identity matrix, in the free part. And what does it have in the pivot variable? What did back substitution give?

[42:19]It gave minus� these guys! Do you see that what this is? It�s any multiple of� This is the identity there, and there is �F here. This is our nullspace matrix N, for this. Our nullspace matrix is they guy whose columns are the special solutions.

[42:35]So their free variables have these special values 1, and pivot variables have �F. So do you see how the �F just automatically shows up in the special solution.

[42:55]That�s it really. I don�t there is anything more I can say, about Ax = 0. There�s more I can say about Ax = b. But that will be Friday. OK. So, that�s the nullspace, thanks!

Comments:

Well I am coming back!

We get used to counting the number as 1,2,3.......So I suggest that we could creat a new system to� count the number.By counting the vectors in the same new way .

Now let us consider A as any thing� you like but it should follow� the rules that the determination .And to seperate A into as many equations as you can ,then to use 0*the equations.

FROM� WU BIN