Minimal (max,+) Realization of Convex Sequences (Q4388906)

The minimal realization problem over the \((\max,+)\) semiring \(({\mathbb R}\cup \{-\infty\}, \otimes,\oplus)\) is addressed in terms of the following specific concepts and notations: (i) a sequence \(h_0, h_1,\dots\in{\mathbb R}\) is convex if \(k\geq 1\Rightarrow h_{k+1}- h_k\geq h_k- h_{k-1}\); (ii) the polynomial \(p(x)= \bigoplus_{i=1}^{i=r} (\alpha_i\otimes x^{\beta_i})\) is a polynomial realization of the sequence \(h\), if for all nonnegative integers \(k\), \(p(k)= h_k\); (iii) \({\mathbf {mpr}}(h)\) denotes the minimal number of monomials of a polynomial realization of \(h\), i.e. the minimal value of \(r\) (with \({\mathbf {mpr}}(h)= +\infty\), if \(h\) does not admit a polynomial realization); (iv) \({\mathbf {mlr}}(h)\) denotes the minimal dimension of a linear realization of \(h\) (with \({\mathbf {mlr}}(h)= +\infty\), if \(h\) is not realizable). The main contribution of this paper consists in proving that \({\mathbf {mpr}}(h)= {\mathbf {mlr}} (h)\) for every convex sequence \(h\). The proof relies on an intermediate result which guarantees that \({\mathbf {mlr}}(h)\geq \text{rk}_m{\mathbf H}\), where \(\text{rk}_m{\mathbf H}\) denotes the minor rank of the Hankel matrix \({\mathbf H}= ({\mathbf H}_{ij})= h_{i+j}\), \(i,j= 0,1,\dots\;\). An algorithm for finding the minimal polynomial realization is also presented and illustrated by an example.