黃宇飛, 柳柏濂

(1.廣州民航職業(yè)技術(shù)學(xué)院, 廣州 510403；2.華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院, 廣州 510631)

?

本原不可冪符號矩陣的完全不可分基指數(shù)

黃宇飛1*, 柳柏濂2

(1.廣州民航職業(yè)技術(shù)學(xué)院, 廣州 510403；2.華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院, 廣州 510631)

將可分性的概念推廣至廣義符號方陣中,定義了完全模糊不可分和部分模糊可分的廣義符號方陣;把本原(0,1)方陣的(嚴(yán)格)完全不可分指數(shù)的概念推廣到本原不可冪(廣義)符號方陣,提出了(嚴(yán)格)完全不可分基指數(shù)的概念并給出了相應(yīng)的圖論刻畫,同時(shí)獲得了若干本原不可冪符號矩陣類的(嚴(yán)格)完全不可分基指數(shù)的上界. 進(jìn)一步地,將完全模糊不可分廣義符號矩陣和(嚴(yán)格)完全不可分基指數(shù)的概念分別拓展為w-模糊不可分廣義符號矩陣和(嚴(yán)格)w-不可分基指數(shù).

本原; 不可冪; (廣義)符號矩陣; (嚴(yán)格)完全不可分基指數(shù)

1　引言和定義

(0,1)矩陣是元素取自于集合{0,1}的矩陣,其中矩陣元素“0”和“1”的乘法定義為通常的乘法,而加法定義為“1+1=1”(有別于通常的加法). 于是,從代數(shù)結(jié)構(gòu)的觀點(diǎn)來看,(0,1)矩陣就是熟知的布爾矩陣. 符號矩陣是元素取自于集合{0,1,-1}的矩陣. 對于符號方陣A,注意到:在計(jì)算A的冪序列Ak(k=1,2,…)時(shí),由于無法確定“正號”加上“負(fù)號”所得的符號,故引入新的記號“#”來表示這樣的模糊符號(又稱不定號)[1]102. 自然地,集合Γ={0,1,-1,#}中元素的加法和乘法定義如下:

+01-1#·01-1#001-1#00000111##101-1#-1-1#-1#-10-11#######0# ##

我們把元素取自于集合Γ={0,1,-1,#}的矩陣稱為廣義符號矩陣. 易見,符號矩陣是廣義符號矩陣的特例,而(0,1)矩陣又是符號矩陣的特例. (廣義)符號方陣A可分為如下2類:如果A的冪序列Ak(k=1,2,…)均不含模糊符號“#”,那么A稱為可冪的;否則,A稱為不可冪的[1]102. 另外,規(guī)定本文所有的矩陣運(yùn)算均基于集合Γ進(jìn)行.

眾所周知,在矩陣的置換相抵變換下,(0,1)方陣可以劃分為完全不可分和部分可分[2]. n階(0,1)方陣A是完全不可分方陣當(dāng)且僅當(dāng)A的任意k×l階子矩陣皆含有元素“1”,其中1≤k,l≤n且k+l=n. 不是完全不可分的(0,1)方陣稱為部分可分方陣. 關(guān)于(0,1)方陣的可分性刻畫及有關(guān)研究成果已較為豐富[2]. 注意到:(0,1)矩陣中的元素“1”,與廣義符號矩陣中的元素“#”,在運(yùn)算中有著相似的作用. 因此,我們考慮將上述可分性的概念推廣至廣義符號方陣中.

定義1設(shè)A是n階廣義符號方陣. 如果A的任意k×l階子矩陣皆含有元素“#”,其中1≤k,l≤n且k+l=n,則稱A為完全模糊不可分的. 不是完全模糊不可分的廣義符號方陣稱為部分模糊可分廣義符號方陣.

記n階完全模糊不可分廣義符號方陣的集合為SFn. 顯然,對于ASFn,由于A中必含有元素“#”,故A也是不可冪的廣義符號方陣.

n階(0,1)方陣A是本原的當(dāng)且僅當(dāng)存在正整數(shù)k使得Ak=Jn,其中Jn是所有元素均為“1”的n階方陣. 把(廣義)符號矩陣A的所有非零元都換成元素“1”,所得的(0,1)矩陣記為|A|. 那么,|A|完全決定了A的零位模式. 進(jìn)而,稱(廣義)符號方陣A是本原的,如果|A|是本原的.

考察n階(廣義)符號方陣A的冪序列:A,A2,A3,…,因?yàn)?廣義)符號方陣對于乘法而言是1個(gè)有限半群,即n階符號方陣至多有3n2個(gè),n階廣義符號方陣至多有4n2個(gè),所以A的冪序列中必然會出現(xiàn)相同的項(xiàng). 記最先重復(fù)出現(xiàn)的1對冪是Ab=Ab+p,其中b和p都是正整數(shù). 我們稱p=p(A)為(廣義)符號方陣A的(廣義)周期,b=b(A)為A的(廣義)基指數(shù)[1]103.

