Discrepancy of matrices of zeros ond ones. (English) Zbl 0918.05029

Electron. J. Comb. 6, No. 1, Research paper R15, 12 p. (1999); printed version J. Comb. 6, 205-216 (1999).
Authors’ abstract: Let \(m\) and \(n\) be positive integers, and let \(R=(r_1,\dots,r_m)\) and \(S=(s_1,\dots,s_n)\) be non-negative integral vectors. Let \({\mathcal A}(R,S)\) be the set of all \(m\times n\) \((0,1)\)-matrices with row sum \(R\) and column sum \(S\), and let \(\overline{A}\) be the \(m\times n\) \((0,1)\)-matrix where for each \(i\), \(1\leq i\leq m\), row \(i\) consists of \(r_i\) 1’s followed by \(n-r_i\) 0’s. If \(S\) is monotone, the discrepancy \(d(A)\) of \(A\) is the number of positions in which \(\overline A\) has a 1 and \(A\) has a 0. It equals the number of 1’s in \(\overline A\) which have to be shifted in rows to obtain \(A\). In this paper, we study the minimum and maximum \(d(A)\) among all matrices \( A \in {\mathcal A}(R,S)\). We completely solve the minimum discrepancy problem by giving an explict formula in terms of \(R\) and \(S\) for it. On the other hand, the problem of finding an explicit formula for the maximum discrepancy turns out to be very difficult. Instead, we find an algorithm to compute the maximum discrepancy.


05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
15B33 Matrices over special rings (quaternions, finite fields, etc.)
Full Text: EuDML EMIS