---
abstract: 'The Matrix Torsion Problem (MTP) is: given a square matrix $M$ with rational entries, decide whether two distinct powers of $M$ are equal.  It has been shown by Cassaigne and the author that the MTP reduces to the Matrix Power Problem (MPP) in polynomial time [@CassaigneN08]: given two square matrices $A$ and $B$ with rational entries, the MTP is to decide whether $B$ is a power of $A$.  Since the MPP is decidable in polynomial time [@KannanL86], it is also the case of the MTP.  However, the algorithm for MPP is highly non-trivial.  The aim of this note is to present a simple, direct, polynomial-time algorithm for the MTP.' 
author:
- François Nicolas
bibliography:
- 'bibmat.bib'
title: 'A simple, polynomial-time algorithm for the matrix torsion problem'
---

Introduction
============

As usual ${\mathbb{N}}$, ${\mathbb{Q}}$ and ${\mathbb{C}}$ denote the semiring of non-negative integers, the field of rational numbers and the field of complex numbers, respectively. 

Let $M$ be a square matrix over ${\mathbb{C}}$. We say that $M$ is *torsion* if it satisfies the following three equivalent assertions. 

1.   There exist $p$, $q \in {\mathbb{N}}$ such that $p \ne q$ and $M^p = M^q$.

2.   The multiplicative semigroup $\left\{ M, M^2, M^3, M^4, \dotsc \right\}$ has finite cardinality. 

3.   The sequence $(M, M^2, M^3, M^4, \dotsc)$ is eventually periodic. 

The aim of this note is to present a polynomial-time algorithm for the following decision problem:

The *Matrix Torsion Problem (MTP)* is: given as input a square matrix $M$ over ${\mathbb{Q}}$, decide whether $M$ is torsion. 

For every square matrix $M$ over ${\mathbb{Q}}$, the size of $M$ is defined as the order of $M$ plus the sum of the lengths of the binary encodings over all entries of $M$.

#### Previous work. 

The Matrix Power Problem (MPP) is: given two square matrices $A$ and $B$ over ${\mathbb{Q}}$ decide whether there exists $n \in {\mathbb{N}}$ such that such that $A^n = B$. Kannan and Lipton showed that the MPP is decidable in polynomial time [@KannanL86].  It is rather easy to prove that the MTP is decidable in polynomial time by reduction to the MPP (see Section \[sec:comment\]).  However, the original algorithm for the MPP is highly non-trivial.  Hence, a simple, direct algorithm is still interesting. 

Generalities
============

Throughout this paper, ${\mathtt{z}}$ denotes an indeterminate.  The next result is well-known and plays a crucial role in the paper. 

