Wojciech Czaja

Philippe Jaming
email: philippe.jaming@univ-orleans.fr

Máté Matolcsi

An efficient algorithm for positive realizations

Keywords: Positive linear systems, discrete time filtering, positive realizations

 to indicate that the algorithm is indeed efficient in general.

Introduction

Given the transfer function H(z) = p 1 z n-1 + ... + p n z n + q 1 z n-1 + ... + q n , p j , q j ∈ R, of a discrete time-invariant linear SISO system of McMillan degree n, we say that a triple A ∈ R n×n , b, c ∈ R n is an nth order realization of H(z) if it satisfies the condition:

H(z) = c T (zI -A) -1 b.
It is known that an nth order realization of H(z) always exists (see, e.g. [START_REF] Farina | Positive linear systems: Theory and applications[END_REF]Chapter 9]). In this note, however, we are interested in the positive realization problem, i.e. finding A, b, c with nonnegative entries (and possibly of higher dimension M ≥ n). The nonnegativity restriction on the entries of A, b, c reflects physical constraints in applications. Such positive systems appear, for example, in modeling of bio-systems, chemical reaction systems, and socio-economic systems, as described in detail in [START_REF] Farina | Positive linear systems: Theory and applications[END_REF][START_REF] Kaczorek | Positive 1D and 2D systems[END_REF][START_REF] Luenberger | Positive linear systems[END_REF]. A thorough overview of the positive realization problem and related results has recently been given in [START_REF] Benvenuti | A tutorial on the positive realization problem[END_REF], while for a direct application in filter-design we refer the reader to [START_REF] Benvenuti | The design of fiber-optic filters[END_REF].

The existence problem is to decide for a given transfer function whether any positive realization A, b, c of any dimension M exists. It is known that the constraint of positivity may force the dimension M to be strictly larger than n, see [START_REF] Anderson | New developments in the theory of positive systems[END_REF], [START_REF] Benvenuti | An example of how positivity may force realizations of 'large' dimensions[END_REF], [START_REF] Nagy | A lower bound on the dimension of positive realizations[END_REF] for different reasons why this phenomenon may occur. The minimality problem is to find the lowest possible value of M . These problems have been given considerable attention over the past decade. The existence problem was completely solved in [START_REF] Anderson | Nonnegative realization of a linear system with nonnegative impulse response[END_REF] and [START_REF] Farina | On the existence of a positive realization[END_REF], cf., [START_REF] Kitano | Positive realization of discretetime systems by geometric approach[END_REF][START_REF] Nagy | Algorithm for positive realization of transfer functions[END_REF][START_REF] Förster | Nonnegative realizations of matrix transfer functions[END_REF], while a few particular cases of the minimality problem were settled in [START_REF] Benvenuti | Minimal positive realizations of transfer functions with positive real poles[END_REF][START_REF] Halmschlager | Minimal positive realizations for a class of transfer functions[END_REF][START_REF] Nagy | Minimal Positive Realizations of Transfer Functions with Nonnegative Multiple Poles[END_REF][START_REF] Astolfi | A note on the existence of positive realizations[END_REF][START_REF] Sun | Minimal Positive Realizations of Third-Order Systems with Complex Poles[END_REF][START_REF] Picci | Primes in several classes of the positive matrices[END_REF].

The state of the art of the theory is therefore rather two-sided. On one hand, there exists a general and constructive solution [START_REF] Anderson | Nonnegative realization of a linear system with nonnegative impulse response[END_REF][START_REF] Farina | On the existence of a positive realization[END_REF] to the existence problem which, however, is inefficient in the sense that it yields very large dimensions, even in trivial cases. On the other hand, the minimality problem is solved only for particular classes of transfer functions, and a general solution seems to be out of reach for current methods.

