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.