袁躍爽，張子龍，2

（1.河北師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，河北石家莊050024；2.河北省計算數(shù)學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河北石家莊050024）

?

極大加代數(shù)的對稱代數(shù)S上互補(bǔ)基本矩陣

袁躍爽1，張子龍1，2

（1.河北師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，河北石家莊050024；
2.河北省計算數(shù)學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河北石家莊050024）

主要研究了極大加代數(shù)的對稱代數(shù)S上互補(bǔ)基本矩陣，給出本征積的概念，證明了S上的Laplace定理，由此推出所有互補(bǔ)基本矩陣的行列式相等，且任意兩個互補(bǔ)基本矩陣的行列式中的非零項均一一對應(yīng)相等.在一個互補(bǔ)基本矩陣的行列式中，對于確定非零項的任一置換，給出了在另一個互補(bǔ)基本矩陣的行列式中找到置換使其確定相同非零項的方法.

極大加代數(shù)；對稱代數(shù)；互補(bǔ)基本矩陣；Laplace定理；行列式

§1　引　言

2014年，F(xiàn)iedler和Hall給出了極大加代數(shù)上的互補(bǔ)基本矩陣［1］的概念，發(fā)現(xiàn)這些互補(bǔ)基本矩陣與傳統(tǒng)代數(shù)中的互補(bǔ)基本矩陣［2］有些相似的代數(shù)性質(zhì)，例如，互補(bǔ)基本矩陣的（極大）不變量等于各個矩陣（極大）不變量的乘積.極大加代數(shù)的對稱代數(shù)S是一種重要的代數(shù)結(jié)構(gòu)［3］.文獻(xiàn)［3］中引入了S上矩陣的行列式與行列式按照一行展開的概念. 2008年，F(xiàn)iedler提出了多個矩陣的本征積［4］的概念，并得到互補(bǔ)基本矩陣是完全本征的.

本文引入S上互補(bǔ)基本矩陣，給出S上互補(bǔ)基本矩陣的完全本征性的證明，并提出S上k級子式的概念，證明了在S上的Laplace定理.

設(shè)A是n×n矩陣，A的行列式det（A）中共有n！項，則每項是由某個置換確定的矩陣中n個位置的元素作?積得到.根據(jù)Laplace定理，得到所有互補(bǔ)基本矩陣（相同的矩陣因子作積）的行列式相等，而且其中任意兩個互補(bǔ)基本矩陣的行列式中的非零項均一一對應(yīng)相等.

如果存在兩個行列式中的項是一一對應(yīng)的，那么也必定存在一一對應(yīng)的置換.在一個互補(bǔ)基本矩陣的行列式中，對于確定非零項的任意置換，本文給出了定位法，根據(jù)定位法可以在另一個互補(bǔ)基本矩陣（相同的矩陣因子作積）的行列式中找到置換使其確定相同非零項.為了具體說明定位法，給出一個例子.

§2　預(yù)備知識

Rmax= R∪｛-∞｝為具有二元運(yùn)算⊕和?的冪等交換半域，其中二元運(yùn)算⊕和?分別是“取極大”和“加法”運(yùn)算. Rmax的零元是ε= -∞，單位元是e = 0.是｛（x，y）|x，y∈Rmax｝上具有運(yùn)算⊕和?的冪等半域，其中二元運(yùn)算⊕和?定義如下:的零元是（ε，ε），單位元是（e，ε）.

設(shè)x =（x′，x′′），規(guī)定?x =（x′′，x′）為x的負(fù)元，x?= x?x為x的平衡算子.

設(shè)x =（x′，x′′），y =（y′，y′′），如果x′⊕y′′= x′′⊕y′，那么稱x與y平衡，記為x▽y.

在R2max上引入關(guān)系R:

在S中，對任意t∈Rmax，稱（t，-∞）=為正元素，（-∞，t）=｛（x′，t）|x′＜t｝為負(fù)元素，（t，t）=｛（t，t）｝為平衡元素.記為所有正元素和零元的集合，是半域；記為所有負(fù)元素和零元的集合，由于對運(yùn)算?不封閉，所以不是半域；記S?為所有平衡元素的集合具有吸收性.由此可知S⊕，S?和S?唯一公共的元素是零元（ε，ε）.

對任意t∈Rmax，記S中的正元素（t，-∞）= t，負(fù)元素（-∞，t）=?t，平衡元素（t，t）= t?，則可用3?2代替（3，-∞）⊕（-∞，2），這樣就有3?2 =（3，2）=（3，-∞）= 3.

設(shè)σ為｛1，···，n｝的任意置換，定義置換σ的符號為:

在S中，n×n矩陣A =（aij）的行列式為:

記為|A|或det（A）.

在文獻(xiàn)［3］中，設(shè)AT為矩陣A的轉(zhuǎn)置矩陣，則det（A）= det（AT）.元素aij的代數(shù)余子式記為cofij（A）.以cofij（A）為元素作成的矩陣記為A?，稱A?為矩陣A的伴隨矩陣，其中（A?）ij= cofji（A）.行列式det（A）按照一行展開（出自文獻(xiàn)［5］）為

設(shè)A =（aij）n×m和B =（bij）m×n為S上的矩陣，矩陣之間的運(yùn)算?定義為:

矩陣的乘法滿足結(jié)合律.

n維行向量α=（a11，a12，···，a1n）與n維列向量β=（b11，b21，···，bn1）T作積，如果α?β= ⊕nj=1（a1j?bj1）最多只有一個非零積，則稱它們的積是本征的.接下來，看一個向量本征積的例子：

一般地，本征積不滿足結(jié)合律.但是，如果矩陣A，B，C的積A?B?C中的每個元素（A?B?C）il=j，k（aij?bjk?ckl）最多只有一個非零元，則稱矩陣的積A?B?C是本征的.如果其中矩陣的積A?B和B?C都是本征的，那么稱矩陣的積A?B?C是完全本征的，并且對于多個（多于3個）矩陣的積同樣適用.接下來，看一個矩陣本征積的例子:

設(shè)C1，C2，···，Ct是S上級數(shù)分別為l1，l2，···，lt（li≥2；1≤i≤t）的方陣，滿足n =- t + 1.定義n×n矩陣Gk（1≤k≤t）為

這里的I?是單位矩陣，pk= l1+ l2+···+ lk-1- k + 1，qk= n - pk- lk.

定義2.1對于｛1，2，···，t｝的任意置換（i1i2···it），稱矩陣的乘積

為S上互補(bǔ)基本矩陣.

引理2.1設(shè)Ck（1≤k≤t）是級數(shù)分別為li（li≥2；1≤i≤t）的方陣，定義n×n矩陣Gk（1≤k≤t）形如（1），則對于｛1，2，···，t｝的任意置換（i1i2···it），矩陣的乘積

是完全本征的.

證用歸納法證明.

對于｛1，2，···，t｝的任意置換（i1i2···it），當(dāng)t = 3時，結(jié)論顯然成立.假設(shè)當(dāng)t - 1（t＞4）時結(jié)論成立，下面證明當(dāng)t時結(jié)論也成立.

設(shè)1＜it＜t，矩陣Cit為

矩陣Cit去掉第1，lit行和第1，lit列后，剩下的元素按原來的次序所組成的（lit- 2）×（lit- 2）級矩

其中p +（lit- 2）+ q = n，lit- 2≥0.由歸納假設(shè)可知，Gi1?Gi2?···?Git-1是完全本征的. 設(shè)A =（aij），B =（bij），則Gi1?Gi2?···?Git-1?Git為

按照矩陣的乘法規(guī)則計算（2）式，可知（2）式左側(cè)矩陣的任意行向量與右側(cè)矩陣的任意列向量的乘積最多只有一個非零積，因此互補(bǔ)基本矩陣Gi1?Gi2?···?Git是完全本征的.

同理，當(dāng)it= 1，t時結(jié)論仍然成立.定理得證.

定義2.2設(shè)A是n×n的矩陣，對N =｛1，2，···，n｝的子集S =｛j1，···，js｝來說，在矩陣A中選定j1，···，js行和j1，···，js列，位于這些選定行和列的交點(diǎn)上的s2個元素按原來的次序排列成的s級矩陣，稱為矩陣A的一個主子矩陣，記為A［S］.

§3　 S上的Laplace定理

這一部分，給出了矩陣的余子式、代數(shù)余子式與k級子式的概念.并將證明S上的Laplace定理.

在文獻(xiàn)［3］中，設(shè)矩陣A =（aij）為S上n×n矩陣，矩陣A的正行列式與負(fù)行列式分別定義為

則|A| = |A|+?|A|-.

設(shè)Aij表示矩陣A去掉i行j列所得的矩陣，矩陣Aij的正代數(shù)余子式與負(fù)代數(shù)余子式分別定義為

根據(jù)上述概念容易得到以下結(jié)論.

推論3.1設(shè)矩陣A =（aij）為S上n?×n矩陣，則

定義3.1設(shè)A =（aij）為S上n×n矩陣，稱元素aij的余子式為|Aij|. |Aij|的前面加上符號

后稱為元素aij的代數(shù)余子式cofij（A），即cofij（A）= N（i + j）|Aij|.

引理3.1設(shè)σ1，σ2為｛1，···，n｝的互不相交的兩個循環(huán)置換，令τ=σ1σ2，則

證不失一般性，假設(shè)σ1=（i1i2···ik），σ2=（j1j2···js）（k + s≤n）均為循環(huán)置換.由于每個置換都可以表示成若干個對換的乘積，則

因此sgn（σ1）= N（k - 1），sgn（σ2）= N（s - 1），然而，

則sgn（τ）= N［（k - 1）+（s - 1）］.所以不論k與s的奇偶性，均有sgn（σ1）?sgn（σ1）= sgn（τ）.

引理3.2［3］設(shè)σ為｛1，2，···，n｝的任意置換，則|（uσ（1），···，uσ（n））| = sgn（σ）|（u1，···，un）|.

引理3.3［3］設(shè)矩陣A的轉(zhuǎn)置矩陣為AT，則|A| = |AT|.

根據(jù)引理3.2和引理3.3可以直接得到如下結(jié)論.

推論3.2設(shè)A是S上的n×n矩陣，對換行列式|A|中兩行（列）的位置得到行列式為|A′|，則|A| =?|A′|，即行列式的符號改變.

一般地，在矩陣A中任取k行和k列，位于這些選定的行和列的交點(diǎn)上的k2個元素按原來的次序所組成的行列式M，稱為A的k級子式，記|AM|為M的余子式.

定義3.2設(shè)D的k級子式M在D中所在的行和列指標(biāo)分別是i1，i2，···，ik；j1，j2，···，jk，則M的余子式|DM|前面加上符號N［（i1+ i2+···+ ik）+（j1+ j2+···+ jk）］后稱為M的代數(shù)余子式，記為cofM（D）.

引理3.4行列式|D|的任一子式M與它的代數(shù)余子式cofM（D）的乘積中的每一項都是行列式D的展開式中的一項，而且符號也一致.

證首先討論k級子式M位于行列式|D|的左上方的情況.

這時M的代數(shù)余子式cofM（D）為

M的每一項可以表示為a1σ（1）?a2σ（2）?···?akσ（k），其中σ為｛1，2，···，k｝的一個置換，這一項前面所帶的符號為sgn（σ）. |DM|中每一項可以表示為ak+1，τ（k+1）?ak+2，τ（k+2）?···?anτ（n），其中τ為｛k + 1，k + 2，···，n｝的一個置換，這一項前面所帶的符號為sgn（τ）.而這兩項的乘積是

a1σ（1）?a2σ（2）?···?akσ（k）?ak+1，τ（k+1）?ak+2，τ（k+2）?···?anτ（n），（3）

（3）式由置換στ確定，前面的符號是sgn（στ），因?yàn)橹脫Qσ與τ是互不相交的兩個循環(huán)置換，根據(jù)引理3.1可知

因此（3）式是行列式|D|中的一項且符號相同.

接下來證明一般情況.設(shè)子式M在行列式|D|中所在的行和列指標(biāo)分別為i1，i2，···，ik；j1，j2，···，jk，其中

變化|D|中行和列的次序使M位于|D|的左上角.因此，先把第i1行依次與第i1-1，i1-2，···，2，1行對換，共經(jīng)過i1- 1次對換將第i1行換到第一行.如此繼續(xù)進(jìn)行，則共經(jīng)過了

次行對換把第i1，i2，···，ik行依次換到第1，2，···，k行.

類似地，利用列變換將M的列換到第1，2，···，k列，則共經(jīng)過

次變換.

用|D1|表示這樣變換后得到的新行列式，根據(jù)推論3.2，可得

可以得出，|D1|和|D|的展開式中出現(xiàn)的項是一樣的，只是每一項都差符號N［（i1+i2+···+ik）+ （j1+ j2+···+ jk）］.

此時M已經(jīng)位于|D1|的左上角，所以M?|DM1|中每一項都是|D1|中的一項且符號一致.但是

所以M?cofM（D）中每一項都與|D|中一項相等且符號一致.

定理3.1設(shè)在行列式|D|中任意取定k（1≤k≤n - 1）行.由這k行元素所組成的一切k級子式與它們的代數(shù)余子式的乘積的和等于行列式|D|.

證設(shè)在|D|中取定k行后得到的子式為M1，M2，···，Mt，其代數(shù)余子式分別為cofM1（D），cofM2（D），···，cofMt（D），只需證明

根據(jù)引理3.4，Mi?cofMi（D）中每一項都是|D|中一項且符號相同，并且Mi?cofMi（D）和Mj?cofMj（D）（i /= j）無公共項，所以只需證明等式兩邊項數(shù)相等.顯然等式左邊有n！項，而t = Ckn，則右邊的項數(shù)為

§4　互補(bǔ)基本矩陣的行列式

定理4.1設(shè)A0，B0是S上分別為k級，n - k + 1級方陣，且

則det（A?B）= det（A）?det（B）.

證設(shè)

則

取det（A?B）的前k行，根據(jù)定理3.1

推論4.1設(shè)Ck（1≤k≤t）是級數(shù)分別為li（li≥2；1≤i≤t）的方陣，Gk（1≤k≤t）是形如（1）的n×n矩陣，則對于｛1，2，···，t｝的任意置換（i1i2···it）來說，

證用歸納法證明.

對于｛1，2，···，t｝的任意置換（i1i2···it），當(dāng)t = 2時，由定理4.1可知，結(jié)論顯然成立.假設(shè)當(dāng)t - 1（t＞3）時結(jié)論成立，下面證明當(dāng)t時結(jié)論也成立.

事實(shí)上，當(dāng)|i - k|＞1時，有Gi?Gk= Gk?Gi.這意味著，在置換（i1i2···it）中，當(dāng)1?2（i?j表示在置換中i位于j前）時，可以將G1移到第一個位置.設(shè)此時的互補(bǔ)基本矩陣由置換（j1j2···jt）（其中j1= 1）確定，則其余的t - 1個矩陣Gjk（k = 2，···，t）的乘積有如下形式

其中B0= Hj2?···?Hjt（Hjk= Gjk［｛l1，···，n｝］）.由歸納假設(shè)可知，

由定理4.1可知，由于det（Gk）= det（Ck），且S中的元素對運(yùn)算?滿足交換律，所以（4）式成立.

若2?1時，可以將G1移到最后位置，再利用矩陣轉(zhuǎn)置的性質(zhì)，同理可以證明（4）式成立.

推論4.2設(shè)n≥2，Gk（1≤k≤t）是S上形如（1）的n×n矩陣，則對于｛1，2，···，t｝的任意兩個置換（i1i2···it）和（j1j2···jt）來說，行列式det）的非零項與det的非零項一一對應(yīng)，且相對應(yīng)的項相等.

證由推論4.1可知，

引理4.1設(shè)Gk（1≤k≤t）是S上形如（1）的n×n矩陣，若Gi1?Gi2?···?Git=（Aij），則

此結(jié)論根據(jù)Gk的構(gòu)造方式和互補(bǔ)基本矩陣的完全本征性可以直接得到.

n≥2，Gk（1≤k≤t）是S上形如（1）的n×n陣，則對于｛1，2，···，t｝的任意置換（i1i2···it）來說，令Gi1?Gi2?···?Git= A =（Aij），G1?G2?···?Gt= B，則對于det（A）中確定非零項的任意置換σ來說，以下給出“定位法”，確定置換τ使在det（B）中確定相同的非零項.

注4.1

·設(shè)A是n×n矩陣，A的行列式det（A）中共有n！項，則每項都是由某個置換確定的矩陣中n

個位置的元素作?積所得，稱det（A）中每一個不包括符號的非零項為基礎(chǔ)項.

·定位法需要滿足：對det（A）中確定非零基礎(chǔ)項的任意置換σ，存在置換τ使在det（B）中確定相同的基礎(chǔ)項，且sgn（σ）= sgn（τ）.而確定非零基礎(chǔ)項的置換要么是k階循環(huán)置換（1≤k≤n），要么是由若干個互相沒有共同數(shù)字的循環(huán)置換作乘積得到的循環(huán)分解（定位法中提到的置換均為｛1，2，···，n｝的某個置換）.

定位法（不妨假設(shè)確定非零基礎(chǔ)項的置換為k階循環(huán)置換）

取確定det（A）中非零基礎(chǔ)項的一個k階循環(huán)置換σ=（j1j2···jk）（1≤k≤n），由此置換確定的det（A）中基礎(chǔ)項是設(shè)為

且該基礎(chǔ)項的符號為sgn（σ）.

第1步將取定的基礎(chǔ)項列表（注:第k（1≤k≤t）列的元素均屬于Gik）

換句話說，基礎(chǔ)項（5）式是表1中所有因子作?積.

第2步存在置換τ也為｛j1，j2，···，jk｝的某個k階循環(huán)置換（原因如下）.

在det（B）中，由引理4.1可知，置換τ確定的基礎(chǔ)項一定包括Ajk+1jk+1，···，Ajnjn這n -k個元素，且一定不包括Aj1j1，Aj2j2，···，Ajkjk這k個元素.否則，若包括元素Ajsjs（1≤s≤k），則（5）式中也一定包括元素Ajsjs，這與置換σ為k階循環(huán)置換矛盾.可知，在det（B）中存在置換τ為｛j1，j2，···，jk｝的某個k階循環(huán)置換，從而sgn（σ）= sgn（τ）.

第3步確定k階循環(huán)置換τ.

由置換τ為｛j1，j2，···，jk｝的某個k階循環(huán)置換，可知只需在主子陣B［｛j1，···，jk｝］中找到與表1的前k行完全相同的因子.由互補(bǔ)基本矩陣的完全本征性可知，表1的前k行因子確實(shí)出現(xiàn)在主子陣B［｛j1，···，jk｝］中.

按照以下步驟進(jìn)行確定:

1.在主子陣B［｛j1，···，jk｝］中定出第i1個因子是ox1，ox2，···，oxk的元素，這樣就可以找

到與表1的第一列的前k行完全相同的因子.假設(shè)定出了w1個元素，有k≤w1；為找到與（5）式相同的非零項，需要繼續(xù)縮小范圍.

2.在1中所找到的w1個元素中定出第i2個因子是py1，py2，···，pyk的元素，這樣就可以找

到與表1的第二列前k行完全相同的因子.假設(shè)定出了w2個元素，有k≤w2≤w1；

3.以此類推，再根據(jù)第i3個因子，第i4個因子，···，第it個因子依次定位，由推論4.1和矩陣Gi（1≤i≤t）中元素位置的唯一性可知，最終可在主子陣B［｛j1，···，jk｝］中找到唯一屬于不同行不同列的k個元素；

4.再加上n - k個元素Ajk+1jk+1，···，Ajnjn.

