王繪莉, 舒乾宇, 王學(xué)平

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

多機器交互生產(chǎn)過程是一類較為典型的管理應(yīng)用.當(dāng)該過程是多步生產(chǎn)問題時,描述該系統(tǒng)的定態(tài)問題即為max-plus代數(shù)上矩陣的本征問題.一般情況下,解決這類本征問題的算法大小為O(n3)[1].繼文獻[1]之后,max-plus代數(shù)上矩陣的本征問題被很多學(xué)者關(guān)注并深入研究.特別地,對于一些特殊形式的矩陣,計算本征問題的算法復(fù)雜度較一般情況有所降低[5-14].因此從降低算法復(fù)雜度的角度考慮研究特殊矩陣的本征問題是有重大意義的.P. Butkovicˇ等[5]給出一個O(n2)的算法計算雙值矩陣的極大圈平均.M. Gavalec等[6]給出一個O(n2)的算法計算Monge矩陣的極大圈平均.J. Plavka[7-9]討論了循環(huán)矩陣的本征問題、Monotone-Toeplitz矩陣的本征問題和l-parametric本征問題.K. Cechlrov[10]研究了interval矩陣的本征向量問題.隨后M. Gavalec等[11]給出能夠計算出Monge矩陣的一個本征向量的算法.M. Gavalec等[12]給出最快解決極值雙參數(shù)本征問題的算法.

本文在max-plus代數(shù)上討論一類特殊的矩陣,即analogy-transitive矩陣.首先討論analogy-transitive矩陣的基本性質(zhì),給出判定一個矩陣是否為analogy-transitive矩陣的判定定理及算法,其算法復(fù)雜度為O(n2).其次討論該類矩陣的極大圈平均問題、本征值本征向量問題.

1 預(yù)備知識

如果A是一個方陣,則A的k次冪記作Ak,且

Ak=A?Ak-1,

接下來基于文獻[5]給出一些基本概念及符號說明.設(shè)n是一個正整數(shù),Mn表示所有階為n的實矩陣的集合.Σ表示N={1,2,…,n}的子集的循環(huán)置換集(Σ中的元素稱為基本圈).設(shè)A=(aij)∈Mn,σ∈Σ,σ=(i1,…,ik),σ的權(quán)ω(σ,A)=ai1i2+ai2i3+…+aiki1,其中k稱為σ的長度,記作l(σ).進一步定義

(1)

λ(A)表示A的極大圈平均,即

(2)

由于Nc(A)中的元素在本征問題中有非常重要的作用,因此稱為A的關(guān)鍵結(jié)點或本征結(jié)點.如果μ(σ,A)=λ(A),則σ稱為DA中的關(guān)鍵圈.如果i,j∈Nc(A)屬于同一個關(guān)鍵圈,則稱i、j是等價的,記作i～j,否則稱作是不等價的,記作ij.顯然～構(gòu)成一個在Nc(A)上的等價關(guān)系.A的關(guān)鍵圖C(A)由A的關(guān)鍵圈所在的弧及結(jié)點集N構(gòu)成.

定理1.1[1]設(shè)A∈Mn,則λ(A)是A的唯一本征值.

找本征值λ(A)的問題已得到許多學(xué)者的廣泛討論,且給出不同的算法,其中較經(jīng)典的是1978年由Karp給出的大小為O(n3)的算法.

設(shè)矩陣B∈Mn,記Δ(B)=B⊕B2⊕…⊕Bn.令A(yù)λ=(λ(A))-1?A,文獻[1]證明了矩陣Δ(Aλ)至少包含一個對角線元素為0的列向量,且每一個這樣的列向量都是A的本征向量,稱為基本本征向量.易知每一個基本本征向量的線性組合也是一個本征向量.

記Δ(Aλ)=(γij)的列向量為g1,…,gn.由Δ(Aλ)的定義知γij表示DAλ中從i到j(luò)的最重路的權(quán).利用Floyd-Warshall算法,計算Δ(Aλ)需O(n3)步.因此找出Δ(Aλ)的列向量中所有的基本本征向量至多需要O(n3)步.由于A∈Mn,由定理2.1知λ(A)是A的唯一本征值,因此A的所有本征向量都對應(yīng)于本征值λ(A).記A的所有本征向量的集合為V(A),稱為A的本征空間,V(A)的維數(shù)記為pd(A).由以下2個定理易知pd(A)等于C(A)的關(guān)鍵分支的個數(shù),或者等于由A的所有基本本征向量所構(gòu)成的矩陣的列向量空間的任意一個基的基數(shù).已知計算一個矩陣的列向量空間的基的算法大小為O(n3)[15],那么計算pd(A)也需O(n3)步.

引理1.1[15]設(shè)A∈Mn,如果x=(x1,…,xn)T∈V(A),則

?gj.

定理1.2[1]設(shè)A∈Mn,如果i,j∈Nc(A),則存在某個α∈R使得gi=α?gj當(dāng)且僅當(dāng)i～j.

定理1.3[1]設(shè)A∈Mn,則

定理1.4[16]設(shè)A∈Mn,則V(A)是一個非平凡子空間且從(Nc(A),～)的每一個等價類中恰好取出一個向量gk便構(gòu)成V(A)的一個基.

2 Analogy-transitive矩陣

性質(zhì)2.1設(shè)A=(aij)為n階analogy-transitive矩陣,則有

(i)?i∈N,aii=0;

(ii)?1≤i,j≤n,aij=-aji.

證明(i) ?i∈N,由analogy-transitive矩陣的定義有aii+aii=aii,即2aii=aii,則aii=0;

(ii)若i=j,則由(i)的證明知aii=-aii=0.若i≠j,則由analogy-transitive矩陣的定義及(i)有aij+aji=aii=0,即aij=-aji.

如果一個矩陣是analogy-transitive矩陣,則稱這個矩陣具有analogy-transitive性質(zhì).由analogy-transitive矩陣的定義及性質(zhì),給出一個判定analogy-transitive矩陣的充分必要條件.

定理2.1A=(aij)∈Mn是analogy-transitive矩陣當(dāng)且僅當(dāng)

(i)?i∈N,aii=0;

(ii)?i,j∈N,i≠j,aij=-aji;

(iii)?2≤i

證明必要性已知A=(aij)∈Mn是analogy-transitive矩陣,則由性質(zhì)2.1知(i)、(ii)成立.由定義2.1,?i,j∈N,有a1i+aij=a1j,即aij=a1j-a1i.

充分性由定義2.1,只需證明?i,j,k∈N,aik+akj=aij成立.以下分4種情況進行證明.

1)當(dāng)i=j=k時,則由(i)有aii+aii=aii=0.

2)當(dāng)i=k≠j或i≠j=k時,不妨設(shè)i=k≠j,則aii+aij=0+aij=aij;當(dāng)i≠j=k時同理可證.

3)當(dāng)i=j≠k時,由(i)、(ii)有aik+aki=aik-aik=0=aii.

4)當(dāng)i、j、k互不相等時,若i=1,不妨設(shè)ki>1,則ai1+a1j=a1j-a1i=aij.

若i、j、k均不等于1,不妨設(shè)i

綜上,?i,j,k∈N,aik+akj=aij成立.

由以上的analogy-transitive矩陣判定定理易知,任意1個analogy-transitive矩陣的所有元素只需由a12,a13…,a1n這n-1個元素完全刻畫,且刻畫是唯一的.反過來,任意1個n-1維實向量x=(x1,x2,…,xn-1),令a12=x1,a13=x2,…,a1n=xn-1,則由判定定理中的(i)～(iii)可知a12,a13…,a1n可唯一確定1個analogy-transitive矩陣的所有元素,即n-1維實向量與analogy-transitive矩陣一一對應(yīng).

事實上analogy-transitive矩陣的判定定理提供了一種判斷一個矩陣是否為analogy-transitive矩陣的算法.

定理2.2設(shè)A=(aij)∈Mn,存在一種檢驗A是否具有analogy-transitive性質(zhì)的算法,算法復(fù)雜度為O(n2).

3 Analogy-transitive矩陣的本征問題

定理3.1設(shè)A=(aij)∈Mn是analogy-transitive矩陣,則λ(A)=0.

證明設(shè)DA中任意長度大于等于2的圈σ=(i1,i2,…,il,i1)(l≥2),

ω(σ,A)=ai1i2+ai2i3+ai3i4…+ail-1il+aili1=

ai1i3+ai3i4…+ail-1il+aili1=

ai1i4+…+ail-1il+aili1=

?

ai1i1=0,

因此得

再考慮所有自環(huán)?i∈N,aii=0,則

λ(A)=0.

命題3.1設(shè)A=(aij)∈Mn是analogy-transitive矩陣,則A2=A.

證明A是analogy-transitive矩陣,則?i,j,l∈N,aik+akj=aij.因此

即A2=A.

定理3.2設(shè)A=(aij)∈Mn是analogy-transitive矩陣,則本征空間V(A)={α?Aj:α∈R,?j∈N}.

證明對于analogy-transitive矩陣,λ(A)=0是其唯一的本征值,則Aλ=A,因此Δ(Aλ)=A⊕A2⊕…⊕An,由命題3.1有A2=A,則Δ(Aλ)=A.接下來找出Δ(Aλ)中對角線元素為0的列向量.由analogy-transitive矩陣的定義知?i∈N,aii=0,即Nc(A)=N且Δ(Aλ)=A中所有列向量都是A的本征向量.再由analogy-transitive矩陣的定義,對于1≤i,j≤n,且i≠j,有alj=ali+aij,?l∈N,即Aj=aij?Ai,也即gj=aij?gi,由定理1.2,i～j,即關(guān)鍵結(jié)點集Nc(A)關(guān)于“～”有且僅有1個等價類.因此對于1個analogy-transitive矩陣,其本征空間為

