Isolation number versus Boolean rank (Q417483): Difference between revisions

Let \(\mathbb B=\{0,1\}\) be the binary Boolean algebra, and let \(A\) be an \(m\times n\) matrix over \(\mathbb B\). The author exhibits the relationship between the following two numbers: The \textit{Boolean rank}, or factorisation rank, of \(A\) is the smallest \(k\) such that \(A\) can be factored as an \(m\times k\) times a \(k\times n\) matrix. The \textit{isolation number} of \(A\) is the largest number of entries equal to \(1\) in the matrix such that: (i) no two ones are in the same row, (ii) no two ones are in the same column, and (iii) no two ones are in a \(2\times 2\) submatrix of all ones. It is known that the isolation number of \(A\) is always at most the Boolean rank. The main results of this paper are as follows: For \(k\in\{1,2\}\) the isolation number of \(A\) equals \(k\) if, and only if, the Boolean rank is \(k\). Also, for \(1\leq m\leq n\) necessary and sufficient conditions for the Boolean rank and the isolation number to be both equal to \(m\) are given.