Sharp algebraic periodicity conditions for linear higher order difference equations

In this paper we give easily verifiable, but sharp (in most cases necessary and sufficient) algebraic conditions for the solutions of systems of higher order linear difference equations to be periodic. The main tool in our investigation is a transformation, recently introduced by the authors, which formulates a given higher order recursion as a first order difference equation in the phase space. The periodicity conditions are formulated in terms of the so-called companion matrices and the coefficients of the given higher order equation, as well.