零和自由半環(huán)上的半可逆矩陣

龍艷華, 王學(xué)平

(1. 成都大學(xué) 師范學(xué)院, 四川 成都 610106； 2. 四川師范大學(xué) 數(shù)學(xué)與軟件科學(xué)學(xué)院, 四川 成都 610066)

零和自由半環(huán)上的半可逆矩陣

龍艷華1, 王學(xué)平2*

(1. 成都大學(xué) 師范學(xué)院, 四川 成都 610106； 2. 四川師范大學(xué) 數(shù)學(xué)與軟件科學(xué)學(xué)院, 四川 成都 610066)

在零和自由半環(huán)上,舉例說明矩陣方程組AX=B和X+A1B=A2B并不是在所有情況下都同解,其中A是已知的n×n階半可逆矩陣,X是未知的n維列向量,A1和A2分別滿足條件I+AA1=AA2和I+A1A=A2A.得到關(guān)于方程AX=B和X+A1B=A2B同解的一些條件,完善零和自由半環(huán)上半可逆矩陣的相關(guān)性質(zhì),擴(kuò)展矩陣的應(yīng)用范圍.

零和自由半環(huán); 交換半環(huán); 半可逆矩陣; 線性方程組； 方程組的解

1 基本概念及預(yù)備知識(shí)

矩陣是重要的數(shù)學(xué)工具,在信息理論、不確定信息處理、圖像處理、計(jì)算智能和群體決策等方面有著廣泛應(yīng)用,如文獻(xiàn)[1-9].半環(huán)上的矩陣?yán)碚撘苍谧顑?yōu)化理論、運(yùn)籌學(xué)、自動(dòng)化控制、離散事件網(wǎng)絡(luò)與圖論的模型方面有許多應(yīng)用,如文獻(xiàn)[5,10-15]，其中,半環(huán)上的可逆矩陣是一類重要的矩陣.1952年,R. D. Luce[16]討論了布爾代數(shù)(一種特殊的半環(huán))上的布爾矩陣,證明了矩陣可逆當(dāng)且僅當(dāng)它是一個(gè)正交矩陣[15].從此以后,半環(huán)上可逆矩陣的理論便得到了廣泛研究,如文獻(xiàn)[4,17-18].特別地,Zhao C.K.[19]得到了在Brouwer格上矩陣可逆的必要條件和充分條件,Han S.C.等[20]給出了坡矩陣可逆的一些充分必要條件,Tan Y.J.[21]考慮了交換零和自由半環(huán)(亦稱為反環(huán)[21])上的可逆矩陣,得到了矩陣可逆的一些充要條件等.事實(shí)上,max-plus代數(shù)、min-max代數(shù)、完備Brouwer格、模糊代數(shù)、坡代數(shù)和瓶頸代數(shù)等都是特殊半環(huán),如文獻(xiàn)[2,6,22-23].可逆矩陣是一種重要的矩陣,很多學(xué)者研究了各種半環(huán)上的可逆矩陣.

眾所周知,經(jīng)典線性代數(shù)中可逆矩陣對(duì)矩陣方程的求解非常有用.文獻(xiàn)[24]研究發(fā)現(xiàn)在交換的零和自由半環(huán)和零除子自由半環(huán)上,可逆矩陣是非常稀疏的.文獻(xiàn)[25]給出了半可逆的概念,并得到半可逆矩陣的一些性質(zhì),得到了矩陣半可逆的必要條件和充分條件.利用這個(gè)結(jié)論,通過對(duì)矩陣方程X+A1B=A2B的討論,從而研究了矩陣方程AX=B的解的問題.其中,A是已知的n×n階半可逆矩陣,X是未知的n維列向量,A1和A2分別滿足I+AA1=AA2和I+A1A=A2A.然而經(jīng)過討論,發(fā)現(xiàn)方程AX=B和X+A1B=A2B并不是在任何情況下解都相同.

為此,本文將圍繞矩陣的半可逆展開詳細(xì)討論,在交換的零和自由半環(huán)上,研究矩陣方程AX=B和X+A1B=A2B在滿足何種條件下才是同解的.首先給出了半可逆的定義及一些相關(guān)性質(zhì),舉出方程組AX=B和X+A1B=A2B不同解的反例,同時(shí)得到方程同解的一些條件和矩陣可逆的性質(zhì),進(jìn)一步概括并完善了半可逆矩陣的性質(zhì)及其應(yīng)用.

下面給出一些定義和已知引理.為了方便起見,用n代替集合{1,2,…,n},其中n是正整數(shù).

定義 1.1[12]設(shè)R是一個(gè)非空集合,若在R中存在2個(gè)代數(shù)運(yùn)算“+”和“·”,使得:

(i) (R,+,0)是一個(gè)交換幺半群；

(ii) (R,·,1)一個(gè)幺半群；

(iii) 任意r,s,t∈R,r·(s+t)=r·s+r·t,(s+t)·r=s·r+t·r；

(iv) 任意r∈R,0·r=r·0=0；

(v) 0≠1，

則稱R=〈R,+,·,0,1,〉為半環(huán).如果對(duì)任意r,r′∈R,都有r·r′=r′·r成立,那么稱半環(huán)R是交換的.

例 1.1 設(shè)(R,+,0)是交換幺半群,若R={f:R→R,對(duì)任意a,b∈R,都有f(a+b)=f(a)+f(b)},對(duì)任意a∈R,f,g∈R,定義運(yùn)算：

(f+g)(a)=f(a)+g(a),(f·g)(a)=f(g(a)),

則R是交換半環(huán).

設(shè)R=〈R,+,·,0,1,〉是半環(huán),若對(duì)任意a,b∈R,a+b=0蘊(yùn)含a=b=0,則稱半環(huán)R是零和自由的.如果對(duì)任意a∈R,存在b∈R使得ab=ba=1,則稱b是a的逆.容易證明,半環(huán)上a的逆元是唯一的.用U(R)表示半環(huán)R上所有可逆元的集合.若對(duì)任意a∈R都有a∈U(R),則稱半環(huán)R是半域.

例 1.2 設(shè)R是實(shí)數(shù)集,若對(duì)任意a,b∈R∪{-∞},都有

a+Rb=max{a,b},a·b=a+b

成立,其中“+”表示普通的加法,則R=〈R∪{-∞},+R,·,{-∞},0〉是交換的零和自由半環(huán).

例 1.3 1) 設(shè)N是所有自然數(shù)構(gòu)成的集合,“+”、“·”分別表示普通的加法和乘法運(yùn)算,則R=〈N,+,·,0,1,〉是一個(gè)交換的零和自由半環(huán)；

2) 模糊代數(shù)([0,1],max,min)是交換的零和自由半環(huán)；

設(shè)R=〈R,+,·,0,1,〉是半環(huán),用Mm×n(R)表示R上所有m×n階矩陣的集合.特別地,用Mn(R)表示半環(huán)R上所有n階方陣的集合,用Vn(R)表示R中所有n維列向量的集合.明顯地,Vn(R)=Mm×1(R).設(shè)A=(aij)∈Mn×m(R),用AT=(aij)m×n表示A的轉(zhuǎn)置.設(shè)

定義 1.2[5,26]設(shè)A∈Mn(R)且An(或SnAn)為{1,2,…,n}的偶(或奇)置換集合.矩陣A的雙行列式|A|是一個(gè)序?qū)A|=(|A|+,|A|-),

其中

且

對(duì)任意i,j∈n,用Aij∈Mn-1(R)表示矩陣A刪去第i行和第j列后的余子式.特別地,分別稱|Aij|+和|Aij|-為矩陣A的正,負(fù)余子式[13],則

或

(1)

其中,

2 半可逆的基本定義和反例

下面給出零和自由半環(huán)上半可逆矩陣的一些基本定義和反例.

定義 2.1[12]設(shè)R=〈R,+,·,0,1,〉是半環(huán),若對(duì)任意a,b∈R,ab=0蘊(yùn)含a=0或b=0,則稱半環(huán)R是零除子自由的,也稱半環(huán)為整的.

引理 2.1[25]設(shè)A=(aij)∈Mn(R),則對(duì)任意r≠t,

引理 2.2[25]設(shè)A∈Mn(R)是可逆的,則|A|+≠|(zhì)A|-.

定義 2.2[25]設(shè)R為零和自由半環(huán),若對(duì)任意a≠0∈R都存在r,s∈R使得1+ra=sa,則稱半環(huán)R滿足條件(C).

定義 2.3[25]設(shè)R為零和自由半環(huán),若對(duì)任意a≠b,a,b∈R都存在r,s∈R使得1+ra+sb=sa+rb,則稱半環(huán)R滿足條件(D).

明顯地,若半環(huán)滿足條件(D),則一定滿足條件(C).反之,如果半環(huán)滿足條件(C),則不一定滿足條件(D)(參見文獻(xiàn)[25]中的例2.3).

注 1 設(shè)半環(huán)R滿足條件(D)且A∈Mn(R),若|A|+≠|(zhì)A|-,則矩陣A是半可逆的.

定義 2.4[25]設(shè)A∈Mn(R),若存在A1,A2∈Mn(R)使得I+AA1=AA2且I+A1A=A2A,則稱矩陣A是半可逆的.

引理 2.3[25]設(shè)半環(huán)R滿足條件(D)且A∈Mn(R),若|A|+≠|(zhì)A|-,則矩陣A是半可逆的.

以下例子主要說明:設(shè)A∈Mn(R),當(dāng)I+AA1=AA2且I+A1A=A2A時(shí),方程組AX=B和X+A1B=A2B不同解,其中A1,A2∈Mn(R).

1+35r+28s=28r+35s

(2)

成立.因?yàn)榘氕h(huán)R滿足條件(D)且滿足I+B1A=B2A,所以X+B1AX=B2AX,即

X+B1B=B2B.

(3)

3 方程組AX=B與X+A1B=A2B同解的條件

在半環(huán)R=〈R,+,·,0,1〉上討論方程組AX=B與X+A1B=A2B同解的條件.

分別定義矩陣A的A+和A-[18]如下：

(4)

引理 3.1[18]A+A=Aδ++C,A-A=Aδ-+C,其中Aδ+和Aδ-分別是對(duì)角線上元素為|A|+和|A|-的對(duì)角矩陣.

且

同時(shí)有

命題 3.1 設(shè)A∈Mn(R),若1+|A|+=|A|-,則A是半可逆的.

類似命題3.1可以證明以下條件成立.

命題 3.2 設(shè)A∈Mn(R),若1+|A|-=|A|+,則A是半可逆的.

定義 3.1[12]設(shè)R是半環(huán),若ZR={x∈R:x+z=z,對(duì)任意z∈R},則稱ZR是零化的.如果R=ZR,那么稱R是零化半環(huán).

定義 3.2[27]設(shè)R是半環(huán),對(duì)任意a,b,c∈R,若a+c=b+c都有a=b,則稱R是加法可消的.

命題 3.3[25]設(shè)R是半環(huán)且滿足條件(D),則R要么加法可消要么零化.

下文假定B1=rA++sA-,B2=sA++rA-,αij=|Aji|(+),βij=|Aji|(-),A+=(αij)且A-=(βij),其中r,s∈R.

命題 3.4 設(shè)R是半環(huán)且滿足條件(D),A∈Mn(R),若|A|+≠|(zhì)A|-,則以下2個(gè)結(jié)論成立:

(i) 若R是加法可消的,則r≠s;

(ii) 若r=s,則R是零化的.

證明 由引理2.3知A是半可逆的.由定義2.4知,存在A1,A2∈Mn(R)使得I+AA1=AA2和I+A1A=A2A成立.特別地,由文獻(xiàn)[25]中命題2.10的證明可以得到I+AB1=AB2,I+B1A=B2A.以下設(shè)B1A=(Cij)n×n,即有:

(i) 設(shè)R是加法可消的,若r=s,則B1=B2=rA++rA-,再由I+B1A=B2A可以推出I+(Cij)n×n=(Cij)n×n,即1+Cii=Cii,其中i=1,2,…,n,又因?yàn)镽是加法可消的,即有1=0,矛盾,因此r≠s.

(ii) 類似(i)中證明可知:若r=s,則1+Cii=Cii,其中i=1,2,…,n,也就是說1∈Zr,故對(duì)任意x∈R,都有x+Ciix=Ciix,即R?Zr,又因?yàn)镽?Zr,所以R=Zr.

然而,命題3.4的逆命題一般不成立,如例3.2所示.

