Geodesic
Linear operators that preserve graphical properties of matrices: isolation numbers
Czechoslovak Mathematical Journal, Tome 64 (2014) no. 3, pp. 819-826 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
DOI : 10.1007/s10587-014-0134-5
Classification : 15A04, 15A86, 15B34
Keywords: Boolean matrix; Boolean rank; Boolean linear operator; isolation number 
@article{10_1007_s10587_014_0134_5,
     author = {Beasley, LeRoy B. and Song, Seok-Zun and Jun, Young Bae},
     title = {Linear operators that preserve graphical properties of matrices: isolation numbers},
     journal = {Czechoslovak Mathematical Journal},
     pages = {819--826},
     year = {2014},
     volume = {64},
     number = {3},
     doi = {10.1007/s10587-014-0134-5},
     mrnumber = {3298562},
     zbl = {06391527},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0134-5/}
}
TY  - JOUR
AU  - Beasley, LeRoy B.
AU  - Song, Seok-Zun
AU  - Jun, Young Bae
TI  - Linear operators that preserve graphical properties of matrices: isolation numbers
JO  - Czechoslovak Mathematical Journal
PY  - 2014
SP  - 819
EP  - 826
VL  - 64
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0134-5/
DO  - 10.1007/s10587-014-0134-5
LA  - en
ID  - 10_1007_s10587_014_0134_5
ER  - 
%0 Journal Article
%A Beasley, LeRoy B.
%A Song, Seok-Zun
%A Jun, Young Bae
%T Linear operators that preserve graphical properties of matrices: isolation numbers
%J Czechoslovak Mathematical Journal
%D 2014
%P 819-826
%V 64
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0134-5/
%R 10.1007/s10587-014-0134-5
%G en
%F 10_1007_s10587_014_0134_5
Beasley, LeRoy B.; Song, Seok-Zun; Jun, Young Bae. Linear operators that preserve graphical properties of matrices: isolation numbers. Czechoslovak Mathematical Journal, Tome 64 (2014) no. 3, pp. 819-826. doi: 10.1007/s10587-014-0134-5

[1] Beasley, L. B.: Isolation number versus Boolean rank. Linear Algebra Appl. 436 (2012), 3469-3474. | MR | Zbl

[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

[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 | Zbl

[4] Beasley, L. B., Pullman, N. J.: Boolean-rank-preserving operators and Boolean-rank-1 spaces. Linear Algebra Appl. 59 (1984), 55-77. | DOI | MR | Zbl

[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 | Zbl

[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 | Zbl

[7] Kim, K. H.: Boolean Matrix Theory and Applications. Monographs and Textbooks in Pure and Applied Mathematics 70 Marcel Dekker, New York (1982). | MR | Zbl

[8] Song, S.-Z.: Linear operators that preserve column rank of Boolean matrices. Proc. Am. Math. Soc. 119 (1993), 1085-1088. | DOI | MR | Zbl

Cité par Sources :