We show that the linear discrepancy of a totally
unimodular
m×
n matrix
A is at most
$
{\text{lindisc}}{\left( A \right)} \leqslant 1 - \frac{1}
{{n + 1}}
$
{\text{lindisc}}{\left( A \right)} \leqslant 1 - \frac{1}
{{n + 1}}
|
.
This bound is sharp. In particular, this result proves
Spencer$
{\text{lindisc}}(A) \leqslant {\left( {1 - \frac{1}
{{n + 1}}} \right)}
$
{\text{lindisc}}(A) \leqslant {\left( {1 - \frac{1}
{{n + 1}}} \right)}
herdisc(A) in the special case of totally
unimodular matrices. If m$
{\text{lindisc}}{\left( A \right)} \leqslant 1 - \frac{1}
{m}
$
{\text{lindisc}}{\left( A \right)} \leqslant 1 - \frac{1}
{m}
.
Finally we give a characterization of those totally
unimodular matrices which have linear discrepancy
$
1 - \frac{1}
{{n + 1}}
$
1 - \frac{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.
Mathematics Subject
Classification (2000): 11K38 - 90C05 - 05C65
* A preliminary version of this result appeared at
SODA 2001. This work was partially supported by the graduate
school 
Effiziente Algorithmen und Multiskalenmethoden
,
Deutsche Forschungsgemeinschaft 
A similar result has been independently obtained
by T. Bohman and R. Holzman and presented at the Conference on
Hypergraphs (Gyula O. H. Katona is 60), Budapest, in June
2001.