\documentclass{mc}
%%%%% journal  info -- DO NOT CHANGE %%%%%%%%%
\setcounter{page}{363}
\renewcommand\thisnumber{x}
\renewcommand\thisyear {2014}
\renewcommand\thismonth{xxx}
\renewcommand\thisvolume{19}
\renewcommand\datereceived{May 2, 2013}
\renewcommand\dateaccepted{September 13, 2014}
%%%%%%%%   end journal info   %%%%%%%%%%%%%
%Rad zaprimljen dana: 2013-05-02

%Rad prihvacen dana: 2014-09-13

%%%% author macros %%%%%%%%%

%%%%% end %%%%%%%%%

%%%%%%%%%    already loaded packages -- DO NOT RELOAD  %%%%%
% \usepackage{amssymb}
% \usepackage{amsmath,amsthm}
% \usepackage{latexsym}
% \usepackage{amsfonts}
% \usepackage{amsbsyt}
% \usepackage{graphicx}
%%%%%%    end   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage[displaymath,mathlines,pagewise]{lineno}

\begin{document}
%\begin{linenumbers}

%%%%% title and author(s):
% \markboth{Author(s)}{Short Title}
% \title{Title}

\markboth{L.\,B.\,Beasley and S.\,Z.\,Song }{Linear preservers of isolation numbers}
\title{A characterization of linear operators that preserve isolation numbers }


% single author:
% \author[AUTHOR]{AUTHOR}
% \address{address of AUTHOR}
% \email{{\tt email address of AUTHOR} (AUTHOR)}

%\author[Only Author]{Only Author\corrauth}
\author[LeRoy B.\,Beasley, Seok Zun Song]{LeRoy B. Beasley\affil{1} and Seok Zun Song\affil{2}\comma\corrauth }

\address{ \affilnum{1} Department of Mathematics and Statistics, Utah State
University, Logan, Utah 84\,322-3\,900, USA \\
         \affilnum{2} Department of Mathematics,
         Jeju National University, Jeju 690-756, Korea }

\emails{{\tt leroy.b.beasley@usu.edu} \,\,(L.\,B.\,Beasley),
 {\tt
szsong@jejunu.ac.kr} (S.\,Z.\,Song)}

% multiple authors:
% Please mark \corrauth after the name of the corresponding author.
% different addresses:
%\author[AUTHOR1 and AUTHOR2]{AUTHOR1\affil{1}\comma\corrauth and AUTHOR2\affil{2}}
%\address{\affilnum{1}\ address of AUTHOR1\\   \affilnum{2}\ address of AUTHOR2}
%
%same address:
%\author[AUTHOR1, AUTHOR2 and AUTHOR3]{AUTHOR1, AUTHOR2\corrauth and AUTHOR3}
%\address{address of AUTHOR1, AUTHOR2 and AUTHOR3}
%
%\emails{{\tt email of AUTHOR1} (AUTHOR1), {\tt email of AUTHOR2} (AUTHOR2), {\tt email of AUTHOR3} (AUTHOR3)}
%

%%%%% Begin Abstract %%%%%%%%%%%
\begin{abstract}
   We obtain  characterizations of Boolean linear operators that preserve
 some of the isolation numbers  of Boolean matrices.  In particular,
 we show that the following are equivalent:  (1) $T$ preserves the
 isolation number of all matrices; (2) $T$  preserves the set of
 matrices with isolation number one and the set of those with
 isolation number $k$ for some $2\leq k\leq \min\{m,n\}$;
 (3) for $1\leq k\leq \min\{m,n\}-1$, $T$ preserves matrices
 with isolation number $k$, and those with isolation number $k+1$,
 (4) $T$ maps $J$ to $J$ and preserves the set of matrices of
 isolation number 2;  (5)  $T$ is a $(P,Q)$-operator, that is,
 for fixed permutation matrices $P$ and $Q$,  $m\times n$ matrix $X,$~ $T(X)=PXQ$
 or, $m=n$ and  $T(X)=PX^tQ$ where $X^t$ is the transpose of $X$.
\end{abstract}
%%%%% end %%%%%%%%%%%

%%%%% Keywords %%%%%%%%%%%
\keywords{Boolean matrix, Boolean rank, isolation number, Boolean
linear operator}

%%%% AMS subject classifications %%%%
\ams{15A86, 15A04}

%%%% maketitle %%%%%
\maketitle

%%%% Start %%%%%%
\def \s{{\mathbb S}}
\def\dd{\hfill\baseb\vskip .3cm}
\def\oo{\overline}
\def\d{{\noindent \it Proof. }}
\def\S{{\mathbb S}}
\def\B{{\mathbb B}}
\def\Z{{\cal Z}}
\def\I{{\cal I}}
\def\Mmn{{\cal M}_{m,n}(\B)}
\def\F{{\cal F}}
\def\G{{\cal G}}
\def\K{{\cal K}}
\def\i{\iota}
\def\b{\beta}
\def\br{\beta}
\def\SS{{\cal S}}
\def\T{T:\Mmn \rightarrow \Mmn}
\def\dd{\hfill \baseb \medskip}
\def\t{\begin{theorem}}
\def\tt{\end{theorem}}
\def\D{\begin{definition}}
\def\DD{\end{definition}}
\def\l{\begin{lemma}}
\def\ll{\end{lemma}}
\def\c{\begin{corollary}}
\def\cc{\end{corollary}}
\def\ex{\begin{example}}
\def\exx{\end{example}}
\def\p{\pagebreak}
\def\E{{\cal E}}

\newcommand{\baseb}{\hfill \rule{2mm}{2mm}}




\section{Introduction}

 The characterization of linear operators on vector