注 2 設(shè)R是零化半環(huán)且滿足條件(D),A∈Mn(R),|A|-≠|(zhì)A|+,r,s∈R且r≠s,然而,方程組AX=B和X+B1B=B2B不一定同解(見例3.2).

1+4r+35s=35r+4s

(5)

成立.因?yàn)榘氕h(huán)R滿足條件(D),再由I+B1A=B2A可推得X+B1AX=B2AX,即有

X+B1B=B2B

(6)

成立.由(1)和(4)式可以推出

命題 3.5 設(shè)R是加法可消半環(huán),A∈Mn(R),如果I+AA1=AA2且I+A1A=A2A,那么方程組AX=B和X+A1B=A2B同解.

證明 若存在A1,A2∈Mn(R)使得I+AA1=AA2和I+A1A=A2A都成立,則對(duì)任意X∈Mn×l(R)都有X+A1AX=A2AX,因此,由AX=B可得X+A1B=A2B.

反之,設(shè)X滿足方程X+A1B=A2B,則由I+AA1=AA2知AX+AA1B=AA2B=(I+AA1)B=B+AA1B,即有AX+AA1B=B+AA1B,又因?yàn)镽是加法可消的,所以AX=B.

利用命題3.1，3.2和3.5可以推出：

推理 3.1 設(shè)R是加法可消半環(huán),A∈Mn(R),若1+|A|+=|A|-或1+|A|-=|A|+成立,則方程組AX=B與X+A+B=A-B同解.

應(yīng)該注意的是：一般來說,即使半環(huán)R是零化的,方程組AX=B和X+A1B=A2B也不一定同解,其中I+AA1=AA2,I+A1A=A2A(參見例2.1).

例 3.3 設(shè)R=(N,+,·)是加法可消半環(huán),N為自然數(shù),“+”、“·”分別表示普通的加法和乘法運(yùn)算，求:2x+z=7,3y+5z=15,x+y+2z=8,其中x,y,z∈N.

解 設(shè)

則有AX=B.

由推論3.1知|A|+=12≠13=|A|-,即A是半可逆的,因此再由定義2.4知,存在A1,A2∈Mn(R)使得I+AA1=AA2和I+A1A=A2A恒成立.特別地,由命題3.1的證明可以得到I+AB1=AB2,I+B1A=B2A,其中B1=A+,B2=A-.由I+A+A=A-A知X+A+AX=A-AX,即有

X+A+B=A-B.

(7)

解 設(shè)

則有AX=B.由推論3.1知|A|+=9,|A|-=3,|A|+≠|(zhì)A|-,則A是半可逆的.特別地,由文獻(xiàn)[25]中命題2.10的證明可以得到:I+AB1=AB2且I+B1A=B2A,其中B1=rA++sA-,B2=sA++rA-,r,s∈R,并有

1+9r+3s=3r+9s

(8)

成立.

又因?yàn)榘氕h(huán)R滿足條件(D)且I+A1A=A2A,所以X+A1AX=A2AX,即

X+A1B=A2B.

(9)

故有

[1] BROUWER R K. A method of relational fuzzy clustering based on producing feature vectors using fast map[J]. Info Sci,2009,179(20):3561-3582.

[2] CAO Z Q, KIM K H, ROUSH F W. Incline Algebra and Applications[M]. New York:Ellis Horwood,1984.

[3] GHAZINOORY S, ESMAIL ZADEH A, KHEIRKHAH A S. Application of fuzzy calculations for improving portfolio matrices[J]. Info Sci,2010,180(9):1582-1590.

[4] GIVE’ON Y. Lattice matrices[J]. Info Control,1964,7(4):477-484.

[5] GONDRAN M, MINOUX M. Graphs Dio?ds and Semirings[M]. New York:Springer-Verlag,2008.

[6] KIM K H, ROUSH F W. Generalized fuzzy matrices[J]. Fuzzy Sets and Systems,1980,4(3):293-315.

[7] NOBUHARA H, TRIEU D B K, MARUYAMA T, et al. Max-plus algebra-based wavelet transforms and their FPGA implementation for image coding[J]. Info Sci,2010,180(17):3232-3247.

