半線性空間的基與基數(shù)

舒乾宇, 王學平

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

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

1 預(yù)備知識

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

定義1.1設(shè)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設(shè)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設(shè)L=〈L,+,…,0,1〉是半環(huán),稱L上的半模為L-半線性空間.

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

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

其中(x1,x2,…,xn)T表示(x1,x2,…,xn)的轉(zhuǎn)置.對?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設(shè)〈L,+,·,0,1;?;A,+A,oA〉 是L-半線性空間,稱表達式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1)A是左可逆的;

2)A是右可逆的;

3)A是可逆的;

4)AAT是可逆的對角陣;

5)ATA是可逆的對角陣.

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

2 L-半線性空間Vn的基的基數(shù)

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

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

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

證明 充分性設(shè)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中,不同基有相同的基數(shù),則不妨設(shè){x1,x2,…,xn}為Vn的任意一組基.對 ?xi∈ Vn,i∈,設(shè)

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

其中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中,每組基有相同的基數(shù)的充要條件是:任一向量都可以由基唯一的線性表出.

由引理2.2易得推論2.1.

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

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

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

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

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

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

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

證明只需證Vn中任意一組基都含有n個向量.設(shè)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是線性無關(guān)的,顯然有(xk,xk)≠0,其中k∈又U(L)=L{0},從而aikajk=0,其中i,j∈,i≠j,k∈，這就意味著矩陣A的每一行恰好有一個非零元.因此不妨設(shè)

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