[SOUND] In this section, we will talk about complementary slackness. Complementary slackness are a set of conditions that enable you, given, Solution X for a primal L-P, and another solution for a dual L-P, to try to see whether they are both optimal. So for that, it is useful to review the weak duality proof in one line. The cum of Ci Xi is, at most, the sum of i of A transpose y. The eight rule of this, times xi which is the sum of a j of e x y j, which is less than the reported sum of b j y j. That's the weak duality proof in one line, however, this proof is valid for any feasible solution x to the primal, and any feasible solution y to the dual. Now, imagine X is an optimal solution of the primal linear program. Imagine Y is an optimal solution of the dual linear program. Then, we know by strong duality that the sum of ci xi is equal to the sum of bjyj. The sum of Ci Xi is equal to the sum of Bj Yj. The sum of Ci Xi is equal to the sum of Bj Yj. But we already know by weak duality that we have a less then near equal here, equal, less near equal, what can we deduce? If the first and the last term are equal, then every single one of these inequalities must be an equality. None of them can be strict. And so what this means is that when we replaced ci by A transposed y i, we used the fact that ci was less than this. Well that upper bound that constraint of a dual must have been true with equality. Otherwise we could never end up with something that was equal to what we started from. So what this means is that for every I Ci Xi must be equal to A transposed y, i Xi. And for every j, similarly, b j y j is equal to this similar expression. So if x is optimal for p, y optimal for d, we have all these conditions that are true at home. Let's look at them. Let's look at the conditions for x i. Ci xi equals, written in form sum over j of aijyj times xi. This is an equality. But the constraint of the duo Ci is less than or equal to that sum. And yet we have an equality. So it must be that Ci is really equal to that unless, of course, unless Xi is zero. If Xi is zero, then these two things can be different. So, I just argued that either Ci is equal to the sum of aijyj or Xi equals 0. When you have a pair of optimal primal and dual solutions, for every i, either xi is equal to 0 or the corresponding constraint in the dual is true with equality, with equality. Similarly, if we look at the conditions for bj written in full bjyj equals sum of i of aij times xi yj. But by the constraint of the primal bj is less than or equal to the sum of i of aijxi so the only way in which this can hold this is if bj is exactly equal to the sum of the i of aijxi unless yj equals 0 so. If X is an optimal solution of the primal and Y an optimal solution of the dual, then for every J, Y J is equal to zero, the dual variable. Or the corresponding constraint of the primal holds with equality. So if X is optimal for the primal and Y optimal for the dual, then for every i, we have at least one of the two conditions. One, they are both equal to zero or the corresponding constraints hold with equality, and similarly for the dual. Now these conditions of course, if they hold then we can go back through the weak duality proof. And again, we have that every inequality along the away is an equality. And so x is optimal for the primal. And the y optimal for the dual. So this conditions are very useful for testing optimality, and also for working towards near optimality when we design approximation algorithms.