This PDF 1.3 document has been generated by Canon / , and has been sent on pdfarchive.com on 07/07/2013 at 17:23, from IP address 67.233.x.x.
The current document download page has been viewed 1289 times.
File size: 22.86 MB (71 pages).
Privacy: public file
NASA Contractor Report 3016
Lectures on Algeb r"ic System Theory:
Linex Systems Over Rings
Edward W'. Kamen
CONTRACT A43TI9.B
JULY
1978
N/\SN
National Aeronautics
and Space Administration
Scientilic and Technical
lnlormation Otlice
1
978
PREFACE
This report provides an introduction to the theory of linear systems defined over rings. The theory is presented with a minimum of
mathematical details, so that anyone having some knowledge of linear
system. theory should find the work easy to read. The presentation
centers on four classes of systems that ean be treated as linear systems
over a ring.
These
are (i) discretetime systems over a ring of scalars
the integers; (ii) continuoustime systems containing time delays;
largescale discretetime systems; (iv) timevarying discrete
such as
(iii)
time systems.
The
material given here is an expanded version of a series of lec
tures given at
NASA Ames Research
during the week of
November
Center, Moffett Fie1d, California
7, L977. I an very grateful to Professor
R E. Kalman and Brian Doolin for the opportunity of giving these lectures.
My
gratitude also extends to Eduardo Sontag' Yves Rouchaleau, and Bostwick
for countless hours of discussions on linear systems over rings'
Part of the research work presented here was supported by the U. S' Army
Research Office, Research Triangle Park, N. C., under Grant DAAG2977G
Wlzman
0085.
1.
INTRODUCTION
1.1 Linear systems over fields.
Since the late 1950'sf a great deal of effort has been devoted
to the study of linear fjnitedimensional continuoustime and discretetime
systems specified by stat,e equations defined over
a field K.
More precisely,
given a triple (FrGrH) of nxtr nxm, pxn matrices over a field Kr. a
m
input poutput ndimensional timeinvariant discretetime system is
defined by the state equations
x(t+1)=Fx11;+eu(t)
(1.1)
y(t) = Hx(t)
where E<Z =
set of integers. In the continuoustime case, with r = n
field of real numbers, a timeinvariant system is given by lhe state
equations
P
=Fx(r) +cu(r)
(r.2)
y(t) = Hx(t)
where
teR. In both (1.1) and (L.2) , the state x(t), input u(t),
output y(t) are column vectors over the field
1
K.
field
Tnitial efforts in studying linear systems defined over a
Kusuallyassl$edthatKwasaparticularinfinitefield,suchasthe
fieldRofrealnumbers.Infinitefieldsarefieldsthatcontaina
subsetwhichcanbeputintoaonetoonecorrespondencewiththesetof
nurnbers
integers. In addition to the field R' the field of rational
andthefieldofcomplexnrunbersareexamplesofinfinitefields.
theory of timeThere are several textbooks (e.9., lL,2,3l) on the
invariantandtimevaryinglinearsystemsdefinedoverthefieldR.
Inasequenceofpublicatlonsbeginningin1965'R'E'Kalman
4,5,6Td.eveloped.analgebraictheoryfordiscretetimesystemsofthe
field K'
form (1.1) defined over an arbitrary (finite or infinite)
in addition to being applicable to systems over the real or
systems over finite
complex numbers, Kalmanrs theory can be applied to
Hence,
fields, which includes linear sequential circuits [7] '
L.2 Discretetime systems over a ring of sealars'
Afterthecompletionofhisworkondiscretetimesystems
over arbitrary fields, Kalman initiated the study of discretetime
sys_
rings. The notion of a ring is a generalization of the notion
and multiof a field: A ring is a set with two operations, called addition
elements
plication; however' unlike a field' a rlng can contain nonzero
tems over
thatdonothaveamultiplicativeinverse(see[B,chapterI]]).
the usual
An example of a ring is the set of integers z with
addition and multiplication operations. since neZ has a multiplicative
a field'
inverse belonging Loz if and only if n = 1 or 1' Z is not
in a symbol
Another exanple of a ring is the set K[z] of polynomia]s
2
z
with coefficients in a field K, with the usual operations of polynomial
addition and multiplication.
The only elements
in K[z] that are invertible
are the nonzero polynomials of degree zero.
The
first detailed results dealing with discretetime
systems
over arbitrary colnmutative rings were derived in Rouchaleaurs Ph.D.
thesis t9l in
concerned
the supervision of R. E. Ka1man. This work was
L972 under
with the class of linear timeinvariant discretetime
systems
over a commutative ring A given by the state equations
x(t+1) =rx11; +cu(t)
(1.3)
y(t) = ux(t)
where
teZ, F, G, H are nxn, nxm, pxn matrices over the ring A, and x(t),
u(t)  y(t) are column vectors over
A.
An interesting example of a system over a ring is a system
with the ring of scalars equal to z. By definition, such a
system
accepts vector sequences ovey z, processes these sequences using integer
operations, and then outputs vector seguences over Z. These systems are
of interest from a computational standpoint, since integer operations
can
be implemented "exactly" on a digital computer (assuming that magnitudes are
less than IO12 for I2digit precision), Further, systems over z appear
in various applications, such as coding theory [10] and scheduling or
sequencing problems
tfll
.
3
1.3 Continuoustime systems over rings of operators'
In1973,Kamen[12]showedthatalargeclassoflinearinfinitedimensional continuoustime systems can be represented by firstorder
vector differential equations defined over a ring of operators (due to
publication delays , l:l.2l did not appear in print until 1975) ' The ring
in t12l and [13,14] applies to timeinvariant and timevarying continuoustime systems containing pure and distributed tine
delays. Independently of this work, williams and Zakian [15,16] constructed
approach developed
the
same
type of operator setting for a class of timeinvariant continuous
tlme systems with pure time delays'
In this section we shall define the operator framework for the
class of systems with commensurate delays given by the dynamical equations
ax(t)  of F.x(t ia)+
'dt
?^a
1=U
y
I crt(tia)
i=0
_L
(t) _t
i=0
(1.4)
H,x(t
 ia)
