舒乾宇, 王學平

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

研究半環(huán)上的半線性結構已經有很長的歷史.1979年,R.A.Cuninghame-Green等[1]在 minplus代數中構建了類似于線性代數的一系列理論:線性方程系統(tǒng)、特征值問題、向量組的線性相關性與線性無關性、秩與維數等.1985年,P.Butkoviˇc等[2]引用線性相關與線性無關以及向量組的秩等經典線性代數中的概念來討論強正則矩陣的相關性質.隨后研究者們將這些理論應用到相應的領域,比如選址問題[3]、控制系統(tǒng)問題[4-5]、分離事件系統(tǒng)[6]以及一些代數基本問題[7-14].而隨后P.Butkoviˇc[15-16]和K.Cechl rov 等[17]則將線性相關與線性無關、特征值、線性方程的求解等相關的定義和結論類似的引入到max-plus代數中.而在2004年,R.A.Cuninghame-Green等[18]在max-plus代數中證明當空間是有限生成時,該空間有基且每組基的基數相等,最后給出在有限生成的空間中求基的方法.在2007年,A.Di Nola等[19]在MV-代數上建立半線性空間,引入向量組的線性相關、線性無關及基的概念,并解決了相應線性方程組有解的充要條件等問題.同時也提出一些公開問題:在半線性空間中,不同基的基數是否相等的問題,線性無關的向量組能否擴張成基的問題等.2010年,S.Zhao等[20]在join-半環(huán)中給出不同基的基數相等的充要條件,而Q.Y.Shu等[21]則在交換的零和自由半環(huán)上給出不同基有相同基數的一些充要條件.本文將主要討論一些零和自由半環(huán)上,半線性空間基的一些性質,首先證明半線性空間中不同基有相同基數的充要條件,然后在一類特殊的零和自由半環(huán)上證明在其對應的半線性空間中,不同基有相同基數.

1 預備知識

以下假定讀者對半環(huán)及半環(huán)中一些基本概念和符號已經熟悉[22],僅給出文中常用的一些基本概念.

定義1.1設L=〈L,+,·,0,1〉為半環(huán).若對 ?r,r′∈L,都有r·r′=r′·r,則稱 L 為交換半環(huán).若a+b=0蘊含a=b=0,?a,b∈L,則稱半環(huán)L是零和自由的.

定義1.2設L=〈L,+,·,0,1〉為半環(huán),a=(A,+A,oA)為一個加法交換幺半群.若外積?:L×A→A滿足對?r,r′∈L和a,a′∈A都有

(i)(r·r′)?a=r·(r′?a);

(ii)r?(a+Aa′)=r?a+Ar?a′;

(iii)(r+r′)?a=r?a+Ar′?a;

(iv)1?a=a;

(v)o?a=r?oA=oA,

則稱〈L,+,·,0,1;?;A,+A,oA〉 為左L- 半模.類似地,還可以定義右L-半模,其中外積的定義為A×L→A.

后面的定義是對文獻[1]中定義的半線性空間的一種推廣.

定義1.3設L=〈L,+,…,0,1〉是半環(huán),稱L上的半模為L-半線性空間.

注意,在定義1.3中,半模即是指左L-半模.方便起見,以下令表示集合{1,2,·s,n},其中n是任意正整數.

例 1設L=〈L,+,·,0,1〉是半環(huán),對n≥1,令

其中(x1,x2,…,xn)T表示(x1,x2,…,xn)的轉置.對?x= (x1,x2,…,xn)T,y= (y1,y2,…,yn)T∈Vn(L)和r∈L,定義運算為

則 Vn= 〈L,+,·,0,1;?;Vn(L),+,on×1〉 為 L-半線性空間,其中on×1=(0,0,…,0)T.也稱 Vn為半環(huán)L上的n維向量空間.

為方便起見,下面在不會引起混淆的情況下,在L-半線性空間〈L,+,·,0,1;?;A,+A,oA〉中,將用ra來代替r?a,其中?r∈L,a∈A.

定義 1.4設〈L,+,·,0,1;?;A,+A,oA〉 是L-半線性空間,稱表達式

為A中向量組a1,…,an的線性組合,其中λ1,λ2,…,λn∈L為標量(也稱系數).若向量x能表示成向量組a1,a2,…,an的線性組合,則稱向量x能被向量組a1,a2,…,an線性表出或線性表示.

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

注意到,半線性空間或半模中相應的線性相關和線性無關的概念曾被許多學者研究過[2,19,22,24-25].

設S是L-半線性空間的一個非空子集,若L-半線性空間中的任意向量都能表由集合S中的向量線性表出,則稱S是L-半線性空間的一個生成集[19].令S表示L-半線性空間a的生成集,則可記作a= 〈S〉.特別地,若S={a1,…,ap},則記作a= 〈a1,…,ap〉.

