For a discrete-time single-input single-output transfer function with non-negative impulse response that admits an entry-wise non-negative (positive) state-space realization, the smallest such dimension N∗N^* is unknown: the minimal positive realization problem, open since the 1990s, is unsolved even for third-order transfer functions, and N∗N^* can exceed the transfer function's order by an unbounded factor. The most recent attack (Taghavian and Sjölund, 2025) computes, via linear-programming feasibility over a padding polynomial, the minimal dimension of a positive realization in Markov (companion) form — an upper bound on N∗N^* that is proven exact only for third-order systems whose complex poles sit at rational angles with magnitudes outside the Karpelevič eigenvalue region. The open core: characterize N∗(H)N^*(H); decide when the Markov-form (LP) dimension equals it; find necessary and sufficient conditions for Markov-form feasibility; and determine N∗N^* for systems with multiple positive poles.

Background

Positive systems are linear time-invariant systems whose state and output remain non-negative for every non-negative initial state and input; they model quantities that are inherently non-negative, such as chemical concentrations, population levels, and electric charge. For a discrete-time single-input single-output (SISO) system, a state-space realization is a representation xt+1=Axt+Butx_{t+1}=Ax_t+Bu_t, yt=Cxty_t=Cx_t whose transfer function H(z)=C(zI−A)−1BH(z)=C(zI-A)^{-1}B equals the given one. A realization is positive if the matrices AA, BB, CC are entry-wise non-negative. In unconstrained linear systems theory the minimal realization dimension is exactly the McMillan degree nn (the degree of the denominator of HH after zero-pole cancellation) and minimal realizations are computed by standard algorithms. Under positivity this theory breaks down. The impulse response (Markov parameters) of a positive system is non-negative — external positivity — and the Perron–Frobenius theorem, which governs spectra of non-negative matrices (the spectral radius is itself an eigenvalue, and every eigenvalue of maximal modulus is a rotation of it by a root of unity), forces the dominant pole (the pole of largest modulus) of a positive realization to be real non-negative and forbids further dominant poles at angles that are irrational multiples of π\pi.

Existence of positive realizations was settled in the 1990s: Farina (1996) gave the characterization, systematized in the tutorial of Benvenuti and Farina (2004) — a transfer function with non-negative Markov parameters admits a positive realization under dominant-pole conditions (no dominant poles besides a positive dominant one, or all pole angles rational multiples of π\pi), and algorithms then compute some positive realization, but not a minimal one. Minimality is the durable gap. The minimal positive realization dimension N∗N^* is unknown in general, is not bounded above by nn (Benvenuti and Farina, 1999, exhibited transfer functions for which positivity forces realizations of dimension far larger than nn, so the ratio N∗/nN^*/n is unbounded), and the equality N∗=nN^*=n is established in general only for n≤2n\le 2. For third-order systems only sufficient pole-region results are known (Wang et al., 2004; Sun et al., 2006), and the general lower and upper bounds of Benvenuti (2020) do not meet even at n=3n=3. Lower bounds are intrinsically tied to the spectral geometry of non-negative matrices — the Karpelevič region ΘN\Theta_N, the set of possible locations of an eigenvalue of an entry-wise non-negative N×NN\times N matrix with spectral radius one — and through it to the nonnegative inverse eigenvalue problem (NIEP), which asks which lists of complex numbers occur as spectra of non-negative matrices and is itself unsolved for matrix orders ≥5\ge 5 (Benvenuti, 2020; Johnson–Marijuán–Pisonero, 2026). Benvenuti's 2022 survey and the 2023 review of Benvenuti and Farina record the minimal positive realization problem as one of the flagship open problems of positive systems theory, open even at order three.

