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

Question

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).

Answer 1

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.

Answer 2

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}.$$

---

Answer 3

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}$.

Answer 4

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}$.

Answer 5

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.