定義1.6[22]稱L-半線性空間a中線性無關的生成集為a的基.

定義1.7[21]在L-半線性空間a中,若每一組基都有相同的基數,則稱每組基的基數為a的維數,記作dim(a).

設矩陣A∈Mn(L),令P表示集合{1,2,…,n}上的所有置換.定義矩陣A的行列式,記作Det(A).

由以上定義易知Det(A)=Det(AT).

定義1.8設向量x=(x1,x2,…,xn)T,y=(y1,y2,…,yn)T∈Vn,則x和y的內積記作(x,y),等于它們對應分量乘積的和

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

定義1.9在半環(huán)L=〈L,+,·,0,1〉中,設a∈L,若存在b∈L使得ab=ba=1,則稱元素a是可逆的,b為a的逆元,記作a-1.用U(L)表示半環(huán)L中所有可逆元構成的集合.

定義1.10矩陣A∈Mn(L)稱為左可逆(或右可逆)的,如果存在矩陣B∈Mn(L)使得AB=In(或BA=In).若矩陣A既是左可逆的又是右可逆的,則稱它是可逆的.

自現在起,都假設L=〈L,+,·,0,1〉是交換的零和自由半環(huán).

引理 1.1[26]設A,B∈Mn(L),若存在k∈使得對?j∈都有ajk=0,那么Det(A)=0.

引理1.2[27]設A∈Mn(L),則下列條件等價.

1)A是左可逆的;

2)A是右可逆的;

3)A是可逆的;

4)AAT是可逆的對角陣;

5)ATA是可逆的對角陣.

引理1.3[27]設矩陣A,B∈Mn(L),若A是可逆的,則有 Det(AB)=Det(A)·Det(B)和Det(BA)=Det(B)·Det(A)都成立.

2 L-半線性空間Vn的基的基數

顯然向量組e1,e2,…,en是L-半線性空間Vn的一組基,其中

稱e1,e2,…,en為Vn的標準基[20].

引理2.1在L-半線性空間Vn中,不同的基有相同的基數的充要條件是:任何一個基中的向量都可以由其所在的基唯一線性表出.

證明 充分性設x1,x2,…,xs是Vn的任意一組基,由已知有?xi,i∈,都可由x1,x2,…,xs唯一的線性表出.只需證n=s.若n≠s,則必有n

因此

又由已知,任何一個基中的向量都可以由其所在的基唯一線性表出,可知AB=Is.由于s>n,則將矩陣A補上s-n列O,而將矩陣B補上s-n行O,使之都變成方陣,則有

一方面,由引理1.2知方陣(AO)和(B)都是可逆矩陣,另一方面,兩邊取行列式,由引理1.1和1.3知

矛盾.同理,也可由s

必要性若L-半線性空間Vn中,不同基有相同的基數,則不妨設{x1,x2,…,xn}為Vn的任意一組基.對 ?xi∈ Vn,i∈,設

其中ri∈L,i∈.由充分性的證明,不妨設

其中C,D∈Mn(L),則有

因此DC=In,也就是說,D是可逆矩陣.從而

因此D(r1,…,ri,…,rn)T=D(0,…,1,…,0)T.而D是可逆的,即(r1,…,ri,…,rn)T=(0,…,1,…,0)T,也就是說,任一向量xi都能被其所在基{x1,x2,…,xn}唯一的線性表出.

引理2.2[21]在L-半線性空間Vn中,每組基有相同的基數的充要條件是:任一向量都可以由基唯一的線性表出.

由引理2.2易得推論2.1.

推論2.1[23]在L-半線性空間Vn中,下列條件等價:

(1)每組基有相同的基數;

(2)任一向量都可以由基唯一的線性表出;

(3)任何一個基中的向量都可以由其所在的基唯一線性表出.

顯然定理2.1是對引理2.1的改進.

從定理2.1前的例子可以看出,并不是所有的零和自由半環(huán)上的半線性空間Vn中不同基都有相同的基數,下面將給出一種特殊的零和自由半環(huán),使得其對應的半線性空間Vn中不同基有相同的基數.

定理2.2若U(L)=L{0},則dim(Vn)=n.

證明只需證Vn中任意一組基都含有n個向量.設x1,x2,…,xs是Vn的任意一組基,若n≠s,則要么n>s,要么ns,由于{x1,x2,…,xs}是Vn的一組基,因此?ei,i∈都能表示成向量組x1,x2,…,xs的線性組合,即由定義1.4知,存在元素aij∈L使得,從而有

