SPANNING COLUMN RANK 1 SPACES OF NONNEGATIVE MATRICES
SEOK-ZUN SONG, GI-SANG CHEON AND GWANG-YEON LEE
1. Introduction
There are some papers on structure theorems for the spaces of matri- ces over certain semirings. Beasley, Gregory and Pullman [1] obtained characterizations of semiring rank 1 matrices over certain semirings of the nonnegative reals. Beasley and Pullman [2] also obtained the structure theorems of Boolean rank 1 spaces. Since the semiring rank of a matrix differs from the column rank of it in general, we consider a structure theorem for semiring rank in [1] in view of column rank.
In this paper, we obtain a characterization of column rank 1 matrices and a structure theorem for the vector space of matrices whose nonzero members all have spanning column rank lover nonnegative part of a unique factorization domain that is not a field in the reals.
2. Definitions and preliminaries
Let R denote the field of reals and S denote an arbitrary semiring of nonnegative reals. Let U+ be the nonnegative part of a unique factorization domain which is not a field in R. Such examples are Z+,(Q[1l'])+ etc., where Z,Q denote the rings of integers and rationals, respectively, and 1l' is a transcendental number over Q.
Let A be an m x n matrix over S. If A is a nonzero matrix, then the umiring rank [3] of A, reA), is the least k for which there exist m x k and k x n matrices F and G over S such that A = FG. The zero matrix is assigned the semiring rank O. The set of m x n matrices
Received November 2, 1994.
1991 AMS Subject Classification: Primary 15A03, 15A23.
Key words: Spanning column rank, spanning column rank 1 space.
Supported by Korea Science and Engineering Foundation 941-0100-027-2, and in part by TGRC-KOSEF, 1994.
with entries in S is denoted by Mm,n(S). Addition, multiplication by scalars, and the product of matrices are defined as if S were a field.
IfV is a nonempty subset of Sk == Mk,l(S) that is closed under addition and multiplication by scalars, thenV is called a vector space over S. The notions of subspace and of spanning sets are the same as if S were a field. As with fields, a basis for a vector space V is a spanning subset of least cardinality. That cardinality is the dimension, dim(V), ofV.
For an m x n matrix A over S, the column rank [5],c(A), is the dimension of the vector space spanned by its columns, and thespanning column rank [4], sc(A), is the minimum number of the columns of A which span its column space..
It follows that
(2.1) 0::; r(A) ::; c(A) ::; sc(A) ::; n
for all m x n matrices A over S. But these rank functions may differ over certain semirings as shown in the following example.
EXAMPLE 2.1. CO+Lsider a matrix A = [3,6- 2-./7,2-./7 - 4] over a semiring S = (Z[v7])+. Then it is trivially that r(A) = 1. Since (6 - 2-./7)+(2-./7 - 4) = 2, 2is spanned by the last two columns ofA.
Then we have (6 - 2-./7) =2(3 - v7) and 2-./7 - 4 =2( -./7 - 2) with 3 - v7,...{i - 2E S, which means that {2,3} is a basis of the column space ofA. So c(A)= 2. But, any column ofA cannot be spanned by the other two columns. That is, sc(A) =.3. •
Let rbe a nonempty subset ofSA: and letg E Sk. We'll say that g is a common factor ofr ifr ~ {ugIu E S}.
LEMMA 2.2. ([1]) Let fbe any nonempty subset of(U+)k. Each pair of nonzero vectorsinr has a common nonzero scalar multiple in (U+)kifand onlyifr has a common factorin (U+)k. •
EXAMPLE 2.3. Ifk >1,let
1 k-1)
k 0 .
o k
H 0 < k < 1, let p = [i1, q= p - 1 and
A(k) = G1- kqko kp -1)0k .
Ifk is a nonzero nonunit inS, thenc(A(k» = 3by definition of column rank. Multiplying the first column ofA( k)bykreduces its column rank to 2. From this matrix A( k) we can obtain an m x n matrix of column rank r such that the matrix obtained by multiplying the jth column of it by k has column rank r - 1 as follows ; let P be the matrix obtained fromIn by interchanging I~sfirst and jth column, and let B be any (m - 3) x (n - 3) matrix over S of column rank r - 3. Then X = (AEElB)P is the required matrix of column rank r. •
3. Column rank 1 matrix
HX is a matrix over a semiring S and X = xat, then the vectors x, a are called left and right factors of X respectively. In particular, a is called a basic right factor ofX ifat has column rank 1.
THEOREM 3.1. For A E Mm,n(S),c(A) = 1 ifand onlyifA can be factored asxat forsome a E sn, x E Srn, wherex i= 0 andat is a basic right factor.
Proof. Suppose that c(A) = 1 and denote the columns of A by
a1,'" ,an' Let {x} be a basis of the column space of A over S, so that x = L:j=l;jaj for some constants;1,' .. ,;n in S. Inparticular, x E Sm and x i= O. Now for eachj between 1 and n,we have aj = ajx
for some aj E S, since x spans the column space of A. Letting at = [ab'" ,an],we have a ESn and A = xat• Further, x = L:j=l;jaj =
Ej=l;jajx, and hence 1= Ej=l;jaj since x is not zero. Thus 1 is in the column space of at, and it follows that c(at)= 1. Consequently, a is a basic right factor ofA, as desired.
The converse is clear. •
Identifying smn with Mm,n(S), we transfer the definitions to Mm,n (S). If V i= {O} is a vector space in Mm,n(S) whose members have column rank at most 1, then V is a column rank 1 space. IfV is a
vector space all of whose members have the same basic right factor b, then V is called a basic right factor space. Notice that in that case W = {a E Sm Iabt E V} is a vector space in Sm. Conversely, ifW is a vector space in sm and c(bt) = 1 then {abt Ia E W} is a basic right factor space in Mm,n(S). Evidently basic right factor spaces are column rank 1 spaces.
Define a relation ,\ on the m x n column rank 1 matrices over S by :A'\B ifA and B have a common basic right factor.
PROPOSITION 3.2. (1) ,\ is an equivalence relation on the m x n column rank 1matrices overU+.
(2) For any nonempty set E of m x n column rank1matrices overU+, the members of E have a common basic right factorifand onlyifX ..\Y forallX, Yin E.
Proof (1) Evidently,\ is refle:ltive and symmetric. Suppose A,B,C arem x n column rank 1 matrices over U+ that satisfy A,\Band B,\C.
Then A,B and C can be factored as A = xat,yat = B = zbt and C = wbt by Theorem 3.1, where at and b t have column rank 1. Now a, b have a common nonzero scalar multiple because the left factors of B are nonzero. Therefore a,b have a common factor f by Lemma 2.2, and ft has column rank 1. So A and Ccan be factored as A = (ax)ft and C = ((:Jw)ft for some a,(:J E U+. Consequently A,\C and hence ,\
is transitive.
(2) SupposeX,\Yfor all X, Y inE. For eachX inE, select a basic right factor gx and put r = {gX IX E E}. By the proof of (1), if A, B are in E, then A and B have a common basic right factor. Thus gA andgB have a common nonzero scalar multiple. Thereforer has a common factor f by Lemma2.2, and ft has column rank 1. Thus f is a cOmlnon basic right factor ofall X inE.
The converse is immediate. ..
Thus the ..\-equivalence classes are the maximal basic right factor spaces in Mm,n(U+). These in turn are of the form yea) = {xat I
x E U+}, where c(at) = 1.
4. Spanning column rank 1 spaces
In this section, we obtain a structure theorem for the vector space
of matrices whose members have spanning column rank at most 1. For this purpose we need some definitions and lemmas.
IfA is a matrix over a semiring S and A has the form fat, then a is called a ~trong right factor of A if at has spanning column rank 1.
Hwang, Kim and Song [4] showed the following Lemma:
LEMMA 4.1. ([4]) For A E Mm,n(S),sc(A)= 1ifand onlyifA can be factored asfat for some a E Sn andf E Sm, where f =1= 0 and at is a strong right factor. •
IfV =1= {O} is a vector space inMrn,n(S) whose members have span- ning column rank at most 1, then V is called a spanning column rank 1
~pace. IfV is a vector space all of whose members have the same strong right factor b, then V is called a ~trong right factor ~pace. As the case of basic right factor space, W = {a E srn Iabt EV} is a vector space in srn. Conversely, ifW is a vector space in srn and sc(bt) = 1 then {abt I a EW} is a strong right factor space in Mrn,n(S). Evidently strong right factor spaces are spanning column rank 1 spaces.
Beasley and Pullman [1] obtained a Lemma for the common factor of two matrices as follows:
LEMMA 4.2. ([1]) Suppose A andB are m xn matrices of semiring rank lover U+ and min(m, n) ~ 2. Then r(A +B) = 1ifand onlyif A and B havea common factor. •
For the common strong right factor of two matrices, we obtain the following Lemma:
LEMMA 4.3. Suppose A, B E Mm,n(U+) with sc(A) = sc(B) = 1 and min( m,n) ~ 2. Then A and B have a commonstrong right factor ifand onlyifsc( aA+(3B) = 1 for any a,(3 E U+, not both zero.
Proof. By Lemma 4.1, we can write A = fat, and B = gbt for somef, g E(u+)m and a, b E(U+t with sc(at) =sc(bt)= 1. Assume
that A and B have a common strong right factor r. Then, for any 0',(3 E U+,aA +(3B = (aaf +(3Tg)rt for some a,T E U+. Since sc(rt) = sc(art) =sc(at) = 1,sc(aA+(3B) =1 for any 0',(3, not both zero.
Conversely, assume that sc(aA +(3E) = 1 for any 0:,(3 E U+, not
both zero. Then we have r(aA+(3B) = 1 by (2.1). In particular, A and B have a common factor by Lemma 4.2.
Case 1) A andB have a common right factor r. Then we can write A +B =((Tf+Tg)rt for some (T,T E U+. Since se(rt) =se((Trt) =
se(at) = I,A and B have a common strong right factor r.
Case 2) A and B have a common left factor d. Then we may write A = daat and B = d,Bbt, where aa = (all"', anY, and ,Bb = (bI,'" , bn)t are strong right factors ofA and B, respectively.
Since there are infinitely many primes in U+ (for the existence of infi- nite primes, see Lemma 2.2 in [4]), we can choose a prime7r such that
7r does not divide all nonzero bi,i = 1" ., , n. Consider
which has spanning column rank 1 for any positive integerp. Since the columns of7rPA+B are finite in number, there exists a column j and a sequence ofp'swith the properties that i) the jth columns of7rPA+B spans the column space for each term p in the sequence, and ii) the difference between two successive tenns in the sequence is at most n.
Therefore for infinitely manyp, (4.1)
for some /-'hk E U+,k = 1,'" ,no In (4.1), if bj = 0, then bk must be divided by nonunit 7rp• But it is impossible since 7r does not divide bk for at least one nonzero bk • Thus bj =1= O. H the column space of
7rqA+B is spanned by its jth column, then we get (4.2)
for some /-,qk E U+,k = 1,'" ,no From (4.1) and (4.2), we get I
/-'qk - /-,pk lE U+for q>p. Since there are only n columns in 7rPA+B for eachp, we can choose infinitelyIilany paitspandq su.chthat they satisfy p < q~ p+n and the column spaces of7rPA+B and 7rqA+B are spanned by their jth column respectively. For such pairsp and q, consider
(4.3)
Assume that Jlqk =f. Jlpk for all such pairs p and q. Since 7r is prime,
7r is not divided by 7rPaj +bj . If 7rPaj +bj has 7r as its prime factor, then 7rPai +bi =f37r for some f3 EU+. Thus 7r(f3 - 7rP - 1ai) =bi and
hence bi is divided by 7r, which is a contradiction. Then 7r P does not have any factor of (7rPai +bi)(7rqai +bi)' Since Iakbi - ajb k Iis fixed and I 7rq-p
- 1 Itakes at most n values for any pairs p and q with 1 ::::; q - p::::; n, the prime factors ofI(7rq- p -l)(akbi - ajh) Iare finite in number. Thus we can choose sufficiently large pair p and q with 1::::; q - p::::; n such that I(7rg-p -l)(akbj - aibk) Idoes not contain some prime factors of(7rPaj+bj )(7rqaj+bj ). Then the denominator of (4.3) contains some nonunit prime factors such that the numerator of (4.3) does not contain. Since U+ contains no element of the fonn ~,
where y has a prime factor which x does not, the fractional expression of (4.3) is not an element of U+. Thus we have a contradiction such that I7rqk - 7rpk I~ U+ for some pair p and q with p < q ::::; p +n.
Hence Jlqk = Jlpk for some p and q. Subtracting (4.1) from (4.2), we have ak = Jlpkai for all k = 1"" ,n. And we get h = Jlpkbj for all k = 1"" ,n from (4.1). That is, a = ajr and b = bir where r = [Jlpl,' .. ,Jlpn] with Jlpj = 1.
By cases 1) and 2), A and B have a common strong right factor r . •
Define a relation p on the m x n spanning column rank 1 matrices over a semiring S by : ApB ifA, B have a common strong right factor.
Then we have some properties on the relation p that are similar to those on the relation ,\ in section 3.
PROPOSITION 4.4.
(1) p is an equivalencerelation on the m x n spanning column rank 1 matrices over U+.
(2) For any nonempty set F of m x n spanning column rank 1 matrices over U+, the members of F have a common strong right factorifandonlyifX pY for all X, Y in F.
Proof. Similar to the proof of Proposition 3.2. •
Thus the p-equivalence classes are the maximal strong right factor spaces in Mm,n(U+). These in turn are of the form V(a) = {xat I
x E(u+)m}, where at has spanning column rank 1.
THEOREM 4.5. Suppose tbat V is a subspace ofMm,n(U+) witb minern,n) :2:: 2. Tben V is a spanning column rank 1 space if and only ifV is a strong rigbt factor space.
Proof Suppose V is a spanning column rank 1 space. For every A and B in V,sc(aA +j3B) = 1for any a,j3EU+, not both zero. Then A and B have a common strong right factor by Lemma4.3. Therefore V is a strong right factor space by Proposition4.4.
The converse is immediate. •
Thus we have a structure theorem for spanning column rank 1 space inMm,n(U+).
References
1. L. B. Beasley, D. A. Gregoryand N.J. Pullman, Nonnegative rank-preserving operators, Linear Algebra Appl. 65 (1985), 207-223.
2. L. B. Beasleyand N. J. Pullman, Boolean rank-preserving operators and Boolean rank-l spaces, Linear Algebra Appl. 59 (1984), 55-77.
3.L.B. Beasley and S. Z. Song, A comparison of nonnegative real ranks and their preservers, Linear and MultiIinear Algebra 31 (1992), 37-46.
4. S. G. Hwang, S.J. Kim and S. Z. Song, Linear operators that preserve spanning column rank of nonnegative matrices,J. Korean Math. Soc. 31 (1994),645-657.
5. S. Z. Song, Linear operators that preserve column rank of Boolean matrices, Proc. Amer. Math. Soc. 119(1993), 1085-1088.
6. S. Z. Song, Linear operators that preserve column rank of fuzzy matrices, Fuzzy Sets and Systems 62 (1994), 311-317.
Seok-Zun Song
Department of Mathematics Cheju National University Cheju 690-756, Korea Gi-SangCheon
Department of Mathematics Dae Jin University
Pocheon 487-800, Korea Gwang-Yeon Lee
Department of Mathematics Hanseo University
Seosan, Chung-Nam 352-820, Korea
