Computing $k$-th roots of diagonalizable matrices with integer entries

Question

I have got a question concerning the roots of diagonalizable matrices with integer entries. I know that given a diagonalizable matrix I can compute easily a $k$-th root by computing its diagonal decomposition and taking the $k$-th root of the diagonal elements on the middle matrix.

Firstly, I was wondering whether it can help me somehow if I know that the diagonalizable matrix with integer matrices has a $k$-th root that has only integer entries in the computation? Is there another way or some way where I can use the additional knowledge about the entries?

Secondly, I was using Wolfram to get some $k$-th roots via diagonalisation, but in general it seems not to output the root with integer entries. Is there some efficient way to transform a given $k$-th root to one with integer entries if such a matrix exists?

For example, the $2 \times 2$-matrix $\left[\begin{array}{l}-3&2\\2&-1\end{array}\right]$ has the $3$rd root $\left[\begin{array}{l}-1&1\\1&0\end{array}\right]$ which can be easily checked, but how do I efficiently compute it? [Is there a way that is more efficient than diagonalizing it, taking the third root in the diagonal matrix and computing the product repeatedly multiplying the diagonal entries of the diagonal matrix with third roots of $1$ until I get an integer matrix?]

Interesting would be as well how the efficiency of other approach behaves with with respect to the size of the matrix or $k$.

Thank you very much in advance.

Answer 1

The following method works for every $n$, in the generic case (in particular when the eigenvalues are distinct). Let

$B=\begin{pmatrix}8575122907& 15665166770& 8425175847\\-3269081855& -5440457177& -3501145058\\11198886644& 19451961947& 10727299263\end{pmatrix}$

and we know that $B=A^5$ where $A\in M_3(\mathbb{Z})$. (We choose an odd power so that there is only one solution in the generic case). Note that I randomly chose $A$.

Step 1. The characteristic polynomial of $B$ $\chi_B(x)=x^3-13861964993x^2+11936172028314482259x+3752826292644727923435572224$.

Then $\chi_A(x)$ is a divisor in $\mathbb{Z}[x]$ of degree $3$ of $\chi_B(x^5)$. We obtain (with Maple) $\chi_A(x)=x^3-123x^2-1241x+327244$ because it's the unique divisor of degree $3$.

Thus $A$ is similar to its companion matrix (in the generic case).

$C=\begin{pmatrix}0& 0& -327244\\1& 0& 1241\\0& 1& 123\end{pmatrix}$.

Step 2. Let $E=C^5$. We calculate (Maple) the Frobenius forms of $B=QFQ^-1$ and of $E=Q_1F{Q_1}^{-1}$. Thus $B=Q{Q_1}^{-1}EQ_1Q^{-1}$ and, finally,

$A=Q{Q_1}^{-1}CQ_1Q^{-1}=\begin{pmatrix}27& 99& 92\\8& 29& -31\\69& 44& 67\end{pmatrix}$.

Answer 2

One can do it without too much trouble with $2 \times 2$ matrices.

The characteristic polynomial of $$ A^3 = \begin{bmatrix}-3&\phantom{-}2\\\phantom{-}2&-1\end{bmatrix} $$ is $x^2 + 4x - 1$. From here, we can find out that the characteristic polynomial of the cube root is $x^2 + x - 1$. (I'll save this computation until later.) So if $A$ is the cube root matrix, we have $A^2 = I - A$, so $A^3 = A - A^2 = 2A - I$, so $A = \frac12(A^3 + I)$. We know $A^3$, so we can find $A$.

To do the characteristic polynomial calculation: let $x^2 + 4x - 1 = (x-r^3)(x-s^3)$, so that we want to find $(x-r)(x-s) = x^2+px+q$. The polynomial $x^6 + 4x^3 - 1$ is $(x^3-r^3)(x^3-s^3)$, so it will have an $x^2+px+q$ factor, as well as factors for the other roots. So we have $$ x^6+4x^3-1 = (x^2+px+q)(\omega^2x^2 + \omega px + q)(\omega^4 x^2 + \omega^2 px + q) $$ where $\omega = e^{2\pi i/3}$. Expand this out and we conclude first that $q=-1$ and second that $p^3+3p=4$, which has $p=1$ as its only rational root.

What about $n \times n$ matrices in general? The first problem is that the characteristic polynomial of the $k^{\text{th}}$ root matrix is harder to find. Once that's done, we can use the characteristic polynomial to write up a system of equations, giving us $I, A^k, A^{2k}, \dots, A^{k^2-k}$ in terms of $I, A, A^2, \dots, A^{k-1}$. We know the first sequence of matrices (they are powers of the matrix $A^k$ we are given), so we can solve for the second sequence of matrices, giving us in particular $A$.

This is longwinded but necessary for general $n$. For $n \ge 5$, we cannot make progress with this problem in general, so we have to use the assumption that the $k^{\text{th}}$ root matrix is integral somehow. I expect that this can make the computation of its characteristic polynomial work, though I don't quite see the details. Once you have the characteristic polynomial, things become straightforward.