極大代數上線性系統的3維最小實現的研究

張 靜, 張仁忠

(通化師范學院數學系,吉林通化 134002)

極大代數上線性系統的3維最小實現的研究

張 靜, 張仁忠

(通化師范學院數學系,吉林通化 134002)

研究了極大代數上線性系統的3維最小實現問題,給出了特征方程為λ3⊕c0λ0=c2λ2⊕c1λ,當c1=,c0=c1c2時,無窮序列存在3維最小實現的充要條件.

極大代數;最小實現;周期序列

1 引 言

(1.2)稱為(1.1)的一個實現,(1.1)稱為可實現序列.若(1.2)的維數均小于或等于(1.1)中任意一個實現的維數,則(1.2)稱為(1.1)的最小實現,且A的階數稱為最小實現的維數.

求最小實現問題是線性系統研究中的一個困難問題,近20年來,國內外許多學者對該問題做了研究,并取得了一系列成果.但尋找存在n維最小實現的充要條件這一問題尚未得到解決,文[1]曾在這方面做了重要探索,給出了一個充要條件,由于至今沒有給出該條件的嚴密證明,將其稱為涂奉生猜想.

涂奉生猜想[1]無窮序列0∞存在n維最小實現的充分必要條件為它是一個n階周期序列.

文[2]給出了存在1維與2維最小實現的充要條件,徹底解決了1維與2維最小實現問題,并說明了涂奉生猜想在小于等于2維的情況下成立,但在大于2維的情況下不成立.文[3]研究了幾類3階周期序列的3維最小實現問題,得到了大部分3階周期序列存在3維最小實現的充要條件.

本文研究了文[3]未解決的特征方程為λ3⊕c0λ0=c2λ2⊕c1λ,當c1=,c0=c1c2時,序列存在3維最小實現的充要條件問題.

2 準備工作

定義2.1[4]設A為極大代數上n×n矩陣,對于λ≠ε,若存在向量X,使得AX=λX,則稱λ為A的一個特征值,X稱為特征向量,A的特征方程定義為

其中N∪￣N={2,3,…,n},N∩￣N=?,系數cn-k的圖論解釋如下:

設矩陣A對應的有向圖為G(A),在圖G(A)中由一個或幾個回路組成的總長度為k的回路的集合,且回路集合的結點數和弧數相同,則稱這個回路集合為k階回路集.若k階回路集中所含回路的個數為偶數ei(i∈0∪N,其中N為自然數的全體),則記回路集的權重為W(ei,k);若k階回路集中所含回路的個數為奇數oi(i∈0∪N),則記回路集的權重為W(oi,k).對于?v∈R,記Ne=‖{i;W(ei,k)=v}‖No=‖{i;W(oi,k)=v}‖,則cn-k=max{v,Ne≠No},其中若Ne＞No,則k∈N;若Ne＜No,則k∈

3 主要結果

證必要性.c0為一個2階單回路和一個自回路的權重之和,c1為一個2階單回路的權重,c2為一個自回路的權重.由c1=c22知c1為一權重最大的2階單回路的權重,c2當然為權重最大的自回路的權重.又由c0=c1c2知權重為c1的某2階單回路與某個權重為c2的自回路沒有公共端點.(當有一個c時,某c1與c2無公共端點,當有兩個c2時,至少有兩個c1,但不可能有三個c2.)

一、若c′1=c1,分兩種情況討論,在置換的意義下簡圖如圖1.

(A)若g0=b2d2⊕b3d3,則gk+3≥c′1c2gk=c0gk,k=0,1,2,…由序列滿足gk+3⊕c0gk=c2gk+2⊕c1gk+1,k=0,1,2,…,知序列元素之間的關系為gk+3= c2gk+2⊕c1gk+1,k=0,1,2,…,即情況①.

(B)若g0=b1d1.

圖1

(A)若a=c2,則存在另一個權為c1的2階單回路,在置換的意義下簡圖如圖2,則由圖可知gk+3≥c1c2gk=c0gk,k=0,1,2,…由序列滿足gk+3⊕c0gk=c2gk+2⊕c1gk+1,k=0,1,2,…,知序列元素之間的關系為gk+3=c2gk+2⊕c1gk+1,k=0,1,2,…,即情況①.

(B)若a＜c2,簡圖如圖1.

(i)若g0=b1d1(同法可證g0=b2d2的情況),則有g1≥ag0,g2≥c1g0.

(a)若g1=ag0,則g3≥c1g1.

圖2

4 結束語

本文以矩陣對應的有向圖為工具,結合cn-k的圖論解釋,給出了特征方程為λ3⊕c0λ0=c2λ2⊕c1λ,當系數c1=,c0=c1c2時,無窮序列存在3維最小實現的充要條件,進一步解決了存在3維最小實現的充要條件問題.

[1] 涂奉生.極大代數上線性系統的最小實現[C]∥1992中國控制與決策學術年會論文集.哈爾濱：《控制與決策》編輯部,1992：184-189.

[2] 孫志敏,陳文德,于洪年.極大代數上線性系統的最小實現[J].控制與決策,2006,21(5)：521-526.

[3] 孫志敏,陳文德.極大代數上線性系統的3維最小實現[J].系統科學與數學,2007,27(4)：499-509.

[4] Blondel V D,Portier N.The minimal realization problem in the max-plus semiring and pisot’s problem are NP-hard [J].C.R.Acad.Sci.Paris,t,333,SérieI.2001：1127-1130.

On 3-dimensional Minimal Realization in Linear System of Max-algebra

Z HA N G J ing, Z HA N G Ren-zhong
(Department of Mathematics,Tonghua Normal College,Tonghua,Jilin 134002,China)

The 3-dimensional minimal realization of linear system in the max-algebra is studied.The necessary and sufficient condition for the existence of 3-dimensional minimal realization of the infinite sequenceis given,that the characteristic equation of the infinite sequence isλ3⊕c0λ0=c2λ2⊕c1λ,wherec1=,c0=c1c2.

max-algebra;minimal realization;periodic sequence

O231

A

1672-1454(2011)03-0030-06

2008-08-01;[修改日期]2008-11-27

吉教科驗字[2007]34號