從而BA=In.由于n>s,將矩陣A補上n-s行O,而將矩陣B補上n-s列O,使之都變成方陣,則有

矛盾.若n

從而由L是零和自由的,有aikajt(xk,xt)=0,其中i,j∈,i≠j,k,t∈.特別地,aikajk(xk,xk)=0,其中i,j∈,i≠j,k∈.另一方面,由向量組x1,x2,…,xs是線性無關的,顯然有(xk,xk)≠0,其中k∈又U(L)=L{0},從而aikajk=0,其中i,j∈,i≠j,k∈，這就意味著矩陣A的每一行恰好有一個非零元.因此不妨設

因為半環(huán)L是零和自由的,所以由(5)式可知aikkbkt=0,t≠ik,k∈從而由(4)式有bkt=0,t≠ik,k∈,即矩陣B的每一列至多有一個非零元.而由x1,x2,…,xs線性無關可知矩陣B的每一列都有一個非零元.又由n

由定理2.2的證明可得出推論2.2.

推論2.2若U(L)=L{0},則向量集{a1,a2,…,an}是L-半線性空間Vn的一組基當且僅當

其中,對 ?i∈,都有aii≠ 0.

[1]Cuninghame-Green R A,Minimax A.Minimax Algebra(Lecture Notes in Economics and Mathematical Systems)[M].Berlin:Springer-Verlag,1979.

[2]Butkoviˇc P,Hevery F.A condition for the strong regularity of matrices in the minimax algebra[J].Discrete Appl Math,1985,15:133-155.

[3]Francis R L,McGinnis L F,White J A.Locational analysis[J].European J Oper Res,1983,12:220-252.

[4]Carré B A.Graphs and Networks[M].Oxford:Oxford University Press,1979.

[5]Karp R M.A characterization of the minimum cycle mean in a digraph[J].Discrete Math,1978,23:309-311.

[6]Cuninghame-Green R A,Huisman F.Convergence problems in minimax algebra[J].J Math Anal Appl,1982,88:196-203.

[7]Butkoviˇc P,Cuninghame-Green R A.On the regularity of matrices in min-algebra[J].Linear Algebra and Its Applications,1991,145:127-139.

[8]Perfilieva I.Fuzzy function as an approximate solution to a system of fuzzy relation equations[J].Fuzzy Sets and Systems,2004,147:363-383.

[9]Perfilieva I.Semi-linear spaces[C]//Noguchi H,Ishii H,et al.Proc of Seventh Czech-Japanese Seminar on Data Analysis and Decision Making under Uncertainty.Hyogo:Japan,2004:127-130.

[10]Perfilieva I,Novàk V.System of fuzzy relation equations as a continuous model of if-then rules[J].Information Sciences,2007,177:3218-3227.

[11]Perfilieva I,Noskov L.System of fuzzy relation equations with inf- → composition:complete set of solutions[J].Fuzzy Sets and Systems,2008,159:2256-2271.

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

[13]Gondran M,Minoux M.Graphs,Dioids and Semirings[M].New York:Springer-Verlag,2008.

[14]熊清泉,舒乾宇.完備格上區(qū)間值t-半模及其R-蘊含算子[J].四川師范大學:自然科學版,2013,36(2):165-171.

[15]Butkoviˇc P.Simple image set of(max,+)linear mappings[J].Discrete Appl Math,2000,105:73-86.

[16]Butkoviˇc P.Max-algebra:the linear algebra of combinatorics[J].Linear Algebra and Its Applications,2003,367:313-335.

[17]Cechl rov K,Cuninghame-Green R A.Soluble approximation of linear systems in max-plus algebra[J].Kybernetika(Prague),2003,39:137-141.

[18]Cuninghame-Green R A,Butkoviˇc P.Bases in max-algebra[J].Linear Algebra and Its Applications,2004,389:107-120.

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

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

[21]Shu Q Y,Wang X P.Bases in semilinear spaces over zerosumfree semirings[J].Linear Algebra and Its Applications,2011,435:2681-2692.

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

[23]Zimmermannn U.Linear and Combinatorial Optimization in Ordered Algebraic Structures[M].Amsterdamn:North-Holland Press,1981.

[24]Gondran M,Minoux M.Linear algebra in dio?ds:a survey of recent results[J].Ann Discrete Math,1984,19:147-164.

[25]Cechl rov K,Pl vka J.Linear independence in bottleneck algebras[J].Fuzzy Sets and Systems,1996,77:337-348.

[26]Poplin P L,Hartwig R E.Determinantal identities over commutative semirings[J].Linear Algebra and Its Applications,2007,387:99-132.

[27]Tan Y J.On invertible matrices over antirings[J].Linear Algebra and Its Applications,2007,432:428-444.