Linear discrepancy of totally unimodular matrices

We show that the linear discrepancy of a totally unimodular m × n matrix A is at most lindisc(A) ≤ 1 -1/n+1. This bound is sharp. In particular, this result proves Spencer's conjecture lindisc(A) ≤ (1 -1/n+1)herdisc(A) in the special case of totally unimodular matrices. If m ≥ 2, we also show lindisc(A) ≤ 1-1/m. Finally we give a characterization of those totally unimodular matrices which have linear discrepancy 1 - 1/n+1: Besides m × 1 matrices containing a single non-zero entry, they are exactly the ones which contain n + 1 rows such that each n thereof are linearly independent. A central proof idea is the use of linear programs.