記所有元素均為“#”的n階廣義符號方陣為#Jn. 文獻(xiàn)[3]290已證得:n階本原不可冪(廣義)符號方陣A的基指數(shù)b(A)=min{k|Ak=#Jn},周期p(A)=1. 因此,結(jié)合定義1可知:對于n階本原不可冪的(廣義)符號方陣A,必存在正整數(shù)t(如：t=b(A))，使得AtSFn. 由此給出如下概念.

定義2設(shè)A是n階本原不可冪的(廣義)符號方陣. 定義A的完全不可分基指數(shù)(記為ρ(A))是最小的正整數(shù)t使得AtSFn.

另外,我們發(fā)現(xiàn):對于n階本原不可冪(廣義)符號方陣A,由定義2可知Aρ(A)SFn,但并不保證對所有的正整數(shù)i (>ρ(A)),Ai均是完全模糊不可分的. 例如:記n階本原不可冪符號方陣的集合為SPn.令

定義3設(shè)A是n階本原不可冪(廣義)符號方陣. 定義A的嚴(yán)格完全不可分基指數(shù)(記為ρ*(A))是最小的正整數(shù)t,使得對于滿足i≥t的任意正整數(shù)i,有AiSFn.

可見,(嚴(yán)格)完全不可分基指數(shù)正是本原(0,1)方陣的(嚴(yán)格)完全不可分指數(shù)[4-5]在本原不可冪(廣義)符號方陣中的拓廣. 關(guān)于(嚴(yán)格)完全不可分指數(shù)的研究已有較豐富的成果[5-8]，本文主要針對完全不可分基指數(shù)和嚴(yán)格完全不可分基指數(shù)展開研究,給出(嚴(yán)格)完全不可分基指數(shù)的圖論刻畫,探索若干本原不可冪符號矩陣類的(嚴(yán)格)完全不可分基指數(shù)的上界,并把(嚴(yán)格)完全不可分基指數(shù)進(jìn)一步推廣為(嚴(yán)格)w-不可分基指數(shù).

2　(嚴(yán)格)完全不可分基指數(shù)的圖論刻畫

設(shè)A是(廣義)符號方陣,且記Wk(i,j)為其伴隨(廣義)帶號有向圖S(A)中從點(diǎn)i到點(diǎn)j的長為k的有向途徑的集合. 則冪Ak中(i,j)位置元素(Ak)ij的符號可確定為:

(1)

由式(1)可知[3]286-287:

(i)(Ak)ij=0當(dāng)且僅當(dāng)S(A)中沒有從點(diǎn)i到點(diǎn)j的長為k的途徑;

(ii)(Ak)ij=1當(dāng)且僅當(dāng)Wk(i,j)≠?且Wk(i,j)中所有途徑都同為正號;

(iii)(Ak)ij=-1當(dāng)且僅當(dāng)Wk(i,j)≠?且Wk(i,j)中所有途徑都同為負(fù)號;

(iv)(Ak)ij=#當(dāng)且僅當(dāng)S(A)中有從點(diǎn)i到點(diǎn)j的長為k的SSSD途徑對(或有從點(diǎn)i到點(diǎn)j的長為k的符號為“#”的途徑).

