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
wethenhavethematrixidentities
F1(n)=CnF1(0)andF2(n)=CnF2(0)
foralln∈.
Lemma2Inthenotationabove,wehavef1=Esf2ifandonlyif
F1(0)=CsF2(0),
foranys∈.(1)
Proof.Lets∈.Then
f1=Esf2 n∈:F1(n)=F2(n+s) n∈
F1(0)=CsF2(0),:CnF1(0)=Cn+sF2(0)
asclaimed.
Thusinordertosolvetheshiftequivalenceproblemforf1,f2,itremainstosolvethematrixequation(1).
3.2SolutionoftheMatrixEquation
LetC∈kr×rbeinvertible,andu,v∈kr.Weseekalls∈satisfyingthematrixequation¯r×rbeinvertiblesuchu=Csv.ConsidertheJordandecompositionofC,i.e.,letT,J∈k
thatC=T 1JTandJisoftheform
0···0αi1J10···0. .......... 0..... 0 .. J2.... (i=1,...,m), ....withJ=J= ....i.0 .... ... ..0 .... ...1 .0···0Jm0······0αi
whereeachαiisaneigenvalueofC.OwingtothecancellationofT 1withT,wehaveCs=T 1JsT,andsowearedoneifwe ndalls∈suchthatu¯=Jsv¯,whereu¯:=Tuandv¯:=Tv.
Since sJ10···0 s.... .J2. 0 (s∈),Js= . ...... ..0 sJm0···0
wecansolvetheproblemforeachJordanblockseparately.Theintersectionoftheindi-vidualsolutionsetsgivesthesetofallsolutions:
theelectronicjournalofcombinatorics13(2006),#R007