Minimal (max,+) Realization of Convex Sequences
Stéphane Gaubert, Peter Butkovič, R. A. Cuninghame‐Green · SIAM Journal on Control and Optimization · 1998
We show that the minimal dimension of a linear realization over the (max,+) semiring of a convex sequence is equal to the minimal size of a decomposition of the sequence as a supremum of discrete affine maps. The minimal-dimensional realization of any convex realizable sequence can thus be found in linear time. The result is based on a bound in terms of minors of the Hankel matrix.