On matrix powering in low dimensions

Esther Galby, Joël Ouaknine, and James Worrell

We investigate the Matrix Powering Positivity Problem, PosMatPow: given an m x m square integer matrix M, a linear function f : Zm x m → Z with integer coefficients, and a positive integer n (encoded in binary), determine whether f(Mn) ≥ 0. We show that for fixed dimensions m of 2 and 3, this problem is decidable in polynomial time.

Proceedings of STACS 15, LIPIcs 30, 2015. 12 pages.

PDF © 2015 Esther Galby, Joël Ouaknine, and James Worrell.