\((0,1)\)-matrices, discrepancy and preservers. (English) Zbl 07144881

Summary: Let \(m\) and \(n\) be positive integers, and let \(R=(r_1,\ldots,r_m)\) and \(S=(s_1,\ldots,s_n)\) be nonnegative integral vectors. Let \(A(R,S)\) be the set of all \(m\times n\) \((0,1)\)-matrices with row sum vector \(R\) and column vector \(S\). Let \(R\) and \(S\) be nonincreasing, and let \(F(R)\) be the \(m\times n\) \((0,1)\)-matrix, where for each \(i\), the \(i\)th row of \(F(R,S)\) consists of \(r_i\) 1’s followed by \((n-r_i)\) 0’s. Let \(A\in A(R,S)\). The discrepancy of \(A\), \(\mathrm{disc}(A)\), is the number of positions in which \(F(R)\) has a 1 and \(A\) has a 0. In this paper we investigate linear operators mapping \(m\times n\) matrices over the binary Boolean semiring to itself that preserve sets related to the discrepancy. In particular, we show that bijective linear preservers of Ferrers matrices are either the identity mapping or, when \(m=n\), the transpose mapping.


15A04 Linear transformations, semilinear transformations
15A21 Canonical forms, reductions, classification
15A86 Linear preserver problems
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI


[1] Beasley, L. B.; Pullman, N. J., Linear operators preserving properties of graphs, Proc. 20th Southeast Conf. on Combinatorics, Graph Theory, and Computing Congressus Numerantium 70, Utilitas Mathematica Publishing, Winnipeg (1990), 105-112
[2] Berger, A., The isomorphic version of Brualdies nestedness is in P, 2017, 7 pages, Available at https://arxiv.org/abs/1602.02536v2
[3] Berger, A.; Schreck, B., The isomorphic version of Brualdi’s and Sanderson’s nestedness, Algorithms (Basel) 10 (2017), Paper No. 74, 12 pages
[4] Brualdi, R. A.; Sanderson, G. J., Nested species subsets, gaps, and discrepancy, Oecologia 119 (1999), 256-264
[5] Brualdi, R. A.; Shen, J., Discrepancy of matrices of zeros and ones, Electron. J. Comb. 6 (1999), Research Paper 15, 12 pages
[6] Motlaghian, S. M.; Armandnejad, A.; Hall, F. J., Linear preservers of row-dense matrices, Czech. Math. J. 66 (2016), 847-858
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.