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

Autor:	Nicolas, Francois
Rok vydání:	2008
Předmět:	Computer Science - Discrete Mathematics Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	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. Comment: 6 pages. Not intended to be submitted
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/0806.2068 Zobrazit plný text záznamu View this record from Arxiv