Alright, so that was about total unimodularity in general. Now let's come back to our MCNF problem. Obviously, I later will convince you that for any MCNF problem is coefficient metrics is total unimodular. So it's totally unimodular, maybe a fact. But how is it possible for us to take a look at all those possible square submatrices? Maybe it's easier to start from the sufficient condition. If you have a matrix A, such that all, it's elements are either one zero or negative one, okay? So that's the first condition. Second, each column contents at most two non zero elements, okay? So there must be one or negative one. And we may split roles to two groups, so that for each column, if the two non zero values are in the same group, it must be the case that they are different. And if they are different, they must be in the same group. So this is an even only if condition, alright? So if your matrix A, satisfies all these three conditions, then you're A is totally unimodular. So to prove this, this requires some induction on the dimension of square submatrices. So I'm going to skip this part if you are interested. Well, there are all kinds of proofs online, so you may take a look at them. I'm going to use our example to show you when these three things are satisfied, we may say A is totally unimodular. So our formulation was here, right? Our focus would be on our equality constraints, which are from flow conservation or flow balancing. So, first, all the coefficients here. Okay, so for coefficient is just here, Okay? All the values are either zero one or negative one. So that's our condition. One for condition, two it mentions about columns. For each column, we have only two non zero values. That's also good. The last condition says that we may split the rows into two groups, so that different values are in the same group. Or if two values are in the same group, they must be different, okay? So in that case, what we want to do is to split, for example, here. So first you understand that because the two values must be one one and one minus one. So in that case when they fall in the same group, naturally, they are different. Alright, here they are different. But what's going to happen if they are in different groups, are well then that violates the conditions. Because the conditions says if they are in the same group, they must be identical if they were different groups, that means they must be identical according to that even only if condition. So here we are, in a danger that seems that this coefficient matrix does not satisfy proposition two. But the interesting thing is that, if you really need to solve this problem with your simplex method, you see that these two numbers should be positive instead. So actually you would flip the sign for your demand notes. This would become positive, positive, positive, positive, negative, positive and negative. Then very quickly you would see if they are in the same group, they are still of different signs. But if now they are in different groups, they all have the same number, same values for those two non zero things. So once we see this, now we complete our argument for the constraint coefficient for any MCNF problem, it must be totally unimodular. Alright? So if you don't have these capacity constraints, your coefficient matrix would fit the sufficient condition and then it is totally unimodular. A solution generated by the simplex method or whatever method, is going to be in teacher, this problem can give you integer variables for free. If yours is actually not, if you guys actually not infinite. So that means you actually have some more constraints there. In this case, you need some more arguments. You don't just apply proposition to directly, but still, this can be done and I'm going to skip this part, okay? I'm going to go to the conclusions directly which says, for any MCNF problems that is feasible, the simplex method or any other method that talks about basis non basis gives you an interior optimal solution directly. So the discussion about total unimodularity okay, is to help us understand why, for many practical applications of MCNF, we always set variables to be integers and then get integer solutions directly. This is due to the fact that the coefficient matrix of MCNF is totally unimodular. Alright, so this is the key. There are some parts that we skipped, for example, this one. But it's not going to hurt our appreciation on these nice properties, okay? There are just few formulations, few problems that has this property. If you randomly formulate a linear program, in most cases, you don't have this property, alright? So that's why this property for MCNF is nice and valuable, because we happen to have this property. Somehow, that makes MCNF and its variants widely applied in practice because of these nice property, okay? So later we will see all kinds of variants, make some introduction and help you get into the ideas of network flow problems.
