| Title:
|
Possible isolation number of a matrix over nonnegative integers (English) |
| Author:
|
Beasley, LeRoy B. |
| Author:
|
Jun, Young Bae |
| Author:
|
Song, Seok-Zun |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
68 |
| Issue:
|
4 |
| Year:
|
2018 |
| Pages:
|
1055-1066 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
rank |
| Keyword:
|
Boolean rank |
| Keyword:
|
isolated entry |
| Keyword:
|
isolation number |
| MSC:
|
15A03 |
| MSC:
|
15A23 |
| MSC:
|
15B34 |
| idZBL:
|
Zbl 07031697 |
| idMR:
|
MR3881896 |
| DOI:
|
10.21136/CMJ.2018.0068-17 |
| . |
| Date available:
|
2018-12-07T06:21:25Z |
| Last updated:
|
2021-01-04 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147521 |
| . |
| Reference:
|
[1] Beasley, L. B.: Isolation number versus Boolean rank.Linear Algebra Appl. 436 (2012), 3469-3474. Zbl 1245.15003, MR 2900729, 10.1016/j.laa.2011.12.013 |
| Reference:
|
[2] Beasley, L. B., Gregory, D. A., Pullman, N. J.: Nonnegative rank-preserving operators.Linear Algebra Appl. 65 (1985), 207-223. Zbl 0561.15002, MR 0774353, 10.1016/0024-3795(85)90098-9 |
| Reference:
|
[3] Bondy, J. A., Murty, U. S. R.: Graph Theory.Graduate texts in Mathematics 244, Springer, Berlin (2008). Zbl 1134.05001, MR 2368647 |
| Reference:
|
[4] Brualdi, R. A., Ryser, H. J.: Combinatorial Matrix Theory.Encyclopedia of Mathematics and Its Applications 39, Cambridge University Press, Cambridge (1991). Zbl 0746.05002, MR 1130611, 10.1017/CBO9781107325708 |
| Reference:
|
[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. Zbl 0496.20052, MR 0657202 |
| Reference:
|
[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. Zbl 0733.05064, MR 1088627, 10.1016/0095-8956(91)90006-6 |
| Reference:
|
[7] Kato, A.: Complexity of the sex-equal stable marriage problem.Japan J. Ind. Appl. Math. 10 (1993), 1-19. Zbl 0782.68060, MR 1208179, 10.1007/BF03167200 |
| Reference:
|
[8] Markowsky, G.: Primes, irreducibles and extremal lattices.Order 9 (1992), 265-290. Zbl 0778.06007, MR 1211380, 10.1007/BF00383950 |
| . |
