algebra-8

[0:13]OK. This is lecture 8 in linear algebra, and this is the lecture where we completely solve linear equations. So, Ax = 0. That’s our goal. If it has a solution, it certainly can happen that there is no solution. We have to identify that possibility, by elimination. And then if there is a solution, we want to find out if there is only one solution, or there is a whole family of solutions and then, find them all.

[0:51]OK. Can I use as an example, the same matrix that I had last time, when we were looking for the nullspace. So the matrix has rows (1, 2, 2, 2), (2, 4, 6, 8), and the third row, you remember the main point was, the third row (2, 6, 8, 10) is the sum of row-1 + row-2.

[1:20]In other words, if I add those left-hand sides, I get the third left-hand side. So you can tell me right away, what elimination is gonna discover about the right-hand side, what’s… There is a condition, on b1, b2, and b3, for the system to have a solution.

[1:45]Most cases, if I took these numbers to be 1, 5, and 17, there would not be a solution. In fact, if I took those first numbers to be 1, and 5, what is the only b3 that would be OK?

[2:04]6! If the left-hand side… if these left-hand sides that up of that, then b… I need b1 + b2 to equal b3. Let’s just see how elimination discovers that. But we can see it coming, right? That if… Let me say in other words, if some combination of the left-hand side gives all 0’s, then the same combination of the right-hand side must give 0.

[2:35]OK. So let’s… Let me take that example, and write down, instead of copying that all the plus sign, let me write down the matrix: (1, 2, 2, 2), (2, 4, 6, 8), and that (2, 6, 8, 10), where the third row is the sum of first 2 rows. Now how do we deal, with the right-hand side?

[3:06]That’s… We want to do the same thing to the right-hand side that were doing for these rows on the left side. So we just tag on the right-hand side as another vector, another column. So this is the augmented matrix. It’s the matrix A with the vector b, tagged on.

[3:37]In MATLAB, that’s all you would need to type. OK. So we do elimination on that. Can we just do elimination quickly? The first pivot is fine. I subtract 2 of this away from this, 3 of this away from this. So I have (1, 2, 2, 2, b1). 2 of those away will give me (0, 0, 2, 4, b2 – 2b1). I have to do the same thing, to that third, that last column.

[4:10]And then 3 of this away form this gave me (0, 0, 2, 4, b3 – 3b1). So, that’s the elimination with the first column completed. We move on… There’s the first pivot still, here’s the second pivot – we always remembering. Now, these are then gonna be the pivot columns. And let me get the final result.

[4:46]Well, let me… Can I… Can I do it by erase here? We are capable of subtracting this row from this row, just by… that will knock this out completely and give me the row of 0’s. And on the right hand side, when I subtract this from this, what do I have? I think I have b3 – b2 – b1.

[5:27]Oh, yeah! That’s exactly what I expect. So now, what’s the last equation? The last equation… this, represented by this 0 row… That last equation is says, 0 equals b3 – b2 – b1.

[5:46]So, that’s the condition for solvability. That’s the condition on the right-hand side that we expected. It says the b1 + b2 has to match b3, and if our numbers happen to have been 1, 5, and 6. So let me take… Suppose b is (1, 5, 6), that’s an OK b. And when I do this elimination, what would I have? The b1 will still be a 1, b2 would be 5 – 2, this would be a 3. 6 – 5 – 1, this will be – this is the main point – this will be a 0. Thanks! OK!

[6:30]So the last equation is OK now. And I can proceed to solve the 2 equations that are really there, with 4 unknowns. OK. I want to do that. So this b is OK. It allows us to solution. We’re gonna be naturally, interested to keep track what is the conditions on b that… that makes the equation solvable.

[7:06]So, let me put… Let me write down what we already see, before I continue to solve it. Let me first… SOLVABILITY, THIS IS THE CONDITION ON THE RIGHT-HAND SIDE. And what is that condition? This is solvability always of Ax = b.