設(shè)SRt(X)表示從點(diǎn)子集X中的任意點(diǎn)出發(fā)經(jīng)過長為t的SSSD途徑對(或符號為“#”的途徑)所能到達(dá)的所有點(diǎn)的集合,又稱其為模糊可達(dá)集. 對于完全模糊不可分的廣義符號方陣A,亦稱其伴隨廣義帶號有向圖S是完全模糊不可分的. 從圖論的角度出發(fā),結(jié)合定義1,n階廣義帶號有向圖S是完全模糊不可分的當(dāng)且僅當(dāng)S中任一滿足1≤|X|=k≤n-1的k點(diǎn)子集X都有|SR1(X)|≥k+1. 再根據(jù)定義2和定義3,可用圖論的語言來刻畫(嚴(yán)格)完全不可分基指數(shù).

命題1設(shè)S是n階本原不可冪(廣義)帶號有向圖. 那么,S的完全不可分基指數(shù)ρ(S)是最小的正整數(shù)t,使得S中任一滿足1≤|X|=k≤n-1的k點(diǎn)子集X都有|SRt(X)|≥k+1.

命題2設(shè)S是n階本原不可冪(廣義)帶號有向圖. 那么,S的嚴(yán)格完全不可分基指數(shù)ρ*(S)是最小的正整數(shù)t,使得對于滿足i≥t的任意正整數(shù)i,S中任一滿足1≤|X|=k≤n-1的k點(diǎn)子集X都有|SRi(X)|≥k+1.

另外,記本原不可冪帶號有向圖S的模糊指標(biāo)[3]290為r(S),即最小的正整數(shù)r使得在S中存在長為r的SSSD途徑對;另外,對于本原不可冪的廣義帶號有向圖S,若S中含有帶“#”號的弧,則規(guī)定r(S)=1. 易見,

r(S)≤ρ(S)≤ρ*(S)≤b(S),

其中b(S)是本原不可冪(廣義)帶號有向圖S的基指數(shù). 故(嚴(yán)格)完全不可分基指數(shù)是有意義的(為有限值).

(嚴(yán)格)完全不可分基指數(shù)有下述應(yīng)用背景. 1個(gè)n階本原不可冪(廣義)符號方陣對應(yīng)于1個(gè)n階本原不可冪(廣義)帶號有向圖,即帶變極器(及干擾器)的非記憶通訊系統(tǒng)網(wǎng)絡(luò)(其定義及運(yùn)作方式參見文獻(xiàn)[10]). 設(shè)初始狀態(tài)為任選若干個(gè)點(diǎn)(至少1個(gè),至多n-1個(gè))賦予相同的信息,完全不可分基指數(shù)描述的是最短的時(shí)間t1,使得此時(shí)刻比初始狀態(tài)至少多1個(gè)點(diǎn)掌握了該信息的模糊化(即正、負(fù)信息相互干擾的結(jié)果);而嚴(yán)格完全不可分基指數(shù)刻畫的則是最短的時(shí)間t2,使得從該時(shí)刻起的任一時(shí)刻都比初始狀態(tài)至少多1個(gè)點(diǎn)掌握了該信息的模糊化.

最后給出關(guān)于本原不可冪帶號有向圖的刻畫[3],這是研究本原不可冪符號矩陣的重要工具之一.

引理1[3]288設(shè)S是本原帶號有向圖. 那么,S是不可冪的當(dāng)且僅當(dāng)S包含2個(gè)有向圈C1和C2(記其長度分別為p1和p2),它們滿足以下2個(gè)條件之一:

(B1)p1是偶數(shù),p2是奇數(shù), 且sgn(C1)=-1.

(B2)p1和p2都是奇數(shù), 且sgn(C1)=-sgn(C2).

為方便起見,稱這樣一對滿足條件(B1)或(B2)的有向圈C1和C2為“違規(guī)圈對”. 由此還可推出: 途徑對W1=p2C1和W2=p1C2的長度均為p1p2,但符號相異, 即(sgn(C1))p2=-[(sgn(C2))p1].

3　(嚴(yán)格)完全不可分基指數(shù)的界

本節(jié)將探索若干本原不可冪符號矩陣(即帶號有向圖)類的(嚴(yán)格)完全不可分基指數(shù)的上界.

首先,考慮恰有d個(gè)環(huán)的n階本原不可冪帶號有向圖集SPn(d)的(嚴(yán)格)完全不可分基指數(shù)的上界,其中1≤d≤n. 根據(jù)環(huán)點(diǎn)的特征及相關(guān)記號的意義,可證明下述引理.

引理2設(shè)SSPn(d). 若從非空點(diǎn)子集X中的頂點(diǎn)出發(fā)通過長為r的SSSD途徑對能到達(dá)某q個(gè)環(huán)點(diǎn),其中1≤q≤d,則對于任意非負(fù)整數(shù)t,

|SRr+t(X)|≥min{q+t,n}.

對于任意非負(fù)整數(shù)t,由于v1,…,vq都是環(huán)點(diǎn),故存在min{q+t,n}個(gè)頂點(diǎn)(記為uj(j=1,…,min{q+t,n})),分別能從{v1,…,vq}中某些環(huán)點(diǎn)出發(fā)通過長為t的途徑到達(dá),不妨設(shè)點(diǎn)uj可從環(huán)點(diǎn)vhj出發(fā)通過長為t的途徑Pj到達(dá),其中j=1,…,min{q+t,n},而hj{1,…,q}.

引理3設(shè)SSPn(d),且每個(gè)環(huán)均與有向圈C1構(gòu)成違規(guī)圈對. 則

ρ(S)≤ρ*(S)≤2n-d+1.

證明根據(jù)定義2和定義3,顯然有ρ(S)≤ρ*(S). 任取1個(gè)滿足1≤|X|=k≤n-1的點(diǎn)子集X. 結(jié)合命題1和命題2,僅需證明對于滿足η≥2n-d+1的任意正整數(shù)η,都有|SRη(X)|≥k+1.

不妨設(shè)有向圈C1的長度為p1,S中的d個(gè)環(huán)點(diǎn)記為v1,…,vd,其上的環(huán)又分別記為L1,…,Ld. 不失一般性,又設(shè)v1,…,vt不在有向圈C1上,而vt+1,…,vd在有向圈C1上,其中0≤t≤d.

情形1:t=d,即所有的環(huán)點(diǎn)均不在有向圈C1上. 故p1≤n-d. 記從有向圈C1中的點(diǎn)(不妨記其為u0)到某個(gè)環(huán)點(diǎn)(不妨記其為vh, 1≤h≤d)的最短有向路為Q,故Q的長度t1≤n+1-d-p1. 注意到:每個(gè)環(huán)均與有向圈C1構(gòu)成違規(guī)圈對,從而C1+Q與Q+p1Lh是長為p1+t1的SSSD途徑對. 又記從X中的點(diǎn)(不妨記為x0)到點(diǎn)u0的最短途徑為P,易見其長度t2≤n+1-k-1=n-k. 對于滿足η≥2n-d+1的任意正整數(shù)η,由于

p1+t1+t2≤p1+(n+1-d-p1)+(n-k)=

2n-d+1-k≤η-k,

不妨設(shè)μ=(η-k)-(p1+t1+t2),顯然μ≥0. 因此,P+(C1+Q)+μLh與P+(Q+p1Lh)+μLh是從點(diǎn)x0X到環(huán)點(diǎn)vh的長為η-k的SSSD途徑對. 從而由引理2可得:|SRη(X)|=|SR(η-k)+k(X)|≥1+k.

情形2: 0≤t≤d-1,即有d-t(≥1)個(gè)環(huán)點(diǎn)在有向圈C1上. 故p1Lj與C1是從點(diǎn)vj到自身長為p1的SSSD途徑對,其中j=t+1,…,d. 易見,p1≤n-t.

p1≤n-t≤(η-n+d-1)-t,

|SRη(X)|=|SR(η-n+d-1-t)+(n+t-d+1)(X)|≥

(k+d-t-n)+(n+t-d+1)=k+1.

子情形2.2:n+1-k-d+t>0. 此時(shí),存在從X中的點(diǎn)(不妨記其為x0)到有向圈C1上的某個(gè)環(huán)點(diǎn)(不妨記其為vh,t

p+p1≤[n+1-k-(d-t)]+(n-t)=2n-d+1-k≤η-k,

不妨設(shè)μ=(η-k)-(p+p1),則μ≥0. 從而,P+p1Lh+μLh與P+C1+μLh是從點(diǎn)x0X到環(huán)點(diǎn)vh的長為η-k的SSSD途徑對. 結(jié)合引理2,有:|SRη(X)|=|SR(η-k)+k(X)|≥1+k. 證畢.

引理4設(shè)SSPn(d),且所有環(huán)的符號不全相同. 則

ρ(S)≤ρ*(S)≤2n-d+1.

證明任取1個(gè)滿足1≤|X|=k≤n-1的點(diǎn)子集X. 不妨記SSPn(d)的d個(gè)環(huán)點(diǎn)為v1,…,vd,其上的環(huán)又分別記為L1,…,Ld. 由于S中所有環(huán)的符號不全相同, 故d≥2. 根據(jù)命題1和命題2,下面證明：對于滿足η≥2n-d+1的任意正整數(shù)η,有|SRη(X)|≥k+1.

情形1:n+1-k-d>0. 記從X中的點(diǎn)(不妨記其為x)到某個(gè)環(huán)點(diǎn)(不妨記為vh1, 1≤h1≤d)的最短有向路為P,故P的長度t1≤n+1-k-d. 注意到:必存在環(huán)點(diǎn)vh2(1≤h2≤d)滿足sgn(Lh1)=-sgn(Lh2),從而Lh1和Lh2構(gòu)成違規(guī)圈對. 又記從點(diǎn)vh1到點(diǎn)vh2的最短路為Q,則其長度t2≤n-1.

對于滿足η≥2n-d+1的任意正整數(shù)η,由于t1+t2+1≤(n+1-k-d)+(n-1)+1≤η-k,記μ=(η-k)-(t1+t2+1),則μ≥0. 從而P+Lh1+Q+μLh2和P+Q+Lh2+μLh2是從點(diǎn)xX到環(huán)點(diǎn)vh2的長為η-k的SSSD途徑對. 故由引理2可得:|SRη(X)|=|SR(η-k)+k(X)|≥1+k.

對于滿足η≥2n-d+1的任意正整數(shù)η,注意到:

t1+1≤2n-d+1-k≤η-k,

|SRη(X)|=|SR(η-k+1)+(k-1)(X)|≥2+(k-1)=k+1.

證畢.

情形1: 1≤m≤n-d.故從點(diǎn)vm到某環(huán)點(diǎn)(顯然是環(huán)點(diǎn)vn-d+1)的最短有向路的長度為n-d+1-m. 由于-(n-d+1-m)-n≤m-1≤n-d-1≤n-2,故不存在從點(diǎn)vm到點(diǎn)vn-d的長為的SSSD途徑對,其中m=1,…,n-d.

情形2:n-d+1≤m≤n-1.因?yàn)閺狞c(diǎn)vm到點(diǎn)vn-d的最短有向路之長為2n-m-d,且2n-m-d≥n-d+1,又-n≤n-d,所以也不存在從點(diǎn)vm到點(diǎn)vn-d的長為的SSSD途徑對,其中m=n-d+1,…,n-1.

定理1設(shè)SSPn(d),則

ρ(S)≤ρ*(S)≤2n-d+1,

證明由于SSPn(d),故根據(jù)引理1,S包含違規(guī)圈對C1和C2(記其長度分別為p1和p2),它們滿足以下2個(gè)條件之一:

(B1)p1是偶數(shù),p2是奇數(shù), 且sgn(C1)=-1.

(B2)p1和p2都是奇數(shù), 且sgn(C1)=-sgn(C2).

情形1:C1和C2符合條件(B1). 因?yàn)榄h(huán)的長度是1(即奇數(shù)),所以每個(gè)環(huán)均與C1構(gòu)成違規(guī)圈對,從而由引理3可得:

ρ(S)≤ρ*(S)≤2n-d+1.

情形2:C1和C2符合條件(B2). 若S中所有環(huán)的符號均相同,由于環(huán)的長度是1(即奇數(shù)),故每個(gè)環(huán)均與C1(或C2)構(gòu)成違規(guī)圈對. 同樣，由引理3可得:

ρ(S)≤ρ*(S)≤2n-d+1.若S中所有環(huán)的符號不全相同,則由引理4亦得:

ρ(S)≤ρ*(S)≤2n-d+1.

記跡非零的n階本原不可冪符號矩陣之集為SPNn. 由于SSPNn至少含有1個(gè)環(huán)點(diǎn),故根據(jù)定理1可得如下的推論.

推論1設(shè)SSPNn,則ρ(S)≤ρ*(S)≤2n,此上界可達(dá)且是極圖之一.

定理2設(shè)SSPn有長為s的有向圈,且有t(≥s)個(gè)頂點(diǎn)落于某長為s的有向圈上，則

ρ(S)≤s(2n-t+1).

證明設(shè)SSPn的鄰接符號矩陣為A. 由于S是本原不可冪的,故S(As)(又記為Ss)也是本原不可冪的. 又因?yàn)镾有長為s的有向圈,且有t (≥s)個(gè)頂點(diǎn)落于某長為s的有向圈上,所以Ss含有t個(gè)環(huán)點(diǎn),即SsSPn(t). 根據(jù)定理1可得:

ρ*(Ss)≤2n-t+1,

結(jié)合定義2和定義3可得:

ρ(S)≤s·ρ*(Ss)≤s(2n-t+1).

證畢.

由定理2可得以下推論,從而導(dǎo)出若干特殊本原不可冪帶號有向圖類的完全不可分基指數(shù)的上界.

推論2設(shè)SSPn且有1個(gè)哈密頓圈,則ρ(S)≤n(n+1).

證明若SSPn且有1個(gè)哈密頓圈,則S的所有點(diǎn)(即n個(gè)點(diǎn))均落于長為n的有向圈上. 由定理2可得:ρ(S)≤n(2n-n+1)=n(n+1). 證畢.

推論3設(shè)SSPn且其直徑為d,則ρ(S)≤2d(2n-d).

證明由于S的直徑為d,則其存在長為s≤2d的有向圈,包含t≥d+1個(gè)不同的頂點(diǎn). 由定理2導(dǎo)出:ρ(S)≤2d[2n-(d+1)+1]=2d(2n-d). 證畢.

推論4設(shè)SSSn(n階本原不可冪對稱符號矩陣集),則ρ(S)≤2(n+1).

證明因?yàn)镾SSn,所以S的所有點(diǎn)(即n個(gè)點(diǎn))均分別落于某個(gè)長為2的有向圈上. 結(jié)合定理2,有:ρ(S)≤2(2n-n+1)=2(n+1). 證畢.

