A simple, polynomial-time algorithm for the matrix torsion problem

Understand

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: 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, it is also the case of the MTP.
• However, the algorithm for MPP is highly non-trivial.