Geodesic
$(0,1)$-matrices, discrepancy and preservers
Czechoslovak Mathematical Journal, Tome 69 (2019) no. 4, pp. 1123-1131
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2019.0092-18
Classification : 05B20, 05C50, 15A04, 15A21, 15A86
Keywords: Ferrers matrix; row-dense matrix; discrepancy; linear preserver; strong linear preserver 
@article{10_21136_CMJ_2019_0092_18,
     author = {Beasley, LeRoy B.},
     title = {$(0,1)$-matrices, discrepancy and preservers},
     journal = {Czechoslovak Mathematical Journal},
     pages = {1123--1131},
     year = {2019},
     volume = {69},
     number = {4},
     doi = {10.21136/CMJ.2019.0092-18},
     mrnumber = {4039626},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0092-18/}
}
TY  - JOUR
AU  - Beasley, LeRoy B.
TI  - $(0,1)$-matrices, discrepancy and preservers
JO  - Czechoslovak Mathematical Journal
PY  - 2019
SP  - 1123
EP  - 1131
VL  - 69
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0092-18/
DO  - 10.21136/CMJ.2019.0092-18
LA  - en
ID  - 10_21136_CMJ_2019_0092_18
ER  - 
%0 Journal Article
%A Beasley, LeRoy B.
%T $(0,1)$-matrices, discrepancy and preservers
%J Czechoslovak Mathematical Journal
%D 2019
%P 1123-1131
%V 69
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0092-18/
%R 10.21136/CMJ.2019.0092-18
%G en
%F 10_21136_CMJ_2019_0092_18
Beasley, LeRoy B. $(0,1)$-matrices, discrepancy and preservers. Czechoslovak Mathematical Journal, Tome 69 (2019) no. 4, pp. 1123-1131. doi: 10.21136/CMJ.2019.0092-18

[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. | MR | JFM

[2] Berger, A.: The isomorphic version of Brualdies nestedness is in P, 2017, 7 pages. Available at | arXiv

[3] Berger, A., Schreck, B.: The isomorphic version of Brualdi's and Sanderson's nestedness. Algorithms (Basel) 10 (2017), Paper No. 74, 12 pages. | DOI | MR | JFM

[4] Brualdi, R. A., Sanderson, G. J.: Nested species subsets, gaps, and discrepancy. Oecologia 119 (1999), 256-264. | DOI

[5] Brualdi, R. A., Shen, J.: Discrepancy of matrices of zeros and ones. Electron. J. Comb. 6 (1999), Research Paper 15, 12 pages. | MR | JFM

[6] Motlaghian, S. M., Armandnejad, A., Hall, F. J.: Linear preservers of row-dense matrices. Czech. Math. J. 66 (2016), 847-858. | DOI | MR | JFM

Cité par Sources :