Note on surjective polynomial operators

Let I m := { 1, ••• , m } he a fiilite set. a := I m \ a be a complement of a subset a C I m. and | a | be the number of Its elements. Suppose that Rm is equippetf with the 1 1-iiomi kxk i := P m=₁ lx_k | where x = (x i , ••• ,x_m) E R m and {e i } i _Gi_m stands for the standard basis. We say that x >  0 (respex > 0) if xi > 0 (respexi > 0) for all i E Im. Let S^m-1 = {x e Rm : 11x111 = 1, x > 0} be the (m - 1)-dhnenslonal standard simplex. An element of the simplex Sm^-1 is called a stochastic ucctiw. For a. stochastic vector x E Sm^-1, we set supp(x) = {i E Im : xi > 0},mill(x) = {i E Im : xi = 0}. We define a face Га = COnv{ei}i_Ga of the simplex Sm^-1 where a C Im and conv(A) is the com-ex hull of a set A. Let mt Г_а= {x E Г_а: supp(x) = a} aiid дГ_а= Г_а\iiit Г_а be respectively the relative interior and boundary of the face Га.

Recall that a square matrix P = (pij ) ^m_j=1 is called non-ncgativc. written P >  0. if p i, >  0 for all i E I m . A square matrix P = (pij )^m_j=₁ is called stochastic if each row p i, = (p_ti, ... ,pim) is a stochastic vector for all i E I m . Let L : S m^-1 ^ S m^-1 be a linear operator (a Markov operator) associated with a square stochastic matrix P = (pij)^mj=₁, i. e.,

m

L (x) = x P = X xipi,.

i =1

It is easy to see that the linear operator L : S m ¹ ^ S m ¹ is a surjection if and only if it is a bijection. Indeed, the straightforward calculation shows that if L : S m^{- 1} ^ S m^{- 1} is a surjection then for each i there exists j such that L ^{- 1} ( e i) = ej where L ^{- 1} ( e i) is a preimage of the vertex e i of the simplex S m ^-1. Consequently, surjective linear operators of the simplex are only permutation operators.

Recently, the similar problem for a. quadratic operator (a. nonlinear Markov operator [6]) associated with a. cubic stochastic matrix was solved in the paper [5]. In general, the convexity of the quadratic operators is strongly tied up with the nonlinear optimization problems [1, 2, 4, 7] and is not an easy problem [8]. In this paper, we provide a. criterion for surjectivity of polynomial operators associated with stochastic hyper-matrices.

• 2.    Polynomial Operators Associated with Stochastic Hyper-Matrices

Let P = (pi1...ik )m ik=1 be a k-order m-dimensional hyper-matrix. We define the following vectors and matrices pi 1 ...ik — 1 •     (pi 1 ...ik — 11 , . . . , pi 1 ...ik — 1 ^m) ,    Pi 1 ...ik — 2 »»     (pi 1 ...ik — 2 jl) j l — 1, for am- i1,...,ik-1 E Im. In what follows, we denote i[1:l] := i1 ...ii for index.

for any x E S m^{- 1}. It is easy to check that

P (x) = x P x                                    (2)

where mm

Px = 52 " * 52 x i1 ... xik—2 ^Pi[1:k — 2]»» = ( P jl^(x) ) mi=1

i1=1    i _{k — 2} =1

is a square stochastic matrix for any x E S m^-1. Due to the matrix form (2). the polynomial operator P : S m^-1 ^ S m^-1 associated with k-order m-dhnensional stockastic hyper-matrix P is a nonlinear Markov operator (see [6]). Unlike the classical Markov chain, the nonlinear Markov chain is a stochastic process whose transition matrix Px may depend not only on the current state of the process but also on the current distribution x of the process (see [3]).

for any i 1 ,... ,i _k-1 E I m and any perinutation n of the set I _k-1 . We also assume that m >  k. We need the following auxiliary results.

Proposition 2.1 [6]. The following statements hold:

• ⁽ⁱ⁾    supp^(p(x)) = U        supp⁽Pi[1:k—1]» );

i[1:k — 1]GSUPP( x )

• ( ii )    null(P(^x)) = n        null( p i _[1:k-_ir ,);

i[1: k- 1]GSUPl>( x)

• ( iii )    P(int Га) C intr e where в = U   ^supp(p i _[1:k__1] .);

i[1: k- 1]G^a

• (iv)    P(int Г_а) C iiitTg if and only ifP( x ⁽⁰>) G iiitTg for some x ⁽⁰⁾ 6 iiitT_a .

An absorbing state played an important role in the theory of the classical Markov chains. Analogously, the concept of absorbing sets for nonlinear Markov chains was introduced in the paper [6].

“ = П    ^11U11(Pi[1: k- 1_r»⁾ .

i[1: k- 1]G^a

It is clear that a C Im is an absorbing set if and only if a = |J   supp(pi[1:k-1r,).

i[1: k- 1] ^Oa

The following result presents an insight of an absorbing set.

Proposition 2.2 [6]. The following statements are equivalent:

• (i)    A st ibsel a C I m is absorbing:

• ( ii )    One has that P(mtT_a ) C iiitT_a;

• ( iii )    One has that P (x ⁽⁰⁾ ) G iiit Г_а for some x ⁽⁰⁾ G iiitT_a .

Proposition 2.3. If any subset a C I m with | a | 6 k - 1 is absorbing then so are all subsets of I m.

C Suppose that any sul.set a C I m with |a| 6 k - 1 is absorbing. It means that supp(p_i[1:k_y) C a for any i1, ••• ,i_k-1 G a. In particular, the sets a^o = { i?, • • • ,ik_-1 } and в^o = {j^o} are absorbing for the given indices i^o1, ••• ,ik- 1 ,j ^o G Im (the repetition of indices is allowed). We then obtain that supp(p_j◦•••_j◦•) = {j ^o } and supp(pi=...ik ) C { i?, • • • ik-1} = a^o for any given indices i^, ••• ,i^o_k-1 ,j ^o G Im (the repetition of indeces is allowed). Hence, for any в C Im one lias that

U   supp ( P i[1:k - 1_r.) = |J supp( p j...j.) U U supp( p i[1:k - 1_r,) = в.

i[1:k-1]^e                           joe                      iv=ip.

Lemma 2.1. If any subset a C Im with | a | 6 k - 1 is absorbing then the polynomial operat or P : S m ^{- 1} ^ S m ^{- 1} is a surject ion.

C Due to Propositions 2.2 and 2.3. the polynomial operator P : S m^-1 ^ S m^-1 maps each face of the simplex Sm^{- 1} into itself. It is well-known in algebraic topology that any continuous mapping which maps each face of the simplex Sm^{- 1} into itself is a surjection of the simplex S m^-1 (see Lemma 1. [5]). Th is completes the proof. B

• 3.    Surjective Polynomial Operators vs Lotka Volterra Operators