The combinatorial power of the companion matrix (Q1906799)

The explicit polynomials for all elements in an arbitrary power of the companion matrix depending on \(n\) variables are obtained using combinatorial methods. Several applications are discussed as well as the relationship with Waring's formula on symmetric functions, the general solution to homogeneous linear recurrence relations, the multiplicative inverse of formal power series, the generating function of compositions (of numbers), a unified approach to Chebyshev polynomials, Dickson polynomials of various kinds arising from the theory of finite fields and combinatorial expansions of Toeplitz matrices.