\[prop:mult-root\] For every polynomial $\nu({\mathtt{z}})$ over ${\mathbb{C}}$, the polynomial $$\pi({\mathtt{z}}) {\mathrel{\mathop:}=}\dfrac{\nu({\mathtt{z}})}{\gcd(\nu'({\mathtt{z}}), \nu({\mathtt{z}}))}$$ satisfies the following two properties:

-   $\nu({\mathtt{z}})$ and $\pi({\mathtt{z}})$ have the same complex roots, and

-   $\pi({\mathtt{z}})$ has no multiple roots. 

The set of all positive integers is denoted ${\mathbb{N}^\ast}$.

For every $n \in {\mathbb{N}^\ast}$, the *$n^\text{th}$ cyclotomic polynomial* is denoted $\gamma_n({\mathtt{z}})$: $\gamma_n({\mathtt{z}}) = \prod ({\mathtt{z}}- u)$ where the product is over all primitive $n^\text{th}$ roots of unity $u \in {\mathbb{C}}$. It is well-known that $\gamma_n({\mathtt{z}})$ is a monic integer polynomial and that the following three properties hold [@LangAlgebra]:

\[prop:zm-1\] For every $m \in {\mathbb{N}^\ast}$, ${\mathtt{z}}^m - 1 = \prod_{n \in D_m} \gamma_n({\mathtt{z}})$, where $D_m$ denotes the set of all positive divisors of $m$.

\[prop:irreductible\] For every $n\in {\mathbb{N}^\ast}$, $\gamma_n({\mathtt{z}})$ is irreducible over ${\mathbb{Q}}$.

*Euler’s totient function* is denoted $\phi$: for every $n \in {\mathbb{N}^\ast}$, $\phi(n)$ equals the number of $k \in  \{ 1, 2, \dotsc, n \}$ such that $\gcd(k, n) = 1$.

\[prop:degre-phi\] For every $n \in {\mathbb{N}^\ast}$, $\gamma_n({\mathtt{z}})$ is of degree $\phi(n)$.

The next lower bound for Euler’s totient function is far from optimal.  However, it is sufficient for our purpose. 

\[prop:totient-ineq\] For every $n\in {\mathbb{N}^\ast}$, $\phi(n)$ is greater than or equal to $\sqrt{n {\mathbin{/}}2}$.

A proof of Proposition \[prop:totient-ineq\] can be found in appendix.  Noteworthy is that $\dfrac{\phi(n) \ln \ln n}{n}$ converges to a positive, finite limit as $n$ tends to $\infty$. [@HardyWright]. 

The new algorithm
=================

For every $n\in {\mathbb{N}^\ast}$, let $\displaystyle 
\pi_n({\mathtt{z}}) {\mathrel{\mathop:}=}\prod_{j = 1}^n \gamma_j({\mathtt{z}})
$. 

To prove that the MTP is decidable in polynomial time, we prove that

-   a $d$-by-$d$ matrix over ${\mathbb{Q}}$ is torsion if and only if it annihilates ${\mathtt{z}}^d \pi_{2 d^2}({\mathtt{z}})$, and that

-   ${\mathtt{z}}^d \pi_{2 d^2}({\mathtt{z}})$ is computable from $d$ in ${\mathop{\mathrm{poly}}}(d)$ time. 

\[th:critere-torsion\] Let $d$, $n \in {\mathbb{N}^\ast}$ be such that for every integer $m$ greater than $n$, $\phi(m)$ is greater than $d$. For every $d$-by-$d$ matrix $M$ over ${\mathbb{Q}}$ the following three assertions are equivalent. 

1.   $M$ is torsion. 

2.   $M$ annihilates ${\mathtt{z}}^d \pi_n({\mathtt{z}})$.

3.   $M$ satisfies $M^{n!  +d } = M^d$.

The implication $(iii)  \implies (i)$ is clear.  Moreover, it follows from Property \[prop:zm-1\] that $\pi_n({\mathtt{z}})$ divides ${\mathtt{z}}^{n!} -  1$, and thus ${\mathtt{z}}^d \pi_n({\mathtt{z}})$ divides ${\mathtt{z}}^{n!  + d } - {\mathtt{z}}^d$. Therefore, $(ii) \implies (iii)$ holds.  Let us now show $(i) \implies (ii)$.

Assume that $M$ is torsion.  Let $p$, $q \in {\mathbb{N}}$ be such that $p < q$ and $M^p = M^q$. Let $\mu({\mathtt{z}})$ denote the minimal polynomial of $M$ over ${\mathbb{Q}}$. Since $M^q - M^p$ is a zero matrix, $\mu({\mathtt{z}})$ divides ${\mathtt{z}}^q - {\mathtt{z}}^p$. By Property \[prop:zm-1\], ${\mathtt{z}}^q - {\mathtt{z}}^p$ can be factorized in the form ${\mathtt{z}}^q - {\mathtt{z}}^p =  {\mathtt{z}}^{p} \prod_{j \in D_{q - p}} \gamma_j({\mathtt{z}})$; by Property \[prop:irreductible\] all factors are irreducible over ${\mathbb{Q}}$. Hence, $\mu({\mathtt{z}})$ can be written in the form $\mu({\mathtt{z}}) = {\mathtt{z}}^k \prod_{j \in J} \gamma_j({\mathtt{z}})
$ for some integer $k$ satisfying $0 \le k \le p$ and some $J \subseteq D_{q - p}$. Besides, the Cayley-Hamilton theorem implies that $\mu({\mathtt{z}})$ divides the characteristic polynomial of $M$ which is of degree $d$. Therefore, $d$ is not smaller than the degree of $\mu({\mathtt{z}})$. Since the degree of $\mu({\mathtt{z}})$ equals $k + \sum_{j \in J} \phi(j)$ by Property \[prop:degre-phi\], we have $k \le d$ and $\max J  \le n$. Hence, $\mu({\mathtt{z}})$ divides ${\mathtt{z}}^d \pi_n({\mathtt{z}})$.

Combining Propositions \[prop:totient-ineq\] and \[th:critere-torsion\], we obtain that for every $d \in {\mathbb{N}^\ast}$, a $d$-by-$d$ matrix over ${\mathbb{Q}}$ is torsion if and only if it annihilates the polynomial ${\mathtt{z}}^d \pi_{2 d^2}({\mathtt{z}})$. To conclude the paper, it remains to explain how to compute $\pi_{n}({\mathtt{z}})$ in ${\mathop{\mathrm{poly}}}(n)$ time from any $n \in {\mathbb{N}^\ast}$ taken as input.  The idea is to rely on Proposition \[prop:mult-root\]. 

For every $n \in {\mathbb{N}^\ast}$, let $\displaystyle 
\nu_n({\mathtt{z}}) {\mathrel{\mathop:}=}\prod_{j = 1}^n ({\mathtt{z}}^j - 1) 
$. 

Let $n \in {\mathbb{N}^\ast}$. Clearly, $\nu_n({\mathtt{z}})$ is computable in ${\mathop{\mathrm{poly}}}(n)$ time.  Moreover, it follows from Property \[prop:zm-1\] that $$\nu_n({\mathtt{z}}) = \prod_{j = 1}^n \left( \gamma_j({\mathtt{z}}) \right)^{{\left\lfloor  n {\mathbin{/}}j  \right\rfloor}} \, ,$$ and thus $\nu_n({\mathtt{z}})$ and $\pi_n({\mathtt{z}})$ have the same roots.  Since $\pi_n({\mathtt{z}})$ has no multiple roots, Proposition \[prop:mult-root\] yields a way to compute $\pi_n({\mathtt{z}})$ from $\nu_n({\mathtt{z}})$ in polynomial time:

\[prop:pi-n-nu-n\] For every $n \in {\mathbb{N}^\ast}$, $\pi_n({\mathtt{z}}) {\mathrel{\mathop:}=}\dfrac{\nu_n({\mathtt{z}})}{\gcd(\nu'_n({\mathtt{z}}), \nu_n({\mathtt{z}}))}$.

Comments {#sec:comment}
========

#### The failure of the naive approach. 

Combining Propositions \[prop:totient-ineq\] and \[th:critere-torsion\], we obtain:

\[cor:mandel\] Let $d \in {\mathbb{N}^\ast}$. Every $d$-by-$d$ torsion matrix $M$ over ${\mathbb{Q}}$ satisfies $M^{(2d^2)!  + d} = M^d$.

It follows from Proposition \[cor:mandel\] that the MTP is decidable.  However, such an approach does not yield a polynomial-time algorithm for the MTP:

\[prop:exponential\] Let $t : {\mathbb{N}^\ast}\to {\mathbb{N}^\ast}$ be a function such that for each $d \in {\mathbb{N}^\ast}$, every $d$-by-$d$ torsion matrix $M$ over ${\mathbb{Q}}$ satisfies $M^{t(d) + d} = M^d$. Then, $t$ has exponential growth. 

For every $n \in {\mathbb{N}^\ast}$, let $\ell(n)$ denote the least common multiple of all positive integers less than or equal to $n$: $\ell(3) = 6$, $\ell(4) = 12$, $\ell(5) = \ell(6) = 60$, *etc*.  It is well-known that $\ell$ has exponential growth: for every $n \in {\mathbb{N}^\ast}$, $\ell(2n) \ge \binom{2n}{n} \ge 2^n$ [@HardyWright]. 

For every $d$-by-$d$ non-singular matrix $M$ over ${\mathbb{Q}}$, $M^{t(d)}$ is the identity matrix.  Besides, for every integer $k$ with $1 \le k \le d$, there exists a $d$-by-$d$ permutation matrix that generates a cyclic group of order $k$, and thus $k$ divides $t(d)$. It follows that $\ell(d)$ divides $t(d)$.

#### Reducing the MTP to the MPP. 

For the sake of completeness, let us describe the reduction from the MTP to the MPP.  Let $d \in {\mathbb{N}^\ast}$ and let $M$ be a $d$-by-$d$ matrix over ${\mathbb{Q}}$. Let $N_2  {\mathrel{\mathop:}=}{ \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}  }$, $A  {\mathrel{\mathop:}=}{ \begin{bmatrix} M^d & O \\ O & N_2 \end{bmatrix}  }$, $O_2  {\mathrel{\mathop:}=}{ \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}  }$ and $B {\mathrel{\mathop:}=}{ \begin{bmatrix} M^d & O \\ O & O_2 \end{bmatrix}  }$ where $O$ denotes both the $d$-by-two zero matrix and its transpose.  It is clear that $A$ and $B$ are two $(d + 2)$-by-$(d + 2)$ matrices over ${\mathbb{Q}}$. Moreover, there exists $n \in {\mathbb{N}}$ such that $A^n = B$ if and only if $M$ is torsion [@CassaigneN08]. 

Open question
=============

Let $d \in {\mathbb{N}^\ast}$. It follows from Corollary \[cor:mandel\] that for every $d$-by-$d$ torsion matrix $M$ over ${\mathbb{Q}}$, the sequence $(M^d, M^{d + 1}, M^{d + 2}, M^{d + 3}, \dotsc)$ is (purely) periodic with period at most $(2d^2)!$. Hence, the maximum cardinality of $\{ M^d, M^{d + 1}, M^{d + 2}, M^{d + 3}, \dotsc \}$, over all $d$-by-$d$ torsion matrices $M$ over ${\mathbb{Q}}$, is well-defined.  To our knowledge, its asymptotic behavior as $d$ goes to infinity is unknown. 

Proof of Proposition \[prop:totient-ineq\] {#proof-of-propositionproptotient-ineq .unnumbered}
==========================================

The following two properties of Euler’s totient function are well-known. 

\[prop:ppow\] For every prime number $p$ and every $v \in {\mathbb{N}^\ast}$, $\phi(p^v) =  p^{v - 1} (p - 1)$.

For every integer $k$, $\gcd(k, p^v)$ is distinct from one if and only if $p$ divides $k$. From that we deduce the equality $$\label{eq:pr-pr}
\left\{ k \in \{ 1, 2, \dotsc, p^v \} : \gcd(k, p^v) \ne 1 \right\} 
= \left\{ p q : q \in \{ 1, 2, \dotsc, p^{v - 1} \} \right\} \, .$$ Besides, it is easy to see that the left-hand side of Equation  has cardinality $p^v - \phi(p^v)$ while its right-hand side has cardinality $p^{v - 1}$.

\[prop:mult\] For every $m$, $n \in {\mathbb{N}^\ast}$, $\phi(mn) = \phi(m) \phi(n)$ whenever $\gcd(m, n) = 1$.

Property \[prop:mult\] is consequence of the Chinese remainder theorem.  It states that $\phi$ is *multiplicative*. 

\[lem:golden\] For every real number $x \ge 3$, $\sqrt{x}$ is less than $x - 1$.

The two roots of the quadratic polynomial ${\mathtt{z}}^2 - {\mathtt{z}}- 1$ are $\frac{1 + \sqrt{5}}{2} \approx 1.618$ and $\frac{1 - \sqrt{5}}{2} \approx -0.618$; they are both smaller than $\sqrt{3} \approx 1.732$. Therefore, $y^2 - y - 1$ is positive for every real number $y  \ge \sqrt{3}$. Since for every real number $x \ge 3$, $\sqrt{x}$ is not less than $\sqrt{3}$, $(x - 1) - \sqrt{x} = \left( \sqrt{x} \right)^2 - \sqrt{x} - 1$ is positive. 

\[claim:ineg-phi\] Let $p$ and $v$ be two integers with $p \ge 2$ and $v \ge 1$. Inequality $p^{v / 2} \le p^{v - 1} (p - 1) $ holds if and only if $(p, v) \ne (2, 1)$.

If $(p, v) = (2, 1)$ then $p^{v {\mathbin{/}}2} = \sqrt{2}$ is greater than $1 = p^{v - 1} (p - 1)$. If $v \ge 2$ then $v {\mathbin{/}}2 \le v - 1$, and thus $p^{v {\mathbin{/}}2} \le  p^{v - 1} \le p^{v - 1} (p - 1)$ follows.  If $v = 1$ and $p \ge 3$ then $p^{v {\mathbin{/}}2} = \sqrt{p}$ is less than $p - 1 = p^{v - 1} (p - 1)$ according to Lemma \[lem:golden\]. 

\[lem:phi-sqrt\] Let $n \in {\mathbb{N}^\ast}$. If $n$ is odd or if four divides $n$ then $\phi(n)$ is greater than or equal to $\sqrt{n}$.

It is clear that $\phi(1) = 1 = \sqrt{1}$. Let $n$ be an integer greater than one.  Write $n$ in the form $$n = \prod_{i = 1}^r p_i^{v_i}$$ where $r$, $v_1$, $v_2$, …, $v_r$ are positive integers and where $p_1$, $p_2$, …, $p_r$ are pairwise distinct prime numbers.  Properties \[prop:ppow\] and \[prop:mult\] yield: $$\phi(n) =  \prod_{i = 1}^r \phi(p_i^{v_i}) =  \prod_{i = 1}^r p_i^{v_i - 1} (p_i - 1) \, .$$ Assume either that $n$ is odd or that four divides $n$. Then, for each index $i$ with $1 \le i \le r$, $(p_i, v_i)$ is distinct from $(2, 1)$ and thus inequality $p_i^{v_i {\mathbin{/}}2} \le p_i^{v_i - 1} (p_i - 1)$ holds.  From that we deduce $$\phi(n) \ge \prod_{i = 1}^r  p_i^{v_i {\mathbin{/}}2}  = \sqrt{n} \, .$$

If $n$ is odd or if four divides $n$ then Lemma \[lem:phi-sqrt\] ensures $\phi(n) \ge \sqrt{n} \ge  \sqrt{n / 2}$. Conversely, assume that $n$ is even and that four does not divide $n$: there exists an odd integer $n'$ such that $n = 2 n'$. We have

-   $\phi(n) = \phi(2) \phi(n') =  \phi(n')$ according to Property \[prop:mult\], and

-   $\phi(n') \ge \sqrt{n'} = \sqrt{n / 2}$ by Lemma \[lem:phi-sqrt\]. 

From that we deduce $\phi(n) \ge  \sqrt{n / 2}$.
