OCR of paper; see pdf file polynomial-systems76.pdf for viewable/printable page




Nonlinear Awlysis. Theory. Mchods & Application.%. Vol, I No. 1. pp. 55-454. Perganion Press, 1976. Noted in Great Britain.
ON DISCRETE-TIME POLYNOMIAL SYSTEMS
E. D. SONTAG*
Center for Mathematical System Theory, Department of Mathematics, University of Florida,
Gainesville, I L 32611, U.S.A.
arid
Y. ROUCHALEAU*
Center for Mathematical System Thcor~, Department of Mathematics, University of Florida,
Gainesville. I'L 32611. U.S.A.
and
Centre d'Autornatique, E. N. S. Mines F--7305 Fontainebleau, France
(Received I March 1976)
Ke-v ",ords: Nonlinear dynamical systerns. system analysis, reachability, observability, canonical systems.
applied algebra.
INTRODUCTION
THE FIELD of Algebraic System Theory is slowly expanding beyond the traditional confines of
linear systems to include various restricted types of nonlinear systems, for instance, bilinear
systems. We shall consider here a more general type of systems which have algebraic constraints
on their state set and for which the state transitions are given by (arbitrary) polynomial functions
of the inputs and state variables. The only technical restriction we shall make is to consider
systems which begin their evolution from an equilibrium state.
This paper is a summary (of a preliminary nature) of the results obtained so far on the above
questions. A thorough study of the realization theory of polynomial systems is carried out in
Sontag [7].
One of our main concerns in this work has been to obtain finiteness conditions, t'or it is our
belief that finite computational procedures are an essential goal of applied algebra.
In the first four parts of this paper we give the necessary mathematical preliminaries and define
the systems that we study. Part 5 is concerned with reachability in bounded time, while in Part
6 we look at the problem of deciding whether two systems have the same external behavior by
applying finitely many inputs. In Part 7 we show that finitely many inputs (which can be chosen
quite arbitrarily) are sufficient to separate those states of a system which are distinguishable.
Part 8 is an investigation coticci-ning the conditions under which systems with the same external
behavior are isomorphic.
This research was supported in part by US Army Research Grant DAHC04-74-G-0 153 and by US Air Force G ran i
AFOSR 72-2268 through the Center for Mathematical System Theory, University of Florida, Gainesville, FL 32611,
U.S.A~ This is an expanded version ofthe paper with the same title presented at the CNR-CISM Symposium on Algebraic
System Theory, June 1975, Udine, ITALY. The editor of the proceedings, G. Marchesini, was unable to include this
paper in the proceedings.
55
<<PAGE-DIVIDER>>
56 E. D. SONTAG AND Y. RoucHALEAU
1. ALGEBRAIC PRELIMINARIES
We review now some notions from commutative algebra and algebraic geometry. The results
can be found in any of the standard references; see, for instance, Dieudonn6 [1], Mumford [4],
Macdonald [3]. Although the literature usually treats only the case in which solutions are taken
in algebraically closed fields, the generalization to the present setup (namely, arbitrary infinite
fields) does not present any major difficulty. We shall therefore omit the proofs here.
Throughout this paper, k denotes an arbitrary but fixed infinite field. For any nonnegative
integer n, k" is the set of all n-tuples of elements in k. In particular, k' is a one-element set I01.
Similarly, k[T ..... TI, or k[T] when there is no danger of confusion, is the ring of polynomials
n
in the indeterminates T,,... ~ 7~ with coefficients in k. If n = 0, k[T] is defined to be k. When
f is in k[T,,..., 7J and x e V then f (x) denotes the evaluation (i.e. specialization) of f at x.
For each subset T g k[T,,..., YJ we define
Y(Y): = Ix e k"If (x) = 0 for all f e YJ.
For each subset S k" we define
I(S): = If ek[T1_., 7JIf(x) = 0 for all xc-S).
Of course, V(Y) V(<Y>), where <Y> denotes the ideal generated by the set Y. Since every
ideal of k[T] is finitely generated (Hilbert's Theorem), we note that
Lemma I. I. For every Y 2 k[T] there exists a finite subset Yo Ez Y such that V(Y) ~ V(Td.
Proposition 1.2. Let V and I be defined as above. Then V, I give a Galois connection between
the lattices of subsets of k[T1,..., 7J and of k". Furthermore, the induced closure operator
Sk-+ S: = V(I(S)) defines a topology on kn, called the Zariski topology. The closed sets for this
topology are called k-points of algebraic sets. Algebraic sets in k" can themselves be considered as
topological spaces under the topology induced from V.
Since the field k is infinite, a polynomial function f : V --+ k: x ~4 f (x) can be identified in an
unambiguous way with a polynomial in k[T,,..., 7J. We shall always assume such an identifica-
tion and shall speak indistinctly of polynomials and polynomial functions. A polynomial function
f: V ---* k, where V 9~ k", is by definition the restriction to V of a polynomial function f: 0 -4' k.
Definition 1.3. Let V (-_ k' be an algebraic set. Then the k-algebra A(V) of all polynomial func-
tions f: V - k with pointwise operations is the coordinate ring of V The k-algebras of type A(V)
are affine k-algebras.
It is not difficult to verify that A(V) = k[T]II(V). When k is algebraically closed, affine k-
algebras are characterized as finitely generated k-algebras with no nilpotent elements.
The dimension of a k-algebra A is defined as the maximum possible length of chains of prime
ideals. When A is an integral domain finitely generated over k, the dimension of A coincides with
the transcendence degree of A over k.
We say an algebraic set V 9 V is irreducible if there do not exist algebraic sets Vi, V, such that
Y = V, u V, and V 0 V1, V 54 V2. Such algebraic sets are also called (affine) varieties. The
following results are well known.
Proposition 1.4. An algebraic set V is irreducible if and only if I(V) is a prime ideal. If... - V
cz V,1 c-- is a strictly monotonic chain of algebraic sets, then ... ::) I(V
I I - d - 1(yd
=, ... is also strictly monotonic. In particular, every ascending or descending chain of
irreducible algebraic subsets of V has a length at most equal to the dimension of A(V). The dimen-
sion of A(k") is n.
<<PAGE-DIVIDER>>
On discrete-time polynomial systems 57
We remark that the last statement of Proposition (1.4) is the only place where the assumption
k = field is essential. Generalizations to arbitrary integral domains are not very difficult.
The (algebraic) dimension dim V of an algebraic set V is by definition the dimension of A(V).
Except for the algebraically closed case, this number is only an upper bound on the geometric
dimension given by the maximum length of chains of varieties included in V Clearly, if V 9 V
then dim V < n.
Definition 1.5. Let V, W be algebraic sets and W g k'. A mapf. V --* W is called a morphism (or
polynomial map) if there existf,,. in A(V) such that f(x) = (f,(x),. .. J.(x)) for all x C- V. The
associated comorphism Alf): A(W) -+ A(V) is the k-algebra homomorphism defined by A(f ): g
g -f for all g c- A(W).
Theorem 1.6. Algebraic sets and morphisms define a category, which is equivalent to the dual
of the category of affine k-algebras and k-algebra homomorphisms.
Remark 1.7. The image of an algebraic set under a morphism is not necessarily an algebraic set.
However, it can be proved (see Mumford [4], Chapter 1, 8, Corollary 2]) that the image of an
algebraic set is a constructible set if k is an algebraically closedfield. (A set is constructible in V
if it can be expressed as a finite union of sets of the form U r) F, where U is open and F is closed
in the Zariski topology of V)
Theorem 1.8. Let f: V -+ W be a morphism, of algebraic sets. Then:
(a) f is continuous for the Zariski topologies on V and W.
(b) f is dominating, i,e. 7(f) = W, if and only if Alf) is injective.
(c) f is injective if A(f) is surjective.
Remark 1.9. Injectivity off does not imply surjectivity of Alf ), except in special but important
cases, for example, when f is the restriction of an injective affine map f. V -+ k. (Surjectivity of
A(f ) is in fact equivalent in general off being a closed embedding.)
Proposition 1.10. Products exist in the category of algebraic sets. Moreover, A(V x W) is
isomorphic as a k-algebra to A(V) (D A(W), the tensor product of the k-algebras A(V) and A(W).
Intuitively, if V g k n and W g; V then the categorical product of V and W is the set product
n',
V x W seen as an algebraic subset of k
From Hilbert's theorem on ascending chains, it is known that a chain of ideals in k[T] is
necessarily finite. A recent theorem gives explicit bounds for the lengths of such chains:
Theorem 1.11. (Seidenberg [5]). Let KU) be a nonnegative integer for j = 0, 1.... and consider
strictly ascending chains of ideals I0 C Ii (-- ... c 1, in k[T,,..., 7j, where I ihas a basis of ele-
ments of degree < KU). Then there is an integer U(K, n) computable from K and n such that the
length of any such chain is smaller than U(K, n).
For the explicit form of A the reader is referred to the work of Seidenberg. Another way of
expressing the conclusion of the theorem is the following. We call an (infinite) sequence of ideals
10S: 11 g 12 ~~; ... strict if it satisfies the property:
if = I~ + , then 1.+ 1 = 1,,+2'
Then the conclusion of (1. 11) for a strict sequence is that if each I ican be generated by polynomials
of degree < KU) then I, = I, , for s = U(K, n).
Finally, we shall need an interpolation result. If f e k[T1_., Tj then deg,f is by definition
the degree of f as a polynomial in T.
Proposition 1.12. Assume L ~~- k is a subset of cardinality m + 1. Let A: L? --~ k. Then there
<<PAGE-DIVIDER>>
58 E. D. SONTAG AND Y. RouCHALEAU
exists a unique fe k[T,,..., T] such that deg,f < in and f(1 ......Q 1,,) for all
n
e
2. SYSTEMS
Let k be an infinite field, Y a fixed algebraic set over k and U a fixed variety (irreducible alge-
braic set). Then
Definition 2.1. A (polynomial, discrete time, constant) dynamical system over k, having input space
U and output space Y, is I = (X, x, p, h), where
(i) X (the state space) is an algebraic set over k.
(ii) x0 (the initial state) is a fixed element of X.
(iii) p (the transition map) and h (the output map) are morphisms X x U -* X and X --* Y
Remarks 2.2. (i) x, p(x, - 1, U, - ) is interpreted as the state at time t corresponding to the state
Xt - , and the input U, at time t - 1; y, = h(x,) is interpreted as the output at time t.
(ii) Since k' is irreducible, a system with unconstrained inputs fits in our framework.
(iii) Since any algebraic set is embedded in some affine space, there is no loss of generality in
assuming that the output set is V.
(iv) X. can be identified with a map from V into X.
Definition 2.3. The dimension of a system I is that of the algebraic set XV if XI: V, the system
Y_ is said to be unconstrained.
The map p can be extended recursively to a map X x U* - X (where U* is the free monoid on
U), which we shall also denote by the letter p. Let g: U* -+ X be defined by g(w) = p(xO' w). Then:
Definition 2.4. The input-output map of a system 1 is the map f: U* -+ Y given by f = h,- y.
We shall denote by g, and f, the restrictions of g and f to U' (the t-fold Cartesian power of U).
It follows from the definition of p and Ii that g, and f, are morphisms from the variety U' into X
and Y.
Definition 2.5. Let Y. = (X,x0, p, h) and Y_ be two polynomial systems. A mor-
phism of s'ystems Y_ , Y_ is a morphism T of algebraic sets such that the following diagram com-
mutes:
X X U_ 1'_X
7 x 1,, T Y and T(x,)
X X U-~'~/
Observe that the existence of a morphism I implies that A = A-
3. COSYSTEMS
D~finition 3.1. A polynomial cosystem -7 over k is a quadruple (A, 0~ fl, 7) where A is a k-algebra
and a: A(Y) -~ A, fl: A --+ A (D A(U), j: A --+ k are k-algebra homomorphisms. If A is an affine
algebra, then EE is an affine cosystem.
We can associate in a Straightforward manner to any cosystern an input-output function
mapping A(Y) into FI (O"A(U)).
Definition 3.2. A morphism of cosystems E -~ E" is a k-algebra homomorphism q from A to A
<<PAGE-DIVIDER>>
On discrete-time polynomial systems 59
such that the following diagrams commute:
A A A(U) A
A(Y) A It I
,i A A ( U)) 14
Polynomial, discrete-time, constant systems and cosystems, with their respective morphisms,
form two categories which we shall call Systems and Cosystems respectively. Affine cosystems will
be a full subcategory of Cosystems.
Theorem 3.3. (Duality). Systems and (,4fjjne cosystems)'P are equivalent categories.
Proof This is a direct consequence of (1.6).
4. EQUILIBRIUM-STATE ASSUMPTION
Let X, = g,(U'). It is the reachable set at time t.
Definition 4. 1. The state x. E X. is an equilibrium state for the system 2: if there exists uo C-'U
such that p(xO' 110) ~ X0.
We shall restrict ourselves to considering systems having an initial state which is an equilibrium
state. By a change of coordinates in U and X, we can take x0 = 0, U0 ~ 0 without loss of generality;
this assumption then means that p has no constant term. In other words, we assume that the
system was operating in a certain steady-state mode before we disturbed it with our new sequence
of inputs. Such an assumption is satisfied for most classes of systems studied so far (linear, bilinear).
From our point of view, the main value of the assumption is due to the following easy result:
Lemma 4.2. The sequence of reachable sets f X, I is monotonically increasing if and only if the
k
initial state of the system is an equilibrium state.
5. REACHABILITY AND QUASI-REACHABILITY
Definition 5.1. A system I is reachable iff XR: = J X, = X. I is reachable in bounded time iff
Xr = X for some r. 1~~o
Definition 5. . The system I is quasi-reachable iff its state set is the closure (in the Zariski
topology) of the reachable set, i.e. X u X, = X. It is quasi-reachable in bounded time iff
Q ~~ 0
X, ~ X for some r. A system Y_Q with state-space X. can be naturally defined using the restric-
tions of p, It to X.,
Lemma 5.3. The sequence ~, X,j is strict, i.e. X, = X, I implies X,
Proof. By definition, we have X,, I = p(X, x U), for all t > 0. The morphism p is continuous,
hence p(X, x U) ~~ p(X, x U. Thus
X, AX, X U) =-2 p(X' X U) = P(X, X U) = p(X' + I X U)
But of course p(X,+l X U) z;? P(X"l X U) = X,+2* By (4.2), X,2 2 X"I, So X'+1 ~? X'+2
2 X" 1, and therefore X,i = Xt+2'
Proposition 5.4. Let dim E = n. Then the set of quasi-reachable states is X'.
Proof. Since U is irreducible by assumption, so is U. Since X, is the closure of the image of U'
under the morphism g, (of algebraic sets), X, is also irreducible. We therefore have an increasing
sequence X. c~ X1 S; X2 g; ... of closed irreducible subsets of X. Since dimension of X is n,
<<PAGE-DIVIDER>>
60 E. D. SONTAG AND Y. RoucRALEAU
the preceding sequence cannot have more than n +'I distinct sets, by (1.4). It follows therefore
from (5.3) that this sequence cannot increase after step n.
Remark 5.5. We have just proved that a quasi-reachable system is quasi-reachable in bounded
time. The same property does not hold, however, for reachability, as can be seen from the follow-
ing example.
Let U=X = Y=R,p(x,u)=x+ U2 - 2u, h(x)=x, x0 =0. Then X, = JxeRJx>, -tJ.
The system is clearly reachable, but not in bounded time.
We can nevertheless obtain the following characterization of reachable states:
Proposition 5.6. Let k be an uncountable, algebraically closed field. Then the reachable states
form a constructible set if and only if they can be reached in bounded time.
Proof. Since V is a variety and g, a morphism of algebraic sets, it follows immediately from
(1.7) that X, is a constructible set. If X R is reached in bounded time, it is equal to an X, hence
constructible.
The proof of the converse statement, based on Noether's Normalization Theorem, is too
long to be given here.
6. FINITE CHARACTERIZATION OF THE INPUT-OUTPUT MAP
In this part we study questions related to the specification of polynomials systems. Specifically,
we ask: how many experiments are needed to characterize the input-output map of a system?
Recall that if Z is known to be linear, U = k, and if dim I < n, then to determine the map
it is enough to know the values of f,((o) for the 2n inputs (0,... , 0, 1, 0,..., 0) of length 2n.
To determine uniquely a polynomial of degree r, in general its values at r + I points must be
known. Hence, to obtain similar results for nonlinear systems, some a priori estimates are needed
for the degree of the polynomials involved in the definition of Y. Using such estimates, one of the
contributions of this paper is to effectively compute a bound on the number of input-output
experiments sufficient to decide whether or not two systems have identical external behavior.
Theorem 6.1. Let 1, i be systems of dimension < n. Write f: =fy, f: = f . Then the following
statements are equivalent:
(i) f
Proqf. By definition Y 9 V for some p. Hence the map J':(o~-flw) - J((o) is well defined.
The map f can be realized as where i is defined as X: = X x _k, 9,: = P((x, -4 u): =
(p(x, u), fi(x, u)), and h(x, _iZ): h(x) - h(~). The theorem is then an immediate consequence
of the following
Lemma 6.2. Let f J, where E is a system of dimension r. Suppose that f =_ y c Y, a constant
function. Then f, for all t > 0.
Proof. Since f, h0g, for all t, it follows that f, y if and only if It I X, y. By hypothesis,
h I X, ~_ y. Since h is continuous, it follows that it y. By (3.4), XQ X, for all t. There-
fore It I X, _= y for all t.
Observation 6.3. In general, knowledge of the map f, for some t < 2n is not enough to identify
a system of dimension n. Indeed, consider affine systems with U: = Y: = k, X: = 0 and x0 = 0:
x(t + 1) = Fx(t) + gu(t)
Y(t) = hx(t) + c
~
<<PAGE-DIVIDER>>
On discrete-time polynomial systems 61
Then A is completely determined by c, ap . - ., a, where a. = hF'-'g. It is well known from linear
system theory that the data c, al, a2, (but no proper subset of it) is sufficient to
determine f.
Definition 6.4. degree (1) < s iff there exist representations of p and h by polynomials having
(ordinary) degree <, s separately in each variable up i m (where U s~~ km) and having
degree < s jointly in the variables x '..
If degree (1) _< s then f,: U' --+ Y admits a representation by polynomials of degree < s" in
each variable (easy verification). From Proposition (1.12) and from Theorem (6.1) we obtain the
Corollary 6.5. Let 1, i be systems of dimension < n and of degree < s. Let L g; k be any set of
s2", 1 + I elements. Let L": = ~(u,,. . . , u,) e Ul u, c- LTJ. Therif = f ifand only iffl L, 2n) p2n).
So the equality of behaviors ofany two systems 1, E is effectively decidable.
For the last statement above to be meaningful, we are of course assuming that the field k
itselfis effectively presented.
7. FINITE OBSERVABILITY
Definition 7.1. Two statesxJ'X2 are distinguishable if and only if there exists an input sequence
co e U* such that h"(x 1) :A h'(X2)1 where ho(x): = h-p(x, (o). A system is said to be abstractly
observable when any pair of states are distinguishable.
Proposition 7.2. For any system 1, there exists a finite set of input sequences oil, (021 ... I 0J q
such that h"i(x 1) = h~i(X) for all i e 11, - - - , q', if and only if x, and X2 are not distinguishable.
Proof. An input sequence w enables us to define a morphism
I': X x X -+ V: (x 1, X 2) ~, V(x,) - ho'(X 2)_
If we compose this map with the p coordinate projections V --+ k: -~7 Hy,, i = 1,...,p, we get p
morphisms I': X x X --+ k. The states x, and x2 are distinguishable if and only if one of these
morphisms is nonzero at (x,,x2). Thus the states which are not distinguishable form exactly
the algebraic subset of X x X defined as V(Jl~~10) C- U*' I '< i '< p1). it follows from the Hilbert
Basis Theorem (1.1) that this can be defined as the set of common zeros of finitely many
of the 1-'s. It is therefore sufficient to apply the corresponding finitely many input sequences to
determine whether any two states are distinguishable or not.
Corollary 7.3. Distinguishable states can be separated in bounded time.
We have thus proved that to test whether any two states are distinguishable or not it Is sufficient
to apply input sequences of bounded length to the system. In fact, we have even shown that it is
enough to apply finitely many input sequences. But our result is just an existence statement and
does not tell us how to choose these input sequences. The following theorem answers this
question.
Theorem 7.4. Given a polynomial system I there exist two integers t and r (which can be
computed effectively from Y-) such that the following property is true:
If L is a subset of U of cardinality r, then h'(x 0 = "'O(X2) for all o) e L! implies h~(x) = "'(X2)
for alle) in U*.
Proof Let J~: = t(x, x,) e X x X I li~(x,) = h'(x,), for all (o e Ui, j <_ n, I _< p 1. The
degrees of the polynomials h',(x) in the variables x are bounded for all (o c- U" because of their
recursive definition. It follows that V, = V, +1 = ...for some computable index t (Theorem (1-11)).
Thus x 1 cannot bedistinguished from X2 ifand only 'f(XIIX2)r= V,. But (X I I X 2) C_ V, means that
<<PAGE-DIVIDER>>
62 E. D. SONTAG AND Y. RoucHALFAU
h'(x,) = h'(x,) as morphisms from Ui into k. Since the degrees of the polynomials representing
these morphisms are bounded, the result follows from (1.12).
In other words, the computational aspects of our problem are reduced to those of Seidenberg's
Theorem (I. 11).
8. SYSTEM ISOMORPHISM
This section is concerned with the "uniqueness theorem for canonical realizations". This
theorem, which is known to hold for several classes of systems (e.g. automata, linear systems)
states that two "canonical" realizations of a given input/output map are "isomorphic". The
appropriate notion of system isomorphism in the present context is that given by (2.5); a counter-
example will show, however, that a naive definition of "canonical" as "reachable + (abstractly)
observable" is not sufficient to give us the desired result.
Counterexample 8.1. We wish to construct two systems 11,i with f,: = fj both reachable and
abstractly observable but such that I is not isomorphic to 1. The construction is based on the
fact that (in the category of algebraic sets) a morphism which is bijective (one-to-one and onto)
is not necessarily an isomorphism.
Let q: V --* W be a morphism between varieties V, W such that q is a bijective map but V is
not isomorphic to W For instance, let
V: k,
W: f (x, y) e k21X3 _ 2 = ob
y
2,13).
q:z~~(z Z
(It is a standard algebra ic-geomet ri c fact that V :t W.)
Given any q, V, W as above, let U: ~ V, Y: ~ W and define
y_: = (V, X0, pr2l q),
1: = (W, q(x ), q - Pr 2' t W);
here x0 e V is arbitrary while pr2: V x V V and ~~' 2: W X V V denote the projection on the
second factor.
Since q induces a system morphism Y_ i, it follows that f, fi. Using that q is bijective, it
is easy to verify that both systems are reachable and abstractly observable. Finally, Y_ is not
isomorphic to ñ, because their state-sets V, W are not isomorphic.
The difficulty in proving the uniqueness theorem is most easily understood in terms of co-
systems. In view of Theorem (1.8), the notion of reachability (rather quasi-reachability) is dualized
into a notion of "observability" for cosystems. The notion of abstract observability for systems,
however, does not have a nice dualization (see Remark 1.9)). Categorical problems like system-
isomorphism are easier to study in algebraic categories like Cosystems rather than in geometrical-
topological categories like Systems. Therefore, it is natural to require a stronger notion of system
observability, corresponding to "cosystem reachability".
This stronger notion, which we shall call "algebraic" observability, can also be motivated by
system-theoretic considerations. An intuitive definition of observability for a system Y, is that
there should exist a procedure which permits the determination of an arbitrary initial state of Y_
on the basis of appropriate input-output experiments (see a detailed discussion in Kalman [2,
Chapter 10]). The word "procedure" is, of course, overly vague. In the classical context of linear
systems it is well-known that any possible procedure is equivalent to a linear procedure. Already
<<PAGE-DIVIDER>>
On discrete-time polynomial systems 63
when considering linear systems over rings, however, the definition of "procedure" becomes more
delicate, and is in fact directly related to the existence of "observers" which are systems over the
same rings, see Sontag [6]. It is natural in the present context to ronsider an algebraic notion of
observability. I" other words, we shall only allow algebraic operations on the input-output data.
This is formalized as follows:
Definition 8.2. A system E is algebraically observable if there exist an integers and Co = (6oj--0),)
c=(U*)', such that for every costate q e A(X) there exists 4 e A(Y') with
4-H" = q,
where H": X --* Ys is given by x ~-4 (h"(x), . . . , h',(x)).
Clearly this definition amounts to requiring that A(Hc"): A(Y') -+ A(X) be a surjective comor-
phism. The image of this comorphism is called the observation algebra of the system. Now the
uniqueness theorem can be proved.
Theorem 8.3. Let Y, ~_' have the same input-output map. Assume that Y. is quasi-reachable and
that i is algebraically observable. Then there exists a unique morphism T: Y_ --+ L If i is quasi-
reachable [resp. reachable] then T is dominating [onto]. If Z is observable then T is injective. If
Y_ is algebraically observable and i is quasi-reachable then T is an isomorphism.
Proof. Let the dimension of Z be n. It follows from quasi-reachability of Z and from (5.4) that
g~: U' --+ X is dominating. So, by (1.8), ~ ~ A( gn) : A(X) - A(U") is injective. From the definition
of algebraic observability we obtain s, w such that A(h-): A(V) , A(g) is surjective. Con-
sider the diagram: A(X)
A(Y') A( Un)
A ('k)
Clearly there exists a (unique) k-algebra homomorphism q making the diagram commutative.
It follows from the equivalence of categories (1.6) that there exists a (unique) T: X such
that A(T) = q. A routine calculation shows that T gives the desired morphism.
Uniqueness of T is clear, and the rest of the proof is straightforward.
As an application, we consider the class of state-affine systems: U = k, Y = V, X k", h is
linear and p(x, u) is of the form pju) + P2(U)X (these systems are sometimes called ilariable-struc-
ture systems). In this case the maps h' are affine maps, so that the notions of abstract observability
and algebraic observability coincide (see 1.9). Then:
Corollary 8.4. Let 1, ~ be observable variable structure systems. Assume that f. = f
E Qis isomorphic to i Q, j. Then
CONCLUSIONS
We have presented in this paper several preliminary results relating to reachability, observa-
bility, identification, and isomorphism of polynomial systems. One of the main problems not
discussed here, the problem of minimizing a given system, requires an extension of the present
framework, because the category System is too "small" to permit needed operations (quotients,
etc.). This amounts to saying that Affine cosystems is too "small" and should be replaced by
Cosystems. By dualizing the latter, we obtain a category Scheme Systems containing the original
category Systems. Recent investigation shows that a satisfactory theory of minimal realiza-
tions exists for scheme systems. Although it is not at all clear that the "physical" realization of
such generalized systems would be of interest, only by embedding the theory of nonlinear systems