T
a is a fixed positive number, the F., Gi'Hi are nxn' nxm' pxn
column
matrices over the field of real numbers R, and x(t), u(t) ' y(t) are
where
vectors over
R.
x(t) in (1'4) is usually referred to as the state at
time t; however, as a result of the delay terms' the actual state at time
t is the function segment x(t), t  qa < r < t To solve (1.4) for t > 0,
The nvector
we need to know the actual state at time t = O, which consists of the func
tion segment x(t),
qa < 'r 3 0.
4
In the mathematics literature, equations of the form (1.4), or
generalizations of (1.4), are usually treated as ordinary differential
equations in a Banach or Hilbert space consisting of function segments
(see [17,18,19]). In contrast, we shalt view (1.4) as a vector differen
tial equation with coefficients belonging to a ring of delay operators'
The constructions are as follows
Let V denote the linear spaie consisting of all Rvalued functions
defined on R with support bounded on the left {i.e.,
for each veV, there
Let d:v+V denote the asecond
is a tVeR such that v(t) = o for all t<t_).
V
delay operator on V defined by (dv) (t) = v(ta), v€V. We can extend
d to
column vectors
v = (vl,  . rtr)' over V by defining
(dv)(t)  (vl (ta),..,vn(ta))'
where the
prime denotes the transpose operation.
r a.di where a.<R and
Let Rldl denote the set of all finite sums irlj
(d]v) (t) = v(t_ia), v€v. with the usual operations of polynomial addition
multiplication, R[d] is a ring of delay operators'
Now vlewing the state trajectory x and the input function u as
(1'4) in the form
column vectors over V (or some subspace of V), we can write
and
(r)
%tI = (F(d)x) (r) + (G(d)u)
(1.5)
y(t) = (H(d)x) (t)
5
the operator ring
where F(d), G(d), H(d) are nxnf rIxIIlr Pxrl matrices over
R[d] given
bY
q
F(d) =
I
i=0
_l_
F.d
, c(d) =
l_
r
I c'da,
a=U
fi
H, di
u(d) _L
l_
i=0
of timedelay systems given by (1'A) can be studied
(1.5) defined over the ring
in terms of the vector differential equation
Thus the class
Rtd].Weshallrefertothesystem(1.5)asalineartimeinvariant
continuoustime system over the rinq of operators Rtdl '
given by the dynamical
EXAMPLE 1.1 Consider the timedelay system
equations
dx (t)
+=
dx" (t)
dtr
xl(ta) +xr(t) xr(t2a) + u(t)
= x (t) + xl(ta)  xr(t) + u(ta)
y(t) = xr(ta)  xr(t2a) + xr(t)
(1.5) with
This sYstem of equations can be wrilten in the form
r'(d)
=
II
G(d)
=
6
[l
u
rar =
[42
I
By
exploiting the structure of the operatorring representation
(1.5), we can develop an algebraic theory for the class of timedelay
systems given
by (1.4). In particular, we can obtain constructive results
given in terms of operations on matrices and vectors defined over the ring
R[d], or ring extensions of R[d].
Examples
wilL be given in the next
three chapters of these notes.
As noted above, systems with'noncommensurate delays and distributed
delays can be studied in terms of differential equations over rjngs of
data for equations of the form
operators. AIso. as shown in [14], initial
(1.5), or generalizations of (1.5), can be incorporated into the operator
framework.
Note that in the representation (1.5), the elements of the ring
Rtdl act on functions; whereas in (1.3), the elements of the ring
A
act on values of functions. This is the reason for referring to (1.5)
as a system over a ring of operators and (1.3) as a system over a ring
of scalars.
using the
We
shall
show
that both types of systems can be studied
same techniques.
I.4 Discretetime systems over a ring of operators.
In this section we shall
show
that there are discretetime
systems
that can be treated as systems over a ring of operators. Consider the
class of discretetime systems given by the following dynamical equations
qr
x(t + 1) = I r.x(ti) + I c.u(ti)
g1
a=U
t=U
S
v(r) = I n.x(t_t)
a=u
l
where EeZ, the Fi,Gi, H. are nxn' nxm, pxn matrices over a field K,
x(t),
u(t)'
y(t) are colunn vectors over
7
K.
(1.6)
5sginrssn
Note the similarity
(1'4) and (1'6) '
In fact' if
we
proceedaswedidaboveforcontinuoustimesystemswithtimedelays'
difference equation
it is clear that we can write (1'6) as a vector
riohtover the operator rinq K[ o] consistincr of al1 colvnomials in the
to the fjeld
shift operator o:x(t)+x(t1) with coefficients belonging
K. More PreciselY, we have that
x(t + 1) = (F(o)x) (t) + (G(o)u) (t)
(1.7)
y
where F(o), C(o),
tt (o
(r) =
(H (o)
x) (t)
) are matrices over Klol given
r(o) = .iI"ro^,
1
G(o)
.i

lv,v
?r_
a
f
bY
.i
H(o) = ?a
)H.o
a
WeshallreferLothesystem(1.7)asalineartimeinvariantdiscretetime system over the ring of operators K[o] '
(highdimensional)
Via the representation (1.7), we can study large
discretetime systems in terms of
some subset
of the set of all possible
statevariables.Thisismadepossiblebytumpingtogethercomponents
In ot'her
with memory in the coefficient matrices F(o), G(o), H(o).
aggregated model for
words, the representation (1.7) can be viewed as an
large discretetime
sYstems'
B
The representation
(1.7) is a natural model for systems consisting
of an interconnection of subsystems separated by time lags with the
components
of x(t) equal to the states of the subsystems. This is
illustrated by the following
EXAMPLE
1.2
Suppose
example.
that K = R. Consider the discretetime
system given by the following block diagram.
Here
xl(t) (resp. x, (t) ) is the state of the
function L/ (z+lj (resp. L/zl)).
We
subsystem having transfer
have that
xr(r+1) =*1(r) xr(t1) +u(t)
xr(t+1) = xr(t) + xr(t1)
Y(t) = xr(t)
These
equatl cr:s can be w ritten
r'(o)
=
[: I
in
the form (1.7) with
H(o)
[]
9
=F
!
. Defining xt (t) =
have a representation of order two over R[o]
a f ourdimensional representation
x, (t1) and x,4z(t) = x. (t1) , we also have
Thus
we
over
R
given by
tr+rf Fr
'll
xrtt+r)l lo
*(r+r)l
II
rll
"
xntt+rl
Y
I
L.
'l
F,
,Jl '
o
0
1.
I
;ll";;.;l.l;1",.,
0
o
o
1
0
'l [r''l b]
I
I i*rt.rl l.
(1.
B)
I
(t) = x, (t)
TherepresentationoverR[o]canbeveryuseful'becauseinsomeproblems
work with the
it is more efficient from a computatjona1 standpoint to
than the fourdimensional
two*dimensionar representation over R[o], rather
Chapter 4'
representation over R' An example will be given in
1.
5 Additional
examPles'
In addition to the
examples given above' there are many other
examplesofsystemsthatcanbetreatedaslinearSystemsoverrings.
Theseincludesystemsgivenbydiscretizedpartialdifferentiatequations
digital filters viewed as linear
l2O,2Ll and linear twodimensional
in one variable
defined over a ring of proper rational functions
systems
122)
'
Lineartimevaryingsystemscanalsobeviewedassystemsoverringis,
inthiscasearingoftimefunctions.However,thealgebraictheory
oftimevaryingsystemsdiffersfromthetheoryoftimeinvariantsystems.
from the fact that timevarying
The primary reason for the difference it"*=
systemsrviewedassystemsoveraringoftimefunctions'mustbestudied
cal1ed a pseudolinear
in terms of a special type of nonlinear transformation'
10
transformat.ion [23].
In the last chapter of these notes' we develop this
The
approach for the class of linear timevarying discreteLime systems'
theory is based on the concept of a semilinear transformation, which is
an example of a pseudolinear transformation'
 11
2.
REPRESENTATION AND REALIZATION THEORY
2.I Abstract systems over rings'
ForthethreeclassesofsystemsdefinedinSections1.2L.4,
depend only on
it turns out that many structural and dynamical properties
thetriple(F,G.H)ofmatricesappearinginthestateequations.In
(e.9.,
other words, the particular form of the dynamical equations
primary consideration'
discrete time or continuous time) is not always a
Thusiispossibletodevelopageneraltheoryofsystemsoverrings
This was the
specified in terms of a triple of matrjces over a ring'
rings'
by Sontag in his survey paper 1241 on systems over
approach taken
define the major components of the theory' beginning
with the notion of an abstract system over a ring'
and let n' m' p be
DEFINITION 2.1 Let A be a commutative ring
In this section,
we
fixedpositiveintegers.Anabstract(free)lineartimeinvariantsystem
overAisatriple(F,G,H)ofnxn,fixlllrPxllmatricesoverA.Theinteger
n is called the dimension of the system (F'G'11) '
Althoughtheconceptofanabstractsystemdoesnotincludeany
explicitreferencetodynamicalbehavior'anabstractsystem(F'G'H)
canbeinterpretedasadynamicalsystembyassociatingasetofState
equationsspecifiedintermsofF'G'H'Forinstance'(F'GfH)canbe
interpretedasadiscretetimesystemovertheringofscalarsA,given
by the state equations (1'3)'
Let (F,G,H) be an abstract system over the ring A'
Suppose that
CisaringextensionofA,i.€.,AisasubsetofCwiththeproperty
thatadditionandmultiplicationinC,whenrestrictedtoelementsinA,
rn other words. the
are identicar to addition and muttiplication in A.
L2
ringAisasubringofC'ThensincetheelementscomprisingF'G,H
can be viewed as elements of c, (F'G,H; can be viewed as an abstract system over C.
ItisofparticularinteresttonotethatwhenAisanintegral
Integral
domain, there is a ring extension of A which is a fie1d.
domains are commutative rings that do not contain divisors of zeto'
Thatis,ifab=Oforsomea'b€A,theneitheraorbmustbezero.
Examples of integral
domains are the ring of integers Z and the operator
rings R[d] and Klol constructed in the preceding chapter'
An integral domain A can be viewed as a subring of a field
Q
(A)
'
ca1led the quotient field of A. The field Q(A) is equal to the set of all
formalratiosa,/bwherea,b€A,blo,withadditionandmultiplication
defined by
ut/bt+ ar/b, = (arb, *.2b1)/$Lb2)
(ar,/br)
Gr/b) =
(arar) / (br/b2)
For example, the quotient field of Z is the field of rational
and the quotient field
Now
,.;:
numbers
of R[d] is the field of rational functions in d'
given an abstract system (F,G,H) over an integral domain A'
:a:l view (F,G,H) as a system over the quotient field Q(A) '
;i3i3 =x. ss the possibility
of utilizing
results from the theory of
svs:e!:ls c.=r :i=lCs in the study of systems over rings'
Although
this approac:: is i:seful (e.g., in the realization problem), the

l3
Thus
quotientfield
framework seldom gives a complete solution to a given
problem, si.nce in general the results are specified in terms of elements
of Q(A), rather than elements of A'
Next, we have the concept of an input/output sequence'
input/output
DEFINITION 2.2 Let m,p be fixed positive integers" An
(L/o) sequence f over a commutative ring A is a sequence f = GL' J2' "')
system
consisting of pxm matrices over A. The i/o sequence of an abstract
(F,G,H)oradynamicalsystemspecifiedintermsof(F'G'H)isthesequence
iI
f = (J,, J", ...) where Ji = H(F )G for r = r'z'"'
LZ
In the remainder of this section, we shall show that the i/o sequence
associated with the systems defined in sections 1.2  L.4 completely characterizes the input/output behavior of these systems'
(a) Consider the discretetime system over the ring of scalars
Solving (r.3) by iteration,
with the dynamical equations (1.3).
that the state x(t) at time t resulting from initial
t^o < t and input u(t),
A
we have
state x(to) at time
t = ao is given by
tt ox(to) +'l
 i'rciI"rr(i),
x(t) = I'
t > to
(2.1)
:
IL!
o
If x(t ) = O, the output resPonse is
Lt
y(t) = I
i
HF
Lrrcu(i),
t
L4
t >t
(2.2)
From
(2.2) it is seen that the input,/output behavior of the system is
i 1*G
ptetely determined by the sequence (tr_,tr,...) wher" Ji = HF
com
for i = L,2,..
(b) consider a continuoustime system over the operator ring R[d]
with the dynamical equations (f.5).
that x(t) = O for
t < O and taking the (onesided) Laplace transform of (1.5), we get
Assuming
y(s) = tt(eas) (sr  r("u");161.t=;u1=1
where
r(eas),
settingd=."",
of u (t)
(v
(t) ) .
G{eas)
*") are
, H(e
_ac
and where
Thus
computed from
F(d), G(d), H(d)
by
U(s) (resp. v(s)) is the Laplace transform
the transfer function matrix Tlsreas) is given
T(s,"as) = n(eas) (sr  F(.""))rc(.t")
we have that
Expanding (sr  F(.""))1 i.rto a power series ir,
"1,
T(s,eas) = I Hleas1Ui1(.=)G(eas)si
i=1
Hence
T(s,eas) can be determined from the sequence (Jl(d),J2(d),...),
vhere J. (d) = H(d)ril(a)G(d).
15
by
operator ring
(c) Consider a discretetime system over the
(f'7) ' we shall specify the input'/
K[o] with the dynarnical equations
the formal ztransform defined as follows'
output behavior using
LeEzbeasymbol'Givenafunctionf:Z>KwiLhf(t)equaltozero
fort<0,wedefinethe(formal)zLransfoxmofftobetheformalpower
r?i
series F(z; = L f(i)z
the ztransform
,::h. that x(t) = O for ts O and take
of (1.7) '
we get
r
y(zr) = T(z1)u(z1)
I.
is lhe transier function matrix'
= H(z ) \zr  r,(rt))lc("l)
t
1)) 1 into a formal Power series Ln z , we have that
(z
F
Expanding QI
*)
1
where T(z
eL)ri
,,(rr) = i
"1"1;uir(r1)c
i=l
(2. 3)
where J' (o) = H(o)ril(o)G(o) '
' J2G)' " ') '
the expansion (2;3)
However' it should be noted that
Thus the sequence (Jl(o)
determines r("1)
isnotunique.Therefore,theinput/outputbehaviorofadiscretetime
uniquely by a sequence (Jl(o)' J2(o)
system over K[o] cannol be characterized
over Klol
.
2.2. Problem of realization
to realizability
rn this section we present a general approach
systems' The results given here can
based on the concept of abstract
systems over a ring of scalars
be applied directty to discretetime
a ring of delay operators'
and continuoustime systems over
16
2.3
DEFINItION
An abstract system (FrG,H) over A is a realization
of an i/o sequence (J1,J2,...) over A if and only if Ji = Hlpi115
for i = I,2,...
A realization (F,G,H) is minimal if its dimension is
minimal among all possible realizations.
Let us first
consider the realization
of a scalar sequence f
=
(a.,a.,..),
ae A" To the sequence f, we associate the formal power
LZa
s
'
r =
series w(zr)
I rrrt in the symbol r1 rith coefficients in the ring
i=I
A. The power series w(zl) is said to be rational if it can be written
as a ratio of the form
cn1_z n1 +c nz^z n2 f ... + c1z +
w(z ') n
nl
z+ez+...+ez+e^
l
cO
(2.4)
NIIU
where the c.,e. € A.
l_
We
J_
then have the following resuLts
on
realization.
The proofs of
these results are omitted, as lhey are easy generalJzations of the field
case.
PROPOSITfON
2.4
A scalar sequence is realizable if and only if
its associated power series r(r1)
PROPOSITION
2.5
series given by (2.4).
common
is rational.
Let f be a scalar sequence with associated power
If the polynomials comprisir,g r(r1)
contain
factors of degree > 1, then (r,g,h) is a mi_nimal realization
C
1
00
l
t0
r
,a
0
0
L
ee
0
.e
2
Ll 
,h=
no
of f
F. cr ...""_il
The
extended to matrix
result in Proposition 2'4 can be
t = (rfr2,...)
sequenc
u":;...1" t"':lt matrix:*:t
as rorlows. Ler w(rI)
' By definition'
.,'€" wt'rl =rl1
series in ,1 t"=o"iated with f i
"" scalar power series
whose elements are
can be written as a matrix
"("t)
if each element of w(zl) is
ir, ,r. The matrix w(z\; is rational
rational

We
then have the following result [24] '
PROPOSITION
2'6
The
and onlY if
matrix sequence f is realizable if
:
its associated power series is rational'
realican be aPProached bY first
The realization of matrix sequences
the resulting realizations are seldom
zing the elements of w(zI) ' but
teaLizaspecial class of rings, minimal
minimal. As will be seen' for a
Hankel
(J1'J2" ") can be constructed from the
tions of a matrix sequence f =
matrix
B
(f) given
bY
[",.
tz
I
It2 J^
"3
J3
t4
I
I
B(f)
=
l"^
J 4)
J
I
I
I
l
1
L
f over a field K is
It is well known [6] that a matrix sequence
B(f) is finite' The rank of B(f)
realizable if and onlY if the rank of
minors of B(f) of order greater
all
that
q
such
integer
smallest
is the
B(f) is finite' f has a minimal
than q are zero' If the rank of

IB
of dimension equal to the rank of B(f).
realization
Realizability
results for matrix sequences over fields can be applied
to matrix sequences over an integral domain A: Given such an f, we can view
f as a sequence over the quotient field Q(A). Then since Q(A) is a field,
f has a realization
finite
over Q(A) if and only if the Hanke1 matrix B(f)
rank as a matrix
over
Q
(A)
.
has
But since we are seeking realizations
over Q(A) implies realiz
over A, we would like to know when realizability
over A. As proved in t9l, this is the case for the class of rings
ability
referred to as principal
t25,26,271)
A
ideal domains (for more general results
see
.
principal ideal domain (p.i.d.) is an integral
domain
A with the
property that, for any subset S of A such that a + beS whenever a,beS
and abeS whenever aeA, beS, there is an element aeS such that S = {ab:beA}
(i.e.,
every ideal S of A is generated by a single element
aeS )
.
The
ring of integers and the operator rings a[d] and K[o] are examples of
p. i.d. 's.
since realizability
is a p.i.d.,
over Q(A) implies realizability
over A when
A
we see that if a matrjx sequence oveg z has a realizatjon
over the fietd of rational numbers, there is a realizaLion over Z; and if
a matrix sequence over Rlcll has a realization
functions in d, there is a realization
over the field of rational
over R[d].
These are very interes
ting, results.
It is proved in i9l that a realizable matrix seguence f over a p.i.d.
has a minimal realization
of dimenslon equal to the rank of the Hankel
matrix B(f) as a matrix over Q(A). In the p.i.d.
case, mjnimal realizatjons
can be computed from B(f) using Rouchaleau's algorithm t9l.
19
The algorithm
yieldsaminimalrealizationoverQ(A)usingsilverman'sformulas,fromwhich
aminimalrealizationoverAisgeneratedviaasimilaritytransformation.
Thestepsofacondensedversionofthisalgorithmaregivenbelow.
of pxm matrices
Let f = (J r,J r. . ) be a matrix sequence consisting
finite rank equal to n'
defined over a pi.d' A' Suppose that B(f) has
Then a minimal
realization of f over A can be constructed by carrying
out the following steps'
(1) Let C be a nxn submatrix of
(2) Let D be the
nxnm submatrix
B
(f) having rank n as a matrix over
of
B
(A) '
Q
(f) containing the same rows as c
first n block columns of B (f) '
be the
(3) From D construct a nxn matrix V as follows' Let bl
and the
greatestcommondivisoroftheelementsinthefirstrowofD.Thereis
anAlinearcombinationvrofthecolumnsofDhavingbrasfirstelement;
r'eA such that the first element
anrl for each column d. of D' there is a
d2 '2uL ' ' un*  r*nvrJ '
of d.a  rirt i" zero. Define Dl = [d1  tltl
with the second row' which yields a
Apply the sarne procedure to D1 working
column
vectorvrandarilatrixD2'Continueuntil[t1't2"'t,,]=Visconstructed'
of B(f)
(4) Let N be the nxrn submatrix of the first block column
containing the
same rows
as c'
B(f)
(5) Let E be the pxn submatrix of the first block row of
containing the
(6) Let
same columns as C'
M
right of C'
be the nxn submatrix of B(f) sitting to the
Then (F,G,H) is a minlmal realization of f where
F
= tvl)l,t(ct)v, c = (v1)n,
20
H =B(c1)v
(2.5)
2.3
Example
Consider the continuoustime system with time delays given by the
transfer function matrix
T(s,es1
We
=
)
s
want to
+
(ec I) se c
compute
t . "'"1
es s+
['
1
["
a mjnimal realization of T(",.=) given by a triple
(F(d), c(d), H(d)) over the operator ring n[d] with
T(s,es) = H(e s) (sr 
F
(es)
)lc(.=)
Since Lhe least common denominator (as a polynomial
in s) of T(sres)
has degree equa
to two, it follows that T(=,.") has a realization over Rldl
of
we
dimension 4.
shall
compute a minimal
realization using the
algorithm. Fir t, expanding T(sres) into a power series i., =I,
. s.
T(s,e
)
I
I'
=t
above
we get
l
1 3
l Il"1* lI "= r+eJJ
"r.

s l=
 1 I "'*lfe2s .'*r[
o J*
L"=
.=
2I
Then
t
T
lr
l_,
lI
o
tl"
le
I
B(f)=
t
e
e
r1
S
.S
I
I
I
I
t
I
I
I
I
s
0
l++e
s
1+e
1
2s
I
I
1
t
I
+l t'
es_
2s
I
I
I
L
of B(f) must be less
Since there is a realization of dimension 4, the rank
any more blocks
than or equal Lo 4, so it is not necessary to consider
in B(f) than those given above'
Checking the minors
of the 4x4 submatrix of
2. Thus there is a realiB(f) given above, we find that the rank of B(f) is
zation of dimension 2. we then choose
['L' "1ol
so that
il1
s
ee
ID= l_
;I
0e
22
s
s
1+e
1
1
I
Applying the procedure g:iven in Step (3) to D, we get
[r
.._tt
v t
l'
lfehavethatN=E=Cand
M
o
I
I
^sI
,*.1
[."
=
t
L.=
]
Then from (2.5) , we have the following mlnim a1 reali zation of T(s,e "):
F(d)
In
=
F.
L. ,
component
dx, (t)
dr
dx, (t)
*
t*u*u'l
=
c (d)
.1'
Fq
=I
H
(d)
J
form, the realization is given

FE
tt
['
ei
by
xI(t1) + xr(t) + xr(t1) + x2(L2') + u1(t) + u, (t1)
= xr(t) + ur(t)
y1(t) = x, (t)
vr(t) = xr(t) +xr(t1)
23
3. REACHABILITY, OBSERVABILITY,
AND DUALITY
Weshallnowstudytheconceptsofreachabilityandobservability
fordiscretetimeSystemsoveraringofscalarsandconinuoustime
Systemsovertheoperatorringn[d].Theresultsobtainedhereleadto
systems over
a definition of reachability and observability for abstract
rings.Inthelastpartof,section3.3,weconsideraconceptofduality
for abstract
systems.
3.1 Discretetime systems over a ring of scalars'
equations
Consider the discretetime system given by the state
x(r+1)
=Fx111 +Cu(t)
(3.1)
y(t) = ttx(t)
the ring A' Let An denote
where FrGrH df€ flxor fiXIIIr pxn matrices over
the set of all
nelement column vectors over A.
DEFINITION
3.1
ThE
there is an integer N >
0
system (3.1) is reachable if for any xcAh'
and inputs u(0) , u(1) , .. " ,u(N1) thaL drive
the system from the zero state at time t =
O
to the state x at time t
n
Thesystemisreachableinnstepsifforanyx€A..,theintegerNcan
=N.
be taken
to be n.
the initial
time
of generality' since the
system
In Definition 3.1,
does not imply any loss
we have taken
to be zeYa This
is time invariant
Let v1'v2 ,..',Yqbe fixed elements belonEing to An . We say
be written
that xeAn is an Alinear combination of vr'vr" " 'vn if x can
in the
i
form
q
x= I? ..n.a
r
II
for some e.a €A
24
!;1.
ffi
Hl
In terms of this conceptr we have the following criterion for reachability.
PROPOSITTON
3.2 The following conditions are equivalent.
(1) The system (3.1) is reachable.
(2) The system (3.1) is reachable jn n steps.
(3) Every element of An can be written as an Alinear combination
of the columns of G,FG,...,FtlG.
Proof. f'rom (2.1), the state x(n) at time t = n starting
x
from
(0) = 0 is given by
_1
x(n) = i u"ita,rtil
(3.2)
i=0
The equivalence
of conditions (2) and (3) follows frorn (3.2)
The
equivalence of conditions (1) and (2) follows from the CayleyHamilton
theorem [8, page 400].
coRoLLARY
3.3 Let
m
= 1 (the singleinput case). Then (3.1) is
reachable if and only if the nxn matrix [G,FG,...,FtlG] is invertible
over A, which is the case if and only if the determinant of [G'FG,...,FtlG]
has an inverse in e.
EXAMPLE
3.4
Suppose
that. (3"1) is a singteinput system over the ring
of integers Z. Since the only invertible elements of Z ate *1 and 1,
by Corollary 3.3 we have that the system is reachable if and only if the
determinant of [G,FG,...,FtlG] is equal to *] or 1" Thus, given a system
selected "at random", it is very unlikely that every element in Zn can
be
reached using integervalued controls.
Again consider the system (3.1) defined over the ring A" Let U de
note the
nxmn
matrix [G,FG..,.rrtlc]" and let
ueAmn
denote the control
vector u = [u(n1) u(n2) .." u(1) u(0)]'. It foltoios from (3.2) that u drives
25
the system to the state xcAn at time t = n if and onlv if u satisfies the
equation x = Uu. If the system is reachable, .in the singleinput case there
__I
1
a unique solution given bY u = U X, wnere u ls the inverse of U' In the
multiinput case (m > 1), the computation of a control u (if one exists) is IN
general a difficult
Problem
For a class of fields, we have the following
result.
THEOREM
1
3.5 Let A
=
for any a.€K. Then the system (3.1) is reachable if and only if the nxn
matrix U(U') is invertible
u
K, where K is a field with the property that lrur'/
over K, in which case a solution ,"tf,t of x = Uu is
= (u') Iu(u')ll 'x.
of
The above result is well known for the case in which K = R = field
real numbers" The usual proof for the K = R case extends to the class of
fields Kwith the property thatlr.rt
that
when K
I I for any a.<K. It is also well
= Rr the control u = (u') Iu(u')l1x minimizes lirrll, *L,"r" ll
known
ll
denotes the Euclidean norm, and where u ranges over all solutions of x = Uu.
In the ring case. j.nvertibility of U(U') over A implies that the
system
is reachable, but the converse is not true:
EXAMPLE
3.6 Consider the discretetime system ovex Z given by x(t + 1)
x(t) + u,(t)
+ u.(t), y(t) =Hx(t).
L2
Here
G= [1 1], andU = G. Since the
columns of u generale z, the system is reachable. But u(u') = 2, which does
not have an inverse in Z.
Novi assume
that A is an integral domain with quotient field
Q
(A)
having the property that I*.*2 I r for any a.ee(A). suppose that the system
"l l(3.r), viewed as a system over Q(A), is reachable. Then by Theorem 3.5,
any x€An can be reached by applying the eontrol u = (U')[U(U')]Ix,
in general is defined over
Q
(A)
. This is an acceptable solution if the
control over Q(a) can be generated.
26
I
Fi
$
which
=
3.7 Again let (3.1) be a system ovey Z. Viewing (3.1)
EXAMPLE
as
a system over QG) , the f ield of rational nurnbers, we have that it is
reachable if and only jf the determinant of U(U') is nonzero. In this case,
the control
u
= (U')[U(u')] t 'x would be a vector of rational
numbers
in
general.
For systems over Z, a very interesting problem is the computation of
integervalued. controls u that minimize llull, wfrere u ranges over all integervalued solutions of x =Uu.
the determinant of U(Ur) is equal to +1 or
1, an integervalued solution minimizing llull is u = (U') [U (u, ) ] 1x. Unfor
tunately, invertibility
When
of U(U') is too severe of a condition to be of
much value.
For systems over a p.i.d. (such as Z), controls belonging to A*t .r,
be computed by first putting U into di_agonal form (the Smith form) using
row and column operations (see [28, page 109] ) . The details of this
proce
dure will not be considered here.
We now
consider the concept of observability.
DEFINITION
3.8 The system (3.1) is observable if for any nonzero initial
state x(O)<An, there is an integer N > 0 such that the output response y(t)
resulting from x(0) is nonzero for at least one value of t <{0,1,...,N1}.
system is observable in n steps if
for any nonzero x(O)eAn, the integer N
be taken to be n.
PROPOSITfON
3,9 The following conditions are equivalent.
(1) The system (3.1) is observable.
(2) The system (3.1) is observable in n steps.
(3) There is no nonzero x€An such that
x' [H" (F') (H,),...,
(F')tl(H';
1 = g.
21

The
can
Proof.
initial
state
From (2.1), the output response y (t)
ILI
[." ,J
S
t < nl resulting
from
in the form
x (0) ean can be expressed
t::] =
for 0
(3.3)
x (0)
lo,""'J
Tire equivalence of conditions (2) and (3) follows directly
from (3.3).
The equivalence of conditions (1) and (2) follows from the CayleyHamilton
theorem.
Let V denote the npxn matrix
FI
v = tt
IHF
l:l
l'6,1
IJ(F
I
U
and 1et y€Atp denote the response vector ty(O) y(1) ... y(nl)l
the response vector y resulting from initial
given by y = vx.
icnowledge
We
By (3.3),
state xeAn at time t = 0 is
would like to be able to compute the initial
state x
from
of y. In the case of systems over fields, this problem is dual to
the problem of computing controls in the generation of states. ln particular,
we have
the dual of Theorem 3.5.
3.10 Let A = K, where K is a field with lr.r' I I for any a.€K.
fhen the system (3.1) is observable if and only if the nxn matrix (V')V is
THEOREM
invertible over K, in which case, given y = Vx for
24
some
x€Kfl, x = (V'V)1(V')y.
Proof.
Recall that a system over a field is observable if and only if
its dua1, specified in terms of the matrices F',H',G',
is reachable [5].
Then apply Theorem 3.5.
Although the d.uality between reachability
and observability
does not
extend to systems over rings (see Section 3.3), Theorem 3.10 can be extended
to systems over an integral domain as follows.
COROLLARY
3.11 Suppose that A is an integral domain with I . u.' I t
"L 1
for any a.eQ(A). Then the system (3.1) over A is observable if and only if
(V')V is invertible over Q(A), in which case, given y =Vx for
some xeAn,
x = (v'v)l '(v')y.
Proof. It is easily verified that the system (3.1) is observable if
and
only if it is observable as a system over the field Q(A). Then apply Theorem 3.10.
3.2 Contjnuoustime systems over a ring of delay operators
Consider the continuoustime system given by
q*P = (p(d)x) (r) + (c(d)u) (r)
(
y
(t) =
(tt (d)
x) (t)
where F(d), G(d), H(d) are nXnr nXrrlr pxn matrices over the operator ring
RIdl
.
Given a fixed positive nunber tl , let i,2( to,trJ;Rn) d.enote the Hilbert
space of squareintegrable functions on
lltll "t a function belonging to
llt
[0,t1] with values in Rn The norm
2n
L ( [o,trJ ;R')
ll' =
ff
'tt'
is defined
,', ll'u.
29
by
3.4)
where the norm
We
in the integrand is the Euclidean norm.
can now oefine the notion of Euclidean reachability.
3.12 rhe system (3.4) is Rnreachable in time a1 t
DEFINITION
if for any x€Rn, there is an input rrul,2([O,tr];nm) that drives the
O
system
to the state x at time t = t1 with initia1 state function x(t) = 0 for t < 0'
We
shall give a necessary and sufficient condition for Rnreachability
terms of the following constructions
Let I'4(t) denote the inverse Laplace transforrn of th.e nxn na+ri>i Ir'("t"))le(.t").
rt can be shown (see [14]) that the state x(t 1) at time t1
resulting from the input urt'2 ([c,tl];Rm) with x(t) = 0 for t < o i s given
x
(tr)
tt*,.,
=
f
r0
Define the map ).(tr):L2([0,t1];Rm)' RD:u +

map
(3.s)
s) u (s) ds
fL
 s)u(s)ds.
Jott,a,
We then have the following result which follows directly fron (3.5).
PROPOSITION 3.I3 The system (3.4) is Rnreachable in time t, if
only if the
by
and
tr(tr) is onto.
we can get an explicit condition
*
adjoint I (t1) ot tr (tt) defined bY
for reachability in terms of the
f tarl ,Rn*L2([0,t1];f)'xm'(t,  s)X, 0 < ". tl
Here we are using
on any finite
the result that the elements of M(t) are squareintegrable
interval 0 S t =
t1
.
 30
composition
l
(t1)
l *"(t1) is
a map from Rn into Rn given by
f (t1) I (ta)
:
x+B (ra) x
where
B
The
(r1)
=
I.t'.'  s)M'(L,  s)ds
matrix B(t1) is the controllability gramian for timedelay systems.
THEOREM
3.14 The system (3.4) is Rnreachable in time t1 if and only
if B(tl) is invertible, in which case the control r = tr*(tf)B1(tr)x sets
up the state xeRn at time t = tt. Further, this control minimizes llull,
where u ranges over all solutions of x = tr(tr)u.
Proof. Follows from standard results in the theory of linear transformations and their adjoints (refer to Luenberger's book [29]).
Although B(t) is constructed from the matrices F(d) and G(d), we would
like to have a criterion for Rnreachability specified directly in terms
of F(d), c(d). This can be accomprished by first noting that the system
(3.4) is Rnreachable in time tl if and onry ir l* 1tr; is onetoone,
which is the case if and only if there is no nonzero xcRn such that x'M(t) =
for 0 < t < t .
I
THEOREM
r
c (d)
We
then have the following result.
3.15 Glven the system (3.4),
 .^r
I ".dt,
a=u
suppose
that Ftal = fn,di
i:d
and
where the F. and G. are matrices over R. Then the following
l_
l_
are equivalent.
 31
0
n(r) The system is R"reachable in time tI for
n_
(2) The system is R"reachable in time t1 for
(3)
some
any
t I > 0.
tI > q(n])a + ra.
n
There is no nonzero xeR' such that
xt
Proof.
[c(d),F(d)c(d),...,T(a)nlc(d) ] = 0.
we shall show that (1) implies (3):
clearly, (2) +(I).
there is a nonzero xeRn such that x'[G(d) ,F(d)c(d),...,F(d)nle(a) I = c'
bY
Then by the cayleyHamilton theorem, x'F(d)iIc(a) = o for all i > 1. Now
Suppose that
definitlon of M(t), it can be
M
expanded
(r) = 
tr tal
i=1
it.
into the series
(u)
)
til, t '
o
Thus, x,M(t) = O for all t > 0, so the system is not Rnreachable.
(3)+(2): Suppose that the system is not Rnreachable for tl t Q(nL)a + ra'
+ ra'
Then there exists a nonzero xeRn such that x'M(t) = O for O < t < q(n1)a
Now
let A(t) denote the inverse Laplace transform of (sI  r("t"))1'
T
Then M(t) = (AG(d)) (t) = [ att  ia)G..
i=0
Evaluating M(t) at t = ia
and
noting that A(o) = r = nxn identity matrix, we have that x'Gi = 0 for i
o,It2,
.
.. tT.
Taking the first
Hence x'G (d) = o.
=
derivative of x'M(t)
 ia ja) c
O, we have that x' (F(d)AG(d) ) (t) = x' Ei' ^ I: r'.A(t
^r=u
t=u
lr=
at
t= ia* ja, we get
Evaluatingthis
forO < t< q(nl)a+ ra.
for t
=0
0r1,...,q and j = O r.,.. ,r, which implies that x'F(d)G(d) = 0'
Continulng in this manner, we can show that x'r(d)i]e (a) = 0 for i = I,2'""n'
::tF.G.
rl =
O
Now
for i
let
U
=
(d) denote
the
nxmn
and Let R(d) denote the quotient
sufficient
matrix [c(d),F(d)G(d),.'F16;nlc(d)
field of Rldl 
condition for Rnreachability'
12
we then have
J,
the following
COROLLARY
3.16
SuPPose
that the rank of
U
(d) , viewed as a matrix
over R(d) ' is egual to n Then the system (3.4) is Rnreachable.
Proof. The rank of U(d) is equal to n if and only if there is
no
;lonzero xeR(d)n such that x'U(d) = O. Then apply Theorem 3.15.
A generalized version of condition (3)
in Theorem
3.15 was given
bY
Sontag [24, page 2Bl  Results simjIar to those given in Theorem 3.15
were clerived by Williams and Zakian [16] '
For a geometric version of these
results, see Byrnes i301.
Unfortunately, the notjons of Rnreachability and Rncontrollability
(driving
x
(t) to zero at
some
time t, > o) are of limited use in the
design of control systems with time delays, since the value of
x
(t) at time
is not the complete state of the system. For example, the existence of
an openloop or closedloop control which drives x(t) to zero at some time
"lt
0 does not imply that x(t) will remain zero for all tt
al. This of
course is due to the storage of signals within the delay lines.
In the literature on systems with time delays, conditions based
on
ihe concepts of exact or approximate function space reachability are usually
considered [31]. These conditions are much stronger than Rnreachability
since they deal with the problem of reaching (from zero) or controlling
(to zero) Rnvalued function
segirnents,
rather than points in
Rn.
It is interesting to note that the rank condition in Corollary
is stronger than Rnreachability:
EXAMPLE
F (d)
3.17: Consider the system(3.4) with
FE
IJ
and
G
(d)
=
I
so that
tt,
bl
lr
33
U
(d)
[r
_tl
lt
te
rT
ql
3.16
)
2
!L^
^.^!^,
There is no nonzero x€R such that x'u(d) = o, so the system is Rreachable'
But the rank of U(d) is equal to one. Thus Rnreachabitity does not neces
sarily imply that the rank of U(d) is equal to n'
A very interesting open question is whether or not the rank condition
in corollary 3.16 is equjvalent to one of the various notions of function
Spacereachabilityspecifiedintermsofsometopologicalstructure.
There is a much stronger condition than the rank condition given in
Corollary 3.16. Namelyf we can require that any xeR[d]t.u' be written
as an nldlIinear combination of the columns of U(d). In the singleinput
case, we can do this if and only if the determinant of u(d) is equal to
in
nonzero element of R (which is seldom the case) ' As will be seen
the next chapter, this condition is necessary and sufficient
asslgnabllity,,using
a
for "pole
state feedback of the form u = B(d)x, where the feedback
nratrix B(d) is a lxn matrix over e[d] '
The last toPic of this section is RnobservabilitY.
DEFINITION
3.18
if for any nonzero initial
The sYstem (3'4)
is Rnobservable in time tl t
0
state x(O)eRn withx(t)=0foral1t<0,
of
the output response y(t) resulting from x(0) is nonzero for some range
values of t belonging to [0,t]1.
The next result states that RnobservabilitY
is dual to
Rn
reachabilitY.
PROPOSITION 3.
19
ThE
system (3.4) is Rnobservable in time t1 if
only if the dual system' specified by the matrices F(d)', H(d)',
n_
isR 'reachable in time trProof. Follows from the theory of adjoints [29].
and
34
G(d)
3.2O Given the system (3.4), suppose that F(d)
COROLLARY
o
=
s
I t ]. da and H(d) =  H.ar. Then the following are equivalent.
l
:
I_U
^
r=(J
n
is Robservable in time t I for sorne t, > 0.
n
The system is Robservable in time t, for any t, > g(nl)a + sa.
(1) The system
(21
ll
(3) There
is no nonzero xeRn such that
V
Duallzing Corollary 3.16, we have t'hat the system (3.4) is
observable
if
the rank
of
Rn
lH(d)',F(d)'H(d) ',...,(F(d)')nlu(d)'1,
viewed as a matrix over the quotient field R(d), is equal to n.
The relation
ship (if there is one) between this rank condition and the various notions
of function space observability is not known at present.
Suppose
response
that (3.4) is Rnobservable in time tr.
y(t) on lO,trJ resultjng from initial
Theorem 3.14 we can derjve an expression
The straightforward
state
for x(0) in
Given
x(O)eRn
terms
the output
by dualizing
f y(t) on [0,t'].
details are omitted.
3.3 Abstract systems.
The results given in Sections 3.I and 3.2 suggest the following notions
of reachability
I
I
and observability
for abstract systems. Here we afso define
canonical systems and minimal systems.
DEFINITIOI{ 3.2}
Let (F,G,H) be an ndimensional abstract system
over the commutative ring A. Then (F,G,H) is reachable if any xeAn can
be written as an Alinear combination of the columns of GrFGr...,FtlG.
The system is observable if there is no nonzero xcAn such that x'[H'rF'H',
h
1
...(r")"'H'l
The system
= O. The system is canonical if it is reachable and observable.
is minimal if its input/output
Itr
JJ
sequence
f = (HG,HFG,...'H(r'il)G,..)
r
cannot be realized by a system over A with dimension strictly
When
less than n.
A is a field, it i_s known [6] that a system is canonical if
only if it is minimal.
when
A is not a field, it is still
true that
and
a
canonical system is minjmal, but the converse is not necessarily true:
EXAMPLE
322 Consider the onedimensional system (1,d,1) over R[d].
is obviously rninimal. But since Ridl I{ar(a):n(d)eRldl}, it is not
reachable, so it j_s not canonical.
The system
i
We
define the dual of (l.,G,H) to be the system(Fr,H',cr). If (r',H',G')
is reachable, it can be
shown
that (F,c,H)
j_s
observable. But it is not
necessarily true that observability of (F,G,H) implies reachability of
(F, ,Ht ,Gt )
:
EXAMPLE
3.23 Consjder the system (F,G,H) over Z with F = I and H = 2.
There is no nonzero xeZ such that Hx = 0, so the system i_s observable.
But not every x€Z carr be written in the form x = (H')a:2a
for some aeZ,
so
the dual is not reachable.
Thus reachability
of the dual is a stronger condition than observability
of the given system. rn the next chapter, we shall see that the stronger
condition is useful in the construction of state observers.
A reachable system whose dual is also reachable is said to be a split
system [24].
For split
systems, it is possible to approach the design of
regulators by feeding back an estimate of the state obtained. from a state
observer. An interesting question is whether or not a given lnput/output
sequence can be realized by a split
system. For results on this, see Sontag [24]
and Byrnes [30].
36
4.
CONTROLLERS AND OBSERVERS
4.L Introduction.
In the first
part of this chapter, we consider the construction of
feed.back controllers
is illustrated
for abstract systems over rings.
The general theory
by examples involving the three classes of systems defined
in Sections I.2  L.4.
In the last section of the chapter, we consider the
construction of observers by dualizing the results on feedback controllers.
4.2 Assignability.
Let O be a ring extension of the ring A. Given a fixed element
0belonging toQ, let A[0] denote the subring of fl consisting of all finite
q
of the form .'^L lwhere a.eA and 00 = 1. Given a symbol z, LeLAlzl
l1=u ".Ot,
denote the ring of polynomials in z with coefficients in A. Finally, 1et p
sums
denote the
map
p:AIz]+A[0]
:
rt
r
1
+ F) a.z
) a.0
ll''^
].=u
a=U
,'^
The element 0 is said to be transcendental over A if the map p is
onetoone. That is, there does not exist a nonzero polynomial tr(z)eAlzl
such that p(n(z)) = t(0) = 0.
If 0 is transcendental over A. the rings Alzl
and A[0] are isomorphic (i.e..
p is onto and onetooner and p(TIT2+ n3)
p
(nr) I (rir) + o (nr) for any n
L,n 2,
Tr3€A
=
Iz] ) .
tf 0 is not transcendental over A, it is said to be algebraic over
A.
If 0 is algebraic over A, an element of A[0] does not have a unique expression
as a polynomial in 0 with coefficients in A.
Nevertheless, we can sti1l
say that bea is a zero of n(0)eA[0] if there exists a B(0)eA[0] such that n(0)
= (0 
b)B(0).
Let (FrGrH) be an abstract system over A. As before, we assume that
the system
F iS nxn, G is nxm, and H is pxn. Given a mxn matrix B over A,
(FcB,c,H)wilfbereferredtoasaclosedIoopsystemformedfrom(F'G'H)'
The matrix B is called the feedback matrix (or controller) '
Now
given
+
where I
O€0)A, let det(or  F + GB) denote the determinant of 0I  F GB'
isan
is the nxn identity matrix. It can be shown that det (0I  F+GB)
"it t'oi, a'EA' rn terms of these construcelement of A[0] of the form 0t *
i=oaa
tlons, we have the following concepts'
DEFINITTON
4.1 The triple
(l',G,0) is coefficient
assignable if
b0,b1,... ,bnl belonging to A' there is a B over A such that
n nr
I r.r_ gt. The triPre (F,c,0) is zero assignable
det (0I F+GB)=
r=u
F + s'
if for an! crr c2,... ,cra belonging to A, there is a B over A such that det(Ol 
for
any
 c).
 c^)...(0
= (0  c)(0
t'
n
2.
Asindicatedbelow,forthethreeclassesofsystemsdefinedin
sections L.2  L.4, zero (or coefficient) assignability implies that
by
employingstatefeed.back,wecanspecifythe''aslrmptotic''behaviorofthe
state response resulting from arbitrary initial states with zero input'
(a)ConsideradiscretetimesystemoveraringofscalarsAgiven
by the dYnamical equations
x(t + t)
y (t)
We can
Fx(t) + eu(t)
Hx
(4.
feed back the state x(t) bY setting
u(r) =Bx(t) +r(t)
(4.2)
is the feedback matrix defined over a and r (t) is an external inPut
or disturbance. Combining (4.1) and (4.2), we have that the closedloop
where B
38
F
I
t
F.1
8.
li
lr
i
1
r)
(t)
is given
system
by
x(t+1) = (FGB)x(r) +cr(r)
y(t) = Hx(t)
(
4. 3a)
(4. 3b)
Let o1 denote the leftshift
operator defjned by (olt) (t) = f (t + 1),
where f is a function on Z with'values in A. Then viewjng A as a subring
1_J, we can write (4.3a) in
ot Ato
the form
(o1rF+cB)x=cr
(4.4)
Fron a wellknown result in matrix theory [g, page 334), we have that
., 1_
r
1
ldet(oI
 F + cB)llo'l't  F + GBI'=
Adj(otl
 F + cB)
(4. s)
where Adj (o1t
 F + cB) is the transpose of the matrix of cofactors of
sl tI  F + GB. It follows from (4.4) and (4.5) that if the triple (F,G,oI)
is zero or coefficient assignable. by selecting the feedback matrix B,
we can specify the behavior
of the free response x(t) (i.e., r(t) = 0 for
t > 0) as t'@ rn particular, by choosing B so that det(olt  F + GB) ot. r. have that the free response x(t) is zero for t > n, starting from
any initial
state x(0)ean. This is often referred to as,,deadbeat,,control.
(b) consider the discretetime system over the operator ring K[o]
given by
x(t + 1) =
y(t) =
(r'(o)x)
(r) + (c(o)u) (r)
(H(o)x) (t)
39
(4.6)
Setting u(t) = (B(o)x)(t) + r(t), we have that the closedloop system is
given by
x(t + 1) = (r(o)  c(o)B(o)x) (t) + (G(o)r) (t)
(4.7b1
v(t) = (H(o)x) (t)
whereB(o)isamatrixoverKto].Inthiscase,thefeedbacksignal
(B(o)x) (t) consists of delayed versions of x(t) '
Let o1 denote the inverse of o, so that ol i" the leftshift
operator.
Now we can
view K[o] as a subring of the ring f[o, o1] consisting
ii l,
ii
of all finite sums I^ .f'ar.o'oJ wi_th the a..<K. It is important to
rhar o1 i_s nor ,r"il:.1;:nra1 over Ktol . To see rhis, consider rhe
polynomiat rG) = oz Le(iciol)tzl . Wehave that n(o
l
*)
1
 1=
= o(o*)
note
0,
so the map p defined above is not onetoone. It follows that the ring
1
is not isomorphic to (Ktol) tzl.
K[o,o']
viewing (4.7a) as an operator equation over K[o'ot] ' t" have that
(orr  F(o) + e(o)B(o))x = G(o)r
(
4.8)
As in the ease of systems over A' it follows from (4.8) that if the triple
_1
(F(o), c(o), of) is zero or coefficient assignable' we can specify the
behavior of the free response x(t) as t + @. In fact, if B(O) is chosen
that the determinant of o1r  r(o) + G(o)B(o) is equal to on' the free
response
x(t) will be zero for t = ar, where t, is
40
some
positive integer'
so
(c) Consider the closed1oop continuoustime system over R[d]
given by
(t)
dr
dx
(F
(d) 
G
(d) B (d)
x) (t) + (c (d) r) (t)
(4.9a)
y(t) = (tt(d)x) (t)
(4. eb)
As in the previous example, the feedback signal (B(d)x)(t) consists of
delayed versions of x(t).
Letting D denote the derivative operator, we can view R[d] as
a
subring of R[d,D] which consists of delay differential operators of the
ii
form ))a..dD'
acting on some (unspecified) space of functions (see[14]
:; l_"1
r_l
for details). As
shown
in [12], D is transcendental over R[d], so R[d,D] is
isomorphic to the ring (R[d] ) lzJ of polynomials in z with coefficients in
Rtdl
.
Viewing (4.9a) as an operator equation over R[d,D], we have that
(DI  F(d) + c(d)B(d))x = G(d)r
In this case, if lhe triple
(F(d),c(d),D) is zero or coefficient
(4.10)
assignable,
by choosing B(d) we can get the free response x(t) to converge to zero at
an exponential rate utt fot any a > O (see [14] ) .
4.3 Singleinput case.
Let (F'G,H) be an abstract system over A, where now G is an nelement
column vector over A (i.e.,
m
= 1, which is the singleinput case). Given 0€fl,
4r
where Q
is
some
ring extension of A, in this section we shal1 present
necessary and sufficient conditions for the triple
(F,Gr0) to be zero or
coefficient assignable. Our first approach to this problem is based on the
concept of cyclicity which we now define.
DEFINfTION
to
4.2 A nxn matrix F over a commutative ring A is said
cyclic with generator gcAn if every element of An can be expressed
be
asa finite
Alinear co.mbination of gfFgr... rFigr...
It follows from the CayleyHamilton theorem that a nxn F is cyclic
wjth generator g if and, only if the elements g,Fg,...,Ft1g
generate An;
i.e., every element of An can be written as an Alinear combination of
nl9. Hence F is
_
t",F7,...,E
cyclic with generator 9 if and only if the
delerminant of the matrix lg,Fg,...,F"
h
gl has an inverse in A.
1
We
also
have the following result.
PROPOSITION
4.3 Let (F,G,H) be a singleinput system, so that 6:
Then (F.g,H) is reachable (nefinition
geA
3,21) if and only if F is cyclic with
generator g.
As we now show,
cycljcity is equivalent Lo the existence of
particular canonical form. As before, let z
be
a
a symbol. Given a nxn matrix
n1
t over Af we have that det (zI  F) = ,n+  u.,  for
some
a=u
F=
01
00
b
00
::
00
10
0
aU1
,s
a_
a2
(4. 1
;
o
I
43
42
a.€A.
Define
1
PROPOSITION
4.4 The matrj_x F is cyclic with generator g if and only
if there exists a nxn invertible matrix p over A such that F = plr'P
P1 g, where F and g are given by (4.11).
9r P can
be taken to be the matrix [q,Fg,...,F
and.
If F is cyclic with generator
n]
n1" sl
'n, I
., (r)"
ts,F9,..
This result is an easy generalization of the field case, so the proof
is omitted.
cyclicity
Using Proposition 4.4, we can prove the following result relating
and assignability.
THEoREM
4.5 Let (F,9,H) be a singleinput system and let 0 be a fixed
element of Q:A, with
0 transcendental over A, Then the following are
equivalent.
(1) F is cyclic with generator g.
(2) The tripte
(F,g,0) is coefficient
(3) The triple
(F,g,0) is zero assi_gnable.
Proof.
Clearly, (2)l(3).
assignable.
It follows from Sontag 124, proposition
4.31
that (3) implies that (F,g'H) is reachable. Hence F is cyclic with generator
9.
So the proof is completed if it is shown that (1))(2) :
beJonging to A, fet e denote the row vector [boo
n1
v;hered.et(zlF)
=zn+
I
Given bO,bI,...,bn_1
b1u1...brr_l  arr_al,
Thendet(OlF+gil
=
nI
t=U ^,rt.
a
u^n + .^fFI b.',0
. where F,g are given by (4.11). rf F is cyclic with generator g,
a=u
it foltows from Proposition 4.4 LhaL det(ol  r * S"l = det(ol  F + gB)
i,vhere B
= B(P,1).
Thus the triple
By Theorem 4.5t if
zero or coefficient
(l',g,0) is coefficient
assignable.
0 is transcendental over A, the lriple
(F,g,0) is
assignable if and only if the determinant of [g,Fg,...,Ftlg]
has an inverse in A. Unfortunately, this condition can be very severe. For
example, in the case of a singleinput continuoustime system over R[d], the
triple
(F(d),g(d),D) is zero or coefficient assignable if and only if the
l_.r_
I
I
determinant of [q(d),F(d)S(d),...,F(d)t1g(a)
] is a nonzero etement
of R (whlch is seldom the case). This limitation
can be overcome by
considering feedback matrices defined over a ring extension c of R[d].
rf c contains a "1arg:e" subset of elements that are invertible
but not in n[d] , assignability
with respect to C (i.€.,
in c,
B is over
C)
wrll be a much weaker condition than assignability with respect to Rtdl.
An interesting example of a ring extension of Rtdl is the ring
consisting of aii proper rational functjons in d1 which satisfy a stability
criterion (see Sontag 124) for details).
It may seem reasonable to take
C to be the quotient field R(d), since every nonzero element of R(d) is
invertible.
However, in general it is not possible to implement feedback
matrices defined over R(d) since they may contain noncausaL or unstable
elernents. For instance, it is not possible to implement the ideal predictor
given by dl *.
When
0 is algebraic over A, cyclicity of F is no longer necessary
for assignability (see Exarnple 4.8). In this case, a necessary and
sufficient condition for coefficient assignability can be derived using
the identity
det(Ol  F + 9B) = det(OI  F) + BlAdj(er  F)ls
where Adj
(0I  F) is the transpose of the matrix of cofactors of eI 
(see [14]
)
(4.12\
F
.
pRoposrrroN
4.6 The triple (r,9,0) is coefficient assignable if
only if there is a nxn matrix
W
over A
such
and
that
lr I
le
wlAdj (0r
 F)ls
44
=
l:l
tl
I
[e"']
(4.13)
Proof.
Suppose that there is a W satisfying
belonging to A, let B= [bO  aO
b]
n1
det(0rF)
nl
F
^n
0
 1 . .
(4.13).
Given b.,bl,...,bn_l
brr_I  .rr_11W, where
(4.12) thatdet(OrF+9B)
rtfollowsfrom
=
I ,0t.
i=O r'
Conversely, suppose that (f,9,0) is coefficient assignable.
=0n+
^t
+ ul) f.O.
a=u
Then for i = 1,2,...rn,
 det(or  F) = oiI.
8..
.l_
Then W
there is a row vector B. such thaL det(0I  F + gB.)
Let w denote the nxn matrix with ith row equal to
satisfies (4.13).
COROLLARY
4.7 Suppose that F is cyclic with generator g.
Then
(4.13) is satisfied wtih w = Pl . where P is the matrix defined in Proposition
44
Proof. rt is easily verified that Adj(or  F);= [I e... etl]', where
F,{.t. givenby (4.I1). UsingF= p1r'p, g=
wehave thatW= pI
"1g,
satisfies (4.13) .
EXAMPLE
F(o)
4.8 Consider the discretetime system over R[o] with
=
['
lo
1,
9(o)
=
[]
U
This is the system given by the block d.iagram in Example 1.2.
example, the determinant of [9(o),F(s)S(o)]
not have an inverse in R[o].
For this
is equal to or which does
rhus F(o) is not cyclic with generator g(o).
But since o1' is algebraic over R[o], cyclicity is not necessary for assign
ability. By Propositron 4.6, (F(o),g(o),o1) is coefficient assignable
if and only if there is a W over R[o] such that
l
wtAdj (o1r
 r'(s))ls(o)

=*
r
l"
Lo
JI = [,1
I rl
l
I!'
I
(4.L4)
Multiplying both sides of (4.I4) by o, we have
that (r1o;,g(o'), o1)
is coefficient assignable if and only if there
is a W over Rlol such that
n
wi);ll=llFl
I lrl
lq
t
Sjnce 1o and o are
relatively prime
satisfying (4.15). Further,
algorithm. This yields
a
,ier.ce
(!. (o) , g(o)
, o1)
IS
so that det(o.1'r _ r(o)
))
=ol+o.
+
elements of
solulion
vJ=
using the Euclidean
rT
I
1l
assignable. Let's compute B(o)
g(o)B(o)1 = o2. we have thar der(o1r
 F(o))
Thus
B(o)
=
lb.ao
brarlW
B(o)
=
lo+ro2
o (o) l
["1
lg*r il
B(o) = [o3 *
1ol
o
2
In this case, the feed.back signal _(B(o)x) (t)
is equal to xl(t3)  xr(tl)
+ xr(t2)  x, (t) .
As noted in Example 1.2, this system also
has a fourdimensional
representation over R gj_ven by (1.8). Letting
F,g denote the coefficients
46
4. 1s)
R[o], there is a W
W can be computed
l o
i
jo
+r
coefficient
(
of (t.B),
we have
rhar rhe rank of f;,;;,trlrs,tul3si
is
equal
to four,
so (F,g,o ^; is coefficient assignable. It is interesting to note
that
in this framework, the computation of feedback matrices using the canonical
forrn (4.11) requires that we work wLLh 4x4 matrices over R; in particular,
it is necessary ro inverr i;,;;, <ilrn,tul 3sf . rn general rhis procedure
appears to be less efficient from a computationar standpoint, than
the one
given above which utilizes
(4.13).
the Euclidean algorithm to compute a w satisfying
This point is currently under investigation.
4.4 Multiinput
case.
Given an abstract system (F,G,H) over A, in this section v/e
that
is
assume
with m > 1 (the multiinput case). As before, 1et 0 be a
fixed element of fl>A. We then have the following two results on zero assign_
G
nxm
ability.
THEOREM
4.9 If 0 is transcendental over A,
zero assignable
only if
the triple (F,c,0)
(F,G,II) is reachable.
4.10 If the ring A is a p.i.d., reachability of (F,c,H)
inrplies that (F, G, O ) is zero assignable .
THEOREM
Theorem
4.9 (resp.
Theorem
4.LO) follows from the work of Sontag [24]
(liorse i32l ) . rt should be noted that there is a constructi_ve proof
of
Theorem 4ro based on the diagonalization of matrices defined over a
p'i'd'
(see [32]).
rnstead of pursuing this, we shal1 consider the problem
of coefficient assignability using the concept of cycrieity.
pRopoSITIoN 4.11 Given (F,c,H) and Oefl,
suppose that there is a
feedback matrix L over A such that FcL is cyclic with generator g gu
=
for some ucAm. Then (F,G,O) is coefficient assignable. Further, there
exists an nxn invertible matrix p over A such that, for any b^rb.,...,b
NASA Lecture Notes.pdf (PDF, 22.86 MB)
Use the permanent link to the download page to share your document on Facebook, Twitter, LinkedIn, or directly with a contact by eMail, Messenger, Whatsapp, Line..
Use the short link to share your document on Twitter or by text message (SMS)
Copy the following HTML code to share your document on a Website or Blog