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
• Received : March 01, 2014
• Accepted : May 01, 2014
• Published : May 31, 2014 PDF e-PUB PubReader PPT Export by style
Article
Author
Metrics
Cited by
TagCloud
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 (  ) 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  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 (  ) 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  .
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 (  ). 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 (  ) 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 (  ) 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).
References