In this note we first observe (Section 2) that an appropriate combination of known results leads to a constructive, efficient, general algorithm to solve the existence problem in close-to-minimal dimensions. We observe that a repeated application of a lemma of Hadjicostis [START_REF] Hadjicostis | Bounds on the size of minimal nonnegative realizations for discrete-time LTI systems[END_REF] leads to the positive decomposition problem which, in turn, may be treated by methods of [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF][START_REF] Nagy | Order Bound for the Realization of a Combination of Positive Filters[END_REF]. In Section 3 we give two illustrative examples. In the first we compare the arising dimension to that of the earlier general algorithm of [START_REF] Anderson | Nonnegative realization of a linear system with nonnegative impulse response[END_REF]. In the second we complement the results of [START_REF] Benvenuti | An example of how positivity may force realizations of 'large' dimensions[END_REF] by determining the minimal value of M for a class of transfer functions. Finally, in Section 4 we provide a new lower-bound on M , improving a result of [START_REF] Nagy | A lower bound on the dimension of positive realizations[END_REF]. This latter contribution is independent of earlier results.

The algorithm

It is known that a necessary condition for the existence of positive realizations is that one of the dominant poles (i.e. the poles with maximal modulus) of H(z) be nonnegative real, and there is no loss of generality in assuming that it is located at λ 0 = 1, see, e.g. [START_REF] Anderson | Nonnegative realization of a linear system with nonnegative impulse response[END_REF]. The transfer function H(z) is called primitive if λ 0 is a unique dominant pole. It is also known, see [START_REF] Farina | On the existence of a positive realization[END_REF], that by the method of down-sampling the case of non-primitive transfer functions can be traced back to primitive ones. Therefore it is customary to assume that H(z) is a primitive transfer function with dominant pole at λ 0 = 1. We shall also assume, for technical simplicity, that λ 0 = 1 is a simple pole (this makes the calculations less involved; we note that the case of a multiple dominant pole can be reduced to the simple pole case as in [START_REF] Nagy | Algorithm for positive realization of transfer functions[END_REF]Step 4]). Without loss of generality we may assume that the residue at λ 0 = 1 is 1 (see e.g. [START_REF] Anderson | Nonnegative realization of a linear system with nonnegative impulse response[END_REF]).

With these normalizing assumptions, the transfer function H(z) takes the form

H(z) = 1 z -1 + G(z) = 1 z -1 + r j=1 nj i=1 c (i) j (z -λ j ) i , (2.1)
where the poles λ j of G(z) are of modulus strictly less than 1, i.e. G(z) is asymptotically stable (note that λ j s and c

(i) j s are possibly complex).

In the series expansion

H(z) = ∞ k=1 t k z -k the co- efficients t k are called the impulse response of H(z). If H(z) = c T (zI -A) -1 b then t k = c T A k-1 b for all k ≥ 0.
In particular, t k s must be non-negative for H(z) to have a positive realization. We now give the main ingredients upon which the algorithm is based. The first is the following simple but powerful result of Hadjicostis (see [START_REF] Hadjicostis | Bounds on the size of minimal nonnegative realizations for discrete-time LTI systems[END_REF]Theorem 5]).

Lemma 2.1 (Hadjicostis)

Let H(z) = ∞ j=1 t j z -j be a rational transfer function with non-negative impulse response t 1 , t 2 , . . . . For m ≥ 1 let H m (z) denote the transfer function corresponding to the shifted sequence t m , t m+1 , . . . ,

i.e. H m (z) = ∞ j=1 t m+j-1 z -j . Assume that H m (z)
admits a positive realization of some dimension k. Then H(z) admits a positive realization of dimension k + m -1.

We apply Lemma 2.1 to H(z) as given in (2.1). Note that H 1 (z) = H(z) by definition, and for each m ≥ 2 we have

H m (z) = zH m-1 (z) -t m-1 . Hence, for each m ≥ 1, H m (z) = 1 z-1 + r j=1 nj i=1 c (i) j,m
(z-λj ) i . The leading coefficient remains 1, while all other coefficients c (i) j,m → 0 exponentially as m → ∞ (due to the asymptotic stability of G(z)). That is, the leading coefficient becomes large compared to other coefficients, and this is exactly the familiar situation of the positive decomposition problem, which we now turn to.

