Possible isolation number of a matrix over nonnegative integers

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

Czechoslovak Mathematical Journal, Tome 68 (2018) no. 4, pp. 1055-1066

Résumé

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.

Détail

DOI : 10.21136/CMJ.2018.0068-17

Classification : 15A03, 15A23, 15B34
Keywords: rank; Boolean rank; isolated entry; isolation number