On coefficients of powers of polynomials and their compositions over finite fields
For any given polynomial f over the finite field Fq with degree at most q−1, we associate it with a q×q matrix A(f)=(aik) consisting of coefficients of its powers (f(x))k=∑i=0q−1aikxi modulo xq−x for k=0,1,…,q−1. This matrix has some interesting properties such as A(g∘f)=A(f)A(g) where (g∘f)(x)=g(f(x)) is the composition of the polynomial g with the polynomial f. In particular, A(f(k))=(A(f))k for any k-th composition f(k) of f with k≥0. As a consequence, we prove that the rank of A(f) gives the cardinality of the value set of f. Moreover, if f is a permutation polynomial then the matrix associated with its inverse A(f(−1))=A(f)−1=PA(f)P where P is an antidiagonal permutation matrix. As an application, we study the period of a nonlinear congruential pseduorandom sequence aˉ={a0,a1,a2,...} generated by an=f(n)(a0) with initial value a0, in terms of the order of the associated matrix. Finally we show that A(f) is diagonalizable in some extension field of Fq when f is a permutation polynomial over Fq.
