Shift Equivalence of P-finite Sequences(5)

We present an algorithm which decides the shift equivalence problem for Pfinite sequences. A sequence is called P-finite if it satisfies a homogeneous linear recurrence equation with polynomial coefficients. Two sequences are called shift equivalent if shi

Proposition2Letf:→kbeannihilatedbyL∈k[n][E],andletA=a0(n)+a1(n)E+···+ar(n)Er∈k[n][E],B=b0(n)+b1(n)E+···+bs(n)Es∈k[n][E]besuchthatL=AB.ThenB·f=0ifandonlyif(B·f)(n)=0forn=0,...,max(0,n0)+r,wheren0isthegreatestintegerrootofar.

Proof.Firstofall,wehave(A·g)(n)=0forn=0,...,max(0,n0)+rifandonlyifgisthezerosequence.Forn>max(0,n0),thiscanbeseenbyinduction:

ar(n)g(n+r)=a0(n)g(n)+a1(n)g(n+1)+···+ar 1(n)g(n+r 1)

=a0(n)0+a1(n)0+···+ar 1(n)0=0,

hence,sincear(n)=0,wemusthaveg(n+r)=0.Nowtakeg=B·f.ThenA·(B·f)=(AB)·f=L·f=0impliestheclaim.

NotethatAcanbecomputedfromLandBbyrightdivision,ifitisnotgiven.Alsonotethatmoregenerally,wecantestforanyL ∈k(n)[E]whetheritannihilatesfbyapplyingthepropositiontoB:=gcrd(L,L ).

2.2CharacteristicPolynomialandCompanionMatrix

ItwillbeconvenienttoadoptmatrixnotationforC- niteoperators.Iff:→kisC- nite,sayL·f=0forsomeL=Er a0 a1E ··· ar 1Er 1∈k[E],thenwehavethematrixidentity

010...0f(n)f(n+1)......... . ........ .. . .......= .......0 . f(n+r 1) 0······0f(n+r 2) 1

f(n+r 1)f(n+r)a0a1······ar 1

foreveryn∈.Ther×rmatrixinthisequationiscalledthecompanionmatrixofL.Iteratingtheaboveequationntimes,itfollowsthat

n f(0)010...0f(n+1)......... . ........... .......= , ......0 . . f(n+r 1) 0······0f(r 2) 1

f(r 1)a0a1······ar 1f(n+r)

thusanyvalueoffcanbeobtainedbymultiplyingthevectorofinitialvaluesbyasuitablepowerofthecompanionmatrix.

ThecharacteristicpolynomialofthecompanionmatrixispreciselyL.Forthisreason,Lisalsocalledthecharacteristicpolynomialofthesequencef.Wecanalwaysassumethata0=0bychangingtoanoperatoroflowerorder,ifnecessary.Inthiscase,thecompanionmatrixwillnothave0asaneigenvalue.

theelectronicjournalofcombinatorics13(2006),#R005

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库Shift Equivalence of P-finite Sequences(5)在线全文阅读。