Kybernetika 35 no. 1, 13-24, 1999

Controllability in the max-algebra

Jean-Michel Prou and Edouard Wagneur


We are interested here in the reachability and controllability problems for DEDS in the max-algebra. Contrary to the situation in linear systems theory, where controllability (resp observability) refers to a (linear) subspace, these properties are essentially discrete in the $\max$-linear dynamic system. We show that these problems, which consist in solving a $\max$-linear equation lead to an eigenvector problem in the $\min$-algebra. More precisely, we show that, given a $\max$-linear system, then, for every natural number $k\ge 1 $, there is a matrix $\Gamma_k$ whose $\min$-eigenspace associated with the eigenvalue $1$ (or $\min$-fixed points set) contains all the states which are reachable in $k$ steps. This means in particular that if a state is not in this eigenspace, then it is not controllable. Also, we give an indirect characterization of $\Gamma_k$ for the condition to be sufficient. A similar result also holds by duality on the observability side.