Previous |  Up |  Next


Boolean matrix; Boolean rank; Boolean linear operator; isolation number
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\times 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\times 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\leq k\leq \min \{m,n\}$ if and only if there are fixed permutation matrices $P$ and $Q$ such that for $X\in {\mathcal M}_{m,n}(\mathbb B)$ $T(X)=PXQ$ or, $m=n$ and $T(X)=PX^tQ$ where $X^t$ is the transpose of $X$.
[1] Beasley, L. B.: Isolation number versus Boolean rank. Linear Algebra Appl. 436 (2012), 3469-3474. MR 2900729 | Zbl 1245.15003
[2] Beasley, L. B., Li, C.-K., Pierce, S.: Miscellaneous preserver problems. A survey of linear preserver problems. Linear Multilinear Algebra 33 (1992), 109-119. MR 1346786
[3] Beasley, L. B., Pullman, N. J.: Linear operators that strongly preserve upper ideals of matrices. F. Hoffman et al. Proceedings of the Twenty-Third Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Florida Atlantic University, Boca Raton, USA Congr. Numerantium. 88 Utilitas Mathematica Publishing, Winnipeg (1992), 229-243. MR 1208933 | Zbl 0835.15008
[4] Beasley, L. B., Pullman, N. J.: Boolean-rank-preserving operators and Boolean-rank-1 spaces. Linear Algebra Appl. 59 (1984), 55-77. DOI 10.1016/0024-3795(84)90158-7 | MR 0743045 | Zbl 0536.20044
[5] Caen, D. de, Gregory, D. A., Pullman, N. J.: The Boolean rank of zero-one matrices. C. C. Cadogan Proceedings of the Third Caribbean Conference on Combinatorics and Computing, Bridgetown, 1981 Univ. West Indies, Cave Hill Campus, Barbados (1981), 169-173. MR 0657185 | Zbl 0496.20052
[6] Kang, K.-T., Song, S.-Z., Beasley, L. B.: Linear preservers of term ranks of matrices over semirings. Linear Algebra Appl. 436 (2012), 1850-1862. MR 2889962 | Zbl 1236.15058
[7] Kim, K. H.: Boolean Matrix Theory and Applications. Monographs and Textbooks in Pure and Applied Mathematics 70 Marcel Dekker, New York (1982). MR 0655414 | Zbl 0495.15003
[8] Song, S.-Z.: Linear operators that preserve column rank of Boolean matrices. Proc. Am. Math. Soc. 119 (1993), 1085-1088. DOI 10.1090/S0002-9939-1993-1184086-1 | MR 1184086 | Zbl 0802.15006
Partner of
EuDML logo