非負矩陣譜半徑的brauer型估計

定義從a到（a）n，并記錄從n到{1、n}、ri（a）=jnaij、ri（a）=jn，i}，aij，in。關(guān)于非負矩陣譜半徑的估計,最早是Perron-Frobenius的結(jié)果:mini∈Nri(A)≤ρ(A)≤maxi∈Νri(A).雖然這個結(jié)果要早于Gerschorin定理,但它可看作是利用Gerschorin圓盤的右端點對ρ(A)作出估計,所以不妨仍然稱其為Gerschorin型估計.Brauer利用Cassini卵形域給出了非負矩陣譜半徑的Brauer型估計,改進了Perron-Frobenius的結(jié)果.M矩陣一個主要的等價表征指出M矩陣特征值的實部皆正,佟文廷推進了這一結(jié)果,得到M矩陣按模最小特征值是一個正數(shù);張家駒證明了M矩陣的實部最小特征值也是其按模最小特征值,并給出這一特征值的估計式:mini∈Nri(A)≤ω0(A)≤maxi∈Nri(A).同理,這個估計也稱為Gerschorin型的.之后,逄明賢進一步給出M矩陣最小特征值的Brauer型估計.本文利用Brauldi使用的通過有向圖的推證方法以及文獻引進的有向圖的1-path覆蓋,建立了非負矩陣的譜半徑與M矩陣最小特征值的Brauldi型估計和改進的Brauer型估計,從而改進了文獻中的相應(yīng)結(jié)果.1a的內(nèi)涵設(shè)Γ(A)表示A∈Cn×n的有向圖,N是其節(jié)點集合,E(A)={ei,j|aij≠0,i,j∈N}是其有向邊集合.有向邊序列γ:ei1,i2,ei2,i3,…,eis-1,is,eis,i1,其中s≥2,且諸i1,i2,…,is互不相同,稱為Γ(A)的簡單回路,簡記為γ:i1,i2,…,is,is+1=i1.簡單回路的全體記為C(A).Γ+(i)={j∈N|j≠i,ei,j∈E(A)}表示i在Γ(A)中的后繼集合.非空集合ν上的一個關(guān)系“?”稱為先序,如果“?”滿足:自反性與傳遞性,即a?a,?a∈ν;a?b及b?c蘊涵a?c,a,b,c∈ν.引理1.1設(shè)Γ(A)是A的有向圖,?是N上的一個先序.若?i∈N,Γ+(i)≠?,則在Γ(A)中存在一個簡單回路γ:i1,i2,…,is,is+1=i1,使得l?ij+1,?l∈Γ+(ij)?j=1,2,?,s.(1.1)定義1.1設(shè)γ:i1,i2,…,is,is+1(is+1=i1)∈C(A),η表示2與s的最大公約數(shù),τ=s/η,則集合{ei1,i2,ei1+η,i2+η,…,ei1+(τ-1)η,i2+(τ-1)η}稱為γ的奇1-path覆蓋;集合{ei2,i3,ei2+η,i3+η,…,ei2+(τ-1)η,i3+(τ-1)η}稱為γ的偶1-path覆蓋.γ一個確定的1-path覆蓋記為P1(γ).當s為正奇數(shù)時,γ的奇、偶1-path覆蓋相同,即γ僅有一個包含其所有s條有向邊的1-path覆蓋.當s為正偶數(shù)時,γ有2個各包含其s/2條有向邊的奇、偶1-path覆蓋.定義1.2對Γ(A)中的每個γ∈C(A),取定一個1-path覆蓋P1(γ),則稱Ρ1(A)=∪γ∈C(A)Ρ1(γ)為Γ(A)的一個1-path覆蓋.若A是n≥2階的可約矩陣,則有置換陣P,使得ΡAΡΤ=(A11A12?A1Κ0A22?A2Κ????0?0AΚΚ)?2≤Κ≤n?(1.2)其中Att為A的nt階主子陣,其或為不可約矩陣,或是1階零矩陣,Κ∑t=1nt=n.式(1.2)中右端矩陣稱為A的約化法式.若不計Att的次序,法式(1.2)與P的選擇無關(guān),因此式(1.2)惟一地確定集合N={1,…,n}的劃分N1,…,NK對應(yīng)于A11,…,AKK的足碼集合.當A為不可約矩陣或1階零矩陣時,為統(tǒng)一,也記A=(A11),這時n1=n,N1=N.記α=∪nt≥2,1≤t≤ΚNt?ΘA={aii為A的主對角元|i∈N\α},易見α={i∈N|i∈γ∈C(A)}.定義1.3A∈Cn×n,如果N=α,則A是弱不可約矩陣,記為A∈WI.對于一般矩陣,如果α≠?,則稱A[α]為A的弱不可約核,記為?.當α=?時,記?=?.2raaaaa規(guī)定:max?=min?=0.顯然有:引理2.1設(shè)a1,…,an∈R,N={1,…,n},T?N.定義函數(shù)f(x)=∏i∈T(x-ai),則當x≥maxi∈T{ai}時,f(x)嚴格單調(diào)增加.定理2.1設(shè)A=(aij)≥0,對?γ∈C(A),用rA(γ)表示方程∏i∈γ(x-aii)=∏i∈γRi(?A)的大于maxi∈γ{aii}的實根,并記mrc(A)=max{minγ∈C(A)rA(γ),maxΘA}?Μrc(A)=max{maxγ∈C(A)rA(γ),maxΘA}.則對A的譜半徑ρ(A)有估計:mrc(A)≤ρ(A)≤Mrc(A).證明:(1)A為不可約矩陣.設(shè)x=(x1,…,xn)T>0是A的屬于特征值ρ(A)的特征向量.在Γ(A)的節(jié)點集合N上定義先序?:i?j當且僅當xi≥xj.由引理2.1知,存在γ′:i1,i2,…,is,is+1(is+1=i1)∈C(A),使得xl≥xij+1,?l∈Γ+(xij)(j=1,…,s),于是由(ρ(A)-aijij)xij=∑p≠ijaijpxp=∑p∈Γ+(ij)aijpxp≥(∑p∈Γ+(ij)aijp)xij+1=Rij(A)xij+1,j=1,?,s?可得s∏j=1(ρ(A)-aijij)s∏j=1xij≥s∏j=1Rij(A)s∏j=1xij+1,從而有s∏j=1(ρ(A)-aijij)≥s∏j=1Rij(A),即∏i∈γ′(ρ(A)-aii)≥∏i∈γ′Ri(A).(2.1)類似地,在Γ(A)的節(jié)點集合N上定義先序?:i?j當且僅當xi≤xj.由引理2.1知,存在γ″:i1,i2,…,is,is+1(is+1=i1)∈C(A),使得xl≤xij+1,?l∈Γ+(xij)(j=1,…,s).仿上可以得到∏i∈γ″(ρ(A)-aii)≤∏i∈γ″Ri(A).(2.2)再注意到ρ(A)≥maxi∈γ′{aii}及ρ(A)≥maxi∈γ″{aii},由引理2.1\,式(2.1)與(2.2)即可推出minγ∈C(A)rA(γ)≤rA(γ′)≤ρ(A)≤rA(γ″)≤maxγ∈C(A)rA(γ)?即mrc(A)≤ρ(A)≤Mrc(A).(2)A為弱不可約矩陣.不妨設(shè)A已有法式(1.2),此時諸Att為階數(shù)大于等于2的不可約矩陣.分兩步證明:1)因為Ri(?)=Ri(AKK),?i∈NK.由(1)易知ρ(A)≥ρ(AΚΚ)≥mrc(AΚΚ)=minγ∈C(AΚΚ)rAΚΚ(γ)=minγ∈C(AΚΚ)rA(γ)≥minγ∈C(A)rA(γ).2)設(shè)t*使得ρ(A)=ρ(At*t*),由(1)易知ρ(A)=ρ(At*t*)≤Μrc(At*t*)=maxγ∈C(At*t*)rAt*t*(γ)=maxγ∈C(At*t*)rA(γ)≤maxγ∈C(A)rA(γ).綜合1),2)有mrc(A)≤ρ(A)≤Mrc(A).(3)A為非弱不可約矩陣.注意到rA(γ)=r?(γ),C(A)=C(?),由(2)知minγ∈C(A)rA(γ)=minγ∈C(?)r?(γ)≤ρ(?)≤maxγ∈C(?)r?(γ)=maxγ∈C(A)rA(γ).因為ρ(A)=max{maxΘA,ρ(?)},于是max{minγ∈C(A)rA(γ),maxΘA}≤ρ(A)≤max{maxγ∈C(A)rA(γ),maxΘA},即mrc(A)≤ρ(A)≤Mrc(A).注2.1因mcr(A),Mcr(A)與有向圖有關(guān),當A是可約矩陣時,傳統(tǒng)的連續(xù)性推證方法不再有效,故可利用法式(1.2)完成證明.另外,在定理2.1中,rA(γ)必須通過Ri(?)定義,而不能直接由Ri(A)定義.定理2.1中rA(γ)的計算比較復(fù)雜,下面給出一個在實際估計中更為方便的結(jié)果.定理2.2設(shè)A=(aij)≥0,P1(A)是Γ(A)的1-path覆蓋.記rA(i,j)=12{aii+ajj+[(aii-ajj)2+4Ri(?)Rj(?)]12},mer(A)=max{minei,j∈Ρ1(A)rA(i,j),maxΘA},Μer(A)=max{maxei,j∈Ρ1(A)rA(i,j),maxΘA}.則對A的譜半徑ρ(A)有估計:mer(A)≤ρ(A)≤Mer(A).證明:若證mer(A)≤mcr(A),只需證對?γ∈C(A),存在ei,j∈P1(γ),使得rA(γ)≥rA(i,j).否則,存在γ:i1,i2,…,is,is+1(is+1=i1)∈C(A),使得rA(γ)<rA(i,j),?ei,j∈P1(γ),注意到rA(i,j)是方程(x-aii)(x-ajj)=Ri(?)Rj(?)大于max{aii,ajj}的實根,由引理2.1知(rA(γ)-aii)(rA(γ)-ajj)＜Ri(A?)Rj(A?),?ei,j∈Ρ1(γ).(2.3)將式(2.3)中各不等式相乘,有∏ei,j∈Ρ1(γ)(rA(γ)-aii)(rA(γ)-ajj)＜∏ei,j∈Ρ1(γ)Ri(A?)Rj(A?),即(∏i∈γ(rA(γ)-aii))δ＜(∏i∈γRi(A?))δ,當s為奇數(shù)時,δ=2;當s為偶數(shù)時,δ=1.進而有∏i∈γ(rA(γ)-aii)＜∏i∈γRi(A?),(2.4)再由引理2.1知,式(2.4)蘊涵rA(γ)<rA(γ),矛盾.同理可證Mcr(A)≤Mer(A).綜上,由定理2.1即得mre(A)≤ρ(A)≤Mer(A).注2.2定理2.1可以看作是利用特征值分布的Brauldi區(qū)域的右端點對ρ(A)作出估計,故可稱為Brauldi型估計.定理2.2則是改進的Brauer型估計,由于只需計算與簡單回路中的邊ei,j對應(yīng)的rA(i,j),特別當簡單回路的長度為偶數(shù)時,只需對回路中一半數(shù)量的邊所對應(yīng)的rA(i,j)進行計算,故計算量大為減少,同時精確度明顯提高.定理2.1與定理2.2均優(yōu)于Perron-Frobenius和Brauer的結(jié)果.3paa規(guī)定:max?=min?=+∞.定理3.1設(shè)A=(aij)∈Rn×n為非奇異M矩陣,對?γ∈C(A),用lA(γ)表示方程∏i∈γ(aii-x)=∏i∈γRi(A?)的小于mini∈γ{aii}的實根,并記mcl(A)=min{minγ∈C(A)lA(γ),minΘA}?Μcl(A)=min{maxγ∈C(A)lA(γ),maxΘA}.則對A的最小特征值ω0(A)有估計:mcl(A)≤ω0(A)≤Mcl(A).證明:設(shè)A=sI-B,B=(bij)n×n≥0,s>ρ(B),ρ(B)為B的譜半徑.易見ω0(A)=s-ρ(B)>0,由定理2.1知,mcr(B)≤ρ(B)≤Mcr(B),從而s-Mcr(B)≤ω0(A)≤s-mcr(B).首先注意到aii=s-bii,i∈N,進而再由lA(γ)與rA(γ)定義易知,lA(γ)=s-rB(γ).可得mcl(A)=min{minγ∈C(A)lA(γ),minΘA}=min{minγ∈C(B){s-rB(γ)},s-maxΘB}=s-max{maxγ∈C(B)rB(γ),maxΘB}=s-Μcr(B).同理可得Mcl(A)=s-mcr(B),故mcl(A)≤ω0(A)≤Mcl(A).類似地,容易得到:定理3.2設(shè)A=(aij)∈Rn×n為非奇異M矩陣,P1(A)是Γ(A)的1-path覆蓋.記lA(i,j)=12{aii+ajj-[(aii-ajj)2+4Ri(A?)Rj(A?)]12},mel(A)=min{minei,j∈Ρ1(A)lA(i,j),minΘA},Μel(A)=min{maxei,j∈Ρ1(A)lA(i,j),minΘA}.則對A的最小特征值ω0(A)有估計:mel(A)≤ω0(A)≤Mel(A).注3.1定理3.1與定理3.2分別是M矩陣最小特征值的Brauldi型估計和改進的Brauer型估計,它們均優(yōu)于文獻的結(jié)果.4b0.3,3,4,5-四氫-3,4,5-四氫-3,4,5-四氫-3,4,5-四氫-3,4,5-負矩陣2.例4.1考慮非負矩陣A=(8100012100015100012100018).經(jīng)計算ρ(A)=8.18014.由Gerschorin型估計有4≤ρ(A)≤9.因為rA(1,2)=rA(1,4)=rA(2,5)=rA(4,5)=8.31662,rA(1,5)=9,rA(2,4)=4,rA(2,3)=rA(3,4)=6,rA(1,3)=rA(3,5)=8.56155.由Brauer型估計有4≤ρ(A)≤9.取P1(A)={e1,2,e2,3,e3,4,e4,5},由定理2.2,有6≤ρ(A)≤8.31662.考慮非奇異M矩陣B=9I-A,由Gerschorin型估計和Brauer型估計只能得到0≤ω0(B)≤5,取P1(B)={e1,2,e2,3,e3,4,e4,5},由定理3.2有0.68338≤ω0(B)≤3.事實上,ω0(B)=0.81986.例4.2考慮非負矩陣A=(10.600020.600030.60.6004).經(jīng)計算ρ(A)=4.02080.由Gerschorin型估計有1.6≤ρ(A)≤4.6.因為rA(1,2)=2.28102,rA(1,3)=3.16619,rA(1,4)=4.11555,rA(2,3)=3.28102,rA(2,4)=4.16619,rA(3,4)=4.28102.由Brauer型估計有2.28102≤ρ(A)≤4