[7:41]So, Ax = b is solvable. Well, actually we had an answer in the language of the column space. Can you remind me what that answer is? That was like an answer from earlier lecture.

[7:59]b had to be in the column space. SOLVABLE IS when, exactly WHEN b IS IN THE COLUMN SPACE OF A. Right? That just says that b has to be a combination of the columns, and of course that’s exactly what’s the equation is looking for.

[8:23]Now I want to answer it… It’s the same answer, but in different language. Another way to answer this: IF A COMBINATION OF THE ROWS OF A GIVES THE ZERO ROW, IF… And there is an example where it happened, some combinations of the rows of A produce the 0-row, then what’s the requirement on b? That’s… because we’re gonna do the same thing to both sides of all equations. The same combination of the components of b has to give 0, right?

[9:17]If there’s a combination of the rows that gives the 0-row, then THE SAME COMBINATION OF THE ENTRIES OF b MUST GIVE 0. And this in the 0-row, that’s the 0 number. OK.

[9:44]This is another way of saying… It’s not immediate, right, that these 2 statements are equivalent. But somehow they must because they’re both equivalent to the solvability of the system. OK. So, we’ve got this… sort like question 0 is does a system have a solution?

[10:09]OK. I’ll come back to discuss that further. Let’s go forward when it does, when there is a solution. And, so what’s our job now? Abstractly we set back. We said OK, there’s the solution, finished.

[10:27]It exists, but we want it constructed. So, what’s the algorithm, the sequence of steps, to find the solution? That’s what I have… And of course, the quiz and the final, I’m gonna give you a system Ax = b, and I’m gonna ask you for the solution, if there is one, and…

[10:50]So, this is the algorithm that you wanted to follow. OK. Let’s see… So, what’s the… So, now to find the complete solution to Ax = b. OK. Let me start by finding one solution, one particular solution. I’m expecting that I can, because my system of equations now… That last equation is 0 = 0.

[11:33]So that’s all fine. I really have 2 equations. Actually I’ve got 4 unknowns, so I’m expecting to find not only a solution, but the whole bunch of them. But let’s just find 1. So, step 1. Our particular solution, x-particular…

[11:57]How do I find one particular solution? Well let me tell you how I find it. So, this is the… Since there’s lots of solutions, you could have your own way to find a particular one. Bu it just… This is a pretty natural way.

[12:12]SET ALL FREE VARIABLES TO 0. Since those free variables are the guys that can be anything, the most convenient choice is 0. And then, SOLVE Ax = b FOR THE PIVOT VARIABLES. So what does that mean? In this example which are the free variables? Which is the variable that we can assign freely and then there’s one and only one way to find the pivot variables?

[12:56]There x2 and… So x2 is 0, because that’s in the column, because that’s in the column without a pivot. The second column has no pivot. And the… which is the other one? The fourth, x4 is 0. Because those are the free one, those are in the columns with no pivot. So you’ve see what my…

[13:24]So, when x2 and x4 are 0, I’m left with… What am I left with here? I’m just left with… see now I’m not using the 2 free columns I’m only using the pivot columns. So I’m really left with x1, the first equation is just x1, and 2x3 should be the right-hand side which we pick to be a 1.

[13:52]And the second equation is 2x3, as it happened, turned out to be a 3! I’ve just write it again here, with x2 and x4 knocked out, since we’ve set them to 0. And you see, we’re back into normal case, of having back… Well back substitution will do it.

[14:17]So, x3 is 3/2 and then we go back up, and x1 is 1 – 3, that’s probably -2. Good. So now we have the solution x particular is the vector (-2, 0, 3/2, 0). OK Good. That’s one particular solution, and we should and could plot it to the original system. Really on the quiz… please… that’s the good thing to do… just… so we did all these… row operations. But this supposes to solve the original system, and I think it does.

[15:10]OK. So that’s x particular, which we’ve got. So that’s why what’s new today. The particular solution comes first you check that you have 0 equal 0, so you’re OK on the last equations. And then you set the free variable to 0; solve for the pivot variables; and you’ve got a particular solutions, this particular solution that has 0 free variables.

