A comparison of maximal column ranks of matrices over related semirings

A COMPARISON OF MAXIMAL COLUMN RANKS OF MATRICES OVER RELATED SEMIRINGS

SEOK-ZUN SONG

1. Introduction

Let A be a real m x n matrix. The column rank of A is the dimension of the column space of A and the maximal column rank of A is defined as the maximal number of linearly independent columns of A. It is well known that the column rank is the maximal column rank in this situation.

However, we can also consider matrices whose entries come from another kind of algebraic system, such as a semiring or Boolean alge- bra. In this different context, the notions of column rank and maximal column rank can still be defined, but the two ranks do not necessarily agree. Indeed, Hwang, Kim and Song [6] compared the column rank and the maximal column rank for matrices over various semirings and found that except for small values of m and n, the two ranks did not agree

general.

In this paper we continue the study of maximal column rank, but instead of fixing the algebraic system and comparing the two ranks as in [6], we will compare the maximal column rank when the matrix is considered over different algebraic systems. For example, we can consider the matrix

as a matrix over R, the real numbers, or as a matrix over Z2 , the in- tegers modulo 2. Considered as a matrix over R, the maximal column

Received August 2, 1996.

1991 AMS Subject Classification: Primary 15A03, 15A48.

Key words: linearly independent, maximal column rank.

Supported by KOSEF~961-0101-004-2,and partially by TGRC-KOSEF.

rank of A is three, while considered as a matrix over Z2, the maximal column rank of A is two (the third column is the sum of the first two).

More generally, given semirings Sand T, suppose that A is a matrix which can be considered either as a matrix over S or as a" matrix over T. Under what circumstances is the maximal column rank of A over S equal to the maximal column rank of A over T? Is there any rela- tionship? We will investigate these questions for several well-studied semirings, including the reals, the nonnegative reals, the integers, the nonnegative integers, the integers modulo a, finitely generated Boolean algebras, and fuzzy sets.

In section 2, we give necessary definitions and preliminary results, and in section 3, we establish some general inequalities for maximal column rank function, while in section 4, we obtain the cases of equal- ity of maximal column ranks. In section 5, we compare the maximal column rank of a given m

n matrix over both a semiring and its subsemiring as m and n vary.

2. Definitions and preliminaries

A semiring consists of a set S and two binary operations on S, addition and multiplication, such that:

(1) S is an abelian monoid under addition (identity denoted by 0) (2) S is a monoid under multiplication (identity denoted by 1) (3) Multiplication distributes over addition; and

(4) sO=Os=O for

sinS.

Usually S denotes both the semiring and the set. Many combinatorially interesting semirings are the nonnegative integers Z+, the nonnegative rea-Is

The Booleahalgebra[9] of subsets of a

Bk' is also a semiring, where addition corresponds to set union and multipli- cation corresponds to set intersection. In the sequel, we will often want to consider Bk to be a subsemiring of B

when

This is easily accomplished by considering the j-set for B j to be {aI, a2, ... ,aj} and then associating Bk with the isomorphic subsemiring of B

consisting of the set of all unions and intersections of {al}, {a2}, ... ,{ak-l} and {ak, ... ,aj}. Henceforth we will assume that Bk is a subsemiring of B

whenever k ::;

Let S be any set of two or more elements. If S is totally ordered by

~,

that is, S is a chain under