推論5設(shè)SSTn(n階本原不可冪競賽符號矩陣集),則ρ(S)≤3(n+1).

證明若SSTn,則S的所有點(diǎn)(即n個(gè)點(diǎn))均分別落于某個(gè)長為3的有向圈上. 根據(jù)定理2可得:ρ(S)≤3(2n-n+1)=3(n+1). 證畢.

4　完全不可分基指數(shù)的推廣

作為完全不可分矩陣的推廣,SHEN等[11]引進(jìn)了w-不可分矩陣,并把(嚴(yán)格)完全不可分指數(shù)的研究推廣至(嚴(yán)格)w-不可分指數(shù)的研究上,其中w是滿足-n

定義4設(shè)A是n階廣義符號方陣,且w是滿足-n

注1設(shè)A是n階廣義符號方陣. 易見,A是(1-n)-模糊不可分的當(dāng)且僅當(dāng)A不是實(shí)矩陣,而A是(n-1)-模糊不可分的當(dāng)且僅當(dāng)A=#Jn. 特別地,1-模糊不可分廣義符號方陣正是完全模糊不可分廣義符號方陣.

對于w-模糊不可分的廣義符號方陣A,亦稱其伴隨廣義帶號有向圖S是w-模糊不可分的. 用圖論的語言,n階廣義帶號有向圖S是w-模糊不可分的當(dāng)且僅當(dāng)S中任一滿足1≤|X|=k≤min{n,n-w}的k點(diǎn)子集X都有|SR1(X)|≥k+w.

根據(jù)定義4,不難發(fā)現(xiàn):(1)w1-模糊不可分廣義符號方陣必然是(w1-1)-模糊不可分的,其中w1是滿足-n+1