表1

根據(jù)以上步驟所找到的n個元素可以確定k階循環(huán)置換τ使在det（B）中確定相同的非零項.

若確定det（A）中非零基礎(chǔ)項的一個置換σ是由若干個互相沒有共同數(shù)字的循環(huán)置換作乘積得到的循環(huán)分解，對于循環(huán)分解中的每一個循環(huán)按照以上的步驟進(jìn)行確定后再作循環(huán)的乘積.

看一個例子.

例4.1令n = 4，l1= 2，l2= 2，l3= 2.對于

有

于是

而

不妨假設(shè)（7）式中由置換（132）確定的項為非零項，可知該非零項為

且該項的符號為sgn（132）= e.為方便起見，可列表為

表2

設(shè)G1?G2?G3= A =（Aij）.由引理4.1可知，置換σ確定的det（A）中基礎(chǔ)項一定包括元素A44，且一定不包括元素A11，A22，A33.可知置換σ也為3階循環(huán)置換，從而sgn（132）= sgn（σ）= e.

為找到3階循環(huán)置換σ使在（6）式中確定相同的基礎(chǔ)項，可按照以下四步進(jìn)行: 1.在（6）式的主子陣A［｛1，2，3｝］的元素中定位出第1個因子是a12，a21，e的元素，定出四個元素A12，A13，A21，A32；

2.在1中所找到的四個元素中繼續(xù)定位出第3個因子是e，e，c33的元素，定出四個元素

3.在2中所找到的四個元素中繼續(xù)定位出第2個因子是b23，e，b32的元素，定出三個元素

顯然，它們是取自不同行不同列的三個元素；

4.再加上元素A44.

根據(jù)定出的四個元素A13，A21，A32，A44可以唯一確定置換σ=（132），使置換σ=（132）與行列式det（G1?G3?G2）中的置換（132）確定相同的非零項.

根據(jù)定位法的第2步可以直接得到如下結(jié)論.

推論4.3對于所有行列式det（Gi1?Gi2?···?Git）中某個相同的非零項來說，則確定該項的所有置換的區(qū)別為每個置換的循環(huán)中元素的排列順序不同.

［1］Fiedler M，Hall F J. Max algebraic complementary basic matrices［J］. Linear Algebra Appl，2014，457: 287-292.

［2］Fiedler M，Hall F J. A note on permanents and generalized complementary basic matrices［J］. Linear Algebra Appl，2012，436: 3553-3561.

［3］Baccelli F，Cohen G，Olsder G J，et al. Synchronization and Linearity: an Algebra for Discrete Event System［M］. New York: John Wiley and Sons，1992.

［4］Fiedler M，Intrinsic products and factorizations of matrices，Linear Algebra Appl，2008，428: 5-13.

［5］Max Plus. Linear systems in（max，+）algebra［A］. In: Proceedings of the 29-th Conference on Decision and Control IEEE［C］. 1990，151-156.

MR Subject Classification: 15A15；15A57

Complementary basic matrices of the symmetrized algebra of max algebra

YUAN Yue-shuang1，ZHANG Zi-long1，2
（1. College of Mathematics and Information Science，Hebei Normal University，Shijiazhuang 050024，China；
2. Key Lab of Computational Mathematics and Applications of Hebei Province，Shijiazhuang 050024，China）

The paper mainly studies the complementary basic matrices in S. It first introduces the concepts of the intrinsic products and proves the Laplace's Theorem in S. Accordingly，the determinants of CB-matrices are the same and for any nonzero term in the determinant of one CB-matrix，there exists an equal term in the determinant of the other CB-matrix and vice versa. By the same time，for a given permutation which determines the nonzero term of the determinant of one CB-matrix，a method is given to find a permutation who determines the same nonzero term in the determinant of the other CB-matrix.

max algebra；symmetrized algebra；complementary basic matrices；Laplace's Theorem；determinant

O151.21；O151.22

A

1000-4424（2016）01-0116-11

投稿日期：2015-04-292016-01-27

國家自然科學(xué)基金（11271109）