An Algorithm for Computing Minimal Bidirectional Linear Recurrence Relations

We consider the problem of computing a linear recurrence relation (or equivalently a linear feedback shift register) of minimum order for a finite sequence over a field, with the additional requirement that not only the highest but also the lowest coefficient of the recurrence is nonzero. Such a recurrence relation can then be used to generate the sequence in both directions (increasing or decreasing order of indices), so we call it bidirectional. If the field is finite, a sequence is periodic if and only if it admits a bidirectional linear recurrence relation. For solving the above problem we propose an algorithm similar to the Berlekamp-Massey algorithm and prove its correctness. We describe the set of all solutions to this problem and show that if a sequence admits more than one linear recurrence relation then it admits a bidirectional one. We also prove some properties regarding the bidirectionality of the recurrences of the prefixes of the sequence.