Shift Equivalence of P-finite Sequences(8)

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

Algorithm1

INPUT:AmatrixC∈kr×r,vectorsu=(u1,...,ur),v=(v1,...,vr)∈kr

OUTPUT:Alls∈suchthatu=Csv

1function

JordanblockJiofJdo

S

NowassumethatJ∈kr×rconsistsofasingleJordanblock,andletα=0beitseigenvalue.Wecanassumewithoutlossofgeneralitythatu¯r=0=v¯r.(Otherwise:Ifu¯=v¯=0,thesolutionsetis.Ifu¯r=v¯r=0wecandropthelastentriesofu¯,v¯andthelastrowandthelastcolumnfromJ,anditerateifnecessary.Ifu¯r=0andv¯r=0oru¯r=0andv¯r=0,thenthesolutionsetis .)Ascanbeshowneasilybyinduction,wehave s s (r 1) s s 2 s s αsαs 1

2α···r αα10···01. . .................. 0 0... . ..s...... (s∈). ss 2......0 = .......J= ...α 2 .......ss 1.. ...1...αsα

0······0α0······0αs

Ifr=1,thesolutionsetforu¯=Jv¯issimplygivenby

{s∈:u¯r/v¯r=αs}.

Ifr>1,thenthelasttworowsofthematrixequationyield

u¯r 1=αsv¯r 1+sαs 1v¯r=

u¯r v¯r 1u¯rαu¯r

2ifsolveMESingleJordanBlock(J,u,v;k)return