Linear Operators That Preserve Graphical Properties of Matrices: Isolation Numbers

Let A be a Boolean {0, 1} matrix. The isolation number of A is the maximum number of ones in A such that no two are in any row or any column (that is they are independent), and no two are in a 2 × 2 submatrix of all ones. The isolation number of A is a lower bound on the Boolean rank of A. A linear operator on the set of m × n Boolean matrices is a mapping which is additive and maps the zero matrix, O, to itself. A mapping strongly preserves a set, S, if it maps the set S into the set S and the complement of the set S into the complement of the set S. We investigate linear operators that preserve the isolation number of Boolean matrices. Specifically, we show that T is a Boolean linear operator that strongly preserves isolation number k for any 1 ⩽ k ⩽ min{m, n} if and only if there are fixed permutation matrices P and Q such that for X∈m,n(��)T(X)=PXQ or, m = n and T (X) = PX t Q where X t is the transpose of X