spaces of matrices which leave functions, sets or relations
invariant began over a century ago when Fr\"obenius \cite{F}, in 1897,
 characterized the linear operators that leave the
determinant function invariant. Since then, several researchers
have investigated the preservers of nearly every function, set and
relation on matrices over fields. See \cite{PL2,PL} for an
excellent survey of preserver problems through 2001.  For
applications of linear preservers, see \cite{GM}.

In the 1980's, research began on linear preserver problems over
semirings, in particular linear operators on spaces of
$(0,1)$-matrices.  (See for example \cite{BP1}.)  Many functions,
sets and relations concerning matrices do not depend upon the
magnitude or nature of the individual entries of a matrix, but
rather only on whether the entry is zero or nonzero.  These
combinatorially significant matrices have become increasingly
important in recent years.  The Boolean
rank is of primary interest. Finding the Boolean rank of a $(0,1)$-matrix is an
NP-Complete problem, (See \cite{Mar} noting that the Boolean rank is
also called the Schein rank), and consequently finding bounds on
the Boolean rank of a matrix is of interest to those researchers
that would use the Boolean rank in their work.  The isolation number
of a $(0,1)$-matrix is the largest number of entries equal to 1, no two of which are in the same row, no two of which are in the same column, and no two of which are in a submatrix of all ones.   If the $(0,1)$-matrix is the reduced adjacency matrix of a bipartite graph, the isolation number of the matrix is the maximum size of a  non-competitive matching in the bipartite graph.  This is related to the study of such combinatorial problems as the patient hospital problem, the stable marriage problem, etc.  See
{\verb+http://en.wikipedia.org/wiki/Stable_marriage_problem+}.
An additional reason for studying the isolation number is that it is a lower bound on the Boolean rank of a $(0,1)$-matrix, (see \cite{GPJ}).  While finding the isolation number as well as finding the Boolean rank of a $(0,1)$-matrix is an NP-Complete problem (\cite{A}), for some matrices finding the isolation number can be easier than finding the Boolean rank especially if the matrix is sparse:
\ex Let $${\cal X}=\left[\begin{array}{ccccccccc}1&1&1&{\bf 1}&0&1&1&1&1\\1&1&1&1&{\bf 1}&1&1&1&1\\1&1&1&0&0&{\bf 1}&1&1&1
\\1&1&1&0&0&0&0&0&0\\1&1&1&0&0&0&0&0&0\\1&1&1&0&0&0&0&0&0
\\{\bf 1}&1&0&0&0&0&0&0&0\\0&{\bf 1}&1&0&0&0&0&0&0\\1&0&{\bf 1}&0&0&0&0&0&0\end{array}\right].$$  The Boolean rank of ${\cal X}$ is easily seen to be at most 6; however, to find that it is not 5 requires much calculation if the isolation number is not considered.  However, the isolation number is easily seen to be 6, both computationally and visually, the bold ones in the matrix represent a set of isolated ones.  Thus the Boolean rank is 6.

Note that if any of the non-bold ones are replaced by zeros, the resulting matrix still has Boolean rank 6 as well as isolation number 6. \exx

Terms not specifically defined here can be found in Brualdi and
Ryser \cite{BR} for matrix terms, or Bondy and Murty \cite{BM} for
graph theoretic terms.

\section{Definitions and preliminary results}

A {\em semiring}  $\s$ is a set with two binary operations,
addition (+) and multiplication ($\cdot$). There is a zero element
and an identity element (for multiplication) in $\s$. That is,
$(\s,+)$ is closed, commutative and associative, but may not have
additive inverses, except for the zero. $(\s,\cdot)$ is closed,
associative and commutative, but may not have multiplicative
inverses, except for the identity. Further, the distributive laws
hold, and we will only consider semirings which have no zero
divisors, that is, nonzero elements, $s$, for which there is some
nonzero element $t$ in $\s$ such that $st=0$. Of particular
interest in this article is the {\em binary Boolean algebra}, $\B
=\{0,1\}$ with the usual addition and multiplication, except that
$1+1=1$. A semiring is {\em antinegative} if the only element with
an additive inverse is the zero element.

In this article, we only consider matrices over the antinegative semiring $\B$.



Let $\Mmn$ be the set of all $m\times n$ matrices with entries in
the binary Boolean algebra $\B$, and let ${\mathcal
M}_{m}(\B)={\mathcal M}_{m,m}(\B)$. The usual definitions for
adding and multiplying matrices apply to Boolean matrices as well.


The matrix $A^{(m,n)}$ denotes a matrix in ${\mathcal
M}_{m,n}(\B)$, $I_n$ is an $n\times n$ identity matrix, $O_{m,n}$
is an $m\times n$ zero matrix, and $J_{m,n}$ is an $m\times n$
matrix all of whose entries are $1$.  Let $E_{i,j} ^{(m,n)}$ be
an $m\times n$ matrix whose $(i,j)$th entry is $1$ and whose
other entries are all $0$, and we call $E_{i,j} ^{(m,n)}$ a {\it
cell}.
 We will suppress
the superscripts and/or subscripts on these matrices when the
orders are evident from the context and we write $A$, $I$, $O$,
$J$, and $E_{ij}$,  respectively.  Further, we let the set of all
cells be denoted ${\mathcal E}$. That is, \[ {\mathcal E} =
\{E_{i,j} \in \Mmn \mid i= 1,\ldots,m ~\hbox{and}~ j = 1,\ldots,n
\}.\]

The {\it Boolean rank}, $\br(A)$, of a nonzero Boolean matrix $A$
in $\Mmn$ is the minimal number $k$ such that there exist $m\times
k$ and $k\times n$ Boolean matrices $B\in {\mathcal M}_{m,k}(\B)$
and $C\in {\mathcal M}_{k,n}(\B)$  such that $A=BC$.  The Boolean
rank of the zero matrix is $0$. It is well known that $\br(A)$ is
the least $k$ such that $A$ is the sum of $k$ matrices of Boolean
rank $1$ (\cite{BP1}).   By observing that any matrix is a sum of
its rows (or columns), which are rank one matrices, it follows
that $1\le \br(A)\le m$ for all nonzero $A\in\Mmn$.

From now on we will assume that $2\le m\le
n$.

The Boolean rank of a zero-one matrix is equal to the biclique
covering number of a bipartite graph, and hence has applications
in graph theory.  The Boolean rank has also been used in other
applications as well, for example in investigating the exponent of
primitive matrices, see \cite{GKP}.



By considering a minimal sum of rank one matrices for $A$ and $B$
such as $A=A_1 + \cdots + A_k$, and $B=B_1 + \cdots + B_l$, we
have that $A+B =A_1 + \cdots + A_k + B_1 + \cdots + B_l $, so that
$A+B$ has a rank at most $k+l$.  This establishes the following
lemma.

\begin{lemma}
For matrices $A$ and $B$ in $\Mmn$, we have $\br (A+B)\le
\br(A)+\br(B)$.
\end{lemma}



If $A$ and $B$ are matrices in $\Mmn$, we say that $B$ {\it
dominates} $A$ (written $A\leq B$ or $B\geq A$) if $b_{i,j}=0$
implies $ a_{i,j}=0$ for all $i$ and $j$. Equivalently, $A\leq B$
if and only if $A+B=B$. This provides a reflexive and transitive
relation on $\Mmn$.  Let $A$ be a matrix.  We let $|A|$ denote the
number of nonzero entries in that matrix.  So, $|I_n|=n$.  We call
$|A|$ the {\em weight} of $A$.

A set of indices, $\I$, of $A$ is called a set of {\em isolated
ones} of $A$  if (1)  $(i,j)\in\I$ implies $a_{i,j}=1$; (2)
whenever $(i,j),(k,l)\in\I$ we have that $i\neq k$, $j\neq l$, and
the submatrix on rows $i$ and $k$ and on columns $j$ and $l$ is
not $\left[\begin{array}{cc}1&1\\1&1\end{array}\right]$.  The
isolation number was first defined and used by Gregory and Pullman
in 1983 (\cite{GP}).  They were studying Boolean and nonnegative
factorizations of matrices, especially prime matrices.

The {\em isolation number } of $A$, $\i(A)$, is the cardinality of
a largest set of isolated ones of $A$.  In \cite{B}, it was shown
that $\i(A)=1$ if and only if $\b(A)=1$, and $\i(A)=2$ if and
only if $\b(A)=2$.

Since any two entries of $A$ corresponding to distinct isolated
ones can lie in no single Boolean rank one submatrix, we have:

\l \label{i leq b}  Let $A\in\Mmn$.  Then $\i(A)\leq \b(A)$.\ll

However, as the following example illustrates, unless $i(A)=1, 2,
\hbox{ or } m$, the  isolation number may be significantly less
than the Boolean rank of a matrix.

\ex  Let $n\geq 3$ and let $D_n\in{\mathcal M}_{n}(\B)$ be the
matrix $J\setminus I$, that is, $D_n$ is the matrix all of whose
entries are ones except that all diagonal entries are zero.  Then,
$\i(D_n)=3$, for any $n\geq 3$.  However, $\b(A)=k$ where
$\displaystyle k=\min\left\{k \mid n\leq
\left(\begin{array}{c}k\\\lceil\frac{k}{2}\rceil\end{array}\right)\right\}$
{\rm (see \cite{DGP})}.  So $\i(D_{20})=3$ while
$\b(D_{20})=6$.\exx

Let $A,B\in\Mmn$.  Since those indices in any set of isolated ones
for $A+B$ whose corresponding entries in $A$ (or $B$) are ones is
a set of isolated ones for $A$ (or $B$, resp.), it follows that:

\l For matrices $A$ and $B$ in $\Mmn$, we have $\i (A+B)\le
\i(A)+\i(B)$.\ll

In \cite{B} the structure of a matrix $A\in\Mmn$ whose isolation
number is $m$   was provided.  Thus,  the set of matrices with
isolation number $m$ can be systematically described, while the
authors are not aware of any systematic description of the set of
matrices  of Boolean rank $m$.


A mapping $T:\Mmn\to\Mmn$ is called a {\em Boolean linear
operator} if for any $X,Y\in\Mmn$, $T(X+Y)=T(X)+T(Y)$, and
$T(O)=O$.

Let $f:\Mmn\to \S$ be a mapping where $\S$ is any set.  Let $S$ be
a subset of $\Mmn$.



For a Boolean linear operator  $\T$ we say that $T$
\begin{itemize}
\item[(1)] {\it preserves f}  if for any $k\in\S$,
$f(T(X))=k$ whenever $f(X)=k$ for all $X\in\Mmn$;
\item[(2)]{\it strongly preserves f}  if for any $k\in\S$,
$f(T(X))=k$ if and only if $f(X)=k$ for all $X\in\Mmn$;

\hskip -1cm and for $\S=\Mmn$, \item[(3)]{\it preserves S}  if
$T(X)\in S$ whenever $X\in S$ for all $X\in\Mmn$;\item[(4)]{\it
strongly preserves S}  if $T(X)\in S$ if and only if $X\in S$ for
all $X\in\Mmn$.
\end{itemize}

By an abuse of language we use the expression "$T$ preserves
Boolean rank $k$ (isolation number $k$)" to mean "$T$ preserves the
set of matrices of Boolean rank $k$ (isolation number $k$)".

A Boolean linear operator $\T$ is called a $(P,Q)$-{\it operator}
if there are permutation matrices $P\in{\mathcal M}_{m}(\B)$ and
$Q\in{\mathcal M}_{n}(\B)$ such that $T(X)=PXQ$ for all
$X\in\Mmn$, or when $m=n$,  $T(X)=PX^tQ$ for all $X\in{\mathcal
M}_{m}(\B)$, where $X^t$ is the transpose of $X$.

In \cite[Theorem 5.3]{BP1}, it was shown that if $T:\Mmn\to\Mmn$
preserves Boolean ranks one and two, then $T$ is a
$(P,Q)$-operator.  Since $\i(A)=1$ if and only if $\b(A)=1$, and
$\i(A)=2$ if and only if $\b(A)=2$,  we have: \t \label{1 and 2}
Let $T:\Mmn\to\Mmn$ be a Boolean linear operator.  Then the
following are equivalent:
\begin{enumerate}\item $T$ preserves the isolation number of matrices,
\item $T$ preserves isolation numbers one and two,
\item $T$ is a $(P,Q)$-operator.\end{enumerate} \tt


\section{Preservers of isolation number two with $T(J)=J$}

\l \label{2Jisbij} Let $T:\Mmn\to\Mmn$ be a Boolean linear
operator with $m,n\geq 3$.    If $T$ preserves isolation number 2
and $T(J)=J$, then $T$ is bijective on the set of cells (hence,
bijective on $\Mmn$).\ll

\begin{proof} Suppose that $E$ is a cell and $T(E)=O$.  Then $\i(J-E)=2$.
But, $T(J-E)=T(J)=J$, contradicting that $T$ preserves isolation
number 2.

Suppose that for some cell $E$, $|T(E)|>1$.  Then there is some
cell $F$ such that $T(J)=T(J-F)$; however, as above, $\i(J-F)=2$.
But, $T(J-F)=T(J)=J$, again a contradiction.  Thus, the image of a
cell is a cell.

Suppose that for some cells $E$ and $F$, $T(E)=T(F)$. Let
$N=J-(E+F)$.  Then $J=T(J)= T(N+E+F)=T(N)+T(E)+T(F)=T(N)+T(E) =
T(N+E)$ since $T(E)=T(F)$.  But, since $N+E=J-F$,  that says that
$T(J-F)=T(J)=J$ and as above we get a contradiction since
$\i(J-F)=2$ and $\i(J)=1$.

Thus, $T$ is bijective on the set of cells.\end{proof}

A matrix $L\in\Mmn$ is called a {\it line matrix} if $L=\sum
\limits_{l=1}^n E_{i,l}$ or $L=\sum\limits_{s=1}^m E_{s,j}$ for
some $i\in\{1,\ldots,n\}$ or for some $j\in\{1,\ldots,n\}$;
$R_i=\sum\limits_{l=1}^n E_{i,l}$ is the $i$th {\it row matrix}
and $C_j=\sum\limits_{s=1}^m E_{s,j}$ is the $j$th {\it column
matrix}. A matrix in $\Mmn$ is a {\em double star} if it is a sum
of a row matrix and a column matrix which share a diagonal entry.
That is, $D_k=R_k+C_k$ is a double star for all $k=1,\cdots,n$.
Two cells are called {\it collinear} if they are dominated by a
line matrix.

\l \label{2jbijlines}  Let $T:\Mmn\to\Mmn$ be a Boolean linear
operator with $m,n\geq 3$.   If $T$ preserves isolation number 2
and $T$ is bijective on the set of cells, then $T$ maps lines to
lines.\ll

\begin{proof}  Suppose that the image of a line is not a line.  Then, there
are two collinear cells whose images are not collinear.  Without
loss of generality, we may assume that
$T(E_{1,1}+E_{1,2})=E_{1,1}+E_{2,2}$.

Let ${\mathcal S}_2$ be the set of all matrices of weight 2 in
$\Mmn$. That is, $A\in{\mathcal S}_2$ if and only if there are
distinct cells $E$ and $F$ such that $E+F=A$. Thus, $T({\mathcal
S}_2)={\mathcal S}_2$ since $T$ is bijective.  If $\G$ is the
subset of ${\mathcal S}_2$ consisting of all those members with
isolation number 2, then $T(\G)=\G$.  Since $T$ is bijective,
$T({\mathcal S}_2\setminus\G)={\mathcal S}_2\setminus\G$.   Since
$T(E_{1,1}+E_{1,2})=E_{1,1}+E_{2,2}$, $E_{1,1}+E_{1,2}\not\in\G$
and $E_{1,1}+E_{2,2}\in \G$, we have a contradiction.  Thus, $T$
maps lines to lines.\end{proof}


\l  \label{bijlinepres} Let $T:\Mmn\to\Mmn$ be a Boolean linear
operator.  Then,  $T$ is bijective and maps lines to lines if and
only if $T$ is a $(P,Q)$-operator.\ll

\begin{proof}  The sufficiency is obvious.  For the necessity, let ${\mathcal
L}=\{R_i | 1\leq i \leq m\} \cup \{C_j | 1\leq j \leq n\}$.  Then,
since $T$ is bijective, $T$ is bijective on ${\mathcal L}$.

If $m\neq n$, since $T$ is bijective,  the image of each $R_i$
must be some $R_k$, and the image of each $C_j$ must be some
$C_l$. This is easily seen by a counting argument.

If $m=n$ and the image of one row is a row and the image of
another row is a column, say without loss of generality that
$T(R_1)=R_1$ and $T(R_2)=C_1$.  Then, $|R_1+R_2|=2n$ while
$|R_1+C_1|= 2n-1$, an impossibility since $T$ is bijective.

Thus for $m=n$, either the image of every row is a row and hence
the image of every column is a column since $T$ is bijective on
${\mathcal L}$.  If the image of every row is a column and the
image of every  column is a row, composing $T$ with the transpose
operator gives an operator that maps rows to rows and columns to
columns.

In both cases, letting $\sigma$ be a permutation such that
$T(R_i)=R_{\sigma(i)}$ and $\tau$ be a permutation such that
$T(C_j)=C_{\tau(j)}$, we have that $T$ is a $(P,Q)$-operator where
$P$ is the permutation matrix corresponding to $\sigma$ and $Q$ is
the permutation matrix corresponding to $\tau$. \end{proof}

\t  \label{2J} Let $m,n\geq 3$ and  $T:\Mmn\to\Mmn$ be a Boolean
linear operator.  Then,  $T$ preserves isolation number 2 and
$T(J)=J$ if and only if $T$ is a $(P,Q)$-operator.\tt \begin{proof} By Lemma
\ref{2Jisbij} we have that $T$ is bijective.  By Lemma
\ref{2jbijlines}, $T$ maps lines to lines.  By Lemma
\ref{bijlinepres} we have that $T$ is a $(P,Q)$-operator.
Conversely, clearly every $(P,Q)$-operator preserves isolation
number 2 and $T(J)=J$.\end{proof}





\section{Preservers of isolation numbers one and $k$}

Throughout this section we will use without reference the fact
that $\b(A)=1$ if and only if $\i(A)=1$.  So if $T$ preserves
isolation number one, $T$ preserves Boolean rank one.

In this section, we provide characterizations of Boolean linear
operators $\T$ that  preserve isolation numbers  $1$ and $k$,
where $1< k\leq m\leq n$.

\l \label{ZnotF}  Let $E$ be a cell $E\in\Mmn$, and $Z$ a
matrix such that $E\leq Z$ and let $\T$ be a Boolean linear
operator.  If $|T(Z)|\leq |Z|$ and $|T(E)| \geq 2$, then there
exists a cell $F\in\Mmn$ such that $T(Z\setminus F)=T(Z)$.\ll

\begin{proof}
Suppose that $E=E_1$  and  $Z$ is a matrix such that
$|T(Z)|\leq |Z|$.  Further, suppose that $E_1 \leq Z$ and
$|T(E_1)| >1$.   If $T(E_1)\neq T(Z)$, there is some cell $E_2
\leq Z$ such that $|T(E_1+E_2)| >|T(E_1)|$.  Continuing in this
manner, if possible, we find cells $E_1,E_2,\cdots, E_i$ such that
$E_1+E_2+\cdots + E_i\leq Z$ and $|T(E_1+E_2+\cdots +
E_i)|>|T(E_1+E_2+\cdots + E_{i-1})|$.  Since $|Z|$ and $|T(Z)|$
are finite, there exists some $j <|T(Z)|$ such that
$T(E_1+E_2+\cdots + E_j) = T(Z)$.  It now follows that there is
some cell $F\leq Z$ such that $T(Z\setminus F)=T(Z)$. \end{proof}


Let ${\mathcal N}_k$ be the set of all Boolean rank one matrices
in $\Mmn$ which are dominated by a  matrix whose isolation number
is $k$.  Suppose that $w$ is the largest weight of any matrix in
${\mathcal N}_k$.   Let ${\mathcal N}_k^+$ be the set of all
elements of ${\mathcal N}_k$ that are of weight $w$.    Since
$X\in{\mathcal N}_k^+$ implies $PXQ\in{\mathcal N}_k^+$ for any
permutation matrices, $P$ and $Q$ of appropriate orders, the
following is easily seen.

\l \label{maxW} Let $E$ be a cell in $\Mmn$.  Then there is an
element of ${\mathcal N}_k^+$ dominating $E$. \ll

\l \label{image}  If $T$ preserves isolation number one, then
$\i(T(A))\leq\b(A)$ for all $A\in\Mmn$.\ll

\begin{proof}Let $A\in\Mmn$ and suppose $\b(A)=l$.  Then
$A=A_1+A_2+\cdots+A_l$, where $\b(A_i)=\i(A_i)=1$.  Then, using
Lemma \ref{i leq b},  $\i(T(A))\leq \b(T(A))=\b (T(\sum_{i=1}^l
A_i))\leq  \sum_{i=1}^l \b(T(A_i)) =\sum_{i=1}^l 1=l$.  That is,
$\i(T(A))\leq \b(A).$\end{proof}



An operator $\T$ is {\it singular} if $T(X)=O$ for some nonzero
$X\in\Mmn$; otherwise $T$ is {\it nonsingular}. Notice that if $T$
is a $(P,Q)$-operator, then $T$ is nonsingular.  Further, due to
the nature of Boolean operators, we note that a nonsingular
operator need not be invertible, unlike the field case.

\l  \label{cell} If $\T$ is  a Boolean linear operator which
preserves isolation numbers 1 and $k$ for some $1<k\leq m$, then
$T$ maps  cells to  cells.\ll

\begin{proof} If $k=m$, then $T$ preserves Boolean ranks 1 and $m$ and by \cite[Theorem 3.5]{BS2} $T$ is a $(P,Q)$-operator and hence it maps cells to cells.  Thus, assume that $k<m$.

 Since $T$ preserves isolation number  1, $T$ is nonsingular.
Suppose that the image of some cell dominates two or more cells.
Say, $E=E_1$ is such a cell and $|T(E_1)| >1$.
  By Lemma \ref{maxW}, there is $Z\in{\mathcal N}_k^+$ that dominates $E_1$.
That is, $E_1 \leq Z$ and $|T(E_1)| >1$.  Since $Z$ is of
isolation number one and $T$ preserves both isolation number one
and isolation number $k$,  $T(Z)\in{\mathcal N}_k$. Thus,
$|T(Z)|\leq |Z|$ since  $Z\in{\mathcal N}_k^+$.  By Lemma \ref{ZnotF},  there is some cell $F\leq
Z$ such that $T(Z\setminus F)=T(Z)$.  Without loss of generality,
we may assume that $F=E_{1,1}$ and that
$Z=\left[\begin{array}{cc}J_{p,q}&O\\O&O\end{array}\right]$.

If $q=n$, then we must have $p = m-k+1$ (otherwise we could add a
row of ones to $Z$ and still be in ${\mathcal N}_k$).  For $A =
\left[\begin{array}{cc}O&O\\O&I_{k-1}\end{array}\right]$, $A+Z$ is
of isolation number $k$ and dominates $Z$.   Let $B=(A+Z)\setminus
(E_{1,1}+E_{m,n})$. Then $\i(B)=k$, while $\i(B+E_{1,1})= k-1$.
Also, since $\b(B+E_{1,1})=k-1$ and , since $T$ preserves Boolean
rank one,  $\b(T(B+E_{1,1}))\leq k-1$.  Thus, by Lemma \ref{image},
$\i(T(B+E_{1,1}))\leq k-1$.  Further,
$\i(T(B))=k$, since $T$ preserves isolation number $k$.  But
$T(B)=T(B+E_{1,1})$, a contradiction.  Thus, the image of a cell
is a cell.

If $p=m$, a similar argument shows that $T$ maps cells to cells.

Now,  assume that $p<m$ and $q<n$.  Since $Z\in{\mathcal N}_k^+$,
we must have that $(m-p)+(n-q)\geq k-1$.  Let $s=m-p$ and $t=n-q$.
Let
\[B=\left[\begin{array}{ccc}O_{p-t+1,q+1-s}&O_{p-t+1,s}&O_{p-t+1,t-1}
\\O_{t-1,q+1-s}&O_{t-1,s}&I_{t-1}\\O_{s,q+1-s}&I_s&O_{s,t-1}\end{array}\right].\]
Then $\i(Z+B)=k-1$ and $\i((Z\setminus E_{1,1})+B)=k$, a
contradiction since $T(Z+B)=T((Z\setminus E_{1,1})+B)$ and cannot
have isolation number both $k$ and something strictly less than
$k$.\end{proof}

 \l \label{bij} If $\T$ is a Boolean linear operator which preserves isolation numbers 1 and $k$ for
 some $1<k\leq m$, then $T$ is a bijection on $\E$ and hence invertible on $\Mmn$.\ll

 \begin{proof} We  only need to show that $T$ is injective on $\E$.
 By Lemma \ref{cell}, the image of a cell is a cell.  Suppose
 that $T$ is not bijective on the set of cells.  Then, without loss of
 generality, we may assume that $T(E_{1,1})=T(E_{i,j})$ and $i\leq 2$.
 But then, for $Z=\left[\begin{array}{c} J_{m-k+2,n}\\O_{k-2,n}\end{array}\right]$
 and $A=\left[\begin{array}{cc} O&O\\O&I_{k-2}\end{array}\right]$, let
 $X= Z+ A$, and $Y= (Z\setminus E_{1,1})+ A$.  Then
 $\i(X)=\b(X)=k-1$ while $\i(Y)=k$ and $T(X)=T(Y)$.  Since $T$ preserves isolation number $k$, $i(T(Y))=k$,  and by
 Lemma \ref{image}, $\i (T(X))\leq \b(X)= k-1$.  That is, $i(T(X))\leq k-1 < k = i(T(Y))=i(T(X))$, a contradiction.  Thus $T$ is
 bijective on the set of cells.  \end{proof}

 From Theorem 3.1 in \cite{BP1} we have:

 \t[See {\cite{BP1}}] \label{BPthm} Let $\T$ be a Boolean linear operator; then $T$ preserves Boolean rank 1 and is
 invertible if and only if $T$ is a $(P,Q)$-operator.\tt

 Since a matrix has Boolean rank one if and only if it has isolation number one, we have:

 \c \label{BPcor} Let $\T$ be a Boolean linear operator; then $T$ preserves isolation number 1 and is
 invertible if and only if $T$ is a $(P,Q)$-operator.\cc

 \t \label{1k} For a Boolean linear operator $\T$, the following are equivalent:
 \begin{itemize}
\item[(1)] T preserves the isolation number;
\item[(2)] T preserves isolation numbers $1$ and $k$ for
 some $1<k\leq m$ ;
\item[(3)] T is a $(P,Q)$-operator.
\end{itemize} \tt

 \begin{proof} If $\T$ preserves isolation numbers 1 and $k$ for
 some $1<k\leq m$, then $T$ is a bijection on $\E$ and hence invertible on $\Mmn$
 by Lemma \ref{bij}. Thus $T$ is a $(P,Q)$-operator by Corollary  \ref{BPcor}.

 The other implications are obvious. \end{proof}



\section{Preservers of adjacent isolation numbers}

A {\em tournament matrix} is a square matrix $M\in{\mathcal
M}_n(\B) $ such that $M+M^t=J-I$, that is, a $(0,1)$-matrix $M$,
such that $m_{i,i}=0$ and for $i\neq j$, $m_{i,j}=1$ if and only
if $m_{j,i}=0$.  It may be noted that if $M$ is an $r\times r$
tournament matrix and
$A=\left[\begin{array}{cc}I_{r}+M&J_{r,n-r}\\J_{m-r,r}&J_{m-r,n-r}\end{array}\right]$,
then $\i(A)=r$ and, if $ B>A$, then  $\i(B)<\i(A)$.

\l \label{k and k+1 cells}  Let $\T$ be a Boolean linear operator.
If $\T$ preserves isolation numbers $k$ and $k+1$ for
 some $1\leq k\leq m-1$, then $T$ is a bijection on $\E$.\ll
\begin{proof}  By virtue of Theorem \ref{1 and 2}, we may assume that $k\geq
2$.

Suppose that $T(X)=O$ for some nonzero $X\in\Mmn$.  Then, for some
$E_{i,j}$, $T(E_{i,j})=O$. Without loss of generality, we may
assume that $i\neq j$ and $1\leq i,j \leq k+1$.  Let $M$ be a
$(k+1)\times(k+1)$ tournament matrix such that $M\not\geq
E_{i,j}$. Let
$\Xi=\left[\begin{array}{cc}I_{k+1}+M&J_{k+1,n-k-1}\\J_{m-k-1,k+1}&J_{m-k-1,n-k-1}\end{array}\right]$.
Then, $\i(\Xi)=k+1$ while $\i(\Xi+E_{i,j})=k$, so that
$\i(T(\Xi))=k+1$ and $\i(T(\Xi+E_{i,j}))=k$.  But since
$T(E_{i,j})=O$, $T(\Xi+E_{i,j})=T(\Xi)$, a contradiction.  Thus
$T$ is nonsingular.

Let $L=T^q$, where $T^q$ is idempotent.  Then $L$ is idempotent and
preserves isolation numbers $k$ and $k+1$.  Since $T$ is
nonsingular, so is $L$.  Suppose for some $(i,j)$,
$|L(E_{i,j})|>1$.  Then, $L(E_{i,j})=Z+F$, where $F$ is a cell and,
as in the previous paragraph, $\Xi\geq E_{i,j}$ and $\Xi\not\geq
F$.  Thus, $\i(\Xi+E_{i,j})=k+1$ while $\i(\Xi+F)=k$ so that
$\i(L(\Xi+E_{i,j}))=k+1$ while $\i(L(\Xi+F))=k$.

Now, $L(\Xi)=L(\Xi+E_{i,j})=L(\Xi)+L(E_{i,j})=L(\Xi)+Z+F$.  Since
$L$ is idempotent,
$L(\Xi)=L^2(\Xi)=L(L(\Xi)+Z+F)=L(L(\Xi)+Z)+L(F)=
L((L(\Xi)+Z+F)+Z)+L(F)=
L(L(\Xi)+Z+F+Z)+L(F)=L(L(\Xi)+Z+F)+L(F)=L^2(\Xi)+L(F)=L(\Xi)+L(F)
= L(\Xi+F)$.  But, $\i(L(\Xi))=k+1$ while $\i(L(\Xi+F))=k$, a
contradiction.  Thus, $L$, and hence $T$ maps cells to cells.

Now, suppose that $E$ and $F$ are cells and $T(E)=T(F)$.  If
$F\neq E$, we may assume that $\Xi\geq E$ and $\Xi\not\geq F$. But
then, $\i(\Xi+E)=k+1$ while $\i(\Xi+F)=k$ so that
$\i(T(\Xi+E))=k+1$ and $\i(T(\Xi+F))=k$.  But,
$T(\Xi+E)=T(\Xi+F)$, a contradiction.\end{proof}

\l \label{k and k+1 lines}  Let $\T$ be a Boolean linear operator.
If $\T$ preserves isolation numbers $k$ and $k+1$ for
 some $1\leq k\leq m-1$, then $T$ maps lines to lines.\ll
\begin{proof} By Lemma \ref{k and k+1 cells}, $T$ is bijective on the set of
cells.  Suppose $T$ does not map lines to lines, then it must map
some pair of noncollinear cells to a pair of collinear cells since
$T$ is bijective on the set of cells.   Without loss of
generality, we may assume that
$T(E_{1,1}+E_{2,2})=E_{1,1}+E_{1,2}$.  Let
$E_3,E_4,\cdots,E_{k+1}$ be cells such that $T(E_{j,j})=E_j$ for
$3\leq j\leq k+1$.  Then,
$\i(E_{1,1}+E_{1,2}+E_3+E_4+\cdots+E_{k+1})\leq k$. Since
$\i(E_{1,1}+E_{2,2}+E_{3,3}+\cdots+E_{k+1,k+1})=k+1$,
$\i(T(E_{1,1}+E_{2,2}+E_{3,3}+\cdots+E_{k+1,k+1}))=k+1$.  But
$T(E_{1,1}+E_{2,2}+E_{3,3}+\cdots+E_{k+1,k+1})=E_{1,1}+E_{1,2}+E_3+E_4+\cdots+E_{k+1}$
which has the isolation number less than $k+1$, a contradiction.
Thus, $T$ maps lines to lines.\end{proof}


\t \label{k+1} Let $\T$ be a Boolean linear operator.  If $\T$
preserves isolation numbers $k$ and $k+1$ for
 some $1\leq k\leq m-1$, then $T$ is a $(P,Q)$-operator.\tt
\begin{proof} By Lemma \ref{k and k+1 cells}, $T$ is bijective.  By Lemma
\ref{k and k+1 lines}, $T$ maps lines to lines.  The theorem now
follows by applying Theorem \ref{bijlinepres}. \end{proof}

\section{Summary}

In \cite{BS}, the authors prove the following.

\t [See {\cite[Theorem 3.8]{BS}}] Let $\T$ be a Boolean linear
operator.  Then $T$ strongly preserves isolation number $k$ for
any $1\leq k \leq \min\{m,n\}$ if and only if $T$ is a
$(P,Q)$-operator.\tt

A compilation of the above theorem and Theorems \ref{2J},
\ref{1k}, and \ref{k+1} summarizes the results in this article.

\t For a Boolean linear operator $\T$, the following are
equivalent:
\begin{enumerate} \item T preserves the isolation number;
\item T preserves isolation numbers $1$ and $k$ for
 some $1<k\leq m$;
 \item $\T$ preserves isolation numbers $k$ and $k+1$ for
 some $1\leq k\leq m-1$; \item $T$ preserves isolation number 2 and
$T(J)=J$; \item $T$ strongly preserves isolation number $k$ for
any $1\leq k \leq \min\{m,n\}$;
\item T is a $(P,Q)$-operator.
\end{enumerate} \tt

\section*{Acknowledgement}

This research was supported by the Basic Science Research Program through
the National Research Foundation of Korea (NRF) funded by the
Ministry of Education, Science and Technology (No.\,2012R1A1A2042193).


\begin{thebibliography}{99}

\bibitem{A}{\sc K.\,Akiko}, {\it Complexity of the sex-equal stable marriage problem},
Japan J. Indust. Appl. Math.  {\bf 10}(1993), 1--19. (English summary)

\bibitem{B}
{\sc L.\,B.\,Beasley},  {\it Isolation number versus Boolean rank}, Linear
Algebra  Appl. {\bf436}(2012), 3469--3474.


\bibitem{BP1}
{\sc L.\,B.\,Beasley, N.\,J.\,Pullman}, {\it Boolean rank preserving
operators and Boolean rank-1 spaces}, Linear Algebra Appl. {\bf
59}(1984), 55--77.

\bibitem{BS2}
{\sc L.\,B.\,Beasley,  S.\,Z.\,Song}, {\it Linear operators
that preserve Boolean rank}, in press.

\bibitem{BS}
{\sc L.\,B.\,Beasley,  S.\,Z.\,Song, Y.\,B.\,Jun}, {\it Linear operators
that preserve graphical properties of  matrices: isolation
numbers}, in press.

\bibitem{BM} {\sc J.\,A.\,Bondy, U.\,S.\,R.\,Murty}, {\it Graph Theory},  Springer, New York, 2008.

\bibitem{Br} {\sc D.\,E.\,Brown}, {\em Finding the isolation number of a graph
is NP-complete}, personal communication (david.e.brown@usu.edu).

\bibitem{BR} {\sc R.\,Brualdi, H.\,Ryser}, {\it Combinatorial Matrix
Theory}, Cambridge University Press, New York, 1991.

\bibitem{DGP} {\sc D.\,de Caen, D.\,Gregory, N.\,Pullman}, {\it The
Boolean rank of zero one matrices}, in: {\em Proceedings of the Third
Caribbean Conference on Combinatorics and Computing}, (C.\,C.\,Cadogan, Ed.), Barbados,
(1981), 169--173.


\bibitem{F} {\sc G.\,Fr\"obenius}, {\em Uber die Darstellung der entlichen Gruppen
durch Linear Substitutionen}, S. B. Deutsch. Akad. Wiss. Berlin,
(1897), 994--1015.
,v
\bibitem{GP}  {\sc D.\,A.\,Gregory, N.\,J.\,Pullman}, {\it Semiring rank: Boolean and nonnegative rank
factorizations}, J. Combin. Inform. System Sci. {\bf 8}(1983),
223--233.

\bibitem{GPJ}{\sc D.\,Gregory, N.\,J.\,Pullman, K.\,F.\,Jones, J.\,R.\,Lundgren}, {\it Biclique
coverings of regular bigraphs and minimum semiring ranks of
regular matrices}, J. Combin. Theory Ser. B {\bf 51}(1991),
73--89.

\bibitem{GKP} {\sc D.\,A.\,Gregory, S.\,J.\,Kirkland, N.\,J.\,Pullman}, {\it A
bound on the exponent of a primitive matrix using Boolean rank},
 Linear Algebra Appl. {\bf 217}(1995), 101--116.

\bibitem{GM} {\sc A.\,E.\,Guterman, A.\,V.\,Mikhalev}, {\em General algebra
and linear transformations preserving matrix invariants}, {J.
Math. Sci.} {\bf 128}(2005), 3384--3395.


\bibitem{PL2} {\sc C.-K.\,Li, S.\,J.\,Pierce},
{\em Linear preserver problems}, {Amer. Math. Monthly}  {\bf
108}(2001), 591--605.


\bibitem{Mar} {\sc G.\,Markowsky}, {\it Ordering D-classes and computing the
Schein rank is hard},  Semigroup Forum {\bf 44}(1992), 373--375.

\bibitem{PL} {\sc S.\,J.\,Pierce et al.}, {\it A survey of linear preserver problems},
Linear and Multilinear Algebra {\bf 33}(1992), 1--129.



\end{thebibliography}


%\end{linenumbers}

\end{document}
http://en.wikipedia.org/wiki/Stable_marriage_problem


Kato, Akiko(J-TOKYOE-IP)
Complexity of the sex-equal stable marriage problem. (English summary)
Japan J. Indust. Appl. Math.  10  (1993),  no. 1, 1â??19.
