Exact rational solution of the matrix equation A=p(X) by linearization

For any given complex n×n matrix A and any polynomial p with complex coefficients, methods to obtain all complex n×n matrix solutions X of A=p(X) have been discussed from as early as 1906: however, in practice the “solutions” obtained are only approximations (i.e. 2n2 truncated decimal expansions for the real and imaginary parts of the n2 entries of X). The present article treats the corresponding Diophantine problem where both A and p are defined over the rational field Q, and where, if rational solutions X exist, they are to be found exactly. A complete solution is given when A has no repeated eigenvalue, in which case all rational solutions X are obtained using only linear procedures and integer arithmetic. The method generalizes at once from Q to any finite algebraic extension of Q (or of any Zp).