Hello everybody, welcome back. Today we're talking more about linear programming, well actually we're not. We're looking at sort of a simpler problem first. So linear programming talks about dealing with systems of linear inequalities. Today we're going to look at sort of a simple special case of this where we look at systems of linear equalities. So for example we have a system of linear equalities x + y = 5, 2x + 4y = 12 and we'd like to be able to solve this for x and y. So the very general way to do this is by what's known as the method of substitution. You use the first equation to solve for one variable in terms of the others. You then take that variable and substitute it into the other equations. You now have a bunch of equations with n-1 variables and you recursively solve those. Then once you have the answer to those equations, you substitute them back into the first equation to get the value of the initial variable. Okay, let's see how this works in practice. So, x + y = 5. 2x + 4y = 12. Using the first equation, we solve x as 5- y. We substitute that into the second equation and we find that 12 = 10 + 2y. Solving that for y, we find out that y = 1. And substituting back into the first equation, x = 5- 1 = 4. So, x = 4y = 1, that's the solution to the system. Now, just to make sure we're on the same page, if we have the system x + 2y = 6, and 3x- y = -3, what is the value of x in the solution to that system? Well the answer is 0 here. So from the first equation, we get x = 6- 2y. Substituting into the second, we get that -3 is 18-7y. Solving that tells us that y = 3, so x = 6- twice 3 = 0. And that's the answer. Okay, so that was our first example. Let's look at another example. We have a system of linear equations x + y + z = 5. 2x + y- z = 1. So we solve this by substitution, great. From the first equation, x = 5- y- z. We substitute that into the second equation and we solve for y. We find that y = 9 + 3z. Great, we now know what y is and we want to solve for z but we can't. There are no equations left. We've already used the first equation to solve for x and the second to solve for y. We can't solve for z because there's nothing left. But this is actually fine for us. It turns out that any value that we assign z will give us an actual solution. You give me any value for z, we set y = 9 + 3z and then x is 5- y- z or -4- 4z. And any value of z gives us this solution. So there's an entire family of solutions. We can let z be a free variable. And for any value of z, we have a unique solution. So in general, your solution set will not necessarily be a point, but it will be a subspace. You'll have some free variables and no matter what settings you give those, your other variables will be functions of your free variables. Now this subspace has a dimension which is just the number of free variables, the number of parameters you need to describe a point on it. And generally speaking, each equation that you have gives you one variable in terms of the others. And so generally speaking, the dimension of your set of solution is going to be the total number of variables minus the number given in terms of others. So the total number of variables minus the number of equations. So generally speaking, if you have n equations and n unknowns, there'll be no free variables left and you'll have a unique solution. However if you have n+1 equations and n unknowns, the first n of your equation solves for the unique solution and then the extra equation probably is something that isn't satisfied by that solution. So generally if you've got too many equations, there are no solutions to the system. However, if you have n- 1 and n unknowns, you generally solve those and you'll still have one pre-variable left, so generally speaking, you'll have a full dimension one subspace. You'll have a line as your solution instead of just a point. Okay, so in summary, we can solve systems of linear equations using the method of substitution. And generally speaking, and this isn't always the case. But generally, each equation reduces the number of degrees of freedom by one. Now if all you want to do is solve systems of linear equations, you could basically stop here. But we want to do more than that. So next time what we're going to do is we're going to talk about how to systematize this whole thing, and simplify the notation sum to make this into an honest algorithm that we're going to discuss. And so, when you want to talk about how to tell your computer to solve systems of linear equations, that is what we're going to talk about in the next lecture. So I'll see you then.