The source paper (Taghavian and Sjölund, 2025) attacks the problem through a canonical form. A Markov-form realization of dimension N≥nN\ge n pads the denominator A(z)A(z) with a monic polynomial Q(z)Q(z) of degree N−nN-n and takes a companion matrix for A(z)Q(z)A(z)Q(z) with output matrix C=[h1  …  hN]C=[h_1\;\dots\;h_N], so the Markov parameters appear explicitly. Such a realization is positive exactly when the last column of the companion matrix is non-negative, i.e. (a∗q)k≤0(a*q)_k\le 0 for all k∈[1,N]k\in[1,N], where (a∗q)k(a*q)_k is the coefficient of zN−kz^{N-k} in A(z)Q(z)=zN+(a∗q)1zN−1+⋯+(a∗q)NA(z)Q(z)=z^N+(a*q)_1z^{N-1}+\dots+(a*q)_N; for H∈MH\in\mathcal{M} with A(z)=(z−1)A^(z)A(z)=(z-1)\hat A(z), this is equivalent to A^(z)Q(z)\hat A(z)Q(z) having non-negative non-increasing coefficients. This is the feasibility condition of a linear program (LP) in the coefficients of QQ; hence the smallest feasible NN — the minimal positive Markov realization dimension — is computable, for instance by bisection over NN, and gives an upper bound on N∗N^*. The paper proves that this LP is feasible on a dense subset of the interior of the class M\mathcal{M} of transfer functions with exactly one positive pole (normalized to 11; pole scaling does not change realization dimensions), is infeasible for every NN when HH has two or more positive poles (a Descartes' rule of signs argument), admits the sufficient arithmetic condition of its Theorem 1 (poles at angles 2πlk/mk2\pi l_k/m_k in reduced terms with mk∤m1m2⋯mk−1m_k\nmid m_1m_2\cdots m_{k-1} imply feasibility at N=∏kmkN=\prod_k m_k), and gives the exact value N∗=mN^*=m for third-order systems whose complex-conjugate pole pair has angle 2πl/m2\pi l/m and magnitude large enough that the pair leaves the Karpelevič region Θm−1\Theta_{m-1}. Outside these islands — for higher-order systems, for poles of smaller magnitude, and for systems with several positive poles, where a series/parallel compound construction still yields positive realizations of dimension ∑iNi\sum_i N_i — the relationship between the Markov-form dimension and N∗N^* is unknown.

Problem Statement

Determine the minimal positive realization dimension N∗(H)N^*(H): given a strictly proper discrete-time SISO transfer function H(z)H(z) with non-negative Markov parameters that admits a positive state-space realization (entry-wise non-negative AA, BB, CC), characterize — by necessary and sufficient conditions in terms of the poles, zeros, and impulse response of HH, or by a terminating algorithm — the smallest dimension N∗N^* of a positive realization of HH, and produce an attaining realization. The same objective comprises the source paper's derived sub-questions on its Markov-form route: (i) for HH in the class M\mathcal{M} (exactly one positive pole, normalized to 11) admitting positive realizations, decide whether the minimal positive Markov realization dimension — the smallest NN for which the linear program on the padding polynomial QQ is feasible — equals N∗N^*, or exhibit a system in M\mathcal{M} for which it is strictly larger; (ii) find necessary and sufficient pole-angle and magnitude conditions for feasibility of that linear program, where the known arithmetic condition (angles 2πlk/mk2\pi l_k/m_k with mk∤m1⋯mk−1m_k\nmid m_1\cdots m_{k-1}) is only sufficient; (iii) characterize N∗N^* for systems with two or more positive poles, where no Markov-form realization exists at any dimension and only compound upper bounds ∑iNi\sum_i N_i are known. These three sub-questions are facets of the same objective, whose core is the general characterization of N∗(H)N^*(H). The problem is open in general and open even for third-order transfer functions; the literature covers only the orders ≤2\le 2 and the third-order systems with rational-angle complex poles outside the Karpelevič region.

References

  1. Hamed Taghavian, Jens Sjölund, "Minimal positive Markov realizations", arXiv:2502.21102 (2025), DOI 10.48550/arxiv.2502.21102, https://arxiv.org/abs/2502.21102; published version: Proceedings of the 2025 IEEE 64th Conference on Decision and Control (CDC), pp. 858–863, DOI 10.1109/CDC57313.2025.11312247, https://doi.org/10.1109/CDC57313.2025.11312247
  2. Luca Benvenuti, "Minimal positive realizations: A survey", Automatica 143 (2022), article 110422, DOI 10.1016/j.automatica.2022.110422, https://doi.org/10.1016/j.automatica.2022.110422
  3. Luca Benvenuti, Lorenzo Farina, "A Tutorial on the Positive Realization Problem", IEEE Transactions on Automatic Control 49(5) (2004), pp. 651–664, DOI 10.1109/TAC.2004.826715, https://doi.org/10.1109/TAC.2004.826715
  4. Lorenzo Farina, "On the existence of a positive realization", Systems & Control Letters 28(4) (1996), pp. 219–226, DOI 10.1016/0167-6911(96)00033-3, https://doi.org/10.1016/0167-6911(96)00033-3
  5. Luca Benvenuti, Lorenzo Farina, "An example of how positivity may force realizations of 'large' dimension", Systems & Control Letters 36(4) (1999), pp. 261–266, DOI 10.1016/S0167-6911(98)00098-X, https://doi.org/10.1016/S0167-6911(98)00098-X
  6. Luca Benvenuti, "A lower bound on the dimension of minimal positive realizations for discrete time systems", Systems & Control Letters 135 (2020), article 104595, DOI 10.1016/j.sysconle.2019.104595, https://doi.org/10.1016/j.sysconle.2019.104595
  7. Luca Benvenuti, "An upper bound on the dimension of minimal positive realizations for discrete time systems", Systems & Control Letters 145 (2020), article 104779, DOI 10.1016/j.sysconle.2020.104779, https://doi.org/10.1016/j.sysconle.2020.104779
  8. Zhizhen Wang, Long Wang, Wensheng Yu, Guoping Liu, "Minimal positive realizations of a class of third-order systems", Proceedings of the 2004 American Control Conference, pp. 4151–4152, DOI 10.23919/ACC.2004.1383958, https://doi.org/10.23919/ACC.2004.1383958
  9. Yuwei Sun, Yuan Yu, Wensheng Yu, Long Wang, "Minimal Positive Realizations of Third-Order Systems with Complex Poles", in Positive Systems, Lecture Notes in Control and Information Sciences, vol. 341, Springer, 2006, pp. 327–334, DOI 10.1007/3-540-34774-7_42, https://doi.org/10.1007/3-540-34774-7_42
  10. Yujie Liu, Dacheng Yao, Hanqin Zhang, "Minimal positive realizations for linear systems with two-different-pole transfer functions", European Journal of Control 69 (2023), article 100720, DOI 10.1016/j.ejcon.2022.100720, https://doi.org/10.1016/j.ejcon.2022.100720
  11. Luca Benvenuti, Lorenzo Farina, "Positive Dynamical Systems: New Applications, Old Problems", International Journal of Control, Automation and Systems 21 (2023), pp. 837–844, DOI 10.1007/s12555-021-0563-5, https://doi.org/10.1007/s12555-021-0563-5
  12. Luca Benvenuti, "The NIEP and the positive realization problem", Electronic Journal of Linear Algebra 36 (2020), pp. 367–384, DOI 10.13001/ela.2020.5039, https://doi.org/10.13001/ela.2020.5039
  13. C. R. Johnson, C. Marijuán, M. Pisonero, "The INIEP: Irreducible and Positive Realizations", arXiv:2605.23552 (2026), https://arxiv.org/abs/2605.23552