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

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

2008-06-12

arxiv.org/abs/0806.2068v3

Computer Science

Discrete Mathematics

6 pages. Not intended to be submitted

Scientific paper

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. The aim of this note is to present a simple, direct, polynomial-time algorithm for the MTP.

Affiliated with

Also associated with

No associations

Rating

A simple, polynomial-time algorithm for the matrix torsion problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A simple, polynomial-time algorithm for the matrix torsion problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A simple, polynomial-time algorithm for the matrix torsion problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-690885