Possible isolation number of a matrix over nonnegative integers

• Published in: Czechoslovak mathematical journal 2018-12, Vol.68 (4), p.1055-1066
• Main Authors: Beasley, LeRoy B., Jun, Young Bae, Song, Seok-Zun
• Format: Article
• Language: English
• Subjects: Analysis; Boolean algebra; Convex and Discrete Geometry; Integers; Lower bounds; Mathematical Modeling and Industrial Mathematics; Mathematics; Mathematics and Statistics; Ordinary Differential Equations
• ISSN: 0011-4642; 1572-9141
• DOI: 10.21136/CMJ.2018.0068-17

Let ℤ + be the semiring of all nonnegative integers and A an m × n matrix over ℤ + . The rank of A is the smallest k such that A can be factored as an m × k matrix times a k × 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 × 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 × 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.