Isolation numbers of matrices over nonbinary Boolean semiring

Abstract

Let Bk be the nonbinary Boolean semiring and A be a m × n Boolean matrix over Bk. The Boolean rank of a Boolean matrix A is the smallest k such that A can be factored as an m × k Boolean matrix times a k × n Boolean 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 on the Boolean rank of A. We also compare the isolation number with the binary Boolean rank of the support of A, and determine the equal cases of them.