## 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`,
`A`^{2}, `A`^{3}, ... has the
same period length as the sequence `A``x`,
`A`^{2}`x`, `A`^{3}`x`, ... 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`(`n`^{2}) time. If only one of the
conditions is satisfied, the problem remains NP-complete.

Last update: October 26, 2001.