Zerosumfree半環上半線性空間的基

羅 琳, 王學平

(四川師范大學 數學與軟件科學學院, 四川 成都 610066)

半環上的矩陣理論應用相當的廣泛,其研究也已有相當長的歷史(參見文獻[1-12]).一方面,展開了半環上矩陣可逆的研究,如:1952年,Luce討論了布爾代數(一類特殊的半環)上的布爾矩陣,并給出布爾矩陣可逆的充要條件是它是一個正交矩陣(見文獻[11]).自此以后,半環上逆矩陣的研究得以迅速展開,如:1963年,D. E. Rutherford[13]給出了布爾矩陣可逆的其他充要條件;1964年,Y. Give’on[14]研究了分配格(一類特殊的半環)上的可逆矩陣;1984年,C. Reatenauer等[7]討論了交換半環上的可逆矩陣.另一方面,Zerosumfree半環上半線性結構的研究也有相當悠久的歷史.1979年,Cuninghame-Green在Min-plus代數上建立了一系列類似于線性代數的理論,如線性方程、特征值問題、線性相關與無關、秩及維數等.之后,許多學者就開始對Zerosumfree半環上的半線性空間進行了深入的研究(可見文獻[15-16]).2007年,Y. J. Tan[9]探討了Antirings(Zerosumfree半環)上矩陣的可逆問題,給出了矩陣為可逆矩陣的一些充要條件;同年,A. Di Nola等應用半環和半模的概念介紹了MV-代數上的半線性空間,同時獲得了類似于經典線性代數中的相關結論(見文獻[8]).但是線性空間中基的一些結論還未得到解決,其中一個就是:是否每個基都具有相同的基數.這個問題在Max-plus代數上已經得到了肯定的回答(見文獻[1]).2010年,S. Zhao等[17-18]給出了并半環(一種特殊的Zerosumfree半環)上基具有相同基數的充要條件.次年,Q. Y. Shu等[19]對Zerosumfree半環進行了深入研究,并給出了半線性空間上基的個數相同的充要條件.在本文中,將進一步研究Zerosumfree半環上n維向量半線性空間中基的個數問題,給出基數都為n的等價條件及基的范圍.

1 預備知識

定義1.1[10,20]設L是一非空集合,如果在L中有2個代數運算+和·滿足:

(i) (L,+,0)是交換幺半群;

(ii) (L,·,1)是幺半群;

(iii)r·(s+t)=r·s+r·t,(s+t)·r=s·r+t·r,?r,s,t∈L;

(iv) 0·r=r·0=0,?r∈L;

(v) 0≠1,

若L中任意的r,r′有r·r′=r′·r,則稱半環=〈L,+,·,0,1,〉為交換半環;若r+r′=0,則一定有r=r′=0稱該半環為Zerosumfree半環.若L中元r滿足對?a,b∈L,r=a+b蘊含r=a或r=b,則稱r為可加既約元.

例1.1設R為實數集,若?a,b∈R∪{-∞}滿足a+b=max{a,b},a·b=a+b(此處的“+”是普通的實數加法),則=〈R∪{-∞},+,·,{-∞},0〉是交換半環.

注1.1半環=〈R∪{-∞},+,·,{-∞},0〉就是通常所指的Max-plus代數(見文獻[15]).

例1.2設M是交換幺半群,若EndM={f:f:M→M滿足f(x+y)=f(x)+f(y),?x,y∈M},?f,g∈EndM,定義運算:

(f+g)(x)=f(x)+g(x),

(f·g)(x)=f(g(x)),

則EndM是交換半環.

例1.3自然數集N對于通常整數間的加法和乘法是交換Zerosumfree半環.

例1.4[0,1]關于運算a+b=max{a,b}和a·b=min{a,b},非負整數關于普通的加法和乘法運算,非負整數集關于運算a+b=g.c.d{a,b}和a·b=l.c.m{a,b}(其中,g.c.d(l.c.m){a,b}代表a與b的最大(或最小)公因子(或公倍數))都是交換Zerosumfree半環.

定義1.2[20]設=〈L,+,·,0,1,〉是一個半環,=〈A,+A,0〉為一個加法交換幺半群.若存在映射*:L×A→A滿足:?r,r′∈L,a,a′∈A,

1) (r·r′)*a=r*(r′*a);

2)r*(a+Aa′)=r*a+Ar*a′;

3) (r+r′)*a=r*a+Ar′*a;

4) 1*a=a;

5) 0*a=r*0A=0A,

則稱為左-半模.右-半模可類似的定義.在此就不累述.

定義1.3[8]設=〈L,+,·,0,1,〉為半環,則稱上的半模為-半線性空間.

注1.2定義1.3中的半模即是指左-半模或右-半模[10].

通常,稱半線性空間的元素為向量;稱半環上的元素為標量(或者系數).前者用黑體表示以區分標量.為方便起見,假設以下均為左-半模.記于是可建立-半線性空間如下:

例1.5設=〈L,+,·,0,1,〉是一個半環,其中(x1,x2,…,xn)T是(x1,x2,…,xn)的轉置,對?x=(x1,x2,…,xn)T,y=(y1,y2,…,yn)T∈Vn(L),r∈L,定義2種運算:

x+y=(x1+y1,x2+y2,…,xn+yn)T,

r*x=(r·x1,r·x2,…,r·xn)T.

0n×1=(0,0,…,0)T.顯然Vn=〈L,+,·,0,1;*;Vn(L),+,0n×1〉是-半線性空間.

定義1.4[8]在半線性空間=〈L,+,·,0,1;*;A,+A,0A〉中,稱下面的表達式

λ1a1+Aλ2a2+A…+Aλnan

定義1.5[8]在-半線性空間,單個向量a是線性無關的.若向量組a1,…,an(n≥2)中任一向量都不能由其余向量線性表出,則稱a1,…,an是線性無關的,否則稱a1,…,an是線性相關的.若無限集合的任意有限子集都是線性無關的,則此無限集合是線性無關的.

注1.3半線性空間或半模上的線性相關和線性無關還有其他定義(見文獻[1-2,10,16]).

若半線性空間的每個元都是其非空子集G中元素的線性組合,則稱G是半線性空間的生成集(見文獻[1]).

定義1.6[10]設為-半線性空間,則稱中線性無關的的生成集為中的基.

例1.6=〈L,+,·,0,1〉為例1.4中最后一個半環.在-半線性空間V2中,向量組和向量組都是V2的基.

λA=(λ·aij)m×n,

則〈Mn(L),+,·,0n,In〉是一個半環,其中

注1.4Mm×n(L)中的置換矩陣,對角矩陣等相關概念都可依照經典線性代數來定義.在此就不贅述.

引理1.1[19]1)-半線性空間Vn中,若僅有1是乘法可逆元,則每個基的基數相同當且僅當1是L中的可加既約元.

定義1.7設=〈L,+,·,0,1,〉是交換Zerosumfree半環,r∈L.若存在{pt∈L:t∈T}?L{0}使得則稱為元r的分解.進一步,若對?t0∈T,?則稱該分解是不可約的.

注1.5在定義1.7中,若|T|<∞,則稱r有|T|個元的有限不可約分解.

例1.7設L=[0,1]2,定義任意(a,b),(c,d)∈L,(a,b)≤(c,d)當且僅當a≤c,b≤d,規定運算:(a,b)+(c,d)=(max{a,c},max{b,d});(a,b)·(c,d)=(min{a,c},min{b,d}).由定義1.7,很容易得到=〈L,+,·,(0,0),(1,1)〉是交換Zerosumfree半環.(1,1)=(1,0)+(0,1),所以(1,1)有不可約有限分解,不難看出(1,1)并無超過2個元素的不可約分解.

例1.8=〈N,+,·,0,1,〉是自然數集Zerosumfree半環.若其運算為例1.4中定義的運算,p1,p2,…,pn是互不相同的素數,則是1的包含n個元素的不可約分解.

例1.9若L是非負整數集,?a,b∈L滿足運算:a+b=g.c.d{a,b};a·b=l.c.m{a,b},則〈L,+,·,0,1〉是一個交換Zerosumfree半環.在V3=〈V3(L),+,03×1〉中,若a+b=1,則(1,0,0)T=(a,0,0)T+(b,0,0)T,所以(1,0,0)T有不可約分解.

易得{e1,e2,…,en}是Vn的一組基,其中

e1=(1,0,…,0),e2=(0,1,…,0),…,

en=(0,0,…,1).

通常稱{e1,e2,…,en}是Vn的一組標準基.

2 半線性空間Vn中的基數

引理2.1若1有t個元素的有限不可約分解,則Vn中存在一組基的基數為nt.

b1=(b1,0,…,0),b2=(b2,0,…,0),…,

bt=(bt,0,…,0),bt+1=(0,b1,…,0),…,

b2t=(0,bt,…,0),…,

b(n-1)t=(0,0,…,b1),…,bnt=(0,0,…,bt).

下面將證明{b1,b2,…,bnt}是Vn的一組基.事實上,

(1)

而{e1,e2,…,en}是Vn的一組標準基,因此任意向量a∈Vn,存在系數λ1,λ2,…,λn∈L,使得

a=λ1e1+λ2e2+…+λnen.

(2)

由(1)與(2)式可以推出:

引理2.2若1有t個元素的有限不可約分解,則1一定含有t-1個元的不可約分解.

引理2.3若1有t個元素的有限不可約分解,則Vn中存在一組基的基數為nt-1.

c=(c,0,…,0),b3=(b2,0,…,0),…,

bt=(bt,0,…,0),bt+1=(0,b1,…,0),…,

b2t=(0,bt,…,0),…,b(n-1)t=(0,0,…,b1),

…,bnt=(0,0,…,bt).

類似于引理2.1的證明,亦可證明c,b3,…,bnt是Vn的一組基.得證.