then define x + y as max{x,y} and xy as min{ x, y} for all x, y in S. If S has a universal lower bound and a universal upper bound, then S becomes a semiring: a chain semiring [2J. In particular, the chain semiring generated by the numbers in the interval [O,lJ is denoted IF, and is called the fuzzy numbers [8]. As above for the Booleansemirings, a

semiring tb-at is a subset of another may be considered a subsemiring by appending the zero and identity of the larger to the smaller. Henceforth we will assume that a chain semiring that is a subset of another is a subsemiring.

Given any semiring S, we denote the set of m x

matrices with entries in S by Mm,n(S), Addition of vectors (mx 1 matrices), addition and multiplication of matrices, and scalar multiplication are defined as if S were a field. A set of vectors is a semimodule [3] if it is closed under addition and scalar multiplication. A subset W of a semimodule V is a spanning set if each vector in V can be written as a sum of scalar multiples (Le., a linear combination) of elements of W. As for real fields, we can define three concepts ofrank for a matrix A

Mm,n(S).

The semiring rank [1] of A, rs(A), is the minimum integer k such that A can be factored as A = XY, where X

Mm,k(S) and Y

Mk,n(S).

The column space of a matrix A is the semimodule spanned by the columns of A. Since the column space is spanned by a finite set of vectors, it contains a spanning set of minimum cardinality; that cardinality is the column rank [2] of A, cs(A).

A set U of vectors over S is linearly dependent if for some u

U,

is a linear combination of another elements of U. Otherwise U is linearly independent. The maximal column rank [6] of A, ms(A), is the maximal number of linearly independent columns of A. Our goal here is to compare the values of ms(A) as S varies over some familiar semirings such as JR, JR+, Z, Z+, Za and Bk. We give an example:

EXAMPLE

2.1. Let A

[2 3 4 5] be a matrix in M

,4(Z+).

Then we have

(A) =

But

(A) = 2 since the first two columns span the column space of A. And

(A) = 3 since the last three columns are the maximal linearly independent columns of A.

The following result is easily established.

PROPOSITION

2.2. Suppose that S is a semiring, and tbat A is a

p

q matrix over S. If X

[~ ~

where the zero block on the diagonal has arbitrary dimensions, then Cs (A) = Cs (X) and ms(A) =

ms(X).

3. The inequality cases in maximal column rank

In this section, we establish some general theorems about the maxi- mal column ranks of matrices whose entries lie in two related semirings.

Suppose that S and Tare semirings and h : 5

T is a semiring homomorphism. We identify an m x n matrix A=[aij] whose entries lie in 5, with the m

n matrix H(A) whose (i,j)-th entry equals h(aij).

Thus

H: M'I1'l,n(5)

M'I1'l,n(T),

and any matrix A

M'I1'l,n(S) can be viewed as a matrix H(A)

M'I1'l,n(T). Our first result can be summarized as follows: a homomor- phism does not increase the maximal column rank.

THEOREM

3.1. Let 5 and T be semirings and h : 5

T be a semiring homomorphism. Then ms(A)

mT(H(A)) for every matrix AEMm,n(S),

Proof. Let ms(A) = ^{k and let A} = [a1Ia2/ ... Ia

where ai is a column vector of A for each i

1,2, ... , n. Put

where each H(ai) represents the entrywise image vector of

under h. We Win show that the maXimal number of linearly independent columns of H(A) is at most k. To show this, let us choose any k + 1 column vectors

...

of H(A). Then the col- umn vectors

of A are linearly dependent over 5 by the maximality of k. Hence there exists at least one aip among them such that

with

E S.

Since h is a semiring homomorphism, so is H. Thus

H(ai p) =

+ H(r2ai2) + ... + H(rp-laip_l) + H(rp+laip+l)

+ ... + H(rk+laik+J

= h(rl)H(Cli

+ h(r2)H(Cliz) + ... + h(rp-dH(ai".,..J .

+ h(rp+l)H(aip+J+ ... + h(rk+l)H(aik+J.

Since each h(ri) ET, we have

is a linearly dependent set over T. Thus the maximal number of lin- early independent columns of H(A) is not greater than k. That is,

ms(A) 2:: mT(H(A)). 0

If S is a subsemiring of T, then the canonical injection of S into T is a homomorphism, and hence by Theorem 3.1, ms(A) 2:: mT(A) for each matrix A

Mm,n(S). In this case, we abbreviate the above to ms 2:: mT·

COROLLARY

3.2. H S is a subsemiring of T, then ms 2:: mT. In particular,

(1) if

2:: k, then

2::

(2) mz+ 2:: mz, mz 2::

mp 2:: mjR for any subring P of the reals with identity and

(3) mz+ 2::

2:: mjR+ for any subsemiring

with iden- tity ofR+.

Let A = [aij] be an m x n matrix whose entries belong to a semiring S. We define the

of A to be the m x n matrix A =

where

= ^{0 if}

= ^{0 and}

= 1 otherwise.

COROLLARY

3.3. Let S be an antinegative semiring (that is, only

o ^has an additive inverse) with identity 1 and B

be the two element Boolean algebra {O, 1}. Then

(A) ::; ms(A) for all matrices A

Mm,n(S), In particular, if A is any (0,1) matrix, then

(A) ::;

ms(A).

Proof. The mapping h :

B

defined by h(a) =

if a =

and h(a) = 1 if a

0, is a semiring homomorphism. The result now follows

from Theorem 3.1. 0

[ 1 2 3]

EXAMPLE

3.4. Let S = ^{JR+ and let A} = ^{4 5 6 . Then H(A)} =

- [1 11]

A = 1 1 1 and therefore mjR+ (A) =

since any two columns are linearly independent but the second column can be spanned by the others. Clearly,

(A) = 1. This shows that strict inequality can hold in Corollary 3.3.

COROLLARY

3.5. Let a and b be integers with a, b 2: 2. Suppose A is a matrix with entries in {a, 1,2, ..., a-I}. Then

Proof. Consider the canonical mapping h : Z

and k :

Then

and

are ring homomorphisms. The results

follow from Theorem 3.1. 0

4. The equality cases in maximal column rank

In section 3, we obtained some general inequalities for maximal col- umn ranks of matrices over various semirings. We find certain cases such that the given matrix has the same maximal column rank over different semirings. In this section, we discuss the equality cases for some types of semirings.

THEOREM

4.1. If A

Mm,n(Z), then we have mz(A) = mjR(A).

Proof. It is well known that the column rank of A over Z equals the column rank of A over JR. Since, over JR, c(A) = meA), we will show that mz(A) = ^{cz(A). In general mz(A) 2: cz(A). If cz(A)} = ^{k, then}

the column space of A has dimension k. So any k + ¹ columns of A are linearly dependent over Z. Hence mz(A)

k. 0

THEOREM

4.2. Let

and

be chain semirings such that

is a

subsemiring ofC

If A E Mm,n(C

then mCl (A) = mC2(A).

(1)

Proof. Since Cl

C

we have

by Corollary 3.2. Let C(A) be the chain semiring consisting of 0,1 and the entries in A. Then C(A) is a chain semiring such that C(A)

Cl.

It follows that (2)

by Corollary 3.2. Let

C

C(A) be the map such that h(a)

L ^b

bEU(a)

for

where

U(a)

{b

C(A)lb:::; a}.

If

aI, a2

C

with al :::; a2, we find that U(al)

U(a2) and hence head :::; h(a2). It follows that h is a homomorphism from C

to C(A).

By the construction, H(A)

A. Therefore, we have (3)

(A) 2:

(H(A))

(A)

by Theorem 3.1. Hence (1),(2) and (3) imply that

(A) =

(A).

o

THEOREM

4.3. Suppose that

k, so that B

C Bk. If A

Mm,n(B

then mBj(A)

mBk(A).

Proof. Since B

Bk , mBj(A) 2: mBk(A). Let B(A) be the Boolean algebra generated by 0 (empty set), 1 (the j-set) and the en- tries of A. Then B(A)

B

Thus mB(A) (A) 2: mBj(A) by Corollary 3.2. By the analogous method of the proof in Theorem 4.2, we have

mBj (A) = mBk (A). 0

COROLLARY

4.4. For any (0,1) matrix A, any chain semiring C which contains 0,1 and any integer k with k 2: 1, we have

where IF is the semiring of fuzzy numbers.

Proof By Theorem 4.3,

(A) =

for any k ;:::: 1. Since the Boolean algebra B

is also a chain semiring and it is contained in any chain semiring C, and in particular, in the semiring IF of fuzzy numbers. Thus by Theorem 4.2, both mc(A) and m]F(A) are equal to

mBl(A).

D

5. The comparison of maximal column ranks

In this section, we compare the maximal column rank of a given matrix over both a semiring and its subsemiring.

Suppose that S is a subsemiring of a semiring T. Let F(S, T, m, n) denote the maximum integer k such that there exists a matrix in Mm.,n(S) with maximal column rank k and for every A

Mm.,n(S) with ms(A) ::; k we have ms(A) = mT(A). Then F(S, T, m, n) ;:::: 0 since for any semiring S, ms(A) = 0 ifand only if A is the zero matrix.

In section 4, we have obtained the following equalities:

mBj

=

for anyj ::;

and

=

for any chain semirings Cl and C

with Cl

C

Also, we have shown that for any matrix A

Mm.,n(R+), (4)

where A is the pattern matrix of A. And we have

(5) (6) (7)

mjR ::; mjR+

mjR+ ::; mz+

... < ...

mZ_a _ mZ_ab

for any positive integers a and

(8)

for any positive integer a.

We will show that equality does not hold in general for any of (4)-

(8). Our approach will be to investigate the values of F(S, T, m, n) for

appropriate semirings Sand T. First we will look at (4).

EXAMPLE

5.1. Let

x=u _{~ ~].}

Then

(X) =.2 since.the la..c:;qwocolu.mns

first column.

Thus the maximal number of linearly independent columns is 2, while mlR+ (X) = 3 since the three columns of X are linearly independent over lR+. Thus mB} (X) < mlR+ (X).

THEOREM

5.2. Suppose that A

M

,n(B

(1) Hmin(m,n)::S; 2, then mBl(A) = mlR+(A).

(2) Let min(m, n) 2: 3. Then mBl (A) = mlR+ (A) whenever mlR+(A)::S; 2, whilethereexistsanmxnmatrixY

Mm,n(B

such that mB

(Y) < mlR+ (Y) whenever mlR+ (Y) 2: 3.

Proof. (1) If m = 1 or n = 1, then it is clear. Suppose that m 2: n =

2. Let A

be an mx2 matrix. IfmB

(A)

1, then

ba.2 or

0.2

= ba.1 for b

B _{1. But b} = 0 or 1, so mlR+(A) =

If mB

(A) = 2, then

and

are linearly independent over B

Thus there exists at least one positive integer

such that aj1

aj2. This implies that mlR+ (A)

2. Since we have mB

(A) ::s; mlR+ (A) by Corollary 3.3, it follows that mB

(A) = mlR+ (A).

Suppose n 2: m = 2. Let A =

lOon] be a 2 x n ma- trix. Since each entry of A is either 0 or 1, the only forms of a.i are

[ ^~] , ^[~] ,U] , ^[~]. Thus the maximal column rank of A on lR+ is at most 2. Therefore, if mBl (A)

2, then A has at least two columns among the above three nonzero columns. It follows that mlR+ (A)

2.

Also if mBl (A) = 1, then there exists one nonzero column

such that a.i = bia.j with bi

B 1. But bi = 0 or 1, so mlR+(A) = ^1. Using mB

(A) ::s; mlR+(A) by Corollary 3.3, we have mBl (A) = mlR+(A).

(2) If mlR+ (A) = 1, then clearly mB

(A) = 1, and vice verse. If mlR+ (A)

2, then mB

(A) ::s; 2 by Corollary 3.3. But mB

(A) = 1 if and only if mlR+ (A) = ^1. So mB

(A) = 2.

Now, consider the matrix X in Example 5.1 and let

Y

~] ^ffil

where I

is an r

r identity matrix and the zero blocks are suitable zero submatrices such that Y is an m x n matrix. Then Y is the desired one.

For example, we can construct an 10 x 9 matrix Y over B

such that mjR+ (Y) = 6 > 5 = mBl (Y) as follows;

with a 4 x 3 zero submatrix 03. D

COROLLARY

5.3. Suppose that A

M m,n(1R+). ^Hmin(m,n) 1, then mBJA)

mjR+(A). On the other hand, ifmin(m,n) 2: 2, then there is a matrix YE M m,n(1R+) ^{such that mBJY)} < mjR+(Y), whenever mjR+ (Y) 2: 2.

Proof. For the case min(m, n)

1, it is clear. Consider a matrix X = D ~] over lR+. Then mjR+(X) = ^{2 but mBl(X)}

^{1. Thus we}

can construct an m x

matrix Y such that Y

[~ ~] ^{EI3 I}

^{as the}

case of Theorem 5.2 (2). D

The following example gives some insight into inequality (5.3).

EXAMPLE

5.4. Let A = [3 5] be a 1 x 2 matrix. Then the sec- ond column of A is 5/3 times the first, so there

only one linearly independent column in A over lR+ and hence mjR+ (A) = 1.

However, no integer multiple of the first colUIIin equals the second, and vice versa, so the two columns of A are linearly independent over Z+ and hence we have that mz+(A)

2 > mjR+(A).

Thus we have the following comparison theorem.

THEOREM

5.5. F(Z+,lR+,m,n) = ^1.

Proof Since we know that any nonzero matrix has maximal column

rank at least 1, it

clear that mjR+ (A) = mz+ (A) whenever mz+ (A) :S

1. But we had a matrix A in Example 5.4 such that mjR+(A) = 1 and

mz+(A)

2. By proposition 2.2, we always have an m x

matrix X

over Z+ with mjR+ (X)

1 and mz+ (X)

2 whenever n

2. Thus

F(Z+,~+,m,n)=

1.

Let A

If mlR(A)

1, then each column of A is a multiple of the first nonzero column of A. Moreover', each column of A is a. normegatille multiple of that column, and hence there exist no two linearly independent columns of A. Consequently mjR+ (A)

1 and hence we have

1. We establish further result.

THEOREM

5.6. Let A

Mm,n(lR+) with min(m,n)

2. HmjR(A)

=

2, then mjR+ (A)

2.

Proof.

Suppose that mjR(A) = 2. Then the number of maximal linearly independent columns of A is 2

That is, for any three columns

and ak of A, we have XOi + yaj + ZOk

0 for some x,

R. Since ai, aj and

have nonnegative entries, one of x,

and

is positive while another is negative. Without loss of generality, we may assume that x is positive and the others are negative. Then

0i =

(-yjx)aj + (-Z/X)Ok. Since (-yjx) and (-zjx) are positive,

Oi,Oj

and ak are linearly dependent over R+. Thus three arbitrary columns of A are linearly dependent over R+ and hence mjR+(A) ::; 2.

Using (5), the result follows. 0

Now we see that there exists a matrix A

such that mjR(A) < mjR+ (A) for mjR(A)

3.

EXAMPLE

5.7. Let

[ 110 0]

A= 0 1 1 0

0 0 1 1

1 0 0 1

Then mjR (A)

3 since any three columns of A are linearly independent over R but

+

where

a2,

and

are the columns of A by turns. From Corollary 3.3, we have 4 =

(A) ::; mjR+ (A).

Hence mjR(A) < mjR+ (A).

Using Proposition 2.2, we can obtain a matrix A

such

that mlR(A) < mlR+(A) for min(m,n)

4.

LEMMA 5.8. Let S be a field.

A E Mm,n(S) and rnin(m, n) = k, then ms(A)

k.

Proof In a field, the maximal column rank and the field rank are

the same. So ms(A)

k. 0

Using Theorem 5.6, Example 5.7 and Proposition 2.2, we have the following comparison theorem.

THEOREM 5.9.

F(lR+,R,m,n) ~{ ~ ^{if if min(m,n) min(m, n) =}

^{1 2}

otherwise

Proof Ifmin(m, n)

1, then it is trivial. Suppose that min(m, n) =

2. For any A E Mm;n(R+) with mlR+ (A)

1, it

clear that mlR(A) =

mlR+(A). And we have mlR(A)

2 by Lemma 5.8. Assume mlR+(A) =

2. Then mlR(A)

2. But mlR(A) can be neither 0 nor 1. Thus mlR(A) = 2. Then mlR+(A) = mlR(A) by Theorem 5.6. So this case holds.

Now, let min(m, n) 2: 3. By Theorem 5.6, it suffices to show that for any A E Mm,n(R+) with mlR+(A) = 3, mlR+(A) = mlR(A). Assume that mlR+ (A)

3. Then mlR(A)

3 by (5). But mlR(A) cannot be 0, 1 and 2 by Theorem 5.6. Thus mlR(A)

3.. Thus for any A E Mm,n(R+) with mlR+(A)

3, we have mlR(A) = mlR+(A). Further, Example 5.7 and Proposition 2.2 imply that there exists a matrix A E Mm,n(R+) such that mlR+(A) > mlR(A). Hence we have

F(R+,R,m,n)= 3. 0

Next we show that equality need not hold in (7) and (8).

EXAMPLE 5.10. Let

A

[a _~ 1 a':' 2]

^M2,2(Za)

with a 2: 3. Then mza(A)

1 but mzab(A)

2 for any

2: 2 and

mz(A)

2.

ACKNOWLEDGEMENT.

The author would like to thank Professor Ludwig Elsner for his hospitality while the author was

Bielefeld University, Germany.

References

1. L.B. BeasleyandN.J.Pullman,Nonnegative rank preserving operators, Linear Algebra Appl. 65(1985), 207-223.

2. , Semiring rank and column rank, Linear Algebra Appl. 101 (1988), 33-48.

3. L. B. Beasley, S. J. Kirkland and B. L. Shader, Rank comparisons, Linear Algebra Appl. 221 (1995), 171-188.

4. L. B. Beasley and S.Z.Song, A comparison of nonnegative real ranks and their preservers, Linear Algebra Appl. 31 (1992), 37-46.

5. R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985.

6. 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.

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

8. , Linear operators that preserve column rank of fuzzy matrices, Fuzzy Sets and Systems62 (1994),311-317.

9. S. Z. Song and S. G. Lee, Column ranks and their preservers of general Boolean matrices, J. Korean Math. Soc. 32 (1995),531-540.

Department of Mathematics

Cheju National University

Cheju 690-756, Korea