Every optimum so far has come out in whole units without anyone asking. The reason is a property of the matrix: every square submatrix of a node-arc incidence matrix has determinant zero, one or minus one, so Cramer's rule divides by one and a basic solution of whole data is whole. Drop the directions and the property fails — on an odd cycle the determinant is two and the optimal corner is genuinely halves.
Core ideas
This is the lesson the path's ordering exists for. Three ideas, and the third is the one that stops it becoming a slogan.
It is not enough that the determinant of the whole matrix be ±1, and it is not about the entries being 0 and ±1 either. Every square submatrix of every size must have determinant in {0, +1, −1}. On a four-by-five incidence matrix that is 120 submatrices up to size three, and the lab sweeps all of them and reports zero failures.
A basic solution solves B x_B = b for a square non-singular submatrix B of the constraint matrix. Cramer's rule gives each component as a ratio of determinants with det B underneath. If the data are whole, the numerator is whole; if det B = ±1, the division is exact. The corners are then lattice points, and a linear programme attains its optimum at a corner.
The +1 and −1 in each column are not decoration. Replace them with two +1s — the undirected incidence matrix — and the property fails on any cycle of odd length: the triangle's determinant is 2. The lab then solves a packing programme on that matrix and returns x = (1/2, 1/2, 1/2) worth 3/2, which no integer point reaches. Integrality is earned, and this is what earns it.
The material
The definition, then the theorem and its two-line proof, then the matrix that fails it and the halves it produces.
A matrix A is totally unimodular when every square submatrix of A — of every size, formed by choosing any rows and any equally many columns — has determinant 0, +1 or −1.
Every entry of such a matrix is itself a one-by-one submatrix, so every entry is 0, +1 or −1. The converse fails, and the failure is the interesting part of this lesson.
Let A be totally unimodular and b an integer vector. Then every basic feasible solution of Ax = b, x ≥ 0 is an integer vector.
The node-arc incidence matrix N of any directed network is totally unimodular. Hence every corner of the minimum-cost flow programme is whole, on whole supplies and whole capacities, with no integrality constraint written anywhere.
A basic solution takes a square non-singular submatrix B of the columns and sets x_B = B⁻¹b, with every other variable zero. By Cramer's rule the k-th component of x_B is det(Bₖ) / det(B), where Bₖ is B with its k-th column replaced by b.
B is a square submatrix of a totally unimodular matrix and is non-singular, so det(B) is +1 or −1. Bₖ has integer entries throughout — the columns of B are integer and b is integer — so det(Bₖ) is an integer. An integer divided by ±1 is an integer, and every component of x_B is therefore whole. The non-basic components are zero.
Nothing in this depends on the objective, so it holds at the optimum in particular; and since a bounded linear programme attains its optimum at a corner, the optimum is an integer point.
□
That the incidence matrix satisfies the condition is checkable rather than memorable, and the lab checks it. On the five-arc network from the minimum-cost flow lesson, N is four by five and the sweep runs every submatrix of size one, two and three — 20, then 60, then 40, which is 120 in all — and reports every determinant in {0, ±1}.
Now take the triangle on three vertices and build the undirected incidence matrix instead: +1 at both ends of each edge rather than +1 and −1. Nothing about the picture has changed. The matrix is three by three, and its determinant is 2.
The lab runs the same exact simplex on the same kind of programme and returns 1/2 three times, printed as a fraction. There is no rounding anywhere and nothing has gone wrong: (1/2, 1/2, 1/2) is a genuine corner of that polyhedron, and it is strictly better than any lattice point inside it.
This is the gap that the whole of Integer Programming is about, arriving here as a two-line consequence of one determinant. It is also the reason this course can be solved by the simplex method and that one cannot.
Do the same on the four-cycle. The undirected incidence matrix has determinant 0, the sweep finds nothing outside {0, ±1}, and the packing programme's corner is (1, 0, 1, 0) worth 2 — whole.
So it is not undirectedness as such that breaks integrality; it is the odd cycle. An even cycle is bipartite, and bipartite graphs are where the undirected incidence matrix stays totally unimodular. That observation is what makes the assignment problem behave, and it comes back on the matching lesson.
Two warnings about the direction of the theorem. It says total unimodularity is sufficient for integer corners, not necessary: plenty of programmes have integral polyhedra for other reasons. And it says nothing whatever about a programme whose matrix is not totally unimodular — such a programme may still happen to have a whole optimum on some instance, and that is luck rather than structure.
Interactive
Every square submatrix of a node–arc incidence matrix has determinant 0, +1 or −1 — and an odd cycle does not
Method
Build the matrix, check the condition, and then say which of the two conclusions you are entitled to.
Total unimodularity is a property of a matrix. Two different matrices can describe the same picture — the directed and undirected incidence matrices of the triangle are the standard example — and one of them is totally unimodular and the other is not.
Every entry must already be 0, +1 or −1, since each is a one-by-one submatrix. An entry of 2 anywhere settles the question immediately and you have spent no effort.
Every two-by-two, then every three-by-three. A failure is not a verdict of “probably not”: it is a specific submatrix with a specific determinant, and quoting it is the difference between a check and an impression.
Integer right-hand side gives integer corners. On fractional supplies you get fractional corners from a totally unimodular matrix too, and the theorem never claimed otherwise.
Failure removes the guarantee; it does not prove a fractional optimum exists. The odd cycle really does produce one, and finding it is what turns the failed check into something you have learned.
The triangle throughout. The only thing that changes is whether each column gets a plus and a minus or two pluses, and every number below is read off the sweep and the exact simplex.
The pair of three-by-three matrices differs in three minus signs and in nothing else, and that is the whole of the difference between a problem the simplex method settles and a problem that needs a search. Worth staring at for a minute.
For a rehearsal, take the four-arc network from the minimum-cost flow lesson and use the lab's row and column pickers to find a three-by-three submatrix with determinant −1, then one with determinant 0. Both exist; predicting which is which before you press the button is the exercise.
The harder rehearsal: build the undirected incidence matrix of the five-cycle and sweep it. It fails, for the same reason the triangle does, and the half-integral corner is worth 5/2 against a best whole answer of 2. Then do the six-cycle and watch the failure disappear.
You should be able to define total unimodularity over all square submatrices, build both incidence matrices of a small graph, explain where det(B) = ±1 enters the proof, say why an integer right-hand side is part of the hypothesis, and exhibit the odd cycle's half-integral corner.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.