Linear Discrepancy of Basic Totally Unimodular Matrices

Benjamin Doerr^{∗}

Mathematisches Seminar II, Christian–Albrechts–Universität zu Kiel Ludewig–Meyn–Str. 4 24098 Kiel, Germany

                  bed@numerik.uni-kiel.de

Submitted: April 6, 2000; Accepted: September 13, 2000 AMS Subject Classification: Primary 11K38

Abstract

We show that the linear discrepancy of a basic totally unimodular matrix A ∈ ℝ^{m×n} is at most 1 − \frac{1}{n+1}. This extends a result of Peng and Yan. AMS Subject Classification: Primary 11K38.

1 Introduction and Results

In [PY00] Peng and Yan investigate the linear discrepancy of strongly unimodular 0, 1 matrices. One part of their work is devoted to the case of basic strongly unimodular 0, 1 matrices, i. e. strongly unimodular 0, 1 matrices which have at most two nonzeros in each row. The name ’basic’ is justified by a decomposition lemma for strongly unimodular matrices due to Crama, Loebl and Poljak [CLP92].

A matrix A is called totally unimodular if the determinant of each square submatrix is −1, 0 or 1. In particular, A is a −1, 0, 1 matrix. A is strongly unimodular, if it is totally unimodular and if this also holds for any matrix obtained by replacing a single non-zero entry of A with 0. Note that for matrices having at most two non-zeros per row both notions coincide.

∗supported by the graduate school ‘Effiziente Algorithmen und Multiskalenmethoden’, Deutsche Forschungsgemeinschaft

The linear discrepancy of an m × n matrix A is defined by

lindisc(A) := max_{p∈[0,1]^{n}} min_{χ∈{0,1}^{n}} ∥A(p − χ)∥_{∞}.

The objective of this note is to show

Theorem. Let A be a totally unimodular m×n matrix which has at most two non-zeros per row. Then

lindisc(A) ≤ 1 − \frac{1}{n+1}.

Our motivation is two-fold: Firstly, we extend the result in [PY00] to arbitrary totally unimodular matrices having at most two non-zeros per row. We thus expand the assumption to include matrices with entries of −1, 0, and 1. This enlarges the class of matrices for which Spencer’s conjecture lindisc(A) ≤ 1 − \frac{1}{n+1} herdisc(A) is proven^{1}. Secondly, our proof is shorter and seems to give more insight in the matter. For the problem of rounding an [0, 1] vector p to an integer one we provide a natural solution: We partition the weights p_{i}, for i ∈ [n] := {1, …, n}, into ’extreme’ ones close to 0 or 1 and ’moderate’ ones. The extreme ones will be rounded to the closest integer. The moderate ones are rounded in a balanced fashion using the fact that totally unimodular matrices have hereditary discrepancy at most 1. The latter is restated as following result:

Theorem (Ghouila-Houri [Gho62]). A is totally unimodular if and only if each subset J ⊆ [n] of the columns can be partitioned into two classes J_{1} and J_{2} such that for each row i ∈ [m] we have | ∑_{j∈J_{1}} a_{ij} − ∑_{j∈J_{2}} a_{ij}| ≤ 1.

This approach is a main difference to the proof [PY00], where the theorem of Ghouila-Houri is applied to the set of all columns only.

2 The Proof