[15:43]OK. Now, but that’s only 1 solution and now I’m looking for all. So how do I find the rest? The point is I can add on to… add on x… anything out of the nullspace.

[16:06]We know how to find the vectors in the nullspace, because we did last time. But I will remind you what we’ve got. And then… Oh add. So the final result will be, that the complete solution… This is now the complete guy. The complete solution is this one particular solution plus any, any vector… all different vectors out of the nullspace, x_n.

[16:40]Why this pattern? Because this pattern shows up through all the mathematics, because it shows up every where we have linear equations… Let me just put here the reasoning. Ax_p… So that’s x-particular… So what does Ax_p give? That gives a correct right-hand side b.

[17:07]And what does A times the x in the nullspace give? 0! So I add, and I put in preferences… So x_p + x_n is b + 0, which is b. So… Oh, what am I saying… let me just say it in words. If I have 1 solution, 1 solution, I can add on anything in the nullspace, because anything in the nullspace has a 0 right-hand side and I still have a correct right-hand side b.

[17:48]So that’s my system; that’s my complete solution. Now let me write out what that would be for this example. So this example, in this example, x-general, x-complete, the complete solution, is x_p, which is (-2, 0, 3/2, 0), with those 0’s in the free variable, plus… Do you remember there was a special solution in the nullspace, that had a 1 in the free variables, or 1 and 0 in the free variables, and then we filled in to find the others.

[18:29]I’ve forgotten what they were, but maybe it was that. That was a special solution, and then there was another special solution, that had that free variable to 0, and this free variable equal 1, and I have to fill those in…

[18:49]Let’s see, can I remember how this filled in? Maybe this was a -2, and this was a 2 possibly. I think probably that’s right. I’m not… Yeah! 2, minus… that’s a great deal…

[19:08]I’ve had to remember what are my equations… Can I… rather than go way back to that board, let me remember the first equation… it was 2x3 + 2x4 equaling 0 now, because I’m looking for the guys in the nullspace. So I set x4 to be 1 and the second equation that I didn’t copy again gave me -2 for this and then… Yeah, I think that’s right. 2, –4 and 2, gives 0. Check!

[19:43]OK. Those were the special solutions. What do we do to get complete solution? How do I get the complete solution now? I multiply this by anything, c1, say… And I multiply this by anything. I take any combination. You remember that how we describe the nullspace?

[20:06]The nullspace consists of all combinations of… So this is X_n, all combinations of the special solutions. There were 2 special solutions because there were 2 free variables. And we want to make that count… carefully now.

[20:29]Just why I’m up here… So that’s… That’s a kind of answer I’m looking for. Is there are constant multiplying this guy? Is there a free constant that multiply that particular? No way. x_p solves Ax = 0. I’m not allowed to multiply that by 3. But AX_n, I’m allowed to multiply X_n by 3, or add to another X_n, because I keep getting 0 on the right.

[20:59]OK. So again, x_p is 1 particular guy, X_n is a whole subspace, right? It is one guy plus anything from a subspace. Let me draw it! Let me try to…

[21:15]Oh, I want to draw, I want to graph all the… I want to plot all solutions. Now x… So what dimension am I in? This is the unfortunate point. How many points does x have? 4! There’re 4 unknowns. So I have to draw a 4-dimensional picture on this MIT cheap blackboard.

[21:51]OK. So here we go. x1… Einstein could do it, but… Those are 4 perpendicular axes, in representing 4-dimensional space. OK, where are my solutions? Do my solutions form a subspace? Does the set of solution to Ax = b form a subspace? No way!

[22:35]What is that actually looks like. So, there is a subspace in this picture, this part of a subspace, right? That part is some like 2-dimensional, because I’ve got 2 parameters. So I’m thinking of this nullspace as a 2-dimensional subspace inside R⁴.

[22:45]Now I have to tell you next time, what is that mean to say a subspace; what’s the dimension of a subspace. But you see what it’s gonna be. It’s the number of free, independent constants that we can choose.

