張 靜, 張仁忠

(通化師范學(xué)院數(shù)學(xué)系,吉林通化 134002)

極大代數(shù)上線性系統(tǒng)的3維最小實(shí)現(xiàn)的研究

張 靜, 張仁忠

(通化師范學(xué)院數(shù)學(xué)系,吉林通化 134002)

研究了極大代數(shù)上線性系統(tǒng)的3維最小實(shí)現(xiàn)問題,給出了特征方程為λ3⊕c0λ0=c2λ2⊕c1λ,當(dāng)c1=,c0=c1c2時(shí),無窮序列存在3維最小實(shí)現(xiàn)的充要條件.

極大代數(shù);最小實(shí)現(xiàn);周期序列

1 引 言

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

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

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

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

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

2 準(zhǔn)備工作

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

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

設(shè)矩陣A對應(yīng)的有向圖為G(A),在圖G(A)中由一個(gè)或幾個(gè)回路組成的總長度為k的回路的集合,且回路集合的結(jié)點(diǎn)數(shù)和弧數(shù)相同,則稱這個(gè)回路集合為k階回路集.若k階回路集中所含回路的個(gè)數(shù)為偶數(shù)ei(i∈0∪N,其中N為自然數(shù)的全體),則記回路集的權(quán)重為W(ei,k);若k階回路集中所含回路的個(gè)數(shù)為奇數(shù)oi(i∈0∪N),則記回路集的權(quá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 主要結(jié)果

證必要性.c0為一個(gè)2階單回路和一個(gè)自回路的權(quán)重之和,c1為一個(gè)2階單回路的權(quán)重,c2為一個(gè)自回路的權(quán)重.由c1=c22知c1為一權(quán)重最大的2階單回路的權(quán)重,c2當(dāng)然為權(quán)重最大的自回路的權(quán)重.又由c0=c1c2知權(quán)重為c1的某2階單回路與某個(gè)權(quán)重為c2的自回路沒有公共端點(diǎn).(當(dāng)有一個(gè)c時(shí),某c1與c2無公共端點(diǎn),當(dāng)有兩個(gè)c2時(shí),至少有兩個(gè)c1,但不可能有三個(gè)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,…,知序列元素之間的關(guān)系為gk+3= c2gk+2⊕c1gk+1,k=0,1,2,…,即情況①.

(B)若g0=b1d1.

圖1

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

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

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

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

圖2

4 結(jié)束語

本文以矩陣對應(yīng)的有向圖為工具,結(jié)合cn-k的圖論解釋,給出了特征方程為λ3⊕c0λ0=c2λ2⊕c1λ,當(dāng)系數(shù)c1=,c0=c1c2時(shí),無窮序列存在3維最小實(shí)現(xiàn)的充要條件,進(jìn)一步解決了存在3維最小實(shí)現(xiàn)的充要條件問題.

[1] 涂奉生.極大代數(shù)上線性系統(tǒng)的最小實(shí)現(xiàn)[C]∥1992中國控制與決策學(xué)術(shù)年會論文集.哈爾濱：《控制與決策》編輯部,1992：184-189.

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

[3] 孫志敏,陳文德.極大代數(shù)上線性系統(tǒng)的3維最小實(shí)現(xiàn)[J].系統(tǒng)科學(xué)與數(shù)學(xué),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

吉教科驗(yàn)字[2007]34號