COLUMN RANKS AND THEIR PRESERVERS OF GENERAL BOOLEAN MATRICES
SEOK-ZUN SONG AND SANG -Gu LEE
1. Introduction
There is much literature on the study of matrices over a finite Boolean algebra. But many results in Boolean matrix theory are stated only for binary Boolean matrices. This is dueinpart to a semiringiso- morphism between the matrices over the Boolean algebra of subsets of a k element set and the k tuples of binary Boolean matrices. This isomorphism allows many questions concerning matrices over an arbi- trary finite Boolean algebra to be answered using the binary Boolean case. However there are interesting results about the general (i.e. non- binary) Boolean matrices that have not been mentioned and they differ somwhat from the binary case.
In many instances, the extension of results to the general case is not immediately obvious and an explicit version of the above men- tioned isomorphismwasnot well known. In[4], Kirkland and Pullman gave a way to derive results in the general Boolean algebra. case via the isomorphism from the binary Boolean algebra case by means of a canonical form derived from the isomorphism.
In [2], Beasley and Pullman compared semiring rank and column rank of the matrices over several semirings. The difference between semiring rank and column rank motivated Beasley and Song to in- vestigate of the column rank preservers of matrices over nonnegative integers [3] and over the binary Boolean algebra [5].
In this paper, we will show the extent of the difference between semiring rank and column rank of matrices over a general Boolean
Received June 10, 1994.
AMS Classification: Primary 15A03, 15A04.
Key words and Phrases: Boolean column rank, linear operator.
This researchwassupportedbythe Research FUnd of the Ministry of Education, Korea in 1993, and in part byTGRC-KOSEF.
algebra and we also obtain characterizations of the linear operators that preserve column ranks of general Boolean mat.rices..
Let B be the Boolean algebra of subsets of a k element set Sk and
0"1, 0"2, ••• , O"k denote the singleton subsets of Sk. We write + for union and denote intersection by juxtapositionj 0 denotes the null set and 1 the set Sk. Under these two operations, B is a commutative, antinegative semiring (that is, only 0hasan additive inverse)j allof its elements, except 0 and 1, are zero-divisors. Let Mm,n(B) denote the set of all m X n matrices with entries in B. The usual definitions for adding and multiplying matrices apply to Boolean matrices as well.
For each mX n matrix A over 8, the p-th constituent [4]' of A, Ap ,is the m X nCO,I)-matrix whose (s,t)-th entry is 1ifand onlyifast 20"p.
Via the constituents, A can be written uniquely as EO"pAp,which is
~a1!ed ~he_C~!!~~~l?_a! fo~e>.LA. . __..
It follows from the uniqueness of the decomposition, and the fact that the singletons are mutually orthogonal idempotents, that for all m x n matrices A, alln x r matrices B and C, and all a E 8,
(a)(AB)p =ApBp, (b) (B+C)p =Bp+Cp, (c) (aA)p =apAp
for all1 ~P~k.
2. Boolean rank versus Boolean cloumn rank
The Boolean rank, b(A), of a nonzero A E M m,n(8) is defined as the least index r such that A =BCfor sOme B E Mm,r(8) and C E Mr,n(B). The rank of zero matrix·is zerOj in the case that B =81 =
{O,I}, we refer to b(A) as the binary Boolean rank, and denote it by b1(A).
For a binary Boolean matrix A, -we haveb(A) = b1(A) by definition.
IT V is nonempty subset of Mr,!(B) that is closed under addition and multiplication by scalars, then V is called a vector space over 8.
The concepts of "subspace" andof"generating sets" are defined soas to coincide with familar definitions when B is a field. We'll use the notation < F > to denote the subspace generated by the subset F of V. As with fields, a basis for a vector space V is a generating subset of least cardinality. That cardinality is the dimension, dim(V), of V.
Since B1 is canonicallyide~tifiedwith the subsemiring {O,I} of 8, a binary Boolean matrix can be considered as a matrix over both B and B1 .
The Boolean column rank, c(A), of A E Mm,n(B) is the dimension of the space< A >generated by the columns of A. In the bip,ary Boolean algebra, we denote it by cl(A) for A E Mm,n(B1 ).
(2.1) Itis known [2] that for allm Xn matrices Aover'B,0:$ b(A) :$
c(A) :$ n.
(2.2) For any p x q matrix Aover B, the Boolean rank of [~ ~]
is b(A) and its Boolean column rank is c(A).
(2.3) The Boolean rank of a matrix is the maximum of the binary Boolean ranks of its constituents. ([4])
Let us start with the relationship between c(A) and cl(A) for a binary Boolean matrixA when considered inB and 81 •
LEMMA 2.1. For any binary Boolean matrix A, we have c(A) = cl(A).
Proof. . SinceB1 can be considered as a subsemiring of8, we have c(A) :$ cl(A). Conversely, if c(A) = r, then there exists a basis B =
{Xb X2, ••• ,xr } of the column space of A such that eachXi is a linear combination of the columns of Aover B. Then the p-th constituents
(Xl)p,(X2)p, .•• ,(xr)p can generate all columns ofApover81 • Hence cl(Ap ) :$r. But A = Ap for allp, so cl(A) :$ r = c(A).,
Letp,(8,rn,n)be the largest integer"'tsuch that for all AE Mm,n(8), b(A) =c(A) if b(A) :$ "'t.
(2.4) Itfollows from definition ofp, and(2.2) that if c(A) >b(A)for some p xqmatrix A, thenp,(8,m,n) < b( A)for allm ;::: pand n ;:::q.
Beasley and Pullman determined the value of p, on 81 in [2] as follows;
LEMMA 2.2. ([2])
p(Bl,m, n)= { :
ifmin(m, n) =1 ifrn ;::: 3andn = 3 otherwise.
Now we determine the valuep, for a nonbinary Boolean algebra 8.
LEMMA 2.3. HB is any Boolean algebra and m ~ 3 and n >3, p(B,m,n) ~2.
Proof. Let
A=[~ ~ ~ ~].1 1 0 0
Then c(A) = Cl(A) by Lemma 2.1. Since the four columns of A con- situte a basis for the colunui space of A over Bl , Cl(A) = 4. Thus c(A) = 4. But b(A) ~ min{m,n} = 3. The result follows from the
property(2.4).'
LEMMA 2.4. Ifc(A)= rand 'EO'pApis the canonicalform of A E
Mm,n(B) thenmax{cl(Ap) 11 ~ p ~ k} ~ r .
.Proof. . Assumethat c(A)=r. Then there exists some basis
{Xh ,xr } for the column space qf A. Then the pth constituents (Xl)p, ,(xr)p can generate all columns of AI' over Bl . Therefore cl(Ap ) ~r for allp.'
We remark that the inequalityinLemma2.4may be strict forr > 1 as shown in Example 2.1 below.
EXAMPLE 2.1. Let
A=
[l1
ol . 0'111]
1be a matrix over the nonbinary Boolean algebra of the k element set
S",where0'1 isa singleton subset. of Sk. Then c(A) = 3by the proof of
[111]
Theorem 2.1 below. But cl(Al ) = Cl( 0 1 1 ) =2 and cl(Ap ) =
[00 1]
Cl ( 0 1 1 )= 2for allp = 2,3, ... ,k. 1[
LEMMA 2.5. IfB is any Boolean algebra and m > 1 and n ~ 1, then J.t(B,m,n) ~ 1.
Proof. . IT c(A) = 1 then b(A) = 1 by the property (2.1). IT b(A) = 1, then Acan be factored as xat where at = [a}, ... ,an] E M1,n(B) andx E Mm,1(B). Thus the column space ofAcan be generated by one column vectorx. Soc(A) ~ 1= b(A). On the other handb(A) ~ c(A) by (2.1).,.
THEOREM 2.1. For a nonbinazy Boolean algebraH,
{
2 if2 = n < m
Jl(B,m,n) = . -
1 otherwIse
Proof. By Lemma 2.5,Jl(llt,m,n) ~ 1 for all positive integers m and n. Let 0'1 E B be a singleton subset ofSk. Consider the matrix
Then the column space ofA is
v = { x [~1] +y [:~] +z [~1] +10 [~] Iz,1O E B, and x,y E<0'1 > } .
Let 11 be any subset of V generating V. Let
IT a rt 11, then
a -- [x+Y+1o] for some 10 E B,x,y E<0'1>'
Y+1o
Now 1 = Y+10 and y = 0 or 0'1, so that 10 = 1 or 1 - 0'1(which is the complement of 0'1)' But then 0'1 = X +y +10 = 1 or 1 - 0'1, a contradiction, since 0'1 =1= 1. Hence a E 11.
Let
H b ftQ, then
b= [x +y +ZO"l] for some ZED,x,y E<0"1>.
y+z .
Since 1 =y +Z and y =0 or 0"1, we have Z = 1 or 1 - 0"1. But then
1 = x + y+ ZO"l = ZO"l(~ O"t} or 0"1, a contradiction, since 0"1 =J 1.
Hence bE Q.
Let
Then c ftQ would iInply· that 0=y+z+wfor somey,Z aIldtV,one of
which is nonzero, which is impossible. Hence {a, b, c} ~ Q. Therefore c(A) = 3. But h(A) ~ 2 by definition. Thus p. (D,m,n) ~ 1 when m ~ 2 and n ~ 3, by property (2.4). Hencep.(D,m,n) =1 for m ~ 2 and n ~ 3 by Lemma 2.5. Evidently p.(D, m, 1) = 1 for all m ~ 1.
H 1 = m ~ n, then the fact that < Xl, X2, ••• , Xn >=< E:=lXi >
implies that p.(B, 1,n) = 1. H 2 = n ~ m, then c(A) = 2 whenever h(A) =2 by property (2.1). Thus p.(D, m, 2) =2 for m ~ 2 by Lemma 2.5.'
3. Linear operators that preserve cloumn rank of the non- binary Boolean matrices
In this section, we obtain the characterizations of the linear oper- ators that preserve Boolean column rank of the nonbinary Boolean matrices.
. A linear operatorT on Mm,n(D) is said to preserve Boolean column rank if c(T(A» = c(A) for all A E Mm,nOIJ). It preseT1Jes Boolean column rankr ifc(T(A»= r wheneverc(A)=r. For the terms Boolean rank preserver and Boolean rank r preserver, they are defined similarly.
IfT is a linear operator on Mm,n(D), for each.I ~ p ~ k define its p-tk constituent, Tp, by Tp(B) = (T(B»p for every B E Mm,n(DIJ.
By the linearity of T, we have T(A) = EO"pTp(Ap) for any matrix A E Mm,n(D).
SinceMn,n(B) is a semiring, we can consider the invertible members of its multiplicative monoid. The permutation matrices (obtained by permuting the columns of In, the identity matrix) are all invertible.
Since 1 is the only invertible member of the multiplicative monoid of B, the permutation matrices are the only invertible members ofMn,n(B).
LEMMA 3.1. The Boolean column rank of a Boolean matrix is un- changed bypre- or post-multiplication by an invertible matrix.
Proof. This follows from the fact that an invertible matrix is just a permutation matrix.'
LEMMA 3.2. Suppose T is a linear operator on Mm,n B). HT preserves Boolean column rank r, then each constituent Tp preserves Boolean column rank r on Mm,n (Bt).
Proof. Assume that A EMm,n(Bd is a binary Boolean matrix with cI(A)= r. By Lemma 2.1, we havec(A) = r and c(O'pA) = r for each p = 1, ... , k. Since T preserves Boolean column rank r,c(T(O'pA»= r.
But
c(T(O'pA»= c(O'pT(A» = c(O'p LO'iTi(Ai» = c(O'pTp(A»
i
for each p. Therefore c(O'pTp(A» = r for eachp = 1, ... , k, and hence cI(Tp(A» =r.'
LEMMA 3.3. Suppose T is a linear operator on the m x n matrices over B. H each constituent Tp preserves bina:zy Boolean rank r, then T preserves Boolean rank r.
Proof. Let b(A) = r for A E Mm,n(D). Then there exists some p such that bl(Ap) = r and bl(Aq) ~ r for 1 ~ q ~ k by property (2.3). Thus bl(Tp(Ap» = r and bl(Tq(Aq» ~ r for 1 ~ q ~k. Since b(T( A» = max{bl(Tp(Ap» 11 ~ p ~ k} by property (2.3),T preserves Boolean rank r.
Now we need the following definitions of linear operators on the m X n matrices over B. For any fixed pair of invertible m x m and n x n Boolean matrices U andV, the operator A - 7 UAV is called a congruence operator. Letq* denote the complement ofqfor eachq in B. For 1:$ p :$ k, we define the p-th rotation operator, R(p), on the n x n matrices over B by
R(p)(A) - q At- P p p '+q* A
where.A; is the transpose matrix ofAp. We see that R(p) has the effect oftransposingAp while leaving the remaining constituents unchanged.
Each rotation operator is linear on then xn matrices overBand their product is the transposition operator, R : A - 7 At.
EXAMPLE 3.1. Let
o
be a matrix over B. Then c(A) = 3 by Example 2.1 and property (2.2). But R(l)(A) = At, the transpose matrix of A, has Boolean column rank 2. Consider B =A E9On-3,n-3 for n ;::: 3. By property (2.2), the rotation operator does not preserve Boolean column rank 3 onMn,n(B).'
LEMMA 3.4. ([4}) IfT is a linear operator .on the m x n matrices (m,n ;::: 1) over a general Boolean algebraB, then the followings are equivalent.
(1) T preserves Boolean ranks. 1 and 2.
(2) T isin the group of operators generated bythe congruence (if m = n, also the rotation ) operators.
THEOREM3.1. Suppose T is a linear operator onMm,n(B)for m ;:::
3 andn ;::: 1. Then the following are equivalent.
(1) T preserves Boolean column rank.
(2) T preserves Boolean column ranks 1, 2 and 3.
(3) T is a congruence operator.
Proof. Obviously (1) implies (2). Assume that T preserves Boolean column ranks 1, 2 and 3. Then each constituent Tp preserves binary Boolean column ranks 1, 2 and 3 by Lemma 3.2. For A E Mm,n(B), Lemma2.2implies that bl(A) = Cl(A)for bl(A) $ 2.ThusT" preserves binary Boolean ranks 1 and 2. ThenT preserves Boolean ranks 1 and 2 by Lemma 3.3. So T is in the group of operators generated by the congruence ( ifm = n, also the rotation ) operators. But the rotation operator does not preserve Boolean column rank 3 by Example 3.1.
Hence T is a congruence operator since T preserves Boolean column rank 3. That is, (2) implies (3). Now, assume that T is a congruence operatorofthe formT( A)=UAV, whereU and V are invertiblem x m and n x n Boolean matrices respectively. Then T preserves Boolean column rank by Lemma3.1. Hence (3) implies (1). 1
ITm $ 2, then the linear operators that preserve column rank on Mm,n(B) are the same as the Boolean rank-preservers, which were char- acterized in [4].
Thus we have characterizations of the linear operators that preserve the Boolean column rank of general Boolean matrices.
References
1. L. B. Beasley and N.J. Pullman, Boolean rank-presenJing operators and Boolean rank-l spaces, Linear Algebra Appl 59 (1984), 55-77.
2. L. B. Beasley and N. J. Pullman, Semiring rank 1Iersus column rank, Linear Algebra Appl 101 (1988), 33-48.
3. L. B. Beasley and S. Z. Song,A comparison of nonnegativerealranks and their preseroers, Linear and Multilinear Algebra 31 (1992),37-46.
4. S. Kirkland and N.J. Pullman, Linear operators presenJing invariants of non- binary matrices, Linear and Multilinear Algebra 33 (1992),295-300.
5. S. Z. Song, Linear operators that presertJes Boolean column ranks, Proc. Amer.
Math.Soc. 119 (1993), 1085-1088.
6. S. Z. Song,Linear operators that presertJe column rank of fuzzy matrices, Fuzzy Sets and Systems 62 (1994), 311-317.
7. S. Z. Song, S. G. Hwang and S.J. Kim, Linear operators that presertJe maximal column rank of Boolean matrices, Linear and Multilinear Algebra 36 (1994), 305-313.
8. S. G. Hwang, S. J. Kim and S. Z. Sone, Linear operators that presertJe span- ning column ranks of nonnegative matrices, J. Korean Math. Soc. 31 (1994), 645-657.
Seok-Zun Song
Department of Mathematics Cheju National University Cheju 690-756, Korea Sang-Gu Lee
Department of Mathematics Sung Kyun Kwan University Suwon 440-746, Korea