The task in the positive decomposition problem is to decompose an arbitrary transfer function G(z) as the difference G(z) = T 1 (z) -T 2 (z), with T 1 (z) and T 2 (z) both admitting positive realizations (see [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF][START_REF] Halmschlager | Minimal positive realizations for a class of transfer functions[END_REF][START_REF] Nagy | Minimal Positive Realizations of Transfer Functions with Nonnegative Multiple Poles[END_REF][START_REF] Nagy | Order Bound for the Realization of a Combination of Positive Filters[END_REF]). By rescaling, one may assume that G(z) is asymptotically stable, and then the usual approach is to take a one-dimensional positive system T 2 (z) = R z-w , where 0 < w < 1 is larger than the modulus of any pole of G(z), and R is a sufficiently large positive number. Then T 1 (z) = G(z) + T 2 (z) can be shown to admit a positive realization which, in some cases, turns out to be also minimal [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF][START_REF] Halmschlager | Minimal positive realizations for a class of transfer functions[END_REF][START_REF] Nagy | Minimal Positive Realizations of Transfer Functions with Nonnegative Multiple Poles[END_REF][START_REF] Nagy | Order Bound for the Realization of a Combination of Positive Filters[END_REF]. For our purposes, the essence of these results can be summarized as follows: for any primitive transfer function, as long as the partial fraction coefficient of the dominant pole is significantly larger than all other coefficients (as in H m (z) and T 1 (z) above) there exist efficient methods to construct positive realizations. We shall not list all relevant results of [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF][START_REF] Halmschlager | Minimal positive realizations for a class of transfer functions[END_REF][START_REF] Nagy | Minimal Positive Realizations of Transfer Functions with Nonnegative Multiple Poles[END_REF][START_REF] Nagy | Order Bound for the Realization of a Combination of Positive Filters[END_REF] concerning the positive decomposition problem; instead, we give as an example Theorem 8 of [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF], which handles all transfer functions with simple poles.

Theorem 2.2 (Benvenuti, Farina & Anderson) Let H(z) = 1 z -1 + G(z) = 1 z -1 + n-1 j=1 c j z -λ j ,
where G(z) is a strictly proper asymptotically stable rational transfer function of order n, with simple poles. Let P j (j ≥ 3) denote the interior of the regular polygon in the complex plane with j edges located at the j-th roots of unity. P j can formally be defined in polar coordinates as in [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF]:

P j := (ρ, θ) : ρ cos (2k + 1)π j -θ < cos π j ,
for k = 0, 1, . . . , j -1 .

Let N 1 be the number of non-negative real poles with positive residue in G(z) and let N 2 denote the number of other real poles in G(z). Let N 3 denote the number of pairs of complex conjugate poles of G(z) belonging to the region P 3 , and let N j (j ≥ 4) denote the number of pairs of complex conjugate poles of G(z) belonging to the region

P j \ j-1 m=3 P m .
If all c j s are sufficiently small then H(z) admits a positive realization of dimension

N = (n-1)+N 2 + j≥3 (j -2)N j = j≥1 jN j . x x x x x x x x x x p p p p p p p p p p c c c c c c c c c c c c c c c c c c V V V V V V V h h h h h h h Ö Ö Ö Ö Ö Ö Ö P 3 -P 4 -P 5 • • • P 3 • • • P 3 and P 4 Figure 1.
The sets P j .

Remark 2.1

The dimension N appearing in the theorem is not necessarily minimal but it is a good a priori upper bound on the order of the realization. Further, by carefully analysing the proof in [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF], the condition on the residues may be given explicitely to be |c j | ≤ 2 -5/2 (where the sum runs only over the j's for which

λ j is counted in N k , k ≥ 2)
. In such case it can be computed that H(z) admits a positive realization of dimension N = j≥1 jN j . For the reader's conve-

nience, we have indicated in the appendix

The proof in [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF] is constructive and it gives a socalled cone-generated positive realization (see Section 4). We remark that in the case of simple poles the value of N in Theorem 2.2 is better than in Theorem 2.3. All the results above are constructive (see [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF][START_REF] Halmschlager | Minimal positive realizations for a class of transfer functions[END_REF][START_REF] Nagy | Minimal Positive Realizations of Transfer Functions with Nonnegative Multiple Poles[END_REF][START_REF] Nagy | Order Bound for the Realization of a Combination of Positive Filters[END_REF]).

Theorems 2.2 and 2.3 yield that the following is a general algorithm which terminates in a finite number of steps for any given transfer function H(z).

ALGORITHM:

