零和自由半環(huán)上可逆矩陣的一些性質(zhì)

龍艷華, 王學(xué)平

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

1 預(yù)備知識

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

2 矩陣的一些性質(zhì)

定義2.1[12]設(shè)R是一個非空集合,如果在R中有2個代數(shù)運算“+”和“·”使:

(i) (R,+,0)是一個交換幺半群;

(ii) (R,·,1)一個幺半群;

(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).如果?r,r′∈R,r·r′=r′·r,則稱半環(huán)R是交換的.

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

設(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è)

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

或

其中

定義2.3設(shè)D∈Mn(R),任意選擇D中k行k列(k≤n).如果位于這些行和列的交點上的k2個元素按照原來的次序組成k×k階矩陣M,則稱矩陣M為D的子矩陣,稱M的雙行列式det(M)為det(D)的k級子式.如果劃去D中的k行k列,剩下的元素按照原來的次序組成(n-k)×(n-k)階矩陣M′,稱矩陣M′為M的余矩陣,稱M′的雙行列式det(M′)為det(M)的余子式.

以下如果沒有特別說明,假定半環(huán)是交換的零和自由半環(huán).

3 主要結(jié)果

對?A∈Mn(R),如果存在B∈Mn(R)使得AB=I(BA=I),則稱A是右(左)可逆的.如果A既是右可逆的又是左可逆的,則稱A是可逆的.用GLn(R)表示Mn(R)中所有可逆矩陣的集合.設(shè)A,B∈Mn(R),若AB=In,則BA=In.

證明因A=(aij)∈Mn(R)是可逆的,設(shè)B=(bij)∈Mn(R)使AB=BA=I,因此B也可逆.設(shè)A1,B1∈Mn-1(R)分別是矩陣A、B去掉第i行、第j列后的余矩陣,則矩陣A、B、A1和B1分別為:

即A1B1=In-1,由引理3.1知B1A1=In-1,故A1可逆.

定理3.2如果A∈Mn(R)是可逆的,則A的所有行列上有且只有一個元素不為零.

(1)

a1j=a2j=…=ai-1,j=

ai+1,j=…=anj=0,

同理,由BA=I得

ai1=ai2=…=ai,j-1=

ai,j+1=…=ain=0.

注3.1定理3.2的逆命題一般不成立.

例3.1設(shè)R=〈R,+,·,0,1〉為圖1所示的半環(huán)(在定義2.1中,+=∨,·=∧),

但A不可逆.

推論3.2設(shè)A∈Mn(R)是可逆的對角矩陣,

則A對角線上的元素全不為零.

定理3.3設(shè)A∈Mn(R)是可逆的,則|A|+和|A|-有且只有一個不為零.

證明由定理3.2知A的所有行列上有且只有一個元素不為零.不妨設(shè)a1σ(1),a2σ(2),…,anσ(n)不為零,其中,σ(1),σ(2),…,σ(n)是{1,2,…,n}的排列.若σ(1),σ(2),…,σ(n)是{1,2,…,n}的偶排列,則有

|A|+=a1σ(1)a2σ(2)…anσ(n)≠0,

|A|-=a1σ(2)a2σ(1)…anσ(n)=0.

反之,若σ(1),σ(2),…,σ(n)是{1,2,…,n}的奇排列,則有

|A|-=a1σ(1)a2σ(2)…anσ(n)≠0,

|A|+=a1σ(2)a2σ(1)…anσ(n)=0.

故定理成立.

引理3.2[22]設(shè)R是零和自由半環(huán),A∈Mn(R),以下各條件等價:

1)A是左可逆的;

2)A是右可逆的;

3)A是可逆的;

4)ATA是可逆的對角矩陣;

5)AAT是可逆的對角矩陣;

6)AAT和ATA都是可逆的對角矩陣.

定義3.1設(shè)In∈Mn(R)是單位矩陣,將交換In的第i行和第j行后所得到的矩陣Pi?j稱為初等矩陣.

AT=(aji).

引理3.3[22]在零和自由半環(huán)R上,A∈Mn(R)是可逆的,則A[n]是可逆對角陣,其中,[n]是1,2,…,n的最小公倍數(shù).

定理3.5在零和自由半環(huán)R上,A∈Mn(R),如果A是可逆的,則A[k]是可逆對角陣,其中,k是矩陣A對角線上為零的元素的個數(shù),[k]是1,2,…,k的最小公倍數(shù).

定理3.6在零和自由半環(huán)R上,A∈Mn(R),以下各條件等價:

1)A是左可逆的;

2)A是右可逆的;

3)A是可逆的;

4)ATA是可逆的對角矩陣;

5)AAT是可逆的對角矩陣;

6)AAT和ATA都是可逆的對角矩陣;

證明由引理3.2知僅需證3)?7).7)?3)顯然成立.

由定理3.2和3.6可得到推論3.4.

推論3.4在零和自由半域R上,A∈Mn(R),A可逆當(dāng)且僅當(dāng)A的所有行列上有且只有一個元素不為零.

引理3.4[12]設(shè)A∈Mn(R),若A可逆,則|A|+≠|(zhì)A|-.

定理3.7設(shè)A∈Mn(R),若存在A的一個子陣B,使得|B|+=|B|-,則|A|≡0.

證明由定義2.2知

不妨設(shè)B∈Mn-k(R),則有

其中,ε(1),ε(2),…,ε(k)是{1,2,…,k}的排列.又因為|B|+=|B|-,即有|A|+=|A|-,則|A|≡0.

注3.2反之,若A∈Mn(R),|A|≡0,則不一定存在A的一個子陣B,使得|B|+=|B|-成立,如例3.2.

例3.2設(shè)R=〈R,+,·,0,1〉,a+b=g·c·d·{a,b}(即a、b的最大公因子),a·b=l·c·m·{a,b}(即a、b的最小公倍數(shù)).

設(shè)A∈Mn(R),

|A|+=2·1·3=6,|A|-=(1·1·12)+(2·6·6)=12+6=6=|A|+,即|A|≡0.但不存在A的子陣B使得|B|+=|B|-.

注3.3由引理3.4知,設(shè)A∈Mn(R),若|A|+=|A|-,則A不可逆.

由定理3.7、引理3.4及定義知推論3.5成立.

推論3.5設(shè)A∈Mn(R),如果存在A的子陣B使得|B|+=|B|-,則A不可逆.

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

[2] Cao Z Q, Kim K H, Roush F W. Incline Algebra and Applications[M]. New York:Ellis Horwood Ltd,1984.

[3] Ghazinoory S, Esmail Zadeh A, Kheirkhah A S. Application of fuzzy calculations for improving portfolio matrices[J]. Info Sci,2010,180:1582-1590.

[4] Give’on Y. Lattice matrices[J]. Info Control,1964,7: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: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:3232-3247.

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

[9] Zhao X Z, Jun Y B, Ren F. The semiring of matrices over a finite chain[J]. Inform Sci,2008,178:3443-3450.

[10] Baccelli F L, Mairesse I. Ergodic theorems for stochastic operators and discrete event networks[C]//J Gunawardena. Bristol:Publ Newton Inst. Cambridge:Cambridge University Press,1998: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]. Ann Discrete Math,1984,19:147-164.

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

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

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

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

[18] Give’on Y. Matrix over semirings[J]. Info Control,1964,7:477-484.

[19] Reutenauer C, Straubing Howard. Inversion of matrices over a commutative semiring[J]. J Algebra,1984,88:350-360.

[20] Zhao C K. Inverses of L-fuzzy matrices[J]. Fuzzy Sets and Systems,1990,34:103-116.

[21] Han S C, Li H X. Invertible incline matrices and Cramer’s rule over inclines[J]. Linear Algebra and Its Appl,2004,389:121-138.

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

[23] Cechlacutearovacutea K, Placuteavka J. Linear independence in bottleneck algebras[J]. Fuzzy Sets and Systems,1996,77:337-348.

[24] Cuninghame-Green R A, Butkovic P. Bases in max-algebra[J]. Linear Algebra and Its Appl,2004,389:107-120.

[25] Gondran M, Minoux M. Graphs, Dio?ds and Semirings[M]. New York:Springer-Verlag,2008.

[26] Perfilieva I, Kupka J. Kronecker-Capelli theorem in semilinear spaces[C]//Proceedings of the 9th International FLINS Conference. Ruan D, Li T R, Xu Y, et al. New York:World Scientific,2010:43-51.