定義5設(shè)A是n階本原不可冪(廣義)符號方陣,且w是滿足-n

用圖論的語言來描述w-不可分基指數(shù),有下述命題.

命題3設(shè)S是n階本原不可冪(廣義)帶號有向圖,且w是滿足-n

注意到:對于n階本原不可冪(廣義)符號方陣A,雖然Aεw(A)是w-模糊不可分的廣義符號方陣,但是并不保證對所有的正整數(shù)i (>εw(A)),Ai均是w-模糊不可分的. 因此,我們提出以下嚴(yán)格w-不可分基指數(shù)的概念.

[1]LIZS,HALLF,ESCHENBACHCA.Ontheperiodandbaseofasignpatternmatrix[J].LinearAlgebraandItsApplications, 1994, 212/213(94).

[2]柳柏濂. 組合矩陣論[M]. 北京: 科學(xué)出版社, 2005: 60-65.

[3]YOULH,SHAOJY,SHANHY.Boundsonthebasesofirreduciblegeneralizedsignpatternmatrices[J].LinearAlgebraandItsApplications, 2007, 427(2/3).

[4]SCHWARZ.ThesemigroupoffullyindecomposablerelationsandHallrelations[J].CzechoslovakMathematicalJournal, 1973, 23:151-163.

[5]BRUALDIRA,LIUBL.Fullyindecomposableexponentsofprimitivematrices[J].ProceedingsoftheAmericanMathematicalSociety, 1991, 112(4):1193-1201.

[6]CHAOCY.Onaconjectureofthesemigroupoffullyindecomposablerelations[J].CzechoslovakMathematicalJournal, 1977, 27:591-597.

[7]CHAOCY,ZHANGMC.Onthesemigroupoffullyindecomposablerelations[J].CzechoslovakMathematicalJournal, 1983, 33:314-319.

[8]LIUBL.OnfullyindecomposableexponentsforprimitiveBooleanmatriceswithsymmetricones[J].LinearandMultilinearAlgebra, 1992, 31:131-138.

[9]BONDYJA,MURTYUSR.Graphtheorywithapplications[M].London:TheMacmillanPressLtd, 1976.

[10]柳柏濂, 黃宇飛. 組合矩陣的結(jié)構(gòu)指數(shù)[M]. 北京: 科學(xué)出版社, 2015:30-33.

[11]SHENJ,GREGORYD,NEUFELDS.Exponentsofindecomposability[J].LinearAlgebraandItsApplications, 1999, 288(1):229-241.

【中文責(zé)編：莊曉瓊英文責(zé)編：肖菁】

Fully Indecomposable Bases of Primitive Non-Powerful Sign Pattern Matrices

HUANG Yufei1*, LIU Bolian2

(1.Guangzhou Civil Aviation College, Guangzhou 510403, China;2.School of Mathematical Sciences, South China Normal University, Guangzhou 510631, China)

The definition of indecomposability for generalized sign pattern matrices is extended firstly in this paper. The fully ambiguous indecomposable generalized sign pattern matrices and partly ambiguous decomposable generalized sign pattern matrices are then defined. Moreover, the (strict) fully indecomposable base for a primitive non-powerful (generalized) sign pattern matrix is put forward, which is the generalization of the (strict) fully indecomposable exponent for a primitive (0,1) matrix. Meanwhile, the graph depicts for (strict) indecomposable base is given, and some upper bounds for the (strict) fully indecomposable base of primitive non-powerful sign pattern matrices are obtained. Furthermore, the definitions of fully ambiguous indecomposable generalized sign pattern matrix and (strict) fully indecomposable base tow-ambiguous indecomposable generalized sign pattern matrix and (strict)w-indecomposable based are generalized respectively.

primitive; non-powerful; (generalized) sign pattern matrix; (strict) fully indecomposable base

2015-12-18《華南師范大學(xué)學(xué)報(bào)(自然科學(xué)版)》網(wǎng)址：http://journal.scnu.edu.cn/n

國家自然科學(xué)基金青年科學(xué)基金項(xiàng)目(11501139)

黃宇飛,講師,Email: fayger@qq.com.

O151.21

A

1000-5463(2016)04-0088-07