# Rewriting a matrix as a polynomial

If a finite dimensional matrix $A$ is positive semidefinite, how can we write $A$ as a polynomial in $A^{2}$? Thanks.

-
Interesting question. How does it arise? –  user1551 Nov 30 '11 at 13:25
$A = q(A^2)$ for polynomial $q$ if and only if $\lambda = q(\lambda^2)$ for each eigenvalue $\lambda$ of $A$. Use Lagrange interpolation. If $A$ is $n \times n$, there is a solution of degree at most $n-1$.
Alternatively: knowing there is such a solution, write $q(t) = \sum_{j=0}^{n-1} a_j t^j$. Let $p(t)$ be the minimal polynomial of $A$ (which can be obtained from the squarefree factorization of the characteristic polynomial of $A$). We want $q(t^2) - t$ to be divisible by $p(t)$. If $r_j(t)$ is the remainder of $t^{2j}$ on division by $p(t)$, this says $\sum_{j = 0}^{n-1} a_j r_j(t) - t = 0$. Set to $0$ the coefficients of this for each power of $t$ from $t^0$ to $t^{n-1}$, and you have $n$ equations to solve for the $n$ coefficients $a_0, \ldots, a_{n-1}$. This version of the solution does not require solving for the eigenvalues, and in fact if the entries of $A$ are rational the computation uses only rational arithmetic and the result will have rational coefficients.