Okay, so that was about how to look at linear systems. Right? So we have the row view, we have the column views. Now we don't just want to look at these equations, we want to solve these systems. So the thing is that if you have some equations if you have a system if the size is too small. If the scale is small solving, it does not require any techniques. You just do some very simple replacement, everything is fine. But if you have hundreds of variables, hundreds of constraints, you really need a systematic way. So the systematic way that we're going to introduce is called the Gaussian elimination.Obviously this means this method is introduced and developed by Gaus or the mathematician. So let's see how to do this. So we still want to use this very simple example to illustrate the idea. If you know the ideas, you may solve a linear system with seven by seven,ten by ten, hundreds by hundreds, if you are patient enough. Or if you really know that idea, you may write a computer program to iteratively, do some operations and then solve whatever system you'd like. So let's see. What's this? The idea is that if you look at this particular equation, if you find the right numbers to plug in, your solution is going to satisfy this particular equation. But for the equation itself, it may be too difficult because there are too many options. Too many possibilities for you to satisfy this particular equation. The second one is different because for the second one, you only have two variables, right? So the flexibility becomes not so many. You don't really have such a large flexibility, you may only adjust the two variables. To satisfy this equation. Then that gives us a very simple idea. How about this? Let's do some operations, like to introduce some modifications among these equations. What if we may do something to eliminate this particular variable? If there is only one variable in your constraint, then solving it is very simple because there is only one possibility. So the idea is to eliminate variables. That's why it's called Gaussian elimination. So let's try to see how to do this. Suppose it is you that want to apply this idea, then the first thing that you are going to do is that, okay I want to eliminate this particular variable. The way that you may do Is that all right, I can see that I have to do here and here I have for you here. So, how about this? I'm going to multiply the first equation by two, I'm going to get 4u plus 2v plus 2w, which should equal to 14. So this and that they are just equivalent, right? You don't really add anything into your formulation. And then I'm going to subtract this particular equation from your second equation. In that case, what I'm going to do is that four would become zero right after I do this subtraction. Negative three minus two is going to become negative five. And there you have nothing. This becomes negative 2w. Five minus 14 you're going to get negative nine, something like this. So once you do this, you are going to get a different equation, too. The different equation two is actually the same as your equation one I mean previous equation two, but pretty much it becomes easier because you are first variable is eliminated. So you may do the same thing to eliminate this. And that creates only one variable in your first column. Once you're done with that, let's see what's going to have later. So the thing that I do is to eliminate you the first column variable from the last two equations. The way to do it is to take the second equation, take the first equation, multiply the first equation by some number and then do some subtraction. I'm going to get a new equation two, a new equation three. Now the system, the solution is still there, it does not change. But the system looks easier now. You may argue that well, how can this is easier because I still cannot see any solution. But if you are able to eliminate numbers in the first column, obviously you are able to eliminate numbers in the second column. So, we will do that. This part is called forward elimination, we go forward to eliminate column one, eliminate column two, and so on and so on and so on. And here, there are some numbers that we will give them spatial numbers because they will play some role later. The only number that remains in the first column two would be called the first pivot. The second column now contains another number negative five. So negative five is not the single the only number on column two. But later we will do one more iteration to eliminate numbers in the second column right? Then negative five eventually will be the only thing we have for the second row or second column, that will be our second pivot. So starting from this particular step, we will do one step further. We're going to look at your third row and the try to eliminate that 5V from your second equation. So that part would be very simple What you need to do is to add your second row to your third row, right. And once you do that, you get to this one. This immediately tells you that ,okay, value should be two. And then once we are done with this we get three pivots. The three pivots are two. Negative five, and one. So pretty much the stage one of forward elimination is that we have a matrix, and then we make it easier by making this part zero. So there are some numbers but we don't care. Because then we will focus on this particular sample problem for at least a problem, we do it again, we're going to eliminate some numbers here. There are some other numbers. We don't care, but we're going to get an even smaller sample problem. We keep doing this. Doing this until for the last one, we have only one variable. And once we are done with that, we know w must be true. And once we are done with w, now we are having a triangular system here. And then once we have a triangular system, those numbers on the diagonal are called pivots. So we have two, negative five and one. And then the last thing to do is to do back substitution to find w, v, and u, so how to do that? Well, if your w must be to your negative 2 w must be negative 4, right? So that means your negative 5v must be negative 5 or your v must be 1. If your v must be 1 and your w must be 2, then your first equation would become 2u must be equal to 4, you will know your u must be 2. So once you have the last variable in triangular system go backward, go backward, go backwards. You will solve the whole problem, sometimes you may need to do the calculations by hands. If that's the case, actually, you don't need to repeatedly write down those u v w, u v w, right? We only care about those coefficients, so maybe you may also want to do this, you collect all the numbers into a matrix, the left hand side part, the three columns are the coefficients for the left hand, left hand side columns. The right hand side part is the three numbers at the right hand side and then you'll start to do eliminations. You will first do some row operations to get rid of these two numbers to get rid of the numbers in the first columns, you keep only the first number there. Once you are done with this, now you have a smaller linear system to deal with. You have a smaller linear system and then you do the whole thing again. You'll try to eliminate all numbers but the first one in your first column or in this case, it's the second of the original column. So then you do that, you eliminate that number then you have the last equation. This means w should be equal to 2 and then you'll start to do backwards substitution until you get some kind of identity matrix and the left hand side, and then what it remains at the right hand side must be your solution. This simply tells you you must be too, v must be 1 and the w must be 2, right? That's your solution for this particular linear system, if you have a 4 by 4 linear system 10 by 10 linear system, you always do the same thing. You eliminate the first column, all the numbers in the first column except the first one, and then you get a smaller linear system, do this again, do this again, do this again until you have a definite solution for the left variable. Back substitution, back substitution, until you solve the whole problem. So that was the process of solving a non singular case with Gaussian elimination, it's also possible that you have a system which is singular, right? So Gaussian elimination if it is a good algorithm issues somehow help us identify singularity. You should you should find singularity during the process and the report saying that hey, this is a singular case so let's see whether that is possible. Suppose we have n equations, ideally we should get n pivots, okay? Because for the first one, we have a paper here for the second one, we have a pivot here for the third one we have a pivot here and so on and so on. So, if you have n equations, you should get n pivots, ideally, if so, we say the system is non singular and we may get exactly one solution. But the thing is that it's still possible for 0 to appear in the pivot position. Somehow this may create some problems, because if you say 0, who should be to is impossible. All the people's at some time may serve as the denominator of some calculations, so if your pivot is zero, that should create some problem. So this actually may or may not be a problem, that's the two examples, the first example here is that we have a non singular case. So this may be cured by row exchange, that's the fastest so I have a system like this, okay? So what I should do is to eliminate the first column except the first one, so after some observation, I know I should multiply the first row by 2 and add it into the second row, all right? And I should add the first row to the third row directly or use a multiply it by 1 so once I do that, we can see this part would disappear. But if I do the same thing if I multiply this by 2 and then to the subtraction, immediately we will see this number also disappear. Okay for your second row, the coefficient for V would also become 0, in that case here, you don't really have a triangular system, so this seems to be a problem. But for this particular case actually is not a problem, because it doesn't really matter which column which row is the third row, which row is the second row. So all you need to do is to replace or flip the two rows, you exchange them, so that you still get a linear system. So if that's the case, if a 0 appears on your pivot position but it may be solved with row exchange, that's not a problem. What may be a problem in this example, so again, you should multiply the first row by 2 and then do the subtraction. Or let's say you multiply it by negative 2 somehow, once you do that, this number disappear, this number also disappear. You also want to eliminate negative 2, so you multiply your first row by 1 add it to your second row. And once you do that, you may see this number disappear, this number also disappear. So in that case, there is no way for you to do any row exchange to get you a non zero number in that pivot position. If that's the case, now you this is singular so the process Gaussian elimination is actually very good, because during the process, whenever you see this guy is 0, if it is a pivot position, you look at his, pattern numbers. If any one of it is nonzero, you do the replacement, you do the exchange, if all of them are zero, then you're dead this is singular. So when the system is singular very quickly you may also see it may be inconsistent or consistent. Inconsistency means here, suppose you have a singular case and we have this number as negative6 this number as 7, then immediately we know there is no way for you to find a single w to satisfy both equations. The system is inconsistent and that there is no solution, suppose this number is actually six and what you need to do is to say w is to and then w is 2 allows you to determine what should be the outcome of 2u minus v As long as your v and u satisfies 2u plus v equals something, then each of them would be a good solution. So that means in this case, you have infinitely many solutions. If you were announcing if your singular system is consistent. Okay, so in all cases, whatever you have non singular case, singular consistent case, singular inconsistent case, Gaussian elimination would make a correct conclusion at the end. So that's why it is powerful, so it may be good, but maybe we also want to take a look at what's the computation time we need to spend, if we want to carry over the whole Gaussian elimination. Technically we want to see how complex this algorithm is, how much time we need. And if when we talk about how much time typically we don't really count the number of seconds to run an algorithm on the computer, because different computers may have different computing powers. Typically what we do is to do some kind of obstruction so that we may count something that may be identical among all computers. So that's the number of basic operations. We're going to count the number of elementary arithmetic operations. The process of Gaussian elimination when it is used to solve a n by n system, here and operation may include many things in this particular example, we would define operation as a division, or a combination of multiplication and subtraction. If you want to ask why we defined things in this way, I would say it doesn't really matter. If we really want to make into details, we need another one hour, two hour lectures about complexity, about algorithms that don't do that. Let's assume division is difficult, right, it takes some time, multiplication is easier, subtraction is even easier. So when we do a combination of multiplication and subtraction, we consider it as, difficult as doing a division. Okay, so let's see how many operations we need. So basically our first target is to eliminate all numbers except the first one in the first row. All right, so we need to complete the elimination for the first column, that's look at the second row, first. We need to do something to eliminate one number in the second row, right. So how much time do we need?. We need to do one division and many multiplication and subtraction. So this n is n minus 1 plus 1, except the first column, you have a minus 1 column at the left hand side and the 1 column at the right hand side. So these are the remaining left hand side columns or sorry, this is one and this is the remaining column at the right hand side, okay. So what, why do we need one division is because if your first row has 2u, if you're a second row has for you, do a division to understand that you need to multiply the first row by 2 before you may do some multiplication and subtraction. So one division happens on the first row, first column and for the remaining you have multiplication and subtraction. So to complete one row, you need n + 1 operations, there are n- 1 rows, right, so in total you have n + 1 for one row and you have n- 1 rows. So to complete everything for the first column, you need n squared minus 1 operations. For your second column, that's pretty much the same, except that the matrix is smaller, so you replace n by n minus 1. For your third column, n minus 1 becomes n minus 2, and so on. So the total number of operations you need to do the eliminations is n square plus or minus 1 square plus or minus 2 square that up to 1 square. You're going to minus 1, minus 1, minus 1,minus 1. So it would be this particular number minus n, so these numbers should be, this formula should be familiar enough to you. This is the formula for the sum of square numbers, okay. So after some arithmetic we would get this is our final outcome. To complete formula elimination we need n cube divided by 3 plus n squared divided by 2 minus 5 over 6 times n as the total number of operations we need. So if your only is quite large 10, 100, 1 million, pretty much you don't care the other numbers. You should say n cubed divided by three is a good rough estimation of the number of operations you need pretty much is n cubed. Once we are done with forward elimination, we get these triangular system right and then we need to do backwards substitution. So I'm going to skip the details here pretty much when you need to go one step further, the number of operations you need would be increased by one. So here you need one iteration, one step, here, you need two operations here, you needed three operations and so on and so on. You have unrolls, so in total you need roughly n square divided by 2 as the total number of patients you need for back substitution. So in total, you have n to the power of 3 divided by 3 plus n to the power of 2 divided by 2. As the total number of iterations you need, so if that's the case, when n is large enough, we only focus on n cube, because n cubed will dominate n square. So technically we would say the complexity of Gaussian elimination would be big all of unplug the power of 3. If you know what's the notation for big O, then you should feel comfortable here, if you don't, that's fine, we don't really have time to explain the notation. But that has a very simple straightforward meaning, it simply means that the computation time needed to complete this process is proportional to n to the power of 3. When we say the complexity of one procedure is big O of something, that basically means the computation time we need for that procedure is proportional to that particular term. Okay, so when you have more rows, more variables, you need more time definitely. And that relationship is n cube, okay. When you have more variables, the amount of time you need would increase in the shape of third order function, that's pretty much our estimation for the complexity of Gaussian elimination. So, you will see that Gaussian elimination forms some building blocks for example, the next week simplex method. So then we will go back to our discussion a little bit about when we run the simplex method was roughly the computation time. We need to expect, that's why we need to talk about complexity.