Max-plus代數中analogy-transitive矩陣及其本征問題

王繪莉, 舒乾宇, 王學平

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

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

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

1 預備知識

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

Ak=A?Ak-1,

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

(1)

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

(2)

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

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

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

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

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

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

?gj.

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

定理1.3[1]設A∈Mn,則

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

2 Analogy-transitive矩陣

性質2.1設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性質.由analogy-transitive矩陣的定義及性質,給出一個判定analogy-transitive矩陣的充分必要條件.

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

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

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

(iii)?2≤i

證明必要性已知A=(aij)∈Mn是analogy-transitive矩陣,則由性質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)當i=j=k時,則由(i)有aii+aii=aii=0.

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

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

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

若i、j、k均不等于1,不妨設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矩陣一一對應.

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

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

3 Analogy-transitive矩陣的本征問題

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

證明設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,

因此得

再考慮所有自環?i∈N,aii=0,則

λ(A)=0.

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

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

即A2=A.

定理3.2設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,即關鍵結點集Nc(A)關于“～”有且僅有1個等價類.因此對于1個analogy-transitive矩陣,其本征空間為

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

{Aj:j∈N},

即pd(A)=1.

定理3.3設A=(aij)∈Mn是analogy-transitive矩陣,則存在一個算法計算出A的本征值及所有本征向量,算法復雜度為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.