Previous |  Up |  Next


Title: $(0,1)$-matrices, discrepancy and preservers (English)
Author: Beasley, LeRoy B.
Language: English
Journal: Czechoslovak Mathematical Journal
ISSN: 0011-4642 (print)
ISSN: 1572-9141 (online)
Volume: 69
Issue: 4
Year: 2019
Pages: 1123-1131
Summary lang: English
Category: math
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, ${\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. (English)
Keyword: Ferrers matrix
Keyword: row-dense matrix
Keyword: discrepancy
Keyword: linear preserver
Keyword: strong linear preserver
MSC: 05B20
MSC: 05C50
MSC: 15A04
MSC: 15A21
MSC: 15A86
idZBL: 07144881
idMR: MR4039626
DOI: 10.21136/CMJ.2019.0092-18
Date available: 2019-11-28T08:53:38Z
Last updated: 2022-01-03
Stable URL:
Reference: [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. Zbl 0696.05049, MR 1041590
Reference: [2] Berger, A.: The isomorphic version of Brualdies nestedness is in P, 2017, 7 pages.Available at
Reference: [3] Berger, A., Schreck, B.: The isomorphic version of Brualdi's and Sanderson's nestedness.Algorithms (Basel) 10 (2017), Paper No. 74, 12 pages. Zbl 06916733, MR 3708470, 10.3390/a10030074
Reference: [4] Brualdi, R. A., Sanderson, G. J.: Nested species subsets, gaps, and discrepancy.Oecologia 119 (1999), 256-264. 10.1007/s004420050784
Reference: [5] Brualdi, R. A., Shen, J.: Discrepancy of matrices of zeros and ones.Electron. J. Comb. 6 (1999), Research Paper 15, 12 pages. Zbl 0918.05029, MR 1674136
Reference: [6] Motlaghian, S. M., Armandnejad, A., Hall, F. J.: Linear preservers of row-dense matrices.Czech. Math. J. 66 (2016), 847-858. Zbl 06644037, MR 3556871, 10.1007/s10587-016-0296-4


Files Size Format View
CzechMathJ_69-2019-4_19.pdf 269.6Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo