# Condition for a matrix to be a perfect power of an integer matrix

I have a question that seems to be rather simple but for I got no clue so far.

Let's say I have a matrix $$A$$ of size $$2\times 2$$ and integer entries. I want to know if there is a kind of test or characterization that can tell me if there exists an integer matrix $$B$$ such that $$B^k = A$$.

So far the only thing I got was the obvious restriction on the determinant of $$A$$ (it has to be an integer that is a perfect $$k$$-th power), but I was wondering if maybe some other (stronger) restriction on $$A$$ helps.

In my particular case, I had $$k=8$$. It seems to be that it could be possible that some characterization could exist for arbitrary $$k$$ (a characterization depending on $$k$$, certainly).

• If the eigenvalues of $A$ are all distinct, there are only finitely many $k$'th roots of $A$, and you can in principle construct each one and check whether its entries are integers. Nov 3, 2020 at 18:32
• Another necessary condition is that (for $n \times n$ matrices) the eigenvalues of $A$ are $k$'th powers of algebraic integers of degree at most $n$. Nov 3, 2020 at 18:35
• For instance $-4I$ is a fourth power, $-4I=\begin{bmatrix}1 & -1 \\1 & 1\end{bmatrix}^4$, but $-I$ is not. Nov 6, 2020 at 0:03

Here's a necessary condition. Write the symmetric polynomial $$(x+y)^k - x^k - y^k$$ as a polynomial in the elementary symmetric polynomials $$x+y$$ and $$xy$$, say $$(x+y)^k - x^k - y^k = F_k(x+y,xy).$$ Then a necessary condition for $$A\in\operatorname{SL}_2(\mathbb Z)$$ to be a $$k$$th power in $$\operatorname{SL}_2(\mathbb Z)$$ is that the following two conditions hold:

1. $$\det A$$ is the $$k$$'th power of an integer, say $$\det A=D^k$$.
2. The polynomial $$T^k - F_k(T,D) - \operatorname{Trace}(A)$$ has a root in $$\mathbb Z$$.

The proof is easy enough, since if $$B^k=A$$, then $$\operatorname{Trace}(B)$$ is an integer root of the polynomial.

In particular, for the case $$k=8$$, we have $$F_k(u,v) = 8u^6v-20u^4v^2+16u^2v^3-2v^4.$$ So every matrix satisfying $$B^8=A$$ has the property that $$\operatorname{Trace}(B)$$ is a root of the following polynomial, where $$D^k=\det(A)$$, $$T^8 - 8DT^6 + 20D^2T^4 -16 D^3T^2+2D^4 - \operatorname{Trace}(A).$$ In particular, if $$B$$ is required to have integer entries, then this polynomal has an integer root.

Here is the necessary and sufficient condition, in terms of $$\det A$$ and $$\text{tr}(A)$$, in order that a $$2\times2$$ matrix $$A$$ be the $$k$$-th power of some matrix with integer coefficients.

Edit.Edit, 11.11.2020 The proof.The proof, is essentially routine; yet I post everything for convenience, before I forget all details.

It is convenient to introduce the polynomials
$$P_k(x,y):=\sum_{j\ge0}(-1)^j{ k-j\choose j }x^{k-2j}y^j;$$ their relevance in this context being that the polynomial $$z^2-xz+y$$ divides the polynomial $$z^{k+2}-xP_{k+1}(x,y)z+yP_{k}(x,y)$$ (even as elements of $$\mathbb{Z}[x,y,z]$$; see below for other properties we need).

Characterization of the $$k$$-th powers in $$M_2(\mathbb Z)$$. Let $$k\ge0$$. A matrix $$A\in M_2 (\mathbb Z)$$ is a $$k$$-th power of an element of $$M_2 (\mathbb Z)$$ if and only if there are $$t,d$$ in $$\mathbb Z$$ such that

1. $$\det(A)=d^k$$

2. $$\text{tr}(A)=P_k(t,d)-P_{k-2}(t,d)d$$

3. $$P_{k-1}(t,d)$$ divides $$A+ P_{k-2}(t,d)d I$$

Precisely, if $$B\in M_2 (\mathbb Z)$$ verifies $$B^k=A$$ then $$d:=\det(B)$$ and $$t:=\text{tr}(B)$$ satisfy (1,2,3).

Conversely, if $$(d,t)$$ satisfy (1,2,3), there exists a $$B\in M_2 (\mathbb Z)$$ with characteristic polynomial $$z^2-tz+d$$. Precisely, if $$P_{k-1}(t,d)\ne0$$, it is unique, namely $$B:=\frac1{P_{k-1}(t,d)}\Big(A+ P_{k-2}(t,d)d I \Big).$$ If $$P_{k-1}(t,d)=0$$, then $$A=mI$$, is an integer multiple of the identity, and all the infinitely many $$B\in M_2 (\mathbb Z)$$ with with characteristic polynomial $$z^2-tz+d$$ satisfy $$B^k=A$$.

Proof. Assume $$A=B^k$$ and $$B\in M_2 (\mathbb Z)$$ and set $$t:=\text{tr}(B)$$ and $$d:=\det(B)$$. Then (1) is $$\det(A)=\det(B^k)=\det(B)^k=p^k$$. As seen above, the characteristic polynomial of $$B$$, $$p_B(z):=z^2-tz+d$$ divides the polynomial $$z^k-P_{k-1}(t,d)z+P_{k-2}(t,d)d$$, and since by Cayley-Hamilton $$B^2-tB+d=0$$, we also have $$B^k-P_{k-1}(t,d)B+P_{k-2}(t,d)d I=0,$$ so, taking the trace, we have $$\text{tr}(A)= P_{k-1}(t,d)t -2P_{k-2}(t,d)d$$, which is (2), while $$P_{k-1}(t,d)B= A+P_{k-2}(t,d)d I$$, is (3).

Conversely, assume the above conditions (1,2,3) hold for integers $$t,d$$. Consider first the case $$P_{k-1}(t,d)\ne0$$. So one can define $$B:=\frac1{P_{k-1}(t,d)}\Big(A+ P_{k-2}(t,d)d I \Big),$$ an element of $$M_2 (\mathbb Z)$$ thanks to (3). The trace and determinant of $$B$$ are then by (1,2), hidding the variables $$(t,d)$$ in the $$P_j$$ $$\text{tr}(B)=\frac{\text{tr}(A)+ 2P_{k-2}d}{P_{k-1} } = \frac{P_k +P_{k-2} d }{P_{k-1} } =\frac{ t P_{k-1} }{P_{k-1} } =t$$ $$\det(B)= \frac{\det\Big(A+ P_{k-2} d I \Big)}{P_{k-1} ^2} = \frac{P_{k-2}^2d^2 + \text{tr}(A)P_{k-2} d +\det(A) }{P_{k-1}^2}=$$ $$=\frac{P_{k-2}^2d^2 + \big(P_k-P_{k-2}d\big)P_{k-2}d +d^k }{P_{k-1}^2}=$$ $$=\frac{ P_kP_{k-2}d +d^k }{P_{k-1}^2}= d,$$ because $$P_{k-1}^2 -P_kP_{k-2} =d^{k-1}$$. Thus the characteristic polynomial of $$B$$ is $$z^2-tz+d$$, which implies $$B^k=P_{k-1}B-P_{k-2}d\, I=A$$. Finally, consider the case $$P_{k-1}(t,d)=0$$. By (3) $$A$$ is then a multiple of the identity, $$A=m I$$, for $$m:=-P_{k-2}(t,d)d$$. If $$m=0$$, any nilpotent $$B$$ has the wanted properties. If $$m\ne 0$$, let $$\lambda$$ and $$\mu$$ be the roots of $$z^2-tz+d$$, so $$t=\lambda+\mu$$ and $$d=\lambda\mu$$. Then we have $$\lambda\neq\mu$$, otherwise $$0=P_{k-1}(\lambda+\mu,\lambda\mu)=k\lambda^{k-1}$$ and $$\lambda=\mu=0=t=d$$ and $$A=0$$. Also (see below) $$0= P_{k-1}(\lambda+\mu,\lambda\mu)= \frac{\lambda^k-\mu^k}{\lambda-\mu}$$ whence $$\lambda^k=\mu^k$$, and $$m =-\lambda\mu P_{k-2}(\lambda+\mu,\lambda\mu)=-\frac{\lambda^k\mu-\mu^k\lambda}{\lambda-\mu} = \lambda^k=\mu^k.$$ Let $$B$$ one of the infinitely many matrices in $$M_2 (\mathbb Z)$$ with characteristic polynomial $$z^2-tz+d$$. Since $$\lambda\ne \mu$$, $$B$$ is diagonalizable, $$B=Q^{-1}\text{diag}(\lambda,\mu)Q$$, so $$B^k=Q^{-1}\text{diag}(\lambda^k,\mu^k)Q=Q^{-1}mIQ=mI=A,$$ ending the proof.

More details. The sequence of polynomials $$P_k(x,y)\in\mathbb{Z}[x,y]$$ is defined by the two-term recurrence $$\cases{P_{k+2}=xP_{k+1}-yP_k\\ P_0=1 \\ P_{-1}=0.}$$ One easily verifies by induction the expansion $$P_k(x,y):=\sum_{j\ge0}(-1)^j{ k-j\choose j }x^{k-2j}y^j;$$ in fact $$P_k$$ may also be presented in terms of the Chebyshev polynomials of the first kind as $$P_k(x,y^2)=y^kxT_k\big(\frac{x}{2y}\big)\in\mathbb{Z}[x,y^2]$$. They verify $$P_k(u+v,uv)=\frac{u^{k+1}-v^{k+1}}{u-v}=\sum_{j=0}^{k} u^jv^{k-j},$$ and, related to that, for all $$k\ge0$$ one has: $$z^{k+2}-P_{k+1}(x,y)z+yP_{k}(x,y)=\big(z^2-xz+y\big) \sum_{j=0}^kP_{k-j}(x,y)z^j,$$ both easily verified by induction. Finally, since they solve a two-term linear recursion, the Hankel determinant of order $$2$$ must be a $$1$$-term linear recurrence, and one finds $$P_{k}(x,y)^2-P_{k+1}(x,y)P_{k-1}(x,y)=y^{k}.$$

• rmk: if k has an integer factorization these conditions factorize correspondingly, as it has to be. For instance, for k=8, the polynomial $P_4(x,y)-yP(x,y)$, which is $x^8-F_8(x,y)$ in Joe Silverman's answer, is an iterated composition $$\left( \left( {x}^{2}-2\,y \right) ^{2}-2\,{y}^{2} \right) ^{2}-2\,{ y}^{4}=$$$$={x}^{8}-8\,{x}^{6}y+20\,{x}^{4}{y}^{2}-16\,{x}^{2}{y}^{3}+2\,{y }^{4}$$ (coming form the composition property of Chebyshev polynomials $T_n$) Nov 9, 2020 at 9:07
• is this generalizable to higher dimensions? Nov 14, 2020 at 2:42
• Yes to some extent, but I think is going to be more complicated. E.g., for $n=3$ we have a third degree characteristic polynomial $p_B=x^3+ax^2+bx+c$, which does have a sequence of multiples of the form $x^{k}+a_{k}x^2+b_kx+c_{k}$ with explicit coefficients depending on a sequence of polynomials satisfying a three-terms linear recurrence with characteristic polynomial $p_B$ . But then extracting $B$ from $A=B^k=-a_{k}B^2-b_kB-c_{k}$ requires solving a second degree equation. Nov 14, 2020 at 9:11

Here is a way to tackle this matrix equation. Every $$2 \times 2$$ matrix $$A$$ with coefficients in $$\mathbb{Z}$$ is annihilated by a monic polynomial of degree 2 with coefficients in $$\mathbb{Z}$$, namely by the characteristic polynomial $$\chi_A$$ of $$A$$. If $$A$$ is not scalar, then the ring $$\mathbb{Z}[A]$$ is isomorphic to $$\mathbb{Z}[X]/(\chi_A)$$, hence is a free abelian group of rank $$2$$.

Consider a solution $$B$$ to the equation $$B^k=A$$. Then $$\mathbb{Z}[A] \subset \mathbb{Z}[B]$$ and since $$B$$ satifies a monic equation with coefficients in $$\mathbb{Z}[A]$$, the extension $$\mathbb{Z}[A] \subset \mathbb{Z}[B]$$ is integral. In particular $$\mathbb{Z}[B]$$ must be contained in the integral closure of $$\mathbb{Z}[A]$$. Let $$n$$ be the index of $$\mathbb{Z}[A]$$ in its integral closure. The integer $$n$$ can be computed, since $$\mathbb{Z}[A]$$ is either a finite index subring of $$\mathbb{Z} \times \mathbb{Z}$$, or an order in a quadratic field $$K$$, in which case $$n$$ can be expressed in terms of the discriminants of the order and of the ring of integers of $$K$$.

It follows that any potential solution $$B$$ must satisfy $$nB = x + y A$$ for some $$x, y \in \mathbb{Z}$$. Raising to the power $$k$$, we get $$n^k B^k = (x+yA)^k = P(x,y) + Q(x,y) A$$ where $$P$$ and $$Q$$ are homogeneous polynomials of degree $$k$$ with integer coefficients. They are obtained by modding out $$(x+yA)^k$$ by the characteristic polynomial of $$A$$. We want $$n^k B^k = n^k A$$, which gives the system of equations $$P(x,y)=0$$ and $$Q(x,y)=n^k$$, to be solved in $$x,y \in \mathbb{Z}$$. Moreover, we should have $$x+yA \in n M_2(\mathbb{Z})$$. Conversely, if $$(x,y)$$ satisfies all these conditions, then $$B = (x+yA)/n$$ is a solution to the equation.

I believe that there are only finitely many solutions $$(x,y)$$, except in degenerate cases like $$A = 0$$ and $$k \geq 2$$, where we can take $$B = \begin{pmatrix} 0 & b \\ 0 & 0 \end{pmatrix}$$.

For $$k=8$$ (or more generally $$2^m$$), a necessary and sufficient condition on $$\text{tr}(A)$$ and $$\det(A)$$ may be given iterating the simpler condition to be a square of an integer matrix. On the practical side, the corresponding test requires checking a finite tree of cases of the form "$$x$$ is a perfect square" and "$$x$$ divide $$y$$" for integers.

Perfect squares. A square matrix $$A$$ of order $$2$$ is a square of some $$B\in M_2(\mathbb{Z})$$ if and only if, for some integers $$p$$ and $$b$$

i. $$\det(A)=p^2$$

ii. $$\text{tr}(A)+2p=b^2$$

iii. $$b$$ divides $$A+pI$$ (meaning all its coefficients).

Proof. Assume $$A=B^2$$. Then the above conditions are satisfied by $$p:=\det(B)$$ and $$b:=\text{tr}(B)$$. Indeed,(i) is $$\det(A)=\det(B^2)=\det(B)^2=p^2$$. By the Cayley–Hamilton formula, $$B^2-\text{tr}(B)B+\det(B)I=0,$$ that is $$A+pI=bB$$, proving (iii) Taking the trace this also gives $$\text{tr}(A)+2p=b^2$$, whence (ii) follows.

Conversely, assume the above condition holds. Then, if $$b\neq0$$ the matrix $$\displaystyle B:=\frac1b\big(A+pI\big)$$ by (ii) has $$\displaystyle\text{tr}(B)=\frac{\text{tr}(A)+2p}b=b$$ and also $$\det(B)=\frac1{b^2}\det(A+pI)=\frac{ p^2+\text{tr}(A)p+\det(A)}{b^2}=$$ $$=\frac{ p^2+(b^2-2p)p+p^2}{b^2}=p,$$ so the characteristic polynomial of $$B$$ is $$\lambda^2-p\lambda+b$$, which implies $$B^2=bB-pI=A$$.

If $$b=0$$, condition (iii) implies $$A+pI=0$$, therefore $$A$$ is a multiple of the identity, $$A=-pI$$, and has countably many square roots; if fact, for $$x,y,z\in\mathbb{Z}$$ such that $$yz= -x^2-p$$ (e.g. $$y=1, z=-x^2-p$$) $$\begin{bmatrix} x & z \\ y & -x \end{bmatrix}^2=\begin{bmatrix} -p & 0 \\ 0 & -p \end{bmatrix}.$$

$$\sim *\sim$$

Perfect eighth powers. A non-zero square matrix $$A$$ of order $$2$$ is $$D^8$$ for some $$D\in M_2(\mathbb{Z})$$ if and only if, there are integers $$p,b,c ,d$$ such that

i. $$\det(A)=p^8$$

ii. $$\text{tr}(A)+2p^4=b^2$$

iii. $$b+2p^2=c^2$$

iv. $$c+2p=d^2$$

v. $$bcd$$ divides $$A+(p^4+bp^2+bcp)I.$$

Proof. Assume $$A=D^8$$. Then we apply three times the necessity part for perfect squares with $$p=\det(D)$$, $$b= \text{tr}(D^4)$$, $$c= \text{tr}(D^2)$$, $$d= \text{tr}(D)$$, yielding to conditions (i) to (iv).
Also, Cayley–Hamilton now reads $$A+p^4I=bD^4$$, $$D^4+p^2I=cD^2$$, $$D^2+pI=dD$$, whence substituting $$bcdD =A+(p^4+bp^2+bcp)I.$$

Conversely, assume the above conditions. If $$A$$ is not a multiple of the identity, any $$k$$-th root of it is neither: by (v) then $$bcd\neq0$$. By three consecutive extractions of square roots as above one find an eighth root of $$A$$, $$\frac1{bcd}\big(A+(p^4+bp^2+bcp)I\big).$$ If $$A$$ is a multiple of the identity, by (i) either $$A=-p^4I$$ or $$A=p^4I$$. The former leads to $$b=0$$ via (ii) and to $$c=p=d=0$$, by the irrationality of $$\sqrt2$$, via (iii) and (iv) so $$A=0$$. If $$A=p^4$$, it has a fourth root $$pI$$, and a square root of it (necessarily a null-trace matrix, if $$p$$ is not a perfect square) is an eighth root of $$A$$.

$$\sim *\sim$$

Thus, checking if $$A$$ is an eighth power of an integer matrix, and having verified that $$\det(A)$$ is a perfect eighth power, one has to check a finite tree of cases: $$b=\pm(\text{tr}(A)+ 2\det(A)^{1/2})$$; $$c=\pm(\text{tr}(A)+ \det(A)^{1/4})$$; $$d=\pm\text{tr}(A)\pm\det(A)^{1/8}$$.

PART 1. I consider the generic case. The problem is as follows We randomly choose $$B\in M_2(\mathbb{Z})$$ and let $$A=B^k$$. $$k,A$$ are known and $$B$$ is unknown; find the $$X$$'s such that $$X^k=A$$.

i) Calculate $$p(x)$$, the characteristic polynomial of $$A$$, and let $$q(y)=p(y^k)$$.

ii) Factorise in irreducibles over $$\mathbb{Z}$$: $$q(y)=q_1(y)\cdots q_l(y)$$.

Generically, when $$k$$ is odd, there is exactly one factor $$q_i$$ of degree $$2$$ and, when $$n$$ is even, there are exactly two factors $$q_i,q_j$$ of degree $$2$$ corresponding to $$2$$ opposite values ​​of $$X$$.

For example, let $$q_1(y)$$ be one factor of degree $$2$$ and let $$Q$$ be its companion matrix. Then, there is an unknown matrix $$R\in M_2(\mathbb{Q})$$ s.t. $$A=RQ^kR^{-1}$$.

iii) Solve the equation $$RQ^k-AR=0$$ ($$4$$ linear equations in the $$4$$ unknowns $$(r_{i,j})$$'s). Generically, we obtain a vector space solution of dimension $$2$$, that is, a set of solutions that depends on $$2$$ parameters $$u,v$$.

iv) Randomly choose $$u,v$$; we obtain (except if we are very unlucky; in this case, make another choice) a particular matrix $$R$$ and we deduce the essential solution $$X=RQR^{-1}$$.

PART 2. If $$k$$ is not given,we calculate $$\delta=\det(A)$$; we are looking for the $$k$$ such that $$\delta$$ is a power $$k^{th}$$. There is only a finite number of possible values ​​of $$k$$, except when $$\delta=\pm 1$$.

Correction. For $$\delta=\pm 1$$, cf. the Silverman's post.

PART 3. If we randomly choose $$A$$, then, generically, $$\delta$$ is not a power; moreover, if by extraordinary $$\delta$$ is a power $$k^{th}$$, then, generically, the matrix $$R$$ cannot be made invertible.