由定理3.2的證明易知1個analogy-transitive矩陣A的本征空間的基為

{Aj:j∈N},

即pd(A)=1.

定理3.3設(shè)A=(aij)∈Mn是analogy-transitive矩陣,則存在一個算法計算出A的本征值及所有本征向量,算法復(fù)雜度為O(n2).

[1] Cuninghame-Green R A. Minimax Algebra[M]. New York:Springer-Verlag,1979.

[2] Cuninghame-Green R A. Minimax Algebra and Applications[J]. Adv in Imaging and Electron Physics,1995,90:1-121.

[3] Gondran M, Minoux M. Linear algebra of dio?ds: a survey of recent results[J]. Ann Discrete Math,1984,19:147-164.

[4] Zimmermann U. Linear and combinatorial optimization in ordered algebra structures[J]. Ann Discrete Math,1981,10:379.

[5] Butkovicˇ P, Cuninghame-Green R A. AnO(n2) algorithm for the maximum cycle mean of ann×nbivalent matrix[J]. Discrete Appl Math,1992,35:157-163.

[6] Gavalec M, Plavka J. AnO(n2) algorithm for maximum cycle mean of Monge matrices in max-algebra[J]. Discrete Appl Math,2003,127:651-656.

[7] Plavka J. On eigenproblem for circulant matrices in max-algebra[J]. Optimization,2001,50:477-483.

[8] Plavka J. Eigenproblem for monotone and toeplitz matrices in a max-algebra[J]. Optimization,2003,53:95-101.

[9] Plavka J. L-parametric eigenproblem in max algebra[J]. Discrete Appl Math,2005,150:16-28.

[11] Gavalec M, Plavka J. Computing an eigenvector of a monge matrix in max-plus algebra[J]. Math Methods Operation Research,2006,62:543-551.

[12] Gavalec M, Plavka J. Fast algorithm for extremal biparametric eigenproblem[J]. Acta Electrotechnica et Informatica,2007,7:23-27.

[13] Cuninghame-Green R A, Butkovicˇ P. Extremal eigenproblem for bivalent matrices[J]. Linear Algebra and Its Appl,1995,222:77-89.

[14] Plavka J. Static maximum cycle mean problem of a trivalent matrix[J]. Optimization,1996,37:171-176.

[15] Butkovicˇ P. Max-linear Systems: Theory and Algorithms[M]. London:Springer-Verlag,2010.

[16] Akian M, Gaubert S, Walsh C. Discrete max-plus spectral theory[J]. Idempotent Mathematics and Mathematical Physics,2005,377:53-77.

[17] Butkovicˇ P, Schneider H, Sergeev S. Generators, extremals and bases of max cones[J]. Linear Algebra and Its Applications,2007,421(2):394-406.

[18] Butkovicˇ P. Max-algebra: the linear algebra of combinatorics?[J]. Linear Algebra and Its Applications,2003,367:313-335.

[19] Butkovicˇ P, Zimmermann K. A strongly polynomial algorithm for solving two-sided linear systems in max-algebra[J]. Discrete Appl Math,2006,154(3):437-446.

[20] Butkovicˇ P, Cuninghame-Green R A, Gaubert S. Reducible spectral theory with applications to the robustness of matrices in max-algebra[J]. SIAM J Matrix Anal Appl,2009,31(3):1412-1431.

[21] Butkovicˇ P, Lewis S. On the job rotation problem[J]. Discrete Optimization,2007,4(2):163-174.

[22] Burkard R E, Butkovicˇ P. Max algebra and the linear assignment problem[J]. Math Programming,2003,98(1/2/3):415-429.

[23] Cuninghame-Green R A, Butkovicˇ P. Discrete-event dynamic systems: the strictly convex case[J]. Ann Operations Research,1995,57(1):45-63.

[24] Butkovic P. On properties of solution sets of extremal linear programs[J]. Ann Discrete Math,1984,19:41-54.

[25] Butkovic P, Gaubert S. Sign-nonsingular matrices and matrices with unbalanced determinant in symmetrised semirings[J]. Linear Algebra and Its Applications,1999,301:195-201.

[26] Butkovic P. Simple image set of (max,+) linear mappings[J]. Discrete Applied Mathematics,2000,105:73-86.

[27] Butkovic P, MacCaig M. On integer eigenvectors and subeigenvectors in the max-plus algebra[J]. Linear Algebra and Its Applications,2013,438:3408-3424.

[28] Butkovic P, MacCaig M. On the integer max-linear programming problem[J]. Discrete Applied Mathematics,2014,162:128-141.