Linear operators that preserve spanning column ranks of nonnegative matrices

LINEAR OPERATORS THAT PRESERVE SPANNING COLUMN RANKS OF NONNEGATIVE MATRICES'"

SUK-GEUN HWANG, SI-JU KIM AND SEOK-ZUN SONG

1. Introduction

IT Sis a semiring of nonnegative reals, which linear operators Ton the space of m ^X n matrices over S preserve the column rank of each matrix? Evidently if P and Q are invertible matrices whose inverses have entries in S, then T : X ^--? PXQ is a column rank preserving, linear operator. Beasley and Song obtained some characterizations of column rank preserving linear operators on the space of m xn matrices over Z+, the semiring of nonnegative integers in [1] and over the binary Boolean algebra in [7] and [8J. In [4], Beasley, Gregory and Pullman obtained characterizations of semiring rank-l matrices and semiring rank preserving operators over certain semirings of the nonnegative reals. We consider some results in [4] in view of a certain column rank instead of semiring rank.

In this paper, we define "spanning column rank" (see Section 2), which is the same as column rank on the space of matrices over a field or Z+ but differs from column rank in general semirings. We obtain a characterization of spanning column rank 1 matrices. We also characterize linear operators which preserve the spanning column ranks of matrices over the nonnegative part of a unique factorization domain that is not a field in the reals.

Received July 29, 1993.

1991 Mathematics subject classification. Primary 15A03, 14A04, 15A23.

Key words. Spanning column rank, linear operator.

This research was supported by TGRC-KOSEF in 1991.

2. Definitions and basic properties ofspanning column rank Let S be any subset o£ R+(the nonn~g~tivereals). We'll call it a nonnegative semidomain if it contains 0,1 arid is closed under multi- plication and addition (the usual operations). IfD is a subring of R containing 1 (so D is an integraldomain), let D+ denote the set of its nonnegative elem~ts. Then D+ is a nonnegative semidomain. Ex- amples are ~,Q+,Z+, (Z[v'2])+ etc., where Q denotes the rationals and Z the integers. Note that (Z[V21h contains Z+[V2] properly, since e.g.

v'2 -

1 is in the left member but not the right. There are other nonnegative semidomains : e.g. H

=

{O, 1, 2,3} U{q EQ

Iq

~ 4}

is not of the form D+ for any integral domain D in R.

Hereafter, unless otherWise specified, Swilldenote an arbitrary non- negative semidomain.

Let A be an m xn matrix overS. HA is. a nonzero matrix, then the seminng.rii1il:

[lro£

A~rs(A);ls-theleasfkforwhich-tliere

exist

^rrf

x·

k andk xn matricesF andGoverS such that A=FG. The zero matrix is assigned the semiring rankO. The setof

m x

n matrices V\Tith entries in S is denoted by Mm,n(S). Addition, multiplication by scalars, and the product of matrices are deflnedas ifS.were a :field.

IfV is a nonempty su.bs.et ofSk

==

Mk,l(8) that is closed under addition and multiplication by scalars, thenV is called a vector space overS. The notions of subspace and· of spanning .sets are the sameas ifS were .a field.

A set A of vectors overSi~ lirtearly dependent if for some^{a.E A,.a}is a linear combination of theve~torsinA -:-. {a}. OtherwiseAis linearly independent.

.. ..As :wi~h...fitdds,a~i8 ^fQ(aY:e~t9t..,sP~. Yis.a spAARJ.ng ~tlbt,;~t .of least car~aJity. 'that cardina:fity istlle.dimen$ion, dim(V), 9f V.

The·col:umnspa,ceofan m x n matrix

A

over

S

is the _ve~torspace that is spanned by its columns. The ~ol'Umn ta.~k,t:s(A), of a nonzero m x n matrix A over S is·the dimension of its column space. The spanning column rank, scs(A), is the _mini~um.number of the columns of A which span its cohnnn sace. As with"aenriring rank, the zero matrix is assigned column rank and spanning column rank

o.

ItfbHowstba:t ....

0:::; rs(A) ~cs(A) :::; scs(A) :::; n (2.1)

for all m x n matrices A over S.

Over a field F we have cF(A) = sCF(A) for all A E Mm,n(F). For, if cF(A) = k, then the column space of A has dimension k. So any r columns of A are linearly dependent for r which is greater than k.

Hence sCF(A) ~k. Therefore the column rank and spanning column rank functions are equal over any field by (2.1).

We can also show that the column rank and spanning column rank are the same over Mm,n(Z+) or Mm,n(B), where B is the two ele- ment Boolean algebra. But they may differ over other semirings. The spanning column rank may actually exceed its column rank over some semirings.

For example, consider A == [3 -

V7, V7 -

2] over S

= (Z[V7])+.

Since (3 -

..;7) + (..;7 -

2) == 1, {1} is a spanning set of the column space of A. So cs(A) = 1. But scs(A) = 2 since 3 -

..;7 i=

a(

V7 -

2) and

..;7 -

2

i=

^{a(3 -}

..;7)

for any a in S.

Here are some basic properties of spanning column rank.

Ifthe columns ofA E Mm,n(S) are linearly independent over S, then

scs(A)

=

n. (2.2)

IfS ~ T, then scs(A) ~ sCT(A) for arbitrary A with entries in S.

(2.3) Let A and B be matrices over S. Then

scs(AB) ~ scs(B). (2.4)

For, assume that scs(B) = k. Then without loss of generality, we may assume that {bI , ... ,b_{k }} is a set of columns of B of minimum cardinality that spans its column space. Since the jth column of AB is of the form Abj and bj = L:~=I ^{sjb j for some}

Si

E S, we have Abj = L:~=I ^siAbi. That is, any column of AB can be written as a linear combination of Ab}, ... ,Abk. Hence scs(AB) ~ k = scs(B).

But, in general scs(AB) is not less than scs(A) as shown in the following example: let

A

~

[3, 7, 71, B =

(~ ~

^{: )}

be matrices over S

=

^{Z+. Then scs(AB) = scs([3,10, 17]) = 3, but}

scs(A)

=

^2.

ITB is obtained by deleting some rows ofA, then

scs(B) ~ scs(A). (2.5)

But suppressing a column may increase the spanning column rank. For example, consider

A--

(~ ~ ~ ~ ~)

1 1 0 0 1 1 1 1 1 0

over B, the two element Boolean algebra. Then sCB(A) = 3because the last three columns are linearly independent and span the column space of A.We deletecolumnS·fromAto obtainA',then SCB(A'-)=4 since the four columns of A' are linearly independent.

ITV, V-I have all entries in S,then

scs(VA)

=

^{scs(A) by (2.4). (2.6)}

HX is a matrix overSand X = ax^t, then a, x are called left and right factors of X respectively. Both a andx are referred to as factors ofX.

Inparticular, a is called a strong right factor ofX if at has spanning column rank 1. For X .E Mm,n(S), we write sc(X) for scs(X), c(X) forcs(X) andr(X) for rs(X).

LEMMA 2.1. ForA E Mm,n(S),sc(A)

=

^{1ifand onlyifA can be}

factoreclas xa^t for someaE Sn,xES~,:where x ;fOand a.isastrong rightfactor.

Proof ITsc(A) = 1,then there exists one column ak ofA such that all the other columns ai are expressed as a scalar multiple of ak, that is aj = ajak for some aj ES.ThereforeA

=

ak[ar, ... ,an] with ak

=

1.

Let x = ak, at = [al,'" ,an]' Then we have done. The converse is c1ear.O

hitneseqtiel;

IetU+De·

tIle

nonnegatiVepart·· ofa·umque factoriza:' tion domain U which is not a field in R - for example

R.r n

Q[e] with transcendental e, etc.

LEMMA 2.2. There are an .infinitenumber of primesin U+.

Proof. IT there is no primes in U+, then U is a field, which is not the case. So there is at least one prime in U+. Let PllP2, ... , be primes in U+, and suppose that there is a last prime j call it pn' Now consider the positive element

Q = PIP2 ... Pn

+

1.

Since

Q

E U +, there are a unit a and primes ql, . . , ,q. in U + such that Q has the form aql '" q•. But PI,P2, ... ,Pn are the only primes, so that ql must be equal to one of PI ,P2, . .. ,Pn' Sinceql divides both PIP2'" PnandQ,we arrive atql divides Q-PIP2 ... Pn or, equivalently, ql divides 1. Then ql is a unit, which is a contradiction. Thus the number of primes is infinite. 0

3. Spanning column rank preserving linear operators IfT maps Mm,n(S) into itself and T(aX

+

,BY) = aT(X)

+

,BT(Y) for alla,

fJ

^E S and for all X, Y E Mm,n(S), then T is a linear operator on Mm,n(S),

In[4], it was shown that ifS = U+ and T preserves real or semiring ranks of matrices over U+, then there exist nonsingular matrices U and V such that T(X)=UXV ( or possibly T(X) = UXtV if m = n) for all X E Mm,n(U+).

In[1], we obtained a characterization of linear operators which pre- serve column ranks on Mm,n(Z+), Since the column rank and spanning column rank are the same on Mm,n(Z+), the characterization holds for spanning column ranks.

In this section we shall obtain a similar characterization of linear operators which preserve spanning column ranks on Mm,n(U+), We say that a linear operator T preserves spanning column rank k provided that sc(T(X))= k ifsc(X) = k, where X E Mm,n(S),

Let ei be the vector in sn with a "I" in the ith position and zero elsewhere. We say that X is a column matrix if X = xe: for some

1::;

i ::;n and some vector x E

sm.

LEMMA 3.1. Let T be a linear operator on Mm,n(U+),n ~ 2. HT preserves spanningcolumnranks 1 and 2,then T mapscolumnmatrices to columnmatrices.

Proof. Suppose to the contrary that T maps a column matrix to a matrix which is not a column matrix. Say x(el)t

=

^{XI andT(Xd has}

more than one nonzero column. For each 1 :::; i :::; n, let Xi = x(ei)t.

Let 8

=

^{{I, ...} ,n} and let 8₁

=

{j:t.he jth column ofT(Xi ) is zero for all 1 :::;i :::;n}. Then for each i E8 - SI, there is a

iI

such that the ith column ofT(Xj(i» is not zero. Now T(Xd has at least two nonzero columns, say columns kl and kz. Let 8_z= 8 - 81 - {kl, kz}, and let

X = XI

+

L:iEs^{2 Xj(i)'} Note that for any k E 8 - 81 , the kth column ofT(X) is nonzero. Further, sinceX consists of at most n-1 distinct summands, each of which is a column matrix, there is at least one zero column in X, say the ith. Let Y = Xi. Since T(X) has zero columns only corresponding to indices in8₁(whereT(Y) also must have a zero column) we can restrict our attention to those columns in T(X) that are nonzeroj hence we lose no generality in assuming thatT(X) has no zero column. Thus, since

X,

and hence T(X), has spanning column rank 1,T(X) = uat , _~here at = [ah .. ' ,an} has all nonzero entries.

Let T(Y) = vht with h^t

=

^{[bi, ...} ,bn }. Since pX

+

Y has spanning column rank1for arbitrary p. in U+,

has also spanning colUmn rank 1. Now we consider two cases:

Case 1) H cu=f:. dv for all nonzero c,d in U+, then we have, for some fixed j,

pakll

+

bkv= Tk(pajll

+

bjv)

for some Tie E U+,k= 1, ... ,n.

If

ale =f:.Tkaj for some k, then

pi

ale - Tkaj

In

=Irlebj - bk lv,

which is a contradiction to the condition that Cll=f:.dv for all nonzero c, d in U+. Thus ak

=

Tleaj and ble

=

^{Tlcbj, k}

=

1, ... , n. That is, a = ajr and h = bjr, where r^t

=

[TI, ... ,Tn} with Tj

=

^1.

Case2) Assume that Cll

=

dv for some c,dinU+. By Lemma 2.2, we can choose a prime p such that pdoes not divide all nonzero b_{i ,}i = 1, ... , n. Consider

T(CphX

+

Y) =[phalcll

+

blvlphazcll

+

bzvl'" phancu

+

bnvJ

=v[p.ha1d

+

^b},phazd

+

b_{2 , •••},phand

+

bn),

which has spanning column rank 1 for any positive integer h. Since the columns of T(cphX

+

^Y) are finite in number, there exists a column j and a sequence of h's with the properties that i) the jth columns of T(cphX

+

^Y) spans the column space for eachh, and ii) the difference between two successive terms in the sequence is at most n. Therefore for infinitely many h

(1) for some rhk E U+,k = 1, ... , n. In (1), if bj = 0 then bk must be divided by infinitely many nonunit J1^h. But it is impossible since p does not divide b_k for at least one nonzero b_{k •} So b_j is not zero. If the column space of T(cpgX

+

^Y) is spanned by its jth column, then we get

pgakd

+

bk⁼ rgk(pgajd

+

bj ) (2) for somergk EU+. From (1) and (2), we get

I

rgk-rhk lE U+ for9 >h.

By the choice of p, we can choose infinitely many pairs h and 9 such that they satisfy h < 9 S h

+

ⁿ and the column spaces ofT(cphX

+

^Y)

and T(cpg X

+

Y) are spanned by their jth column respectively. For such pairs h and g, consider

Ir

k _ rhkl

=1

^{(p9 ak d}

+

bk ) _ (phakd

+

^h)

I

9 (p 9a jd+bj) (phajd+b j ) _ d

I

(akbj - ajbj)(pg-h - 1)

I

J.Lh

- (p 9aj d

+

bj)(phajd

+

bj ) (3) Assume that rgk

=I

rhk for all such pairs h and g. Since J.L is prime, p is not divided by phajd

+

bj . If J.Lhajd

+

bj has p as its factor, then phajd

+

bj = f3p for some f3 E U+. Thus p(f3 - J.Lh-lajd) = bj and hence bj is divided by p, which is a contradiction. Then J.Lh does not have any factor of (J.Lhajd

+

bj)(J.Lgajd

+

bj). Since d

I

akbj - ajbk

I

is fixed and

I

pg-h - 1

I

is finite value for any pairs hand 9 with 1

S

9 - h

S

n, the prime factors of d

I

(akbj - ajbk)(pg-h - 1)

I

are finite in number. Thus we can choose sufficiently large pair h and 9 with 1

S

9 - h

S

n such that d

I

(akbj - ajbk)(ph-g- 1)

I

does not contain some prime factors of (phajd

+

bj)(pgajd

+

bj). Then the denominator of (3) contains some nonunit prime factors such that

the numerator of (3) does not contain. Since U+ contains no element of the form xfy, where y has a prime factor which x does not, the fractional expression of(3) is not an element of U+. Thus we have a contradiction such that

I

rgk - rhk I~ U+ for some pair 9 and h with h

<

9

:s;

h+n. Hence rgk

=

ru for someh and g. Subtracting(1)from (2), we get ak

=

rhkaj for all k

=

1, ... , n. And we get

h =

^rubj

for all k

=

1, ... ,n from (1). That is, a

=

^{ajr and h}

=

^{bjr where}

r

=

[rh1' ... , rhn] with rhj

=

l.

By cases1) and 2), T(X) and T(Y) has the same strong right factor r. Thussc(T(oX +,8Y»= sc(oaju+,8bjv)rt = 1for arbitrary 0,,8 in U+. This contradicts that T preserves spanning column rank 2 since oX+,8Y has spanning column rank 2 for relatively prime 0 and,8 in U+. Hence T maps column matrices to column matrices. 0

We use the notation Eij for the m xn matrix whose (i,j)-entry is 1 and whose other entries are all O. We also write Xj for the jth column ofX.

PROPOSITION 3.2. Let A be an m x n matrix over S andT(X)

=

AX for allX in Mln,k(S).

(1) IfT preserves spanning column rank 1, then T(X) = 0 onlyif X =0.

(2)Ifk ~ 2, and T preserves spanning column ranks 1 and2, then T is injective on Mln,k(S).

Proof. (1) ITAX= 0 and X=/: 0, then there exists Xij

=/:

0 for some i, j. Then0

=

^{(AX)kj =}

2::=1

aktXtj for arbitrary k. Hence aki= 0 for all k. That is, ai(the ith column of A) is zero. We may take X

=

Eij.

Then sc(X)

=

1 but T(X) is a zero matrix and has spanning column rank O. This contradicts the fact that T preserves spanning column rank 1.

(2) Suppose T(B) = T(e). Then for all j,Ahj

=

ACj == Zj. IT Zj

=

⁰ then it follows from (1) that hj

=

⁰

=

^{Cj' If Zj}

=/:

^0, let Y

=

^[hj

^I

^Cj

10 I ... 101.

Then sc(T(Y»

=

^sc(AY)

=

^sC([Zj

^I

^Zj

10 I ... I

0])

=

1, but T preserves spanning column rank 2, so sc(Y) = l.

Therefore h j

=

^{OCj or Cj =} ,8hj for some 0,,8. IT h j

=

^{OCj, then}

ACj

=

^Zj

=

Abj

=

^{oAcj and Zj}

=/:

o. So 0

=

^{1 and bj = Cj for all}

j. For Cj

=

,8bj , we have the same results. Thus T is injective on Mn,k(S).D

EXAMPLE 3.3. Let Tk(X)

=

(Ei,j xij)A for all X E Mm,n(S), where A E Mm,n(S) and sc(A)=k. Then Tk preserves spanning column rank k, but Tk is not injective. Thus the condition (2) in Proposition 3.2 can not be relaxed by requiring that T preserves spanning column rank 1 or T preserves spanning colwnn rank 2. 0

EXAMPLE 3.4. Let T(EI2 ) = E22 ,T(E22 )

=

E12 and T(Eij)

=

E ij forallother i, j. Extend T to Mm,n(S) by linearity. Let A = Ell

+

E12

and B = Ell +E22 . Then sc(A)

=

¹but sc(T(A))

=

^{2. Also sc(B)}

=

²

but sc(T(B))

=

1. Nevertheless, T is injective. In fact, T is bijective.

Thus injectivity alone does not ensure that spanning column ranks 1, 2 will be preserved by a linear operator.O

THEOREM 3.5. Forn _~ 2,let T bea linear operator on Mm,n(U+).

Then T preserves spanning column ranks 1and 2ifand only if there exist Q E Mm,m(U+),D and PE Mn,n(U+) such that T(X)=QXDP for all X E Mm,n(U+), where Q is invertible in Mm,m(R), D is an invertible diagonal matrix whose diagonal entries are all units in U+

and P is a permutation matrix.

Proof. We first show the sufficiency. Suppose T(X)= QXDP and X has spanning column rank 1, say X = O"xat for some nonzero 0" in U+ and ai = 1 for somei. Let pt correspond to1r E Sn andi = 1r(j). Then QXDP= O"Qx(pt Da)t andd1r(j)a1r(j)

=

d1r(j)' which is a diagonal entry ofD and is a unit element in U+. Hence QXDP has spanning column rank 1. Then T preserves spanning colwnn rank 1. IfX has spanning column rank 2, then X has two linearly independent columns which span all other columns of X. Without loss of generality, we may assume that they areXl andX2. ThenQXl and QX2span all the other columns of QX. Now sc(T(X)) = 1 or 2 by the facts that multiplying DP on the right hand of QX does not change column rank of QX and that T preserves column rank 1. Ifsc(T(X))

=

^{1, then} SC([QXl, QX2]) = 1.

Hence either QXl

=

rQx2 or QX2 = rQxl for some r E U+. Thus

Xl = rX2 orX2 = rXl in R and hence in U+ sinceQis invertible inR.

Then sc(X) = 1, which is a contradiction. Hence sc(T(X))

=

2 and T preserves spanning column rank 2.

Conversely, suppose T preserves spanning column ranks 1 and 2.

Let Xi

=

x(

ed,

i

=

1, ... , n, for some fixed X E(u+)m. By Lemma 3.1, T(Xi) = Yi( e1r(i»)t where (Yi)t = [VIi, Y2i, ... , Ymi] is dependent

on x and ^{11" :} {1, ... ,n} ^-+ {1, ... ,n}. IT 11" is not one-to-one, then for some i and j,aT(Xi)

+

{3T(Xj) has only one nonzero column for all a,(3. That is, T(aXi

+

(3Xj )has spanning column rank 1for all a,{3,a contradiction sinceaXi

+

{3Xj has spanning column rank 2 for relatively prime a,(3 in U+. Thus 11" is one-to-one, and hence it is a permutation. So without loss of generality, we assume 11"

=

e, the identity permutation, so that T(X1 )

=

Y1(el)t and T(X2)

=

Y2(e2)t.

IfYId =1= 0 and YhZ = 0 or vice versa, then T(XI

+

X z)

=

YI(el)t

+

yz(ez)t has spanning column rank 2, contradicting that T preserves spanning column ranks 1 and 2 since X 1

+

^X_z has spanning column rank 1. Thus Yhl

=

0 if and only if Yh2 = O. We assume without loss of generality that Yll andYl2 are positive. Since Xl

+

X 2 has spanning column rank 1, Y2

=

dZ^{Y1 or YI =} d2yz for some dz^{in U+.}

Let Y2 = dZYI. ITd2 is not a unit, choose p relatively prime to d2 in U+, then

T(pXI

+

X 2)

=

[PYI

I

Y2

I

⁰

I I

^0]

= [PY1

I

^d2Y1

I

⁰

I I

^0]

has spanning column rank 2 whilepX1+X₂ has spanning column rank 1,a contradiction. Thus dz is a unit. For the case YI

=

^dZY2' we can show that d₂ is a unit by a similar argument. Then Y2 = (d2)-IY1.

It follows that T(Xi) = (diYI)(ei)t for some unit di,i = 1, ... , n.

In particular, when Xi =.Eji, there exists some vector Y}

==

Uj - [Ylj,Y2j, ... ,Ymj]t E Mm,I(U+) and some unit di E U+ such that

for all i,j. LetQ be the matrix [UI

I

U2

I ... I

um] andD be the diago- nalmatrix diag(dt,d2, ... ,d_{n ).} Then for an arbitrary X E Mm,n(U+),

m n m 11

T(X)

=

LLXjiT(Eji)

=

LLXjiUj(diei)t.

j=1 i=l j=li=1

So the(s,t)

entrY

ofT(X)is :E7=1xjtYsjd:;: The(s,t) entry of QXD is Ei==lYsjXjtdt, which is the (s,t) entry ofT(X). Thus T(X)=QXD for all X EMm,11(U+),

Further we show that Q is nonsingular in Mm,m(R). Suppose that Q= (qij) is singular. Say, Qx

=

⁰ for some nonzero

x

in Mm,I(R).

Since x can be considered as a solution of the homogeneous system of linear equations with coefficients qij E U+, we may assume, without loss of generality, that the entries of x areall inU.So leta = 1+ max

I

I:$i:$m Xi

I,

and z = aj+x, wherej is the vector of alII's. Then z EMm,I(U+) and Qz= Q(aj + x) = Q(aj). Thus

T(ze~+ ode~)

=

Q(ze~)D+ Q(aje~)D

=Q(aj)eiD+ _Q(aj)e~D= Q(aj)(el + e2)tD

has spanning column rank1. Thus ze1_+aje~ also has spanning column rank 1. Then z

=

raj or rz = aj for some r. But then Qz

=

⁰ and hence T(ze1) = 0, contradicting that T preserves spanning column rank 1. Thus Q is nonsingular in Mm,m(R).O

COROLLARY 3.6. Let T : Mm,n(U+) ^-+ Mm,n(U+) be a linear operator, n _~ 2. Then T preserves spanning column ranks if and onlyifthere exist Q E Mm,m(U+),D and P E Mn,n(U+) such that T(X)=QXDP for allX E Mm,n(U+), where Q is invertible in Mm,m (R),D is an invertible diagonal matrix whose diagonal entries are all unitsin U+ and P is a permutation matrix.

Now we have examples which show the Lemma 3.1, Theorem 3.5 and Corollary 3.6 do not hold if certain conditions were not satisfied.

EXAMPLE 3.7. Let S

=

^{(Z[V7])+ and let T: M}2,2(S) -+ M2,2(S) be the linear operator given by T(X)

=

X

[~ ~].

Then T maps column matrices to column matrices and it is of the form QXDP. But the diagonal entries ofD are not units overS. So we show that T does not preserve spanning column ranks 1and 2. Consider Xl

= [~ ~]

^with

sc(Xt} = 1.ThenT(Xt} = [;

~]

has spanning column rank 2 overS.

And consider X2

= [; ~]

^{with sc(X2 )}

⁼

2. Then T(X2 )

= [~ ~]

has spanning column rank1overS. Moreover, this example shows that the converse of Lemma3.1 does not hold.

EXAMPLE 3.8. Let S = {O} U {q E Q Iq;::: I}. Then S is a nonnegative semidomain, but S ^-=1=U+ for some unique factorization domain U in R. Let T : Mm,z(S) ^--+ Mm,z(S) be the linear operator given by T( X) = X

[~ ~

^]. Then we show that T preserves the spanning column rank ofX. Certainly, T preserves spanning column rank O. Let X

=

[Xl

I

xz]. Suppose that sc(X)

=

1; then for some q E S, either Xl

=

^{qxz or Xz}

=

^{qXI. In} the former case, we find that T(X) = [(q+2)xz

I

(2q+l)xz]. Hq = 0, then evidently sc(T(X)) = 1, while if q ;::: 1, then 2q + 1 ;::: q + 2, and so p = (2q + l)/(q + 2) ES.

Since the second column of T(X) isp times the first, we see that T(X) has spanning column rank 1. A similar argument applies if Xz = qx}, and we see that T preserves spanning column rank 1.

Conversely, suppose that T(X) = [Xl +2xz 12xI +xz] has spanning column rank 1. Then for some pE S,either Xl + 2xz

=

P(2XI + xz) or 2XI +Xz = p(XI +2xz). Suppose that the former holds, and note that pcannot be 0 (otherwise T(X) would be the zero matrix). Thusp;::: 1, and (2 - p)xz = (2p - l)XI' Note that 2 - p ;::: 0, and if p = 2, then Xl = 0,and it follows that sc(X) =.1. ITp

<

2, then from the fact that 2p-1 ;::: 2 - p, we have r

=

(2p-1)/(2- p) ES. Since Xz

=

rx}, we see that sc(X)

=

1. A similar argument applies if 2XI + Xz

=

P(Xl + 2xz) and we see that if sc(T(X))

=

^{1then sc(X)}

=

^{1. It} now follows that T preserves spanning column ranks 1 and 2 on Mm,z(S).

But T does not map column matrices to column matrices since T(En ) =

[~ ~].

Moreover T(X) is not of the form QXDP for any 2 x 2 invertible diagonal matrix D and a permutation matrix P over S.D

We have studied the spanning column rank preservers on Mm,n(S) for n ;:::2. Now we make a remark on the spanning colUlnn rank pre- servers on Mm,I(S),

PROPOSITION 3.9. Let T : Mm,I(S) ^--+ Mm,I(S) be a linear opera- tor. Then T preserves spanning colUInn rankifand onlyifthere exists QE. Mm,m(S) each. of whose colUInns have at least one nonzero entry such that T(X) = QX for allX E Mm,I(S),

Proof. Let Q be the matrix of T with respect to the basis {Ej~

I

j = 1, ... ,m} of Mm,l(S). Then T(X)

=

^QX and the jth column of Q is the coordinate ofT(Ej .), which is not zero since T preserves spanning column rank 1. Hence each of the columns ofQhas at least one nonzero entry. The converse is obvious.D

References

1. L. B. Beasley and S. Z. Song, A comparison of nonnegative real ranks and their preservers, Linear and Multilinear Algebra31 (1992), 37-46.

2. L. B. Beasley and N. J. Pullman, Semiring rank versus column rank, Linear Algebra Appl. 101 (1988),33-48.

3. L. B. Beasley and N. J. Pullman, Boolean rank-preserving operators and Boolean rank-1 spaces, Linear Algebra Appl. 59 (1984), 55-77.

4. L. B. Beasley, D. A. Gregory, and N. J. Pullman, Nonnegative rank-preserving operators, Linear Algebra Appl. 65 (1985),207-223.

5. D. A. Gregory and N. J. Pullman, Semiring rank: Boolean rank and nonneg- ative rank factorizations, J. Combin, Inform. System Sci. 8 (1983), 223-233.

6. R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press (1990).

7. S. G. Hwang, S. J. Kim and S. Z. Song, Linear operators that preserve maximal column rank of Boolean matrices, Lin. Multilin. Alg. 36 (1994), 305-313.

8. S. Z. Song, Linear operator that preserves column rank of Boolean matrices, Proc. Amer. Math. Soc. 119(4) (1993), 1085-1088.

Suk-Geun Hwang

Department of Mathematics Education Teachers College, Kyungpook University Taegu, 702-701, Republic of Korea Si-Ju Kim

Department of Mathematics Education Andong University

Andong, 760-749, Republic of Korea Seok-Zun Song

Department of Mathematics Cheju National University

Cheju, 690- 756, Republic of Korea