[23:01]So somehow there would be 2-dimensional subspace, not a line, and not a 3-dimensional plane, but only a 2-dimensional guy. But it doesn’t go through the origin, because it goes through this point. So, there is x_p. x_p is somewhere here, x_p. So it’s somehow a subspace, can I try to draw it that way?

[23:31]It’s a 2-dimensional subspace that goes through x_p, and then onwards by… So there is x_p, and I add it on X_n, and there’s x! There’s x = x_p + Xn. But the X_n is anywhere in the subspace. So that’s filled out a plane.

[23:57]It’s a subspace… It’s not a subspace, what am I saying… It’s like a flat thing. It’s like a subspace, but it’s been shifted, away from the origin. It doesn’t contain 0. OK. Thanks.

[24:16]That’s the picture, and that’s the algorithm. So the algorithm is just go through elimination; and finds the particular solution; and then finds those special solutions. You can do that.

[24:33]Let me take our time here in the lecture, to think about the bigger picture. So, let me think about… So this is my pattern. Now I want to… I want to ask you, about… I want to ask you some questions. So when I mean think bigger I mean I’ll think about an m by n matrix A of rank r. OK.

[25:18]What’s our definition of rank? Our current definition of rank is number of pivots. OK. First of all, how were these numbers related? Can you tell me a relation between r and m? If I have m rows in a matrix, and r pivots, then I certainly know – I know, always – What relation do I know between r and m?

[25:51]r is less or equal, right? Because I get m rows, I can’t have more than m pivots, I might have m, or I might have fewer. Also, I’ve got n columns. So what’s the relation between r and n? It’s the same less or equal, because a column can’t have more than 1 pivot. So I can’t have more than n pivots altogether. OK.

[26:23]So, I have an m by n matrix of rank r. And I always know r less equal n, and r less equal m. Now I’m especially interested in the case of full-rank, when the rank r is as big as it can be.

[28:39]Well, I guess I’ve got 2 separate possibilities here. It’s depending on what these numbers m and n are. So, let me talk about the case of FILL COLUMN RANK. And by that I mean, r = n. And I want to ask you, what does that imply about our solutions.

[27:14]What does that tell us about the nullspace? What does that tell us about the complete solution? OK So what does that mean? So I want to ask you: OK, if the rank is n, what does that mean? That means there’s a pivot in every column. So how many pivot variables are there? N! All the columns have pivots, in this case. So, how many free variables are there? None at all!

[27:54]So, no free variables, r equals n, no free variables. So what does that tell us about? What’s gonna happen then, in our little algorithms? What will be in the nullspace?

[28:11]The nullspace of A, has got what in it? Only the 0 vector! There’s no free variable to give the free variable to give other values to. So the nullspace is only the 0 vector.

[28:33]And what about our solution to Ax = b? What’s the story on that one? So now that’s coming down from today’s lecture. The solution x is… What’s the complete solution? It’s just x_p, right, if there is a solution. It’s x = x_p, there’s nothing… you know, there’s just one solution, if there’s one at all.

[29:15]So, it’s unique solution, unique means only one, if it exist. In other words, I would say, let me put it in a different way, there’s either 0 or 1 solution.

[29:43]This is all in this case r = n. So I’m… Because many many applications in reality that the columns will be, will be what I’ll later call independent… And we’ll have nothing to look for in the nullspace, and we’ll only have particular solutions.

[30:11]OK. Everybody see that possibility? But I need an example, right? So, let me create an example… What sort of the matrix, what’s the shape of the matrix that has full column rank? So can I squeeze in an example here?

[30:34]If it exists… Let me put in an example… It’s just the right space to put in an example, because the example will be like tall and thin. It will have… Well I mean here is an example (1, 2, 6, 5; 3, 1, ,1, 1),brilliant example. OK. So there’s the matrix A, and what’s its rank? What’s the rank of that matrix?