注2.1k(L)=1當且僅當若1=a+b則有a=1或b=1.

定理2.1如果k(L)=q是有限的,則Vn中基的基數為n到nq中所有的整數.

例2.1考察如上圖所示格L,?x,y∈L,定義x+y=x∨y,x·y=x∧y,其中∨(∧)代表并(交).顯然L={0,a,b,1}不是線性的,且k(L)=2.半線性空間V2=〈L2,+,·,(0,0),(1,1)〉的基有:{(0,1)T,(1,0)T};{(a,0)T,(b,0)T,(1,0)T};{(a,0)T,(b,0)T,(0,a)T,(0,b)T}.

推論2.1設=〈L,+,·,0,1,〉是交換Zerosumfree半環.若k(L)=+∞,則對每一個自然數m≥n,Vn都有一組基的基數為m.

e1=(1,0,…,0,0),e2=(0,1,…,0,0),…,

en-1=(0,0,…,1,0),b1=(0,0,…,0,b1),

b2=(0,0,…,0,b2),…,

bt=(0,0,…,0,bt),bt+1=(0,0,…,0,c).

綜上,e1,e2,…,en-1,b1,…,bt+1是Vn的一組基,基數為t+1,定理得證.

下面將繼續研究半線性空間Vn的基數是唯一確定的充分必要條件.

定義2.1[19]設r,a,b∈L,若r=a+b蘊含r=a或r=b，則稱r是半環中的可加既約元.

定理2.2在半線性空間Vn中,下面的條件是等價的:

1) 1是可加既約元;

2)Vn中每個向量可唯一的線性表出;

3)Vn中每個單位向量可被唯一的線性表出;

4)k(L)=1;

5) 每組基都有相同的基數.

證明1)?5),2)?5)可見證明[19].由k(L)的定義可知4)?1),顯然3)?2)所以此定理成立.

注2.2由定理2.2可以得到:

1) 若1∈L是并既約元,則半線性空間Vn的基的基數為n;

2) 若L是線性完備格,則半線性空間Vn的基的基數為n;

3) 若L是完備格,k(L)=q,則Vn中的基的基數為n到nq中的整數.

[1] Cuninghame-Green R A, Butovic P. Bases in max-algebra[J]. Linear Algebra Appl,2004,389:107-120.

[2] Gregory D A, Pullman N J. Semiring rank: Boolean rank and nonnegative rank factorization[J]. J Combin Info Syst Sci,1983,8(3):223-233.

[3] Ghosh S. Matrices over semirings[J]. Information and Sciences,1996,90:221-230.

[4] Beasley L B, Lee S G. Linear operations strongly preservingr-potent matrices over semirings[J]. Linear Algebra Appl,1992,162/163/164:589-599.

[5] Minoux M. Bideterminants arborescences and extension of the matrix-tree theorem to semirings[J]. Discrete Math,1997,171:191-200.

[6] Poplin P L, Hartwig R E. Determinantal identities over commutative semirings[J]. Linear Algebra Appl,2004,378:99-132.

[7] Reutenauer C, Straubing H. Inversions of matrices over a commutative semiring[J]. J Algebra,1984,88:350-360.

[8] Di Nola A, Lettieri A, Perfilieva I, et al. Algebraic analysis of fuzzy systems[J]. Fuzzy Sets and Systems,2007,158:1-22.

[9] Tan Y J. On invertible matrices over antirings[J]. Linear Algebra Appl,2007,423:428-444.

[10] Golan J S. Semirings and Their Applications[M]. Dordrecht:Kluwer Academic Publishers,1999.

[11] Baccelli F, Mairesse J. Ergodic theorems for stochastic operators and discrete event networks[C]//Gunawardena J. Idempotency. Cambridge:Cambridge University Press,1998,11:171-208.

[12] Gondran M, Minoux M. Dioids and semirings: links to fuzzy sets and other applications[J]. Fuzzy Sets and Systems,2007,158:1273-1294.

[13] Rutherford D E. Inverses of Boolean matrices[J]. Proceedings of the Glasgow Mathematical Association,1963,6:49-53.

[14] Give’on Y. Lattice matrices[J]. Inform Control,1964,7:477-484.

[15] Butkovic P. Max-algebra: the linear algebra of combinatorics[J]. Linear Algebra Appl,2003,367:313-335.

[17] Zhao S, Wang X P. Invertible matrices and semilinear spaces over commutative semirings[J]. Information Sciences,2010,180:5115-5124.

[18] Zhao S, Wang X P. Bases in semilinear spaces over join-semiring[J]. Fuzzy Sets and Systems,2011,182:93-100.

[19] Shu Q Y, Wang X P. Bases in semilinear spaces over Zerosumfree semirings[J]. Linear Algebra Appl,2011,435:2681-2692.

[20] Zimmermann U. Linear and combinatorial optimization in ordered algebraic structures[C]//Annals of Discrete Mathematices. Amsterdam:North-Holland,1981:10.