Let p ∈ [0, 1]^{n}. Without loss of generality we may assume p ∈ [0, 1[^{n} (if p_{i} = 1 for some i ∈ [n], simply put χ_{i} = 1). For notational convenience let P := {p_{j}|j ∈ [n]} denote the set of weights. For a subset S ⊆ [0, 1] write J(S) := {j ∈ [n]|p_{j} ∈ S}.

1We will not use this notion in the following explicitly, but an interested reader might like to have this background information: The discrepancy disc(A) := min_{χ∈{−1,1}^{n}} ∥Aχ∥_{∞} of a matrix A describes how well its columns can be partitioned into two classes such that all row are split in a balanced way.

The hereditary discrepancy herdisc(A) of A is simply the maximum discrepancy of its submatrices.

For k ∈ [n + 1] set A_{k} := [\frac{k−1}{n+1}, \frac{k}{n+1}[. For k ∈ [⌊\frac{n+1}{2}⌋] set B_{k} := A_{k} ∪ A_{n+2−k}. From the pigeon hole principle we conclude that there is a k ∈ [⌊\frac{n+1}{2}⌋] such that |P ∩ B_{k}| ≤ 1 or

n + 1 is odd and P ∩ A_{\frac{n}{2} +1} = P ∩ [\frac{1}{2} − \frac{1}{2(n+1)}, \frac{1}{2} + \frac{1}{2(n+1)}[ = ∅. The latter case is solved by simple rounding, i. e. for χ ∈ \{0, 1\}^{n} defined by χ_{j} = 0 if and only if p_{j} ≤ \frac{1}{2} we have ∥A(p − χ)∥_{∞} ≤ 1 − \frac{1}{n+1}.

Hence let us assume that there is a k ∈ [⌊\frac{n+1}{2}⌋] such that |P ∩ B_{k}| ≤ 1. By symmetry we may assume that P ∩ A_{k} = ∅ (and thus P ∩ A_{n+2−k} may contain a single weight). Set X_{0} := J([0, \frac{k−1}{n+1}[) = J(A_{1} ∪ … ∪ A_{k−1}), the set of columns with weight close to 0, M := J([\frac{k}{n+1}, \frac{n+2−k−1}{n+1}[) = J(A_{k+1} ∪ … ∪ A_{n+1−k}), the set of columns with moderate weights, M_{0} := J(A_{n+2−k}) containing the one exceptional column, if it exists, and finally X_{1} := J([\frac{n+2−k}{n+1}, 1[) = J(A_{n+3−k} ∪ … ∪ A_{n+1}), the set of columns with weight close to 1. Note that [n] = X_{0} ˙∪M ˙∪M_{0} ˙∪X_{1}.

As A is totally unimodular and has at most two non-zeros per row, by Ghouila-Houri’s theorem there is a χ′ ∈ {0, 1}^{M∪M_{0}} such that the following holds: For each row i ∈ [m] having two non-zeros a_{ij_{1}}, a_{ij_{2}}, (j_{1} ≠ j_{2}), in the columns of M ∪ M_{0} we have χ′_{j_{1}} = χ′_{j_{2}} if and only if a_{ij_{1}} ≠ a_{ij_{2}}. Eventually replacing χ′ by 1 − χ′ we may assume χ′_{j} = 1 for all (which is at most one) j ∈ M_{0}. As any two weights of p_{|M∪M_{0}} have their sum in [\frac{2}{n+1}, 2 − \frac{1}{n+1}[ and their difference in ]−\frac{n}{n+1}, \frac{n}{n+1}[, we conclude | ∑_{j∈M∪M_{0}} a_{ij}(p_{j}−χ′_{j})| ≤ 1 − \frac{1}{n+1} for all rows i that have two non-zeros in M ∪ M_{0}.

Let χ ∈ {0, 1}^{n} such that χ_{j} = 0, if j ∈ X_{0}, χ_{|M∪M_{0}} = χ′ and χ_{j} = 1, if j ∈ X_{1}. This just means that the extreme weights close to 0 or 1 are rounded to the next integer, and the moderate ones are treated in the manner of χ′. Note that an exceptional column is treated both as extreme and moderate.

We thus have

(∗) |p_{j} − χ_{j}| ≤ \{ \begin{matrix}\frac{k−1}{n+1} & & x ∈ X_{0} ∪ X_{1} \\ \frac{k}{n+1} & if & x ∈ M_{0} \\ 1 − \frac{k}{n+1} & if & x ∈ M \end{matrix} .

Let us call a row with index i ’good’ if |(A(p − χ))_{i}| ≤ 1 − \frac{1}{n+1}. Then by (∗) all rows having just one non-zero are good, as well as those rows having two non-zeros at least one thereof in X_{0} ∪ X_{1}. Rows having two non-zeros in M ∪ M_{0} were already shown to be good by construction of χ′. All rows being good just means ∥A(p − χ)∥_{∞} ≤ 1 − \frac{1}{n+1}. This ends the proof.

References

[CLP92] Y. Crama, M. Loebl, and S. Poljak. A decomposition of strongly unimodular

matrices into incidence matrices of digraphs. Disc. Math., 102:143–147, 1992.

[Gho62] A. Ghouila-Houri. Caractérisation des Matrices Totalement Unimodulaires. C. R. Acad. Sci. Paris, 254:1192–1194, 1962.

[PY00] H. Peng and C. H. Yan. On the discrepancy of strongly unimodular matrices. Discrete Mathematics, 219:223–233, 2000.