On solutions of linear functional systems

Abstract

We describe a new direct algorithm for transforming a linear system of recurrences into an equivalent one with nonsingular leading or trailing matrix. Our algorithm, which is an improvement to the EG elimination method [2], uses only elementary linear algebra operations (ranks, kernels and determinants) to produce an equation satisfied by the degrees of the solutions with finite support. As a consequence, we can bound and compute the polynomial and rational solutions of very general linear functional systems such as systems of differential or (q—) difference equations.