* Edwin Clark <eclark@math.usf.edu> [Mar 04. 2006 22:55]:
In discussing Creighton Dement's floretion generated sequences with him I came across the following fact:
Every sequence a(n) defined by a k-th order linear recurrence with constant coefficients over any commutative ring with identity can be realized in the form
a(n) = trace(B(A^n))
where A and B are k x k matrices over the ring in question.
Surely this must be known! Can someone provide a reference?
[Taking A to be the companion matrix of the polynomial defining the recurrence will clearly give a sequence satisfying a recurrence relation of order k with the desired coefficients then one just needs to fiddle with B to get the desired initial terms. One can take all entries of B to be 0 except for the last column and it is not too hard to find a formula for the last column of B in terms of the coefficients and initial conditions.]
--Edwin
Note that practical computations can be much accelerated via computations modulo the polynomial (cf. p.463 of the fxtbook, http://www.jjj.de/fxt/fxtpage.html#fxtbook ). I'd very much appreciate a reference for that one, too (found it myself). jj