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