Czechoslovak Mathematical Journal, Vol. 68, No. 4, pp. 1055-1066, 2018


Possible isolation number of a matrix over nonnegative integers

LeRoy B. Beasley, Young Bae Jun, Seok-Zun Song

Received February 17, 2017.   Published online May 8, 2018.

Abstract:  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\times2$ 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.
Keywords:  rank; Boolean rank; isolated entry; isolation number
Classification MSC:  15A23, 15A03, 15B34
DOI:  10.21136/CMJ.2018.0068-17


References:
[1] L. B. Beasley: Isolation number versus Boolean rank. Linear Algebra Appl. 436 (2012), 3469-3474. DOI 10.1016/j.laa.2011.12.013 | MR 2900729 | Zbl 1245.15003
[2] L. B. Beasley, D. A. Gregory, N. J. Pullman: Nonnegative rank-preserving operators. Linear Algebra Appl. 65 (1985), 207-223. DOI 10.1016/0024-3795(85)90098-9 | MR 0774353 | Zbl 0561.15002
[3] J. A. Bondy, U. S. R. Murty: Graph Theory. Graduate texts in Mathematics 244, Springer, Berlin (2008). MR 2368647 | Zbl 1134.05001
[4] R. A. Brualdi, H. J. Ryser: Combinatorial Matrix Theory. Encyclopedia of Mathematics and Its Applications 39, Cambridge University Press, Cambridge (1991). DOI 10.1017/CBO9781107325708 | MR 1130611 | Zbl 0746.05002
[5] D. de Caen, D. A. Gregory, N. J. Pullman: The Boolean rank of zero-one matrices. Combinatorics and Computing. Proc. 3rd Caribb. Conf., Cave Hill/Barbados (1981), 169-173. MR 0657202 | Zbl 0496.20052
[6] D. A. Gregory, N. J. Pullman, K. F. Jones, J. R. Lundgren: Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices. J. Comb. Theory, Ser. B 51 (1991), 73-89. DOI 10.1016/0095-8956(91)90006-6 | MR 1088627 | Zbl 0733.05064
[7] A. Kato: Complexity of the sex-equal stable marriage problem. Japan J. Ind. Appl. Math. 10 (1993), 1-19. DOI 10.1007/BF03167200 | MR 1208179 | Zbl 0782.68060
[8] G. Markowsky: Primes, irreducibles and extremal lattices. Order 9 (1992), 265-290. DOI 10.1007/BF00383950 | MR 1211380 | Zbl 0778.06007

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; Young Bae Jun, Department of Mathematics Education, Gyeongsang National University, Jinju 52828, Korea, e-mail: ybjun@gsnu.ac.kr; Seok-Zun Song (corresponding author), Department of Mathematics, Jeju National University, Jeju 63243, Korea, e-mail: szsong@jejunu.ac.kr


 
PDF available at: