Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
rank; Boolean rank; isolated entry; isolation number
rank; Boolean rank; isolated entry; isolation number
Summary:
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.
References:
[1] Beasley, L. B.: 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] Beasley, L. B., Gregory, D. A., Pullman, N. J.: 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] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate texts in Mathematics 244, Springer, Berlin (2008). MR 2368647 | Zbl 1134.05001
[4] Brualdi, R. A., Ryser, H. J.: 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] 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 0657202 | Zbl 0496.20052
[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 10.1016/0095-8956(91)90006-6 | MR 1088627 | Zbl 0733.05064
[7] Kato, A.: 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] Markowsky, G.: Primes, irreducibles and extremal lattices. Order 9 (1992), 265-290. DOI 10.1007/BF00383950 | MR 1211380 | Zbl 0778.06007
Search
Partner of