[31:14]How many pivot will I find if I do elimination? 2! Right? 2! I see a pivot there. Certainly, those 2 columns are headed off in different directions. When I do elimination, I certainly get another pivot here, fine, and I can use those to clean out below and above. So the… Actually, tell me what row reduced… reduced row echelon form would be? Can you carry that, the elimination process to a bitter end?

[31:56]So, what does that mean? I subtract the multiple of this row from this row, so I clean up all 0’s there. Then I got some pivot here, what do I do with that? I go subtract it below, and above, and then I divide through, and what’s r for that example?

[32:15]Maybe I can… you allow me to put it up here in the next board. What’s the row reduced echelon form, just got a practice, for that matrix? It’s got 1’s in the pivot, it’s got the identity matrix. So, little 2 by 2 identity matrix, and below it, all 0’s.

[32:41]That’s the matrix that really has 2 independent-rows, and that’s the first rows, actually. The first 2 rows are independent; they are not in the same direction. But the other rows are the combinations of the first 2. So is there always a solution to Ax = b? Tell me what’s the picture here!

[33:06]For this matrix A, this is a case of full column rank. The 2 columns are…. Give 2 pivots. There’s nothing in the nullspace, there’s no combination of those columns that gives the 0 column, except the 0-0 combination.

[33:36]So, there’s nothing in the nullspace, but, is there always a solution to Ax = b? What’s up with Ax = b? I’ve got 4 equations here, and only 2 x’s. So, the answer’s certainly no. There’s not always a solution. If there… I may have 0 solutions, if I make a random choice, I’ll have 0 solutions. Or if I make a great particular choice of the right hand side which just happen to be a combination of the 2 guys – like tell me one right hand side that would have a solution.

[34:08]Tell me a right-hand side that would have a solution. Well, (0, 0, 0, 0) is OK. No prize for that one. Ah… Tell me another one, another right-hand side that would be (4, 3, 7, 6). I could add the 2 columns. Right? What would be the total complete solution if the right right-hand side was (4, 3, 7, 6)?

[34:34]There would be a particular solution (1, 1) – one of that column and one of that, and that would be the only solution. So there would be x_p, there would be (1, 1) in the case when the right side is the sum of those 2 columns, and that’s it. So, that would be the case with 1 solution.

[34:55]This is the typical setup for the full column rank. Now I’ll go to full row rank. You see the… sort of natural symmetry of this discussion. FULL ROW RANK MEANS r = m. So, this is what I’m interested now. r = m.

[35:27]OK. So, what’s up with that? How many pivots? m! So, what happened when we do elimination in that case? I’m gonna get m pivots. So, every row has a pivot, right? Every row has a pivot. Then what about solvability? What about this business of… for which right-hand side can I solve it? So, that’s my question.

[36:08]I can solve Ax = b for which right-hand side… for… you see what’s coming? I do elimination. I don’t get any 0 rows. So there aren’t any requirements on b. I can solve Ax = b for every b!

[36:40]I can solve Ax = b for every right-hand side. So this is the existence – EXISTS a solution! Now tell me… So every row has a pivot in it. So how many free variables are there? How many free variables in this case? If I had n variables to start with, how many are used up by pivot variables? r which is m! So I’m LEFT WITH n – r FREE VARIABLES.

[37:36]OK. So, this case of full row rank, I can always solve, and then this tells me how many variables are free, and this is of course n – m. This is n – m free variables.

[37:53]Can I do with an example? You know the best way for me to do an example is just to transpose that example. So, let me take that matrix that had column 1, 2, 6, 5, and make it a row. And let me take (3, 1, 1, 1) as the second row. And let me ask you… this is my matrix A, what’s its rank?

[38:34]What’s the rank of that matrix that story… But not a story here, because we just getting the idea of rank. What’s the rank of that matrix? 2! Exactly! 2! There would be 2 pivots. What will the row reduced echelon form be? Anybody know that one? Actually not only tell me… you have to tell me not only there be 2 pivots, but which will be the pivot column?

[38:51]Which columns of this matrix will be pivot columns? So the first column is fine, and then I go on to the next column, and what do I get? Do I get a second pivot out of…? Will I get a second pivot in this position? Yes!

[39:08]So, the pivots, when I get all the way to r will be there, and here will be some numbers. This is the part I previously called F. This is the part so the pivot column in R will be the identity matrix. There’s no 0-rows, no 0-rows because the rank is 2. But there will be stuff over here. And that will enter the special solution in the nullspace.

[39:46]OK. So this is the typical matrix with r = m, smaller than n. Now, finally, I’ve got a space here for r = m = n. I’m often at the corner here with the most important case of all. So what’s up with this matrix? So let me give an example. OK. Brilliant example…

[40:19][1, 2; 3, 1]. Tell me what… How do I describe the matrix that has rank r = m = n? So the matrix is square, right? The square matrix, and if I know its rank, it’s full rank now. I don’t have to say full column rank or full row rank, I just say full rank. Because the column count and the row count are the same, and the rank is as big as it can be. And what kind of a matrix have I got?

[40:59]It’s invertible. So, that’s exactly the invertible matrices. r = m = n means the… and what’s the row echelon form, the reduced row echelon form, for an invertible matrix, for a square, nice square invertible matrix? It’s I! Right!

[41:24]So, you see that the good matrices are the ones that come out trivially in R. You reduce them all the way to the identity matrix. What’s the nullspace for this matrix? Can I just hammer away with the question what’s the nullspace for this matrix? The nullspace for that matrix is the 0-vector only.  The 0-vector only!

[41:58]What are the conditions to solve Ax = b, which right-hand side b are OK. If I want to solve Ax = b for this example, so A is this and b is b1, b2. What’re the conditions on b1, b2? Right! So this is the case, this is the case where I can solve… So, I’m coming back here… I can solve… Since the rank = m, I can solve for every b, and since the rank is also n, There’s unique solution.

[42:39]Let me summarize the whole picture here. Here’s the whole picture. I can have r = m = n. This is the case where this is the identity matrix. And this is the case where there’s on solution. That’s the square invertible chapter 2 case.

[43:09]Now, we’re into chapter 3. We could have r = m smaller than n. Now that’s’ what we have over here, and the row echelon form looks like the identity with some 0-rows. And that was the case where there are 0 or 1 solutions. When I say solution I mean to Ax = b. So this case is always 1, this case is always 0 or 1. And now let me take the case of full column rank, but some… extra rows. So, now R has, well the identity, I’m almost attempt to write the identity matrix and F, but that isn’t necessarily right.

[44:22]I have… Is that right? Sorry… Am I getting this correct here? Ah… I’m not! My god! This is the case r = n, the columns are OK. That’s the case that was on that board r = n, full column rank. Now I want the case where m is smaller than n, and I got extra columns.

[44:50]OK. There we go. So this is now the case of full rank, and it looks like I F, sort of I can’t be sure the pivot columns are the first columns. So the I and the F, the F could be partly mixed into the I. Can I write that to be just like that?

[45:25]So, the F could be sort of partly into the b if the first columns weren’t the pivot column. Now, how many solutions in this case? There’s always a solution. This is the existence case, there’s always a solution. We are not getting any 0-rows. There’s no 0-row there. So there’s always either 1 or infinitely many solutions. OK

[45:58]Actually I guess there’s always an infinite number because we always have some nullspace to be with. Then the final case is where r smaller than m and smaller than n.

[46:14]OK. Now, that’s the case where R is the identity with some free stuff, but with some 0-rows too. And that’s the case where there these are no solution, because we didn’t get a 0 = 0, for some b’s, or infinitely many solutions.

[46:43]OK. This board really summarizes the lecture, and this sentence summarizes the lecture. The rank tells you everything about the number of solutions. That number of rank r tells you all the information except the exact entries in the solution – for that you go to the matrix.

[47:11]OK, good! Have a great weekend…