Martin Gavalec and Günter Rote:

Reachability of fuzzy matrix period

Tatra Mountains Mathematical Publications 16 (1999), 61–79.


Given an n×n matrix A, the problem is to decide whether there is an n-vector x such that the sequence of matrix powers A, A2, A3, ... has the same period length as the sequence Ax, A2x, A3x, ... of iterates of x. In these matrix-matrix and matrix-vector multiplications, the usual operations + and * are replaced by max and min, respectively.

In general, this problem is NP-complete. Two conditions are described, which both together imply that it can be solved in O(n2) time. If only one of the conditions is satisfied, the problem remains NP-complete.

  PostScript file (gzipped)   pdf file   TeX .dvi file (gzipped)
other papers about this subject
Last update: October 26, 2001.