CHARACTERIZATIONS OF BOOLEAN RANK PRESERVERS OVER BOOLEAN MATRICES

The Pure and Applied Mathematics.
2014.
May,
21(2):
121-128

- Received : March 01, 2014
- Accepted : May 01, 2014
- Published : May 31, 2014

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

The Boolean rank of a nonzero
m
×
n
Boolean matrix
A
is the least integer
k
such that there are an
m
×
k
Boolean matrix
B
and a
k
×
n
Boolean matrix
C
with
A = BC
. In 1984, Beasley and Pullman showed that a linear operator preserves the Boolean rank of any Boolean matrix if and only if it preserves Boolean ranks 1 and 2. In this paper, we extend this characterization of linear operators that preserve the Boolean ranks of Boolean matrices. We show that a linear operator preserves all Boolean ranks if and only if it preserves two consecutive Boolean ranks if and only if it strongly preserves a Boolean rank
k
with 1 ≤
k
≤ min{
m,n
}.
binary Boolean algebra
consists of the set
= {0, 1} equipped with two binary operations, addition and multiplication. The operations are defined as usual except that 1 + 1 = 1.
Let
denote the set of all
m
×
n
Boolean matrices with entries in
. The usual definitions for adding and multiplying matrices apply to Boolean matrices as well. Throughout this paper, we shall adopt the convention that 3 ≤
m
≤
n
unless otherwise specified.
The (
Boolean
)
rank, b(A)
, of nonzero
A
∈
is the least integer
k
such that there are Boolean matrices
B
∈
and
C
∈
with
A
=
BC
. It follows that 1 ≤
b(A)
≤
m
for all nonzero
A
∈
. The Boolean rank of the zero Boolean matrix is 0.
A mapping
T
:
→
is called a
linear operator
if
T
(
αA
+
βB
) =
αT(A)
+
βT(B)
for all
A,B
∈
and for all
α,β
∈
.
A linear operator
T
on
is called a (
P,Q
)-
operator
if there are permutation matrices
P
and
Q
of orders
m
and
n
, respectively, such that
T(X)
=
PXQ
for all
X
, or
m
=
n
and
T(X)
=
PX^{t}Q
for all
X
, where
X^{t}
is the transpose of
X
.
Let 1 ≤
k
≤
m
. For a linear operator
T
on
, we say that
Beasley and Pullman (
[1]
) have characterized linear operators on
that preserve Boolean rank as follows:
Theorem 1.1.
For a linear operator T on
,
the following are equivalent
:
The characterization of linear operators on vector space of matrices which leave functions, sets or relations invariant began over a century ago when in 1897 Fröbenius
[7]
characterized the linear operators that leave the determinant function invariant. Since then, several researchers have investigated the preservers of nearly every func- tion, set and relation on matrices over fields. See
[6
,
7]
for an excellent survey of Linear Preserver Problems through 2001. For Boolean matrix and Boolean rank are important research topics on matrix theory. See
[4
,
5]
for detailed contents and applications on Boolean matrix theory.
Recently Beasley and Song (
[3]
) have obtained a new characterization of Theorem 1.1: For a linear operator
T
on
,
T
preserves Boolean rank if and only if
T
preserves Boolean ranks 1 and
k
, where 1 ＜
k
≤
m
. They also have obtained characterizations of the linear transformations that preserve term rank between different matrix spaces over semirings containing the binary Boolean algebra in
[2]
.
In this paper, we extend Theorem 1.1 to any two consecutive Boolean rank preservers. Furthermore we obtain other characterizations.
O
is an arbitrary zero matrix and
J_{m,n}
is the
m
×
n
matrix all of whose entries are 1. A matrix in
is called a
cell
if it has exactly one 1 entry. We denote the cell whose one 1 entry is in the
(i, j)^{th}
position by
E_{i,j}
. Further we let
ε_{m,n}
be the set of all cells in
. That is,
ε_{m,n}
= {
E_{i,j}
| 1 ≤
i
≤
m
, 1 ≤
j
≤
n
}.
If
A
and
B
are Boolean matrices in
, we say that
A dominates B
(written
B
⊑
A
or
A
⊒
B
) if
a_{i,j}
= 0 implies
b_{i,j}
= 0 for all
i
and
j
. This provides a reflexive and transitive relation on
. For Boolean matrices
A
and
B
in
with
B
⊑
A
, we define
A
＼
B
to be the Boolean matrix
C
such that
c_{i,j}
= 1 if and only if
a_{i,j}
= 1 and
b_{i,j}
= 0 for all
i
and
j
.
Lemma 2.1
(
[1]
).
If T is a linear operator on
,
then T is invertible if and only if T permutes ε_{m,n}
.
A Boolean matrix
L
∈
is called a
line matrix
if
L
=
or
L
=
for some
i
∈ {1, …,
m
} or for some
j
∈ {1, …,
n
}:
R_{i}
=
is the
i
th
row matrix
and
C_{j}
=
is the
j
th
column matrix
.
For a linear operator
T
on
, we say that
T preserves line matrices
if
T(L)
is a line matrix for every line matrix
L
.
Lemma 2.2.
Let T be an invertible linear operator on
.
Then T preserves line matrices if and only if T is a (P,Q)-operator
.
Proof
. By Lemma 2.1,
T
permutes
ε_{m,n}
and hence
T(J_{m,n})
=
J_{m,n}
. Let
T
preserve all line matrices. Now we will claim that either
If
m
≠
n
, (1) is satisfied since
T
is invertible and preserves all line matrices.
Thus we assume that
m = n
. Suppose that the claim is not true. Then there are distinct row matrices
R_{i}
and
R_{j}
(or column matrices
C_{i}
and
C_{j}
) such that
T(R_{i})
is a row matrix and
T(R_{j})
is a column matrix. But then
T(J_{m,n})
=
T(R_{1})
+⋯
T(R_{i})
+⋯+
T(R_{j})
+⋯+
T(R_{n})
cannot dominate
J_{m,n}
. This contradicts
T(J_{m,n})
=
J_{m,n}
. Hence the claim is true.
Case (1): We note that
T(R_{i})
=
R_{α(i)}
for all
i
and
T(C_{j})
=
C_{β(j)}
for all
j
, where
α
and
β
are permutations of {1, …,
m
} and {1, …,
n
}, respectively. Then for any cell
E_{i,j}
, we have
T(E_{i,j})
=
E_{α(i),β(j)}
. Let
P
and
Q
be the permutation matrices corresponding to
α
and
β
, respectively. Then for any Boolean matrix
we have
Hence
T
is a (
P,Q
)-operator.
Case (2): We note that
m = n
,
T(R_{i}) = C_{α(i)}
for all
i
and
T(C_{j}) = R_{β(j)}
for all
j
, where
α
and
β
are permutations of {1, ⋯,
n
}. By a parallel argument similar to Case (1), we obtain that
T(X)
is of the form
T(X) = PX^{t}Q
, and thus
T
is a (
P,Q
)-operator. The converse is obvious. □
For nonzero
A
∈
, it is well known (
[1]
) that
b(A)
is the least integer
k
such that
A
is the sum of
k
Boolean matrices of Boolean rank 1. This establishes the following:
Lemma 2.3.
For Boolean matrices A and B in
,
we have
b (A + B ) ≤ b(A) + b(B) .
Theorem 2.4.
Let T be an invertible linear operator on
and
1 ≤
k
≤
m
.
Then T preserves Boolean rank k if and only if T is a (P;Q)-operator
.
Proof
. By Lemma 2.1,
T
permutes
ε_{m,n}
. Assume that
T
preserves Boolean rank
k
. Now, we will show that
T
preserves line matrices, and then
T
is a (
P
,
Q
)-operator by Lemma 2.2. For the case of
k
= 1, it is clear that
T
preserves line matrices since the Boolean rank of every line matrix is 1. Thus we assume that
k
≥ 2. Suppose that
T
does not preserve a line matrix. Then there are two distinct cells
E_{i,j}
and
E_{s,t}
that are not dominated by the same line matrix such that
T(E_{i,j})
and
T(E_{s,t})
are dominated by the same line matrix. Without loss of generality, we assume that
T
(
E
_{1,1}
+
E
_{2,2}
) =
E
_{1,1}
+
E
_{1,2}
. So, we have a contradiction for the case of
k
= 2. Hence we assume that
k
≥ 3. Then for the Boolean matrix
A
=
E
_{3,3}
+ ⋯ +
E_{k,k}
, we have
b
(
E
_{1,1}
+
E
_{2,2}
+
A
) =
k
. But by Lemma 2.3,
b (T (E _{1,1} + E _{2,2} + A )) ≤ b (T (E _{1,1} + E _{2,2})) + b(T(A)) ≤ 1 + (k − 2) = k − 1,
a contradiction to the fact that
T
preserves Boolean rank
k
. Hence
T
preserves line matrices. The converse is obvious. □
T
on
is
singular
if
T(X)
=
O
for some nonzero
X
∈
; otherwise
T
is
nonsingular
. In fact, if
T
is a singular linear operator on
, then we can easily check that
T(E) = O
for some cell
E
. Further, if
T
is a (
P,Q
)-operator on
, then
T
is nonsingular.
Example 3.1.
For 1 ≤
k
≤
m
, let
A
=
E
_{1,1}
+
E
_{2,2}
+ ⋯ +
E_{k,k}
2
. Define an operator
T
on
by
T(O) = O
and
T(X) = A
for all nonzero
X
2
. Clearly,
T
is linear, nonsingular and preserves Boolean rank
k
, while
T
does not preserve Boolean rank.
The number of nonzero entries of a Boolean matrix
A
∈
is denoted by #(
A
).
Lemma 3.2.
Let
1 ≤
k
＜
m and
1 ≤ l ≤
m
.
Assume that T is a linear operator on
.
If
then T is nonsingular.
Proof
. If
T
is singular, then
T(E) = O
for some cell
E
. Hence we have a contradiction for the case of
k
=
l
= 1. Thus we assume that
k, l
≥ 2. Now, choose Boolean matrices
A
and
B
with
E
⊑
A
and
E
⊑
B
such that
b(A)
= #(
A
) =
k
+ 1 and
b(B)
= #(
B
) =
l
. It follows that
b
(
A
＼
E
) =
k
and
b
(
B
＼
E
) =
l
− 1. But then
T(A)
=
T
(
A
＼
E
) +
T(E)
=
T
(
A
＼
E
) contradicts the condition (i) and
T(B)
=
T
(
B
＼
E
) +
T(E)
=
T
(
B
＼
E
) contradicts the condition (ii). Hence
T
is nonsingular. □
Lemma 3.3.
Let T be a linear operator on
.
If
then T maps cells to cells.
Proof
. If
T
preserves Boolean rank
k
and
k
+ 1 with 1 ≤
k
≤
m
− 1, or
T
strongly preserves Boolean rank
k
with 1 ≤
k
≤
m
, then
T
is nonsingular by Lemma 3.2. Suppose that
T
does not map cells to cells, in particular suppose that
T(E)
dominates two cells for some cell
E
. By permuting we may assume that
T(E)
⊒
E
+
F
for some cell
F
≠
E
.
If
E
and
F
are in the same row, we may assume by permuting that
E
=
E
_{1,k+1}
and
F
=
E
_{1,k}
. If
E
and
F
are in the same column, we may assume by permuting that
E
=
E
_{k+1,1}
and
F
=
E
_{k,1}
. If
E
and
F
are in different rows and different columns, we may assume by permuting that
E
=
E
_{1,k+1}
and
F
=
E
_{2,k−1}
. For 1 ≤
r
≤
m
, let
W_{r}
= [
] where
= 0 if and only if
i
+
j
≤
r
. Then
b(W_{r})
=
r
. Since
E
⊑
W
_{k+1}
and
F
⋢
W
_{k+1}
, we have that
b
(
W
_{k+1}
+
E
) =
k
+1 and
b
(
W
_{k+1}
+
F
) =
k
.
Let
L = T^{d}
where
d
is chosen so that
L
is idempotent (
L
^{2}
=
L
). Then,
L
preserves Boolean ranks
k
and
k
+ 1 for case (i), or
L
strongly preserves Boolean rank
k
for case (ii) and
L(E)
⊒
E
+
F
.
Now, since
L(E)
=
F
+
X
for some Boolean matrix
X
,
L(E) + F = (X + F ) + F = X + F = L(E)
and since
L
is idempotent,
L(E) = L ^{2}(E ) = L(L(E)) = L (L(E) + F )
= L ^{2}(E ) + L(F) = L(E) + L(F) = L (E + F ).
That is,
L
(
E
+
F
) =
L(E)
. Thus if
Y
is any Boolean matrix which dominates
E
, we have that
L
(
Y
+
F
) =
L(Y)
since
L
(
Y
+
F
) =
L
(
Y
+
E
+
F
) =
L(Y)
+
L
(
E
+
F
) =
L(Y)
+
L(E)
=
L
(
Y
+
E
) =
L(Y)
. Thus,
L (W _{k+1}) = L (W _{k+1} + F ).
However,
b
(
W
_{k+1}
) =
k
+ 1,
b
(
W
_{k+1}
+
F
) =
k
and
L
preserves both Boolean rank
k
and
k
+1 for case (i) or
L
strongly preserves Boolean rank
k
for case (ii). Thus, we have
k + 1 = b (L (W _{k+1})) = b (L (W _{k+1} + F )) = k ,
which is a contradiction for the both cases (i) and (ii). Therefore
T
maps cells to cells. □
Theorem 3.4.
Let T be a linear operator on
.
Then T preserves Boolean rank if and only if
Proof
. Let
T
preserve Boolean ranks
k
and
k
+1 or
T
strongly preserves Boolean rank
k
. Then
T
maps cells to cells by Lemma 3.3. Now, suppose that
T
is not invertible. Then
T(E)
=
T(F)
for some distinct cells
E
and
F
by Lemma 2.1. If
b
(
E
+
F
) = 2, choose a Boolean matrix
A
∈
with
b(A)
= #(
A
) =
k
−1 such that
b
(
E
+
A
) =
k
and
b
(
E
+
F
+
A
) =
k
+ 1. But then
k
+ 1 =
b
(
T
(
E
+
F
+
A
)) =
b
(
T
(
E
+
A
)) =
k
, a contradiction for both cases (i) and (ii). For the case of
b
(
E
+
F
) = 1, we may assume, without loss of generality, that
E
=
E
_{1,1}
and
F
=
E
_{1,2}
. Let
B
=
E
_{2,1}
+
E
_{2,2}
+
E
_{3,3}
+ ⋯ +
E
_{k+1,k+1}
. Then
b
(
E
+
F
+
B
) =
k
and
b
(
E
+
B
) =
k
+ 1. But then
k
=
b
(
T
(
E
+
F
+
B
)) =
b
(
T
(
E
+
B
)) =
k
+ 1, a contradiction for both cases (i) and (ii). Thus
T
is invertible. By Theorem 2.4,
T
is a (
P, Q
)-operator and hence
T
preserves Boolean rank by Theorem 1.1. The converse is obvious. □
Recently Beasley and Song (
[3]
) showed that for a linear operator
T
on
,
T
preserves Boolean rank if and only if
T
preserves Boolean ranks 1 and
k
, where 2 ≤
k
≤
m
.
Now we summarize our results by:
Theorem 3.5.
Let T be a linear operator on
.
Then the following are equivalent
:
As a concluding remark, we suggest to prove the following conjecture:
Conjecture 3.6.
Let T be a linear operator on
.
Then T preserves Boolean rank if and only if T preserves any two Boolean ranks h and k with
1 ≤
h
＜
k
≤
m
≤
n
.