Assume H(z) is given as in ( At each step, we may apply to H m (z) other known constructions from the literature different than Theorems 2.2 or 2.3. We included only these two theorems to keep the algorithm transparent and because they guarantee that the algorithm terminates in a finite number of steps. Other important partial results which can be incorporated into the algorithm are given in [START_REF] Benvenuti | Minimal positive realizations of transfer functions with positive real poles[END_REF][START_REF] Astolfi | A note on the existence of positive realizations[END_REF][START_REF] Picci | Primes in several classes of the positive matrices[END_REF].

Remark 2.3

We acknowledge that this algorithm is merely an observation that some earlier results in the literature can be combined together. Nevertheless, we find it an important observation as it provides a completely general algorithm. Previously such a general algorithm has only been given in [START_REF] Anderson | Nonnegative realization of a linear system with nonnegative impulse response[END_REF]. There are good heuristic arguments to believe that the algorithm above is efficient in terms of producing small dimensions, and better than the existing algorithm of [START_REF] Anderson | Nonnegative realization of a linear system with nonnegative impulse response[END_REF]. First, the partial fraction coefficients decay exponentially, so that only a few iterations are needed before Theorem 2.2 or 2.3 become applicable, and these theorems already provide minimal or close-to-minimal dimensions (see Section 3 for a numerical examples). Second, the method of [START_REF] Anderson | Nonnegative realization of a linear system with nonnegative impulse response[END_REF] involves the time development of an n-dimensional "cube" around the vector (1, 1, . . . , 1) and, as such, can only produce dimensions larger than 2 n (usually significantly larger than that). This fact, however, by no means diminishes the theoretical significance of the results of [START_REF] Anderson | Nonnegative realization of a linear system with nonnegative impulse response[END_REF] which provided the first general solution to the existence problem for primitive transfer functions.

Examples

In this section we give two examples. In the first we compare the arising dimension of realization with that of the algorithm of [START_REF] Anderson | Nonnegative realization of a linear system with nonnegative impulse response[END_REF]. In the second we complement a result of [START_REF] Benvenuti | An example of how positivity may force realizations of 'large' dimensions[END_REF] and determine the minimal dimension of positive realizations for a class of transfer functions.

First, we note that in the case where there are only simple poles, the number of iterations needed may be evaluated as follows: write

H(z) = n j=0 cj z-λj with λ 0 = 1 and |λ j | < 1. A simple computation shows that H m (z) = n j=0 cj λ m-1 j z-λj . It follows that, if m ≥ log 2 5/2 n max |ci| log max |λi| , then |c j λ m-1 j | ≤ 2 -5/2
and Theorem 2.2 applies (cf. Remark 2.1). Moreover, it is enough to consider those poles that are not nonnegative with non-negative residues.

Example 1. Let

H(z) = 1 z -1 + t(z) = 1 z -1 + 0.3331328522 z 2 + 0.1984152016 z + 0.1253986950 z 3 -0.69055619 z 2 + 0.80189061 z -0.38920832 ,
where t(z) is a low-pass digital Chebyshev filter of order 3. The partial fraction decomposition is

H(z) = 1 z -1 + 3 i=1 c i z -λ i with λ 1 = 0.07522998673 -0.8455579204 i, λ 2 = λ 1 c 1 = -0.01050864690 + 0.1411896961 i, c 2 = c 1 λ 3 = 0.5400962165 c 3 = 0.3541501460.
Let us now apply the algorithm. The above computation shows that after m = 5 iterations, we may apply Theorem 2.2 to H 5 . As N 2 = 0 and as λ 1 , λ 2 ∈ P 4 \ P 3 , N 4 = 1, N j = 0 for j = 4 we obtain a positive realization of H 5 (z) of dimension N = 5 (cf. Remark 2.1). A repeated application of Lemma 2.1 gives a positive realization of H(z) of dimension 9. A more careful examination of the proof of Theorem 2.2 would show that H 3 already satisfies the requirements so that a 7-dimensional positive realization exists. We spare the reader the numerical values.

While we cannot claim that the arising dimension is minimal let us compare it with that of the algorithm described previously in [START_REF] Anderson | Nonnegative realization of a linear system with nonnegative impulse response[END_REF]. In short, a specific minimal realization of H(z) is considered and the time-evolution of a small 4-dimensional cube around the vector [1, 1, 1, 1] T needs to be checked to provide a system-invariant polyhedral cone, which then leads to a positive realization of H(z). The number of edges of the cone equals the dimension of the positive realization. If one carries out this procedure word-by-word for H(z) above the arising dimension is 48.

Example 2. Consider the family of transfer functions

H N (z) = 1 z -1 - 4 • (5/2) N -2 z -0.4 + 3 • 5 N -2 z -0.2 (3.1)
as in [6, Example 4]. It is proved in [START_REF] Benvenuti | An example of how positivity may force realizations of 'large' dimensions[END_REF]

          , (3.2)
Consider now H N (z), N ≥ 4. It is not difficult to see that with the notation of Lemma 2.1 we have

H 1 (z) = H N (z), H 2 (z) = H N -1 (z), . . . , H m (z) = H N +1-m (z).
Let us stop at m = N -3, i.e. at H m (z) = H 4 (z) and make use of the realization (3.2) of H 4 (z). Then, the application of Lemma 2.1 produces a positive realization of H N (z) of order 4 + (m -1) = N . Note that for producing this minimal positive realization we use (3.2) instead of Theorem 2.2 (we have, in fact, followed the suggestion of Remark 2.2).

We have concluded that the minimal dimension of positive realization of H N (z) is N . Let us now see what the word-by-word application of the algorithm of Section 3 gives.

The algorithm terminates when Theorem 2.2 becomes applicable, i.e. when H m (z) = H 0 (z), that is m = N + 1. Then a 3-dimensional positive realization of H 0 (z) is constructed, and the application of Lemma 2.1 produces a positive realization of H N (z) of order 3 + (m -1) = N + 3.

This example is reassuring in that the application of the algorithm of Section 3 produces positive realizations of close-to-minimal order.

Improved lower-bounds

We saw in Section 3 that the minimal order of positive realizations of H N (z) is N . Also, it is easy to calculate (see [START_REF] Benvenuti | An example of how positivity may force realizations of 'large' dimensions[END_REF]) that the impulse response sequence of H N (z) contains zeros, namely t N -1 = t N = 0. A general lower-bound presented in [START_REF] Nagy | A lower bound on the dimension of positive realizations[END_REF] gives that in such case the order M of any positive realization satisfies M(M+1)

2 -1 + M 2 ≥ N , i.e. M is at least ≈ 2N
3 . In view of the actual minimal value M = N a lower-bound of the order of magnitude N is welcome (instead of the order of magnitude √ N ). In this section we present such an improvement (but we note that while the lower-bound of [START_REF] Nagy | A lower bound on the dimension of positive realizations[END_REF] is valid in general, our improvement is restricted to transfer functions with positive real poles, as is the case of the example of the previous section).

Throughout this section we assume that H(z) is a given primitive transfer function of McMillan degree n with positive real poles, and there exists a positive integer k 0 , such that for the impulse response sequence of H(z) we have t k0 = 0 and t k > 0 for all k > k 0 . This means that H(z) is of the form

1 z -1 + r j=1 nj i=1 c (i) j (z -λ j ) i (4.1)
where c

(i) j ∈ R, 0 < λ j < 1, and r j=1 n j = n -1. Let the triple (h, F, g) denote an arbitrary minimal (n-dimensional) realization of H(z) (for canonical minimal realizations see e.g. [START_REF] Farina | Positive linear systems: Theory and applications[END_REF]). Assume that there exists a matrix P of size n × M such that for some triple (c, A, b) with nonnegative entries:

FP = PA, Pb = g, c T = h T P. (4.2)
There is a well-known geometrical interpretation of these equalities. Namely, the columns of matrix P represent the edges of a finitely generated cone P in R n , such that P is F-invariant, and P lies between the reachability cone and the observability cone corresponding to the triple (h, F, g). It is known that the triple (c, A, b) provides a positive realization of H(z). It is a basic result in the theory of positive realizations that a transfer function H(z) admits positive realizations if and only if it admits cone-generated realizations (see [START_REF] Ohta | Reachability, observability and realizability of continuous-time positive systems[END_REF]). Here we present a lower bound on the order of cone-generated realizations of H(z). For this we shall need the following auxiliary result. We are now ready to give an improvement of the lower-bound of [START_REF] Nagy | A lower bound on the dimension of positive realizations[END_REF].

Theorem 4.2

Assume that H(z) is a transfer function of McMillan degree n, with positive real poles, given as in (4.1) above. Assume also that there exists a positive integer k 0 , such that for the impulse response sequence of H(z) we have t k0 = 0 and t k > 0 for all k > k 0 . Then the dimension M of any cone-generated positive realization of H(z) satisfies M ≥ k0 n-1 .

Proof. Let the triple (h, F, g) denote a minimal (n-dimensional) realization of H(z). Consider any cone-generated positive realization (c, A, b) of H(z) arising from a matrix P of size n × M , as in 4.2. Let e i denote an arbitrary column of the matrix P, and consider the sequence g

(i) k := h T F k-1 e i ≥ 0. Let P 1 := [p i,j ] be the nonnegative matrix of size M ×∞ defined by p i,j := g (i) j for 1 ≤ i ≤ M and 1 ≤ j. Let K := [k i,j
] denote the infinite Hankel matrix composed of the impulse response sequence of H(z), i.e. k i,j := t i+j-1 . By assumptions imposed on P there exists a matrix Q = [q i,j ] of size ∞ × M , with nonnegative entries, such that QP 1 = K. This is true because the kth row of K is given by k k,j = t k+j-1 = h T F j-1 (F k-1 g), and the vector F k-1 g lies inside the cone P by assumption. Thus, it may be decomposed as a linear combination of the edges e i of P with nonnegative coefficients, and [one choice of] these coefficients form the kth row of the matrix Q.

Since (h, F, g) is a minimal realization, for an arbitrary column e i of the matrix P, the transfer function corresponding to the impulse response sequence g

(i) k = h T F k-1 e i is of the form H (ei) (z) = C i z -1 + r j=1 nj s=1 d (s) j,i (z -λ j ) s .
(Note that some coefficients C i and d (s) j,i may be 0.) The column e i of P is called dominant if C i = 0 in H (ei) (z). Delete the non-dominant rows from the matrix P 1 and the corresponding columns from the matrix Q. The remaining matrices (of sizes M 1 × ∞ and ∞ × M 1 for some M 1 ≤ M ) are denoted by P (dom) 1 and Q (dom) . We see that Q (dom) P (dom) 1 ≤ K entrywise. Recall that t k0 = 0, by assumption on the impulse response of H(z). This implies that for some dominant index i (1

≤ i ≤ M 1 ), g (i) k0 = 0.
Otherwise, k 1,k0 = t k0 would be strictly positive in the first row of K. Considering the second row of K we see that k 2,k0-1 = t k0 = 0, hence g

(i)
k0-1 = 0 for some dominant index i. By the same argument, for every 1 ≤ j ≤ k 0 , g (i) j = 0 for some dominant index i. In other words, each of the first k 0 columns of the matrix P (dom) 1 contains a zero, and hence there are at least k 0 zero entries in P (dom) 1 . On the other hand, g

(i) k is the impulse response of H (ei) (z) = Ci z-1 + r j=1 nj s=1 d (s) j,i
(z-λj ) s . Thus, g

k = C i + r-1 j=1 p (j) (k)λ k j (i)
, where p (j) are polynomials of degree not exceeding n j -1, for 1 ≤ j ≤ r. Hence, Lemma 4.1 implies that there are at most R = (1 + r j=1 n j ) -1 = n -1 zeros in each row of P (dom) 1

. This means that the number of zeros in the matrix P (dom) 1 is at most M 1 (n -1). Therefore,

k 0 ≤ # of zeros in P (dom) 1 ≤ M 1 (n-1) ≤ M (n-1), and, hence, M ≥ k0 n-1 . 2
Remark 4.1 If we apply Theorem 4.2 to functions H N (z) of Section 3 we obtain M ≥ N/2. This is still far from the actual minimal value N . However, if there are more than 3 poles present in H(z) then the geometric arguments of [START_REF] Benvenuti | An example of how positivity may force realizations of 'large' dimensions[END_REF] are difficult to generalize, while Theorem 4.2 still applies.

Remark 4.2

As mentioned in the "Open Problems and New Directions" section of [START_REF] Benvenuti | A tutorial on the positive realization problem[END_REF] it is desirable to have tight upper and lower bounds on the minimal order of a positive realization in general. Note, however, that the results of [START_REF] Benvenuti | An example of how positivity may force realizations of 'large' dimensions[END_REF][START_REF] Nagy | A lower bound on the dimension of positive realizations[END_REF] and Theorem 4.2 above are all based on the assumption that the impulse response sequence of H(z) contains at least one 0. The only other lower-bound known to us is that of [START_REF] Hadjicostis | Bounds on the size of minimal nonnegative realizations for discrete-time LTI systems[END_REF] which, however, does not give any non-trivial estimates for transfer functions with nonnegative poles. What can be said if the impulse response does not contain zeros? Unfortunately, we do not have a general approach to this case. As a first step in this direction we examined the modified family

H N,ε (z) = 1 z-1 -4•(5/2) N -2 z-0.4 + 3•5 N -2 +ε z-0.2
for small values of ε. Note that the impulse response sequence no longer contains zeros. Since the dimension of the system is 3, we can use elementary (but tedious) geometric arguments to conclude that for small enough ε the minimal order M of positive realizations of H N,ε (z) still satisfies M ≥ N/2. It is not clear, however, how to generalize these arguments to transfer functions of higher degree (as in Theorem 4.2) where the geometric intuition is missing. Therefore, finding tight lower-bounds in the general case remains an open problem.

Conclusion

We have observed that recent results in positive system theory can be put together to produce an efficient, general algorithm to the positive realization problem of transfer functions. We have given two examples to illustrate the algorithm. In the first we compared the arising dimension of realization with that of an earlier general algorithm of [START_REF] Anderson | Nonnegative realization of a linear system with nonnegative impulse response[END_REF]. In the second we examined a family of transfer functions given in [START_REF] Benvenuti | An example of how positivity may force realizations of 'large' dimensions[END_REF], and determined the minimal order of positive realizations. With respect to the minimality problem we have proved a new lower-bound on the order of positive realizations of transfer functions with positive real poles, improving an earlier general result of [START_REF] Nagy | A lower bound on the dimension of positive realizations[END_REF].

Appendix A. Precisions on the paper [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF] In this section, we will show how to obtain a quantitative bound on R in Theorem 2.2 above. This result is not really new as it can be obtained directly from the proof of that theorem in [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF] and some simple observations. This appendix is thus only included here for the reader's convenience. Proposition A.1 [7, Proposition 7] Let H(z) = ηe iϑ z-ρe iθ + ηe -iϑ z-ρe -iθ and assume that ρe iθ ∈ P m . Then for R ≥ 2η cos π m there exists

A + ∈ R m×m + , b + , c + ∈ R m + such that H 1 (z) = H(z) + R z -1 = c T + (zI -A + ) -1 b + Proof.
Let us first consider the Jordan realization of

H 1 : H 1 (z) = c T (zI -A) -1 b with A =      ρ cos θ -ρ sin θ 0 ρ sin θ ρ cos θ 0 0 0 1      , b =      2η(cos ϑ + sin ϑ) 2η(cos ϑ -sin ϑ) R      , c =      1 1 1      . Next, define K by        1 cos 2π m cos 2π m 2 • • • cos 2π m (m -1) 0 sin 2π m sin 2π m 2 • • • sin 2π m (m -1) 1 1 1 • • • 1       
and, for α > 0 define

D(α) =      α 0 0 0 α 0 0 0 1      .
It was proved in [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF] that the positive cone K α generated by D(α)K is A-invariant. To prove the theorem, it is then enough to prove that we can choose α in such a way that

K α ⊂ O := {x ∈ R 3 : c T A k x ≥ 0, k = 0, 1, . . .} and that if R ≥ 2η cos π m then b ∈ K α . For the first one, note that if x = λ(α cos ϕ, α sin ϕ, 1) T ∈ R 3 then c T A k x = λ(1, 1, 1)      ρ k cos kθ -ρ k sin kθ 0 ρ k sin kθ ρ k cos kθ 0 0 0 1           α cos ϕ α sin ϕ 1      = λ αρ k cos(ϕ + kθ) + sin(ϕ + kθ) + 1 .
It follows that, for α = 1/2, λ ≥ 0, ρ ≤ 1, we always have c T A k x ≥ 0, in particular, K 1/2 ⊂ O.

Finaly, note that the cone K α contains the cone {λ(r, α) :

r < cos π m , λ > 0}, in particular b ∈ K α if 2 3/2 η Rα < cos π m . (A.1)
By taking α = 1/2 we can see that this is the case as soon as R ≥ 2 5/2 η cos π m . 2 If the filter is given and that one seeks for more precise estimates, one can slightly improve the result by taking α = 1/2ρ and still a bit further if θ = rπ for some r (necessarily rational) for which one may have cos(j 2π m + kθ) + sin(j 2π m + kθ) ≤ κ < 1 for all integers k ≥ 0 and 0 ≤ j ≤ m. In this case one may take α = 1 2ρκ and then check for the smallest R for which 2η

Rα (cos ϑ + sin ϑ, cos ϑ -sin ϑ) ∈ P m . In the opposit direction, note that R = 2 7/2 η works for all m ≥ 3.

Let us now show how the estimate on R in Theorem 2.2 results from this. We will take the notations from [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF]. Let q be the smallest integer so that all complex poles of H are in P q and let us write (2) j (the estimate is clear from the end of the proof of that proposition in [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF] and the restriction Λ < 1 is irrelevant). According to the improvement of [START_REF] Benvenuti | Filtering through a combination of positive filters[END_REF]Proposition 7] given above, if Note also that this realization has dimension

