Lemma on partitioning columns of TU matrices

51 Views Asked by At

I'm currently looking at Lemma 5 in András Mészáros's A note on disjoint dijoins [PDF].

Lemma: For a Totally Unimodular (TU) matrix $A$ and positive $k \in \mathbb{Z}$, if the sum of columns of $A$ have entries which are all divisible by $k$, then there is a partition of the columns into $k$ classes such that the sum of the columns in each class is the same.

Supposedly, this is taken from Alexander Schrijver's Theory of Linear and Integer Programming, but I cannot find it. Does anyone have insight on the proof of this lemma?

1

There are 1 best solutions below

0
On BEST ANSWER

It was based on Lemma 19.4 in the textbook, where we instead have that $Ay = 1$. Since $x_i \geq 0$ and $y = x_1 + \dots + x_k$, the $x_i$ represent a partition.