1. INTRODUCTION

The
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- (1)T preserves Boolean rank kifb(T(X)) = kwheneverb(X) = kfor allX;
- (2)T strongly preserves Boolean rank kif,b(T(X)) = kif and only ifb(X) = kfor allX;
- (3)T preserves Boolean rankif it preserves Boolean rankkfor allk∈ {1, 2, …,m}.

PPT Slide

Lager Image

PPT Slide

Lager Image

- (i)T preserves Boolean rank;
- (ii)T preserves Boolean ranks1and2;
- (iii)T is a (P,Q)-operator.

PPT Slide

Lager Image

2. PRELIMINARIES

The matrix
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- (1)Tmaps {R1, …,Rm} onto {R1, …,Rm} and maps {C1, …,Cn} onto {C1, …,Cn}, or
- (2)Tmaps {R1, …,Rn} onto {C1, …,Cn} and maps {C1, …,Cn} onto {R1, …,Rn}.

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

3. CHARACTERIZATIONS OF BOOLEAN RANK PRESERVERS

An operator
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- (i)T preserves Boolean rank k and k+ 1,or
- (ii)T strongly preserves Boolean rank l,

PPT Slide

Lager Image

- (i)T preserves Boolean rank k and k+ 1with1 ≤k≤m− 1,or
- (ii)T strongly preserves Boolean rank k with1 ≤k≤m,

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- (i)T preserves Boolean rank k andk+ 1with1 ≤k≤m− 1,or
- (ii)T strongly preserves Boolean rank k with1 ≤k≤m.

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- (i)T preserves Boolean rank;
- (ii)T preserves Boolean ranks k andk+ 1,where1 ≤k≤m− 1;
- (iii)T preserves Boolean ranks1and k, where2 ≤k≤m;
- (iv)T strongly preserves Boolean rank k, where1 ≤k≤m;
- (v)T is a (P,Q)-operator.

PPT Slide

Lager Image

Acknowledgements

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

Beasley LeRoy B.
,
Pullman Norman J.
1984
Boolean rank preserving operators and Boolean rank-1 spaces
Linear Algebra and Its Applications
59
55 -
77
** DOI : 10.1016/0024-3795(84)90158-7**

Beasley L.B.
,
Song S.Z.
2013
Linear transformations that preserve term rank between different matrix spaces
J. Korean Math. Sci. Soc
50
(1)
127 -
136
** DOI : 10.4134/JKMS.2013.50.1.127**

Beasley L.B.
,
Song S.Z.
2013
Linear operators that preserve Boolean rank of Boolean matrices
Czech. Math. J.
63
435 -
440
** DOI : 10.1007/s10587-013-0027-z**

deCaen D.
,
Gregory D.
,
Pullman N.
1981
The Boolean rank of zero one matrices
Proceedings of the Third Caribbean Conference on Combinatorics and Computing
Barbados
169 -
173

Kim K.H.
1982
Boolean Matrix Theory and Applications
Marcel Dekker
New York

Li C.-K.
,
Pierce S.J.
2001
Linear preserver problems
Amer. Math. Monthly
108
(7)
591 -
605
** DOI : 10.2307/2695268**

Pierce S.J.
1992
A Survey of Linear Preserver Problems
Linear and Multilinear Algebra
33
1 -
119
** DOI : 10.1080/03081089208818176**

Citing 'CHARACTERIZATIONS OF BOOLEAN RANK PRESERVERS OVER BOOLEAN MATRICES
'

@article{ SHGHCX_2014_v21n2_121}
,title={CHARACTERIZATIONS OF BOOLEAN RANK PRESERVERS OVER BOOLEAN MATRICES}
,volume={2}
, url={http://dx.doi.org/10.7468/jksmeb.2014.21.2.121}, DOI={10.7468/jksmeb.2014.21.2.121}
, number= {2}
, journal={The Pure and Applied Mathematics}
, publisher={Korean Society of Mathematical Education}
, author={BEASLEY, LEROY B.
and
KANG, KYUNG-TAE
and
SONG, SEOK-ZUN}
, year={2014}
, month={May}