R (i) j ≥ 4η
N 1 + 2N 2 + 3N 3 • • • + qN q .

  This theorem was later improved and generalized in various forms, [13, Corollary 2], [19, Corollary 2], [20, Theorem 1, Theorem 2]. These papers also provide a number of examples where minimality of the arising dimension N can be claimed. Finally, a synthesis of all these results, [20, Theorem4], covers the case of H(z) = 1 z-1 + G(z) for any asymptotically stable rational transfer function G(z).

Theorem 2 . 3 ( 1 z- 1 +

 2311 Matolcsi, Nagy & Szilvási) If G(z) is any asymptotically stable rational transfer function with poles λ 1 , . . . λ r of order m 1 , . . . m r , and if all the partial fraction coefficients of G are sufficiently small, then the function H(z) = G(z) admits a positive realization, the dimension of which is given explicitely as a function of λ 1 , . . . λ r , m 1 , . . . m r .

  that for any N ≥ 4 the minimal dimension of positive realizations of H N (z) is at least N . Here we prove that an N -dimensional minimal positive realization of H N (z) does indeed exist for every N ≥ 4.For N = 4 the following 4-dimensional positive realization of H 4 (z) is given in [6, Example 3] and it is shown to be minimal.

Definition 4. 1 A

 1 triple (c, A, b) which arises in such a manner is called a cone-generated realization of H(z).

Lemma 4. 1

 1 Let f : R → R be defined by f (x) := r j=1 p (j) (x)λ x j where λ 1 > λ 2 > • • • > λ r > 0 and p (j) denotes a polynomial (with real coefficients) of degree n j . Then f has at most R ≡ R f := r j=1 (n j + 1) -1 pairwise distinct real roots. Lemma 4.1 is proved by induction on R.

3 H

 3 other real poles and, for i ≥

  j . A positive realization dimension N (defined in Theorem 2.2) of H is then given by b + = b is given in block-diagonal notation byA + = diag A the theorem is thus that R := R (i) jsatisfies e.g. R ≥ bound may be improved slightly with the above remark.

Partially supported by European Commission Harmonic Analysis and Related Problems 2002-2006 IHP Network, Contract Number: HPRN-CT-2001-00273 -HARP. 2 Partially supported by European Commission grant MEIF-CT-2003-500685. 3 Partially supported by the Hungarian-French Scientific and Technological Governmental Cooperation, no. F-10/04 4 Partially supported by OTKA-T047276, T049301, PF64601.