Geodesic
Possible isolation number of a matrix over nonnegative integers
Czechoslovak Mathematical Journal, Tome 68 (2018) no. 4, pp. 1055-1066
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $\mathbb Z_+$ be the semiring of all nonnegative integers and $A$ an $m\times n$ matrix over $\mathbb Z_+$. The rank of $A$ is the smallest $k$ such that $A$ can be factored as an $m\times k$ matrix times a $k\times n$ matrix. The isolation number of $A$ is the maximum number of nonzero entries in $A$ such that no two are in any row or any column, and no two are in a $2\times 2$ submatrix of all nonzero entries. We have that the isolation number of $A$ is a lower bound of the rank of $A$. For $A$ with isolation number $k$, we investigate the possible values of the rank of $A$ and the Boolean rank of the support of $A$. So we obtain that the isolation number and the Boolean rank of the support of a given matrix are the same if and only if the isolation number is $1$ or $2$ only. We also determine a special type of $m \times n$ matrices whose isolation number is $m$. That is, those matrices are permutationally equivalent to a matrix $A$ whose support contains a submatrix of a sum of the identity matrix and a tournament matrix.
Let $\mathbb Z_+$ be the semiring of all nonnegative integers and $A$ an $m\times n$ matrix over $\mathbb Z_+$. The rank of $A$ is the smallest $k$ such that $A$ can be factored as an $m\times k$ matrix times a $k\times n$ matrix. The isolation number of $A$ is the maximum number of nonzero entries in $A$ such that no two are in any row or any column, and no two are in a $2\times 2$ submatrix of all nonzero entries. We have that the isolation number of $A$ is a lower bound of the rank of $A$. For $A$ with isolation number $k$, we investigate the possible values of the rank of $A$ and the Boolean rank of the support of $A$. So we obtain that the isolation number and the Boolean rank of the support of a given matrix are the same if and only if the isolation number is $1$ or $2$ only. We also determine a special type of $m \times n$ matrices whose isolation number is $m$. That is, those matrices are permutationally equivalent to a matrix $A$ whose support contains a submatrix of a sum of the identity matrix and a tournament matrix.
DOI : 10.21136/CMJ.2018.0068-17
Classification : 15A03, 15A23, 15B34
Keywords: rank; Boolean rank; isolated entry; isolation number 
@article{10_21136_CMJ_2018_0068_17,
     author = {Beasley, LeRoy B. and Jun, Young Bae and Song, Seok-Zun},
     title = {Possible isolation number of a matrix over nonnegative integers},
     journal = {Czechoslovak Mathematical Journal},
     pages = {1055--1066},
     year = {2018},
     volume = {68},
     number = {4},
     doi = {10.21136/CMJ.2018.0068-17},
     mrnumber = {3881896},
     zbl = {07031697},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0068-17/}
}
TY  - JOUR
AU  - Beasley, LeRoy B.
AU  - Jun, Young Bae
AU  - Song, Seok-Zun
TI  - Possible isolation number of a matrix over nonnegative integers
JO  - Czechoslovak Mathematical Journal
PY  - 2018
SP  - 1055
EP  - 1066
VL  - 68
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0068-17/
DO  - 10.21136/CMJ.2018.0068-17
LA  - en
ID  - 10_21136_CMJ_2018_0068_17
ER  - 
%0 Journal Article
%A Beasley, LeRoy B.
%A Jun, Young Bae
%A Song, Seok-Zun
%T Possible isolation number of a matrix over nonnegative integers
%J Czechoslovak Mathematical Journal
%D 2018
%P 1055-1066
%V 68
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0068-17/
%R 10.21136/CMJ.2018.0068-17
%G en
%F 10_21136_CMJ_2018_0068_17
Beasley, LeRoy B.; Jun, Young Bae; Song, Seok-Zun. Possible isolation number of a matrix over nonnegative integers. Czechoslovak Mathematical Journal, Tome 68 (2018) no. 4, pp. 1055-1066. doi: 10.21136/CMJ.2018.0068-17

[1] Beasley, L. B.: Isolation number versus Boolean rank. Linear Algebra Appl. 436 (2012), 3469-3474. | DOI | MR | JFM

[2] Beasley, L. B., Gregory, D. A., Pullman, N. J.: Nonnegative rank-preserving operators. Linear Algebra Appl. 65 (1985), 207-223. | DOI | MR | JFM

[3] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate texts in Mathematics 244, Springer, Berlin (2008). | MR | JFM

[4] Brualdi, R. A., Ryser, H. J.: Combinatorial Matrix Theory. Encyclopedia of Mathematics and Its Applications 39, Cambridge University Press, Cambridge (1991). | DOI | MR | JFM

[5] Caen, D. de, Gregory, D. A., Pullman, N. J.: The Boolean rank of zero-one matrices. Combinatorics and Computing Proc. 3rd Caribb. Conf., Cave Hill/Barbados (1981), 169-173. | MR | JFM

[6] Gregory, D. A., Pullman, N. J., Jones, K. F., Lundgren, J. R.: Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices. J. Comb. Theory, Ser. B 51 (1991), 73-89. | DOI | MR | JFM

[7] Kato, A.: Complexity of the sex-equal stable marriage problem. Japan J. Ind. Appl. Math. 10 (1993), 1-19. | DOI | MR | JFM

[8] Markowsky, G.: Primes, irreducibles and extremal lattices. Order 9 (1992), 265-290. | DOI | MR | JFM

Cité par Sources :