Czechoslovak Mathematical Journal, first online, pp. 1-9


$(0,1)$-matrices, discrepancy and preservers

LeRoy B. Beasley

Received February 20, 2018.   Published online August 30, 2019.

Abstract:  Let $m$ and $n$ be positive integers, and let $R = (r_1, łdots, r_m)$ and $S = (s_1,łdots, 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, ${\rm 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.
Keywords:  Ferrers matrix; row-dense matrix; discrepancy; linear preserver; strong linear preserver
Classification MSC:  15A04, 15A21, 15A86, 05B20, 05C50
DOI:  10.21136/CMJ.2019.0092-18

PDF available at:  Springer   Institute of Mathematics CAS

References:
[1] L. B. Beasley, N. J. Pullman: 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. MR 1041590 | Zbl 0696.05049
[2] A. Berger: The isomorphic version of Brualdies nestedness is in P, 2017, 7 pages. Available at https://arxiv.org/abs/1602.02536v2.
[3] A. Berger, B. Schreck: The isomorphic version of Brualdi's and Sanderson's nestedness. Algorithms (Basel) 10 (2017), Paper No. 74, 12 pages. DOI 10.3390/a10030074 | MR 3708470 | Zbl 06916733
[4] R. A. Brualdi, G. J. Sanderson: Nested species subsets, gaps, and discrepancy. Oecologia 119 (1999), 256-264. DOI 10.1007/s004420050784
[5] R. A. Brualdi, J. Shen: Discrepancy of matrices of zeros and ones. Electron. J. Comb. 6 (1999), Research Paper 15, 12 pages. MR 1674136 | Zbl 0918.05029
[6] S. M. Motlaghian, A. Armandnejad, F. J. Hall: Linear preservers of row-dense matrices. Czech. Math. J. 66 (2016), 847-858. DOI 10.1007/s10587-016-0296-4 | MR 3556871 | Zbl 06644037

Affiliations:   LeRoy B. Beasley, Department of Mathematics and Statistics, Utah State University, Logan, Utah 84322-3900, USA, e-mail: leroy.b.beasley@aggiemail.usu.edu


 
PDF available at: