Advanced
CHARACTERIZATIONS OF BOOLEAN RANK PRESERVERS OVER BOOLEAN MATRICES
CHARACTERIZATIONS OF BOOLEAN RANK PRESERVERS OVER BOOLEAN MATRICES
The Pure and Applied Mathematics. 2014. May, 21(2): 121-128
Copyright © 2014, Korean Society of Mathematical Education
  • Received : March 01, 2014
  • Accepted : May 01, 2014
  • Published : May 31, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
LEROY B. BEASLEY
DEPARTMENT OF MATHEMATICS AND STATISTICS, UTAH STATE UNIVERSITY, LOGAN, UTAH 84322-3900, USAEmail address:leroy.b.beasley@aggiemail.usu.edu
KYUNG-TAE KANG
DEPARTMENT OF MATHEMATICS, JEJU NATIONAL UNIVERSITY, JEJU 690-756, REPUBLIC OF KOREAEmail address:kangkt@jejunu.ac.kr
SEOK-ZUN SONG
DEPARTMENT OF MATHEMATICS, JEJU NATIONAL UNIVERSITY, JEJU 690-756, REPUBLIC OF KOREAEmail address:szsong@jejunu.ac.kr

Abstract
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 }.
Keywords
1. INTRODUCTION
The binary Boolean algebra consists of the set
PPT Slide
Lager Image
= {0, 1} equipped with two binary operations, addition and multiplication. The operations are defined as usual except that 1 + 1 = 1.
Let
PPT Slide
Lager Image
denote the set of all m × n Boolean matrices with entries in
PPT Slide
Lager Image
. 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
PPT Slide
Lager Image
is the least integer k such that there are Boolean matrices B
PPT Slide
Lager Image
and C
PPT Slide
Lager Image
with A = BC . It follows that 1 ≤ b(A) m for all nonzero A
PPT Slide
Lager Image
. The Boolean rank of the zero Boolean matrix is 0.
A mapping T :
PPT Slide
Lager Image
PPT Slide
Lager Image
is called a linear operator if T ( αA + βB ) = αT(A) + βT(B) for all A,B
PPT Slide
Lager Image
and for all α,β
PPT Slide
Lager Image
.
A linear operator T on
PPT Slide
Lager Image
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) = PXtQ for all X , where Xt is the transpose of X .
Let 1 ≤ k m . For a linear operator T on
PPT Slide
Lager Image
, we say that
  • (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}.
