On coefficients of powers of polynomials and their compositionsover finite fields

For any given polynomial f over the finite field F_q with degree at most q-1, we associate it with a q × q matrix A(f) = (a_ik) consisting of coefficients of its powers (f(x))^k= ∫^q-1 _i=0 aikxⁱ modulo x^q-x for k = 0; 1 q-1. This matrix has some interesting properties such as A(gf) = A(f)A(g) where (gf)(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 ā = -a0, a1, a2, generated by an = f⁽ⁿ⁾(a₀) with initial value a₀, in terms of the order of the associated matrix. Finally we show that A(f) is diagonalizable in some extension field of F_q when f is a permutation polynomial over F_q.