% A LaTeX file for a 4 page document
% Eine kleine Bemerkung zur linearen Diskrepanz
% submitted to ElJC 06.04.2000
% revised 17.05.2000
% revised 31.07.2000
% final preparation 04.09.2000
\documentclass[a4paper,12pt]{article}
\usepackage{a4wide}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\DeclareMathOperator{\lindisc}{lindisc}
\DeclareMathOperator{\herdisc}{herdisc}
\DeclareMathOperator{\disc}{disc}
\setlength{\parskip}{2ex plus0.2ex minus0.2ex}
\setlength{\parindent}{0cm}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem*{theoremnn}{Theorem}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\la}{\left|}
\newcommand{\ra}{\right|}
\textwidth6.2in
\textheight8.5in
\begin{document}
\title{Linear Discrepancy of Basic Totally Unimodular Matrices}
\date{}
\author{Benjamin Doerr\thanks{supported by the graduate school `Effiziente
Algorithmen und Multiskalen\-methoden', Deutsche
Forschungsgemeinschaft}\\Mathematisches Seminar II,
Christian--Albrechts--Universit\"at zu Kiel \\Ludewig--Meyn--Str. 4 \\24098
Kiel, Germany\\ \texttt{bed@numerik.uni-kiel.de} \vspace{1ex}\\ Submitted:
April 6, 2000; Accepted: September 13, 2000\\ AMS Subject Classification:
Primary 11K38}
\maketitle
\begin{abstract}
We show that the linear discrepancy of a basic totally unimodular matrix $A
\in \R^{m \times n}$ is at most $1-\frac 1 {n+1}$. This extends a result of
Peng and Yan.
\vspace{1ex}
\noindent {\em AMS Subject Classification: }Primary 11K38.
\end{abstract}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7} (2000),
\#R48\hfill}
\thispagestyle{empty}
%\newpage
\section{Introduction and Results}
In \cite{pylind} Peng and Yan investigate the linear discrepancy of strongly
unimodular $0,1$ matrices. One part of their work is devoted to the case of
{\em basic} strongly unimodular $0,1$ matrices, i.~e. strongly unimodular $0,1$
matrices which have at most two non-zeros in each row. The name 'basic' is
justified by a decomposition lemma for strongly unimodular matrices due to
Crama, Loebl and Poljak \cite{crama}.
A matrix $A$ is called {\em 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 {\em 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.
The {\em linear discrepancy} of an $m \times n$ matrix $A$ is defined by
$$\lindisc(A) := \max_{p \in [0,1]^n} \min_{\chi \in \{0,1\}^n}
\|A(p-\chi)\|_{\infty}.$$
The objective of this note is to show
\begin{theoremnn}
Let $A$ be a totally unimodular $m \times n$ matrix which has
at most two non-zeros per row. Then $$\lindisc(A) \le 1 - \tfrac 1
{n+1}.$$
\end{theoremnn}
Our motivation is two-fold: Firstly, we extend the result in \cite{pylind} 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) \le 1 - \frac 1 {n+1} \herdisc(A)$ is proven\footnote{We 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_{\chi \in \{-1,1\}^n} \|A \chi\|_\infty$ 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.}. 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 \in [n] := \{1, \ldots, 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:
\begin{theoremnn}[Ghouila-Houri \cite{ghou}]
$A$ is totally unimodular if and only if each subset $J \subseteq [n]$ of
the columns can be partitioned into two classes $J_1$ and $J_2$ such that for
each row $i \in [m]$ we have $| \sum_{j \in J_1} a_{ij} - \sum_{j \in J_2}
a_{ij} | \le 1$.
\end{theoremnn}
This approach is a main difference to the proof \cite{pylind}, where the theorem
of Ghouila-Houri is applied to the set of all columns only.
\section{The Proof}
Let $p \in [0,1]^n$. Without loss of generality we may assume $p \in [0,1[^n$ (if
$p_i = 1$ for some $i \in [n]$, simply put $\chi_i = 1$). For notational
convenience let $P := \{p_j| j\in [n]\}$ denote the set of weights. For a
subset $S \subseteq [0,1]$ write $J(S) := \{j \in [n]|p_j \in S\}$.
For $k \in [n+1]$ set $A_k := \left[\frac{k-1}{n+1}, \frac k {n+1}\right[$. For
$k \in \left [ \lf \frac{n+1} 2 \rf \right ]$ set $B_k := A_k \cup A_{n+2 -k}$.
{}From the pigeon hole principle we conclude that there is a $k \in \left [\lf
\frac{n+1} 2 \rf\right ]$ such that $|P \cap B_k| \le 1$ or $n+1$ is odd and
$P \cap A_{\frac n 2 +1} = P \cap \left[\frac 1 2 - \frac 1 {2(n+1)}, \frac 1 2
+ \frac 1 {2(n+1)}\right[ = \emptyset$. The latter case is solved by simple
rounding, i.~e. for $\chi \in \{0,1\}^n$ defined by $\chi_j = 0$ if and only if
$p_j \le \frac 1 2$ we have $\|A(p-\chi)\|_\infty \le 1 - \frac 1 {n+1}$.
Hence let us assume that there is a $k \in \left [\lf \frac{n+1} 2 \rf\right ]$
such that $|P \cap B_k| \le 1$. By symmetry we may assume that $P \cap A_k =
\emptyset$ (and thus $P \cap A_{n+2-k}$ may contain a single weight). Set $X_0
:= J(\left[0,\frac{k-1}{n+1}\right[) = J(A_1 \cup \ldots \cup A_{k-1})$, the set
of columns with weight close to $0$, $M :=
J(\left[\frac{k}{n+1},\frac{n+2-k-1}{n+1}\right[) = J(A_{k+1} \cup \ldots \cup
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(\left[\frac{n+2-k}{n+1},1\right[) = J(A_{n+3-k} \cup \ldots \cup A_{n+1})$,
the set of columns with weight close to $1$. Note that $[n] = X_0 \dot\cup M
\dot\cup M_0 \dot\cup X_1$.
As $A$ is totally unimodular and has at most two non-zeros per row, by
Ghouila-Houri's theorem there is a $\chi' \in \{0,1\}^{M \cup M_0}$ such that the
following holds: For each row $i \in [m]$ having two non-zeros $a_{ij_1},
a_{ij_2}$, $(j_1 \neq j_2)$, in the columns of $M \cup M_0$ we have $\chi'_{j_1}
= \chi'_{j_2}$ if and only if $a_{ij_1} \neq a_{ij_2}$. Eventually replacing
$\chi'$ by $1 - \chi'$ we may assume $\chi'_j = 1$ for all (which is at most
one) $j \in M_0$. As any two weights of $p_{|M \cup M_0} $ have their sum in
$\left[\frac 2 {n+1}, 2 -\frac 1 {n+1}\right[$ and their difference in $\left] -
\frac{n}{n+1},\frac{n}{n+1}\right[$, we conclude $|\sum_{j \in M \cup M_0}
a_{ij} (p_j - \chi'_j)| \le 1 -\frac 1 {n+1}$ for all rows $i$ that have two
non-zeros in $M \cup M_0$.
Let $\chi \in \{0,1\}^n$ such that $\chi_j = 0$, if $j \in X_0$, $\chi_{|M \cup
M_0} = \chi'$ and $\chi_j = 1$, if $j \in 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 $\chi'$. Note that an exceptional
column is treated both as extreme and moderate.
We thus have $$(*) \qquad |p_j - \chi_j| \le \left\{\begin{array}{lll}
\frac{k-1}{n+1} & \mbox{ } & x \in X_0 \cup X_1 \\
\frac{k}{n+1} & \mbox{if } & x \in M_0 \\
1 - \frac{k}{n+1} & \mbox{if } & x \in M \end{array} \right. .$$
Let us call a row with index $i$ 'good' if $|(A(p-\chi))_i| \le 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 \cup X_1$. Rows
having two non-zeros in $M \cup M_0$ were already shown to be good by
construction of $\chi'$. All rows being good just means $\|A(p-\chi)\|_\infty
\le 1 - \frac 1 {n+1}$. This ends the proof.
\begin{thebibliography}{CLP92}
\bibitem[CLP92]{crama}
Y.~Crama, M.~Loebl, and S.~Poljak.
\newblock A decomposition of strongly unimodular matrices into incidence
matrices of digraphs.
\newblock {\em Disc. Math.}, 102:143--147, 1992.
\bibitem[Gho62]{ghou}
A.~Ghouila-Houri.
\newblock Caract\'erisation des Matrices Totalement Unimodulaires.
\newblock {\em C.~R.~Acad. Sci. Paris}, 254:1192--1194, 1962.
\bibitem[PY00]{pylind}
H.~Peng and C.~H. Yan.
\newblock On the discrepancy of strongly unimodular matrices.
\newblock {\em Discrete Mathematics}, 219:223--233, 2000.
\end{thebibliography}
\end{document}