Hello everybody, welcome back to our Linear Programming. Today we're going to talk about Gaussian Elimination. So the basic idea is that last time we talked about how to solve linear systems by substitution. Today, we're going to make it into an algorithm. So remember last time we could solve systems of linear equations using this method of substitution. And to begin with we'd like to simplify the notation a little bit because the way we did it you had to write down these full equations x+y = 5 2x+4y- 12 these have variables and addition signs and equality signs and all this mess. The only thing that really matters are the coefficients of these equations. So what we're going to do is we're going to simplify notation, and just store these coefficients in what's known as an augmented matrix. That's a matrix with this little bar coming down in the middle of the entries. So here, each row is going to correspond with single equation and the entries in that row are going to be the coefficients. So the first row 1, 1, 5 translates to 1 times x plus 1 times y equals 5 x plus y equals 5. The second row 2, 4, 12 means that 2x plus 4y equals 12. And so, this little matrix is sort of just a convenient way of storing that system of linear equations. Now, one complication that this method runs into is when we're storing things in this matrix. How do we implement substitution? How do we solve for x? For example, there's a sense in which we can't write a row that corresponds to the equation x = 5- y. Every row corresponds to an equation where x and y are on the same side of the equality. So this sort of doesn't work. On the other hand, the row 1, 1, 5 is almost as good, it corresponds to the equation x + y = 5 which is equivalent. The next question we ask ourselves is how do we substitute this into the second equation? Because once again, the immediate thing you get when you substitute has Xs and Ys on sort of. I guess they're still in the same side but it's got constants on the wrong side of the equation now. And so you can't substitute directly but really you can do something almost as good. What you can do is the substitution was just to get rid of the x's in that second equation and you can do that by subtracting. If you subtract twice the equation (2x+y=2) times the equation (x+y=5) from the equation (2x+4y=12). That tells you that (2y=2) which is exactly what you would have gotten from substitution and this corresponds to a very nice operation on the matrix rows. You just subtract twice the first row from the second to get the row corresponding to this guy. Okay, so we're given this augmented matrix and what we're going to do is we're going to manipulate it. We're going to use what are called Basic Row Operations. These are ways of transforming your matrix to give you an equivalent system of equations. Now the first piece is addition, just what we just saw. You add or subtract a multiple of one row from another. So for example, we subtract twice the first row from the second and 2, 4, 12 becomes 0, 2, 2 which is good. Next off though we have 2y = 2, we want to change that to y = 1, so to do that we need to use scaling. We need to multiply or divide a row by a non-zero constant and that's just multiplying the equation by a constant. So we should be good. So if we divide the second row by two instead of getting 0, 2, 2 it becomes 0, 1, 1 y equals 1. Now in some sense these two operations are enough but for bookkeeping purposes we might want to reorder the way in which we list the rows. So a final operation is to swap the order of two of the rows. So just list the second row up top and the first row down bottom. This clearly doesn't really effect anything, we're just sort of listing our equations in another order. So these are the three basic row operations. And what we're going to do is we're going to combine them into an algorithm called row reduction, or sometimes Gaussian elimination. We're going to use these operations to put our matrix in a simple standard form. And the idea is actually very simple, we're just going to simulate the method of substitution. Okay, so let's consider this example. We have a big matrix here, it corresponds to a system of three equations in four unknowns, which I'll call x, y, z and w and we'd like to solve them. So method of substitution, what do we do? We use the first equation to solve for the first variable x. And in some sense this first equation 2x + 4y- 2z = 2 already implicitly solves for x in terms of the other variables. But for simplicity we'd like to rescale it so that the x entry is 1, so we divided the row by two. And now it says x + 2y- z = 1 or equivalently, x = 1- 2y + z. We now want to substitute that value into the other equations, which we do by adding this row to others, to clear out the x entries. So we add the first row to the second and subtract twice the first row from the third. And now there are no other entries in that column in any of our other rows. Okay, so now we're done with X we want to solve for the next variable Y using the two other equations. We actually can't use the second to solve for Y but there's no Y in that equation the entry is 0. But we can use the third equation so what we're going to do for book keeping purposes we're going to swap the second and third rows just so that the, row we're using to solve for y is up top. We now want to solve for the second variable by which we mean rescale so that entry is 1, so we divide by -2. And now, we want to substitute this value into the other equations. So we subtract twice the second row from the first and actually the third row is okay. Now the thing to note is we can't actually solve for z. The last equation doesn't have z. The first two equations have z terms in them, but we've already used those equations to solve for x and y. So actually, what we're going to do here, is we're going to skip Z and move on to W. We can solve for w in terms of this variable, so we divide the last row by minus 2. We get the equation w = 0 and we substitute that into the other equation. So we subtract twice the third row from the first and then add the third row to the second. And now we're actually done, this is basically as simple as our matrix is going to get. But now that we have this, it's actually very easy to read off the solutions. We have this matrix, it corresponds to the equations x + z = -1, y- z = 1, and w = 0. And here you can basically read off the solution. For any value of z, we have a solution x = 1- z, y = 1 + z and w = 0. And that's the general solution. Great, so how do we RowReduce a matrix in general? We're going to do is we're just going to take the leftmost non-zero entry. This is the thing we're going to solve for. We swap that row to the very top of the matrix just for bookkeeping purposes. That leftmost entry we're going to call pivot, we're going to use it to clear out the other entries in it's column. We rescale the row to make that entry one because we want to actually solve for that variable. We then subtract that row from all the others to make the other entries in that column 0. Then, we just substitute that into the other equations and we're going to repeat this well, with slight modifications. We want the leftmost non-zero entry not already in a row with the pivot, we then swap that row to be the top of the non-pivot rows. We make a new entry a pivot, we rescale, we clear out the other columns and we keep repeating until all of the non-zero entries are in pivot rows and then we're done. Once you have that it's actually pretty easy to read off the answer. Each row is going to have one pivot entry and maybe a few other non-pivot entries. This will give an equation that writes the pivot variable in terms of a bunch of non-pivot variables. Now, there's a special case if there's a pivot in the units column. That means that we have the equation 0 = 1, and if that happens we have a contradiction and there are no solutions. But otherwise, the non-pivot variables, the variables corresponding to columns with no pivot in them, these are actually free variables. We can set those to whatever we want and then once we've done that each of our rows tells us what the pivot variables should be in terms of the non-pivot variables and that's it. One final thing to discuss is the runtime of this operation. If you have n equations and n variables, there are a minimum of n and m pivots. Whenever you find a pivot, you need to subtract a multiple of that row from each other row. Now each row has n entries that you need to deal with this subtraction for and there are m rows so that takes O of m, n time. And so the total run time is O of n times m times the minimum of n and m. And this is pretty good, it's polynomial n and m. You could maybe expected you a little bit better and in fact there are sophisticated algorithms that do that. But for practical purposes, this is actually a pretty good runtime and it's a very usable algorithm. So that's basically all for a sort of linear algebra sidebar. On next lecture, we're going to go back to talk about linear program, the systems of linear inequalities and how to deal with them. So until next time.
