Linear operators that preserve zero-term rank of Boolean matrices

LINEAR OPERATORS THAT PRESERVE ZERO-TERM RANK OF BOOLEAN MATRICES

LERoy. B. BEASLEY, SEOK-ZUN SONG, AND SANG-GU LEE ABSTRACT. Zero-term rank of a matrix is the minimum number of lines (rows or columns) needed to cover all the zero entries of the given matrix. We characterize the linear operators that preserve zero-term rank of the m x n matrices over binary Boolean algebra.

1. Introduction and Preliminaries

There is much literature on the study of those linear operators on matrices that leave certain properties or subsets invariant. Boolean matrices also have been the subject of research by many authors. But there are few papers on zero-term rank of the matrices over Boolean algebra.

Beasley and Pullman characterized those linear operators that pre- serve Boolean rank in [1Jand term rank of matrices over antinegative semirings in [2J and [3J. In [4J, [6] and [7], analogues of their work were obtained on certain column rank for Boolean matrices.

In this paper, we consider the zero-term rank of Boolean matrices.

We obtain characterizations of those linear operators that preserve zero-term rank of m x n matrices over binary Boolean algebra. We also extend the results in [2] to zero-term rank preserver on Boolean matrices.

We let M = Mm,n(lB) denote the set of all m x n matrices with entriesinB = {O, 1}, the two element Boolean algebra. Arithmetic in B follows the usual rules except that 1+1 =^1.

Let Ei j be the m x n matrix whose (i,j)th entry is 1 and whose other entries are all zero, which is called a cell. Let J denote the m xn

Received June15, 1999.

1991 Mathematics Subject Classification: Primary 15A03, 15A04.

Key words and phrases: Boolean linear operator, term-rank, zero-term rank.

The authors wish to acknowledge the financial support of the Korea Research Foundation made in the program year of1997-1998.

matrix all of whose entries are 1 and ~= {Eij 11~i ~m,1 ~ j ~n}

denote the set of cells.

Thezero-term rank[5} of a matrixX, z(X), is the minimum number of lines (rows or columns) needed to cover all the zero entries ofX.

Of course, the term rank [2] ofX, t(X), isdefined similarly for all the nonzero entries ofX.

If A and B are in M, we say A dominates B (written A ~ B or B :::; A) ifaij = 0 implies bij = 0 for all i,j. Then we obtain the following result.

LEMMA 1.1. For A,B E M, A ~ B implies thatzeAl ~ z(B).

Proof. Ifz(B) = k, then there arek lines which cover all zero entries in B. Since A ~ B, this k lines can also cover all zero entries in A.

HencezeAl ~ k. 0

2. Zero-Term Rank Preserver over Boolean Matrices A function T mapping M =Mm:,n(Iffi) into itselfis called a Boolean linear operatorifT preserves sums and O. Which Boolean linear opera- tors over M- preserve zero-term rank? The operations of(1) permuting rows, (2) permuting columns and (3) (ifm = n) transposing the ma- trices in M are all linear operators that preserve zero-term rank of the matrices on M. That these operations and their compositions are the only zero-term rank preservers is one of the consequences of Theorem 2.5 below. Such operations are described more formally in the following definition.

IfP and Q arem x m andn xn permutation matrices respectively and X is an m x n Boolean matrix, then a Boolean linear operator T : M^-+ M is a (P, Q)-operatorif

(1) T(X) = PXQ for all X in M or

(2) m = nandT(X)= PXtQ for allX inM.

If z(T(X)) = k whenever z(X) = k, we say T preserves zero-term rank k. So a Boolean linear operator preserves zero-term rank if it preserves zero-term rank k for every k :::; min{m, n}. For term rank preserver and term rank k preserver [2], they are defined similarly.

From now on we will assume that 2 ~m ~n unless specified other- wise for all m x n matrices. And a mappingT will denote a Boolean

linear operator on M = Mm,n(:IB).

LEMMA 2.1. SupposeT preserves zero-term rank 1 and T(J) = J.

Then T mapsa cell ontoa cellandhenceit is a bijection on .6..

Proof If T(Eij )= 0 for some E ij E.6., then we can choose mn-1 cells El, E2, . .. ,E_mn-l , which are different from E ij such that

(2.1)

But z(J)

=

=

E k)) = 1. Then we have a contradiction from (2.1). Thus T(Eij) covers at least one cell in .6..

For some cell E ij E .6.,suppose T(Eij) covers two cells, say EkZ and Euvin.6.. For each cell Ers except for both E kZ and E^uv we can choose one cell Eh such that T(Eh ) covers Ers because T(J) = J. Since the number of cells except for both E kZ and Euv is mn - 2, there exist at most mn - 1 cells El, E_{2 , • ••} ,E_{mn- 1}containing E ij such that

(

mn-l )

T

L

k=l

This isimpossible sinceT preserves zero-term rank 1, but

(

mn-l )

z

£;

Hence T(Eij ) covers only one cell, say E kZ , for all Eij ^E .6.. That is, T maps a cell into a cell. Now, we show that T is a bijection on.6.. If

T(E) = T(F) for some different cells E and F, then we have J=T(J) =T({J - (E+^F)} +^(E+^F))

= T(J - (E+F)) +T(E +F)

= T(J - (E+F)) +(T(E)+T(F))

= T(J - (E+^F)) +^(T(E) +^T(E))

=T(J-(E+F))+T(E)

=T({J - (E+F)}+E)

=T(J-F),

whichisimpossible sinceT preserves zero-term rank 1. ThereforeT is

a bijection on Ll. 0

LEMMA 2.2. 1fTis bijectiveon Ll and T preserves zero-term rank 1, then T preserves term rank 1.

Proof. Suppose that T does not preserve term rank 1. Then there exist some cells Ei j and Eil on the same row (or column) such that

withP# r and q # s. Since the zero-term rank ofJ - Eij - Eil is 1 and the zero-term rank of its image underT is

z(T(J - Eij - Eil )) ⁼ z(J - Ers - E_{pq )} = 2,

which is a contradiction. HenceT preserves term rank 1.

o

LEMMA 2.3. HT is bijectiveon Ll and T preserves zero-term rank 1, then T maps a row of a matrix onto a row (or columnifm

=

Proof. Suppose T does not map a row into a row (or a column if m = n). Then T does not preserve term rank 1. This contradicts Lemma 2.2. Hence T maps a row into a row (or a column if m =n).

Then the bijectivity ofT implies that T maps a row onto a row (or

may be a column if m = n). 0

LEMMA 2.4. Suppose T isbijective on~andT preserves zero-term rank 1. For the case m = n, ifT maps a row onto a row (or a column), then all rows of a matrix must be mapped some rows (or columns, respectively) under T.

Proof. Let

n m

~^{= LEij, Cj = L Eij}

j=1 i=1

for i = 1, '" ,m and j = 1, '" ,n. Suppose T maps a row, say RI, onto an ith row ~ and another row, say R_{2 ,} onto a jth column Cj .

ThenRI+^R2 has2ncells but~+^Cj has2n -1cells. This contradicts the bijectivity ofT on~. Hence all rows must be mapped some rows

(or columns) underT. 0

Thus we have the following characterization theorem for zero-term rank preserver over Mm,n(:Im).

THEOREM 2.5. Suppose T isaBoolean linear operator onM. Then the following statements are equivalent:

(i) T isa (P, Q)-operator;

(ii) T preserves zero-term rank;

(iii) T preserves zero-term rank 1 and T(J) = J.

Proof. Obviously (i) implies (ii) and (ii) implies (iii). We now show that (ill) implies (i). By Lemma 2.1,T isa bijectionon~. Lemmas 2.3 and 2.4 imply that T mapsall rows of a matrix onto rows and columns onto columns. Thus for all m x n matrix X, T(X) = PXQ with some permutation matrices P andQof degree m and n, respectively.

Ifm = n, then T may map all rows of a matrix onto columns and columns onto rows. By choosing the permutation matrices P and Q appropriately, we haveT(X) = PXtQ for all matrix X. Hence T is a

(P,Q)-operator. 0

LEMMA 2.6. For A, B inM

A2::B implies T(A) 2::T(B).

Proof By definition ofA 2:: B, we haveaij 2:: _bij for all i,j. Using

m n m n

A

=

=

i=lj=l i=lj=l

for Eij E Do, we have

T(A)

=

(t. t,

m n

=LLaijT(Eij ) i=l j=l

m n

2:: LLbijT(Eij) i=lj=l

=T(B).

o

We say that a Boolean linear operatorT strongly preserves zero- term rank 1 provided that z(T(A)) = 1 ifand only ifz(A) = 1. For term rank, it is defined similarly.

LEMMA 2.7. liT strongly preserves zertrterm rank1, then wehave T(J) = J.

Proof Suppose that T(J) i= J. Since T strongly preserves zertr term rank 1, we have z(T(J)) 2:: 2. Then z(T(A)) 2:: 2 for all A E M by Lemmas 1.1 and 2.6. For any cell Eij ^E M, z(J - Eij ) = 1 but z(T(J - Eij)) 2:: 2 by above argument. This contradicts to the

assumption. 0

THEOREM.2.8. SupposeT is a Boolean linear operator on M. Then T preserves zertrtermrankifandonlyifitstrongly preserves zertrterm

rank 1..

Proof. SupposeT strongly preserves zertrterm rank 1. Lemma2.7 implies that T(J) = J. By Theorem 2.5, T preserves zero-term rank.

The converse is immediate. 0

Notice that the linear operatorT which preserves zero-term rank of Boolean matricesis invertible. Its inverseis a (pt,Qt)-operator.

3. Relation with Term Rank Preserver

In this section, we compare the zero-term rank preserver with term rank preserver, permanent preserver and rook polynomial preserver.

LEMMA 3.1. IfT is bijective on.6., and preserves zero-term rank 1, tben T preserves term rank 2.

Proof. By Lemma 2.3, T maps a row of a matrix onto a row (or a column if^m =n). So T does not increase term rank of a matrix.

Suppose there exists a matrix X such that t(X) =2and t(T(X)) = 1.

Since T is bijective on .6., we can take a submatrix A of X such that A = ^Ei j +^Ekl with i =/: ^k, j =/: ^l, and T(A) has term rank 1. Then we consider three cases:

Case1) EitherT maps i-th and k-th rows into one row (or one column ifm = n) or T maps j-th and l-th columns into one column (or one row ifm = n). This is impossible by the bijectiveness ofT on .6..

Case 2) T maps i-th and k-th row into two rows such that images ofE_ij and Ek1 are the same column. ThenT must map the j-th and l-th column into one column, which is impossible by the bijectiveness ofTon.6..

Case3) m =n andT maps i-th andk-th rows into two column such that the images ofE_{i j} andEkl are in the same row. ThenT must map the i-th and k-th rows into one row, which is also impossible by the bijectiveness ofT on .6.. Therefore we conclude that T preserves term

rank 2. 0

In [2], Beasley and Pullman obtained characterizations of term rank preserver over arbitrary semirings. We restate their results for Boolean linear operators.

LEMMA 3.2 ([2]). Suppose T is a Boolean linear operator on M.

Tben tbe following are equivalent:

(i) T is a (P, Q)-operator;

(ii) T preserves term rank;

(iii) T preserves term ranks 1 and 2;

(iv) T strongly preserves term rank 1.

Using tbis results, we bave tbe following cbaracterizations.

THEOREM 3.3. Suppose T is a Boolean linear operator on M. Then the followings are equivalent:

(i) T preserves zero-term rank;

(ii) T preserves zero-term rank 1 and T(J) = J;

(iii) T strongly preserves zero-term rank 1;

(iv) T is a (P, Q)-operator;

(v) T preserves term rank;

(vi) T preserves term ranks 1 and 2;

(vii) T strongly preserves term rank l.

Proof. The equivalence of (i)rv(iv) comes from Theorems 2.5 and 2.8. And Lemma 3.2 implies the equivalence of (iv)rv(vii). 'l'herefore

we have the results. 0

Inorder to compare the zero-term rank preserver with the perma- nent preserver and rook-polynomialpreserver~we give their definitions.

For an m x n matrix A = [aij] over B, we define the permanent as

per(A) =

L

0"

where the summation extends overallone-to one functions from{1, ... , m} to{1,··· ,n}. And the rook polynomial of a matrix A is RA(x) =

Ej~o^{PjXj ,} where ^Po = 1 and^Pj is the sum of the permanents of the j x j submatrices ofA.

Beasley and Pullman [2] obtained characterizations of permanent preservers and rook polynomial preservers on matrices over antinega- tive semirings. We restate their results for Boolean matrices as follows:

LEMMA 3.4 ([2]). Suppose T is a Boolean linear operator on M.

Then th.ese are equivalent:

(i) T preserves the permanent;

(ii) T preserves term rank;

(iii) T preserves the rook-polynomial;

(iv) T is a (P, Q)-operator.

Using this Lemma 3.4,we have the followings:

THEOREM 3.5. Suppose T is a Boolean linear operator on M. Then the followings are equivalent:

(i) T preserves zero-term rank;

(ii) T preserves term rank;

(iii) T preserves the permanent;

(iv) T preserves the rook-polynomial.

Proof It comes from Theorem 3.3 and Lemma 3.4. 0 Thus we had characterizations of the Boolean linear operators that preserve zero-term rank.

We also extended the characterizations of term rank preservers of Boolean matrices to zero-term rank preservers, permanent preservers and rook polynomial preservers.

References

[1] L. B. Beasley andN.J.Pullman,Boolean rank prest;1JIlJing operators and Boolean rank-1 spaces, Linear Algebra Appl. 59 (1984), 55-77.

[2] , Term-rank, permanent and rook-polynomial preservers, Linear Alge- bra Appl. 90 (1987),33-46.

[3] , Operators that preserve semiring matrix functions, Linear Algebra Appl. 99 (1988), 199-216.

[4] S. G. Hwang, S.J.Kim and S. Z. Song, Linear operators that preserve maximal column rank of Boolean matrices, Linear and Multilinear Algebra 36 (1994), 305-313.

[5] C. R. Johnson andJ. S. Maybee, Vanishing minor conditions for inverse zero patterns,Linear Algebra Appl. 178 (1993), 1-15.

[6J S. Z. Song, Linear operators that preserve column rank of Boolean matrices, Proc. Amer. Math. Soc. 119 (1993), 1085-1088.

[7] S. Z. Song and S. G. Lee, Column ranks and their preservers of general Boolean matrices,J. Korean Math. Soc. 32, no. 3, 531-540.

LeRoy. B. Beasley

Department of Mathematics Utah State University Logan, Utah 84322-4125 USA

E-mail: [email protected]

Seok-Zun Song

Department of Mathematics Cheju National University Cheju 690-756, Korea

E-mail: [email protected] Sang-Gu Loo

Department of Mathematics SungKyunKwan University Suwon 440-746, Korea

E-mail: [email protected]