Beasley and Pullman ( [1] ) have characterized linear operators on
PPT Slide
Lager Image
that preserve Boolean rank as follows:
Theorem 1.1. For a linear operator T on
PPT Slide
Lager Image
, the following are equivalent :
  • (i)T preserves Boolean rank;
  • (ii)T preserves Boolean ranks1and2;
  • (iii)T is a (P,Q)-operator.
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
PPT Slide
Lager Image
, 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.
2. PRELIMINARIES
The matrix O is an arbitrary zero matrix and Jm,n is the m × n matrix all of whose entries are 1. A matrix in
PPT Slide
Lager Image
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 Ei,j . Further we let εm,n be the set of all cells in
PPT Slide
Lager Image
. That is, εm,n = { Ei,j | 1 ≤ i m , 1 ≤ j n }.
If A and B are Boolean matrices in
PPT Slide
Lager Image
, we say that A dominates B (written B A or A B ) if ai,j = 0 implies bi,j = 0 for all i and j . This provides a reflexive and transitive relation on
PPT Slide
Lager Image
. For Boolean matrices A and B in
PPT Slide
Lager Image
with B A , we define A B to be the Boolean matrix C such that ci,j = 1 if and only if ai,j = 1 and bi,j = 0 for all i and j .
Lemma 2.1 ( [1] ). If T is a linear operator on
PPT Slide
Lager Image
, then T is invertible if and only if T permutes εm,n .
A Boolean matrix L
PPT Slide
Lager Image
is called a line matrix if L =
PPT Slide
Lager Image
or L =
PPT Slide
Lager Image
for some i ∈ {1, …, m } or for some j ∈ {1, …, n }: Ri =
PPT Slide
Lager Image
is the i th row matrix and Cj =
PPT Slide
Lager Image
is the j th column matrix .
For a linear operator T on
PPT Slide
Lager Image
, 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
PPT Slide
Lager Image
. 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(Jm,n) = Jm,n . Let T preserve all line matrices. Now we will claim that either
  • (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}.
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 Ri and Rj (or column matrices Ci and Cj ) such that T(Ri) is a row matrix and T(Rj) is a column matrix. But then T(Jm,n) = T(R1) +⋯ T(Ri) +⋯+ T(Rj) +⋯+ T(Rn) cannot dominate Jm,n . This contradicts T(Jm,n) = Jm,n . Hence the claim is true.
Case (1): We note that T(Ri) = Rα(i) for all i and T(Cj) = Cβ(j) for all j , where α and β are permutations of {1, …, m } and {1, …, n }, respectively. Then for any cell Ei,j , we have T(Ei,j) = Eα(i),β(j) . Let P and Q be the permutation matrices corresponding to α and β , respectively. Then for any Boolean matrix
PPT Slide
Lager Image
we have
PPT Slide
Lager Image
Hence T is a ( P,Q )-operator.
Case (2): We note that m = n , T(Ri) = Cα(i) for all i and T(Cj) = 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) = PXtQ , and thus T is a ( P,Q )-operator. The converse is obvious. □
For nonzero A
PPT Slide
Lager Image
, 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
PPT Slide
Lager Image
, we have
b(A + B) ≤ b(A) + b(B).
Theorem 2.4. Let T be an invertible linear operator on
PPT Slide
Lager Image
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 Ei,j and Es,t that are not dominated by the same line matrix such that T(Ei,j) and T(Es,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 + ⋯ + Ek,k , we have b ( E 1,1 + E 2,2 + A ) = k . But by Lemma 2.3,
b(T(E1,1 + E2,2 + A)) ≤ b(T(E1,1 + E2,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. □
3. CHARACTERIZATIONS OF BOOLEAN RANK PRESERVERS
An operator T on
PPT Slide
Lager Image
is singular if T(X) = O for some nonzero X
PPT Slide
Lager Image
; otherwise T is nonsingular . In fact, if T is a singular linear operator on
PPT Slide
Lager Image
, then we can easily check that T(E) = O for some cell E . Further, if T is a ( P,Q )-operator on
PPT Slide
Lager Image
, then T is nonsingular.
Example 3.1. For 1 ≤ k m , let A = E 1,1 + E 2,2 + ⋯ + Ek,k 2
PPT Slide
Lager Image
. Define an operator T on
PPT Slide
Lager Image
by T(O) = O and T(X) = A for all nonzero X 2
PPT Slide
Lager Image
. 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
PPT Slide
Lager Image
is denoted by #( A ).
Lemma 3.2. Let 1 ≤ k m and 1 ≤ l ≤ m . Assume that T is a linear operator on
PPT Slide
Lager Image
. If
  • (i)T preserves Boolean rank k and k+ 1,or
  • (ii)T strongly preserves Boolean rank l,
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
PPT Slide
Lager Image
. If
  • (i)T preserves Boolean rank k and k+ 1with1 ≤k≤m− 1,or
  • (ii)T strongly preserves Boolean rank k with1 ≤k≤m,
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 Wr = [
PPT Slide
Lager Image
] where
PPT Slide
Lager Image
= 0 if and only if i + j r . Then b(Wr) = 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 = Td 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) = L2(E) = L(L(E)) = L(L(E) + F) = L2(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(Wk+1) = L(Wk+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(Wk+1)) = b(L(Wk+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
PPT Slide
Lager Image
. Then T preserves Boolean rank if and only if
  • (i)T preserves Boolean rank k andk+ 1with1 ≤k≤m− 1,or
  • (ii)T strongly preserves Boolean rank k with1 ≤k≤m.
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
, 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
PPT Slide
Lager Image
. Then the following are equivalent :
  • (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.
As a concluding remark, we suggest to prove the following conjecture:
Conjecture 3.6. Let T be a linear operator on
PPT Slide
Lager Image
. Then T preserves Boolean rank if and only if T preserves any two Boolean ranks h and k with 1 ≤ h k m n .
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).
View Fulltext  
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