[8] XU Z. A method based on distance measure for interval-valued intuitionistic fuzzy group decision making[J]. Info Sci,2010,180(1):181-190.

[9] ZHAO X Z, JUN Y B, REN F. The semiring of matrices over a finite chain[J]. Info Sci,2008,178(17):3443-3450.

[10] BACCELLI F L, MAIRESSE I. Ergodic theorems for stochastic operators and discrete event networks[J]. Idempotency,1995,11:171-208.

[11] CUNINGHAME-GREEN R A. Minimax Algebra, Lecture Notes in Economics and Mathematical Systems[M]. Berlin:Springer-Verlag,1979.

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

[13] GONDRAN M, MINOUX M. Linear algebra in dioids:a survey of recent results[J]. North-Holland Mathematics Studies,1984,95(8):147-163.

[14] GONDRAN M, MINOUX M. Dioids and semirings:links to fuzzy sets and other applications[J]. Fuzzy Sets and Systems,2007,158(12):1273-1294.

[15] ZIMMERMANN U. Linear and combinatorial optimization in ordered algebraic structures[J]. Bull Am Math Soc,1985,12(1):148-150.

[16] LUCE R D. A note on Boolean matrix theory[J]. Proc Am Math Society,1952,3(3):382-388.

[17] RUTHERFORD D E. Inverses of Boolean matrices[J]. Proc Glasgow Math Association,1963,6(1):49-53.

[18] REUTENAUER C, STRAUBING H. Inversion of matrices over a commutative semiring[J]. J Algebra,1984,88(2):350-360.

[19] ZHAO C K. Inverses of L-fuzzy matrices[J]. Fuzzy Sets and Systems,1990,34(1):103-116.

[20] HAN S C, LI H X. Invertible incline matrices and Cramer’s rule over inclines[J]. Lin Alg Appl,2004,389(1):121-138.

[21] TAN Y J. On invertible matrices over antirings[J]. Lin Alg Appl,2007,423(2):428-444.

[23] CUNINGHAME-GREEN R A, BUTKOVIC P. Bases in max-algebra[J]. Lin Alg Appl,2004,389(1):107-120.

[24] BEASLEY L R B, PULLMAN N J. Linlnear operators strongly preserving idem, pot, ent matrices over semirings[J]. Lin Alg Appl,1988,99(99):199-216.

[25] GHOSH S. Matrices over semirings[J]. Info Sci,1995,90(1/4):221-230.

[26] PERFILIEVA I, KUPKA J. Kronecker-Capelli Theorem in Semilinear Spaces[M]. Computational Intelligence:Foundations and Applications,2015:43-51.

[27] WEINERT H J. über Halbringe and Halbk?rper Ⅲ[J]. Acta Mathematica Hungarica,1964,15(1):177-194.

2010 MSC： 06B15; 06D05; 03E72

(編輯 陶志寧)

Semi-invertible Matrices over Zero-sum-free Semirings

LONG Yanhua1, WANG Xueping2

(1.CollegeofTeachers,ChengduUniversity,Chengdu610016,Sichuan; 2.CollegeofMathematicsandSoftwareScience,SichuanNormalUniversity,Chengdu610066,Sichuan)

Over zero-sum-free semirings, we give an example to show that matrix equationsAX=BandX+A1B=A2Bdo not always have the same solutions, whereAis a knownn×nsemi-invertible matrix andBis an unknownn-dimensions column vector,A1andA2satisfyI+AA1=AA2andI+A1A=A2A. We present some conditions under which the systemsAX=BandX+A1B=A2Bhave the same solutions and give some properties of semi-invertible matrices. Our results extend the scope of the application of matrices.

zero-sum-free semirings; commutative semirings; semi-invertible matrix; system of linear equations; solving systems of equations

2015-06-08

國家自然科學(xué)基金(11171242)、教育部博士點(diǎn)基金(20105134110002)和四川省杰出青年基金(2011JQ0055)

O153.1; O159

A

1001-8395(2017)04-0450-07

10.3969/j.issn.1001-8395.2017.04.004

*通信作者簡介：王學(xué)平(1965—),男,教授,主要從事不確定性的數(shù)學(xué)理論、格理論和半環(huán)上線性代數(shù)理論等方面的研究，E-mail:xpwang1@hotmail.com