Martin Gavalec and Günter Rote:
Reachability of fuzzy matrix period
Tatra Mountains Mathematical Publications 16 (1999), 61–79.
Abstract
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.
Last update: October 26, 2001.