NASA Lecture Notes (PDF)

NASA Contractor Report 3016

Lectures on Algeb r"ic System Theory:
Linex Systems Over Rings

Edward W'. Kamen

CONTRACT A-43TI9.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) discrete-time systems over a ri-ng of scalars

the integers; (ii) continuous-time systems containing time delays;
large-scale discrete-time systems; (iv) time-varying 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 Dooli-n 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 DAAG29-77-G-

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 fj-nite-dimensional continuous-time and discrete-time
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 p-output n-dimensional time-invariant discrete-time 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 continuous-ti-me case, with r = n

field of real numbers, a time-invariant 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.

fi-eld
Tnitial efforts in studying linear systems defined over a

Kusuallyassl$edthatKwasaparticularinfinitefield,suchasthe
fieldRofrealnumbers.Infinitefieldsarefieldsthatcontaina
subsetwhichcanbeputintoaone-to-onecorrespondencewiththesetof
nurnbers
integers. In addi-tion to the field R' the field of rational
andthefieldofcomplexnrunbersareexamplesofinfinitefields.
theory of timeThere are several textbooks (e.9., lL,2,3l) on the
invariantandtime-varyinglinearsystemsdefinedoverthefieldR.
Inasequenceofpublicatlonsbeginningin1965'R'E'Kalman
|4,5,6Td.eveloped.analgebraictheoryfordiscrete-timesystemsofthe
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 Discrete-time systems over a ring of sealars'
Afterthecompletionofhisworkondiscrete-timesystems
over arbitrary fields, Kalman initiated the study of discrete-time

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
pli-cation; 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 coeffi-cients in a field K, with the usual operations of polynomial
additi-on and multiplication.

The only elements

in K[z] that are invertible

are the nonzero polynomials of degree zero.
The

first detailed results dealing with discrete-time

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 time-invariant discrete-time

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 I2-digit precision), Further, systems over z appear

in various applications, such as coding theory [10] and scheduling or
sequencing problems

tfll

.

-3-

1.3 Continuous-time systems over rings of operators'
In1973,Kamen[12]showedthatalargeclassoflinearinfinitedimensional conti-nuous-time systems can be represented by first-order
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 time-invariant and timevarying continuous-time 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 time-invariant 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(t-ia)

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
matri-ces 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 n-vector

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 R-valued functions
defined on R with support bounded on the left {i.e.,

for each veV, there

Let d:v+V denote the a-second
is a t-V-eR such that v(t) = o for all t<t-_).
V
delay operator on V defined by (dv) (t) = v(t-a), v€V. We can extend

d to

column vectors

v = (vl, - -. rtr)' over V by defining
(dv)(t) - (vl (t-a),..-,vn(t-a))'

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 time-delay systems given by (1'A) can be studied
(1.5) defined over the ring
i-n terms of the vector differential equation
Thus the class

Rtd].Weshallrefertothesystem(1.5)asalineartime-invariant
continuous-time system over the rinq of operators Rtdl '
given by the dynamical
EXAMPLE 1.1 Consider the time-delay system
equations

dx- (t)

-+=
dx" (t)

dtr

--xl(t-a) +xr(t) -xr(t-2a) + u(t)
= x- (t) + xl(t-a) - xr(t) + u(t-a)

y(t) = xr(t-a) - xr(t-2a) + 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 operator-ring representation

(1.5), we can develop an algebraic theory for the class of time-delay
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 rj-ngs 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 Discrete-time systems over a ring of operators.
In this section we shall

show

that there are discrete-time

systems

that can be treated as systems over a ring of operators. Consider the
class of discrete-time systems given by the following dynamical equations

qr
x(t + 1) = I r.x(t-i) + I c.u(t-i)
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

proceedaswedidaboveforcontinuous-timesystemswithtimedelays'
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 fj-eld
shift operator o:x(t)+x(t-1) 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)asalineartime-invariantdiscretetime system over the ring of operators K[o] '
(high-dimensional)
Via the representation (1.7), we can study large
discrete-time 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 discrete-time

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 discrete-time

system given by the following block diagram.

Here

xl(t) (resp. x, (t) ) is the state of the

function L/ (z+lj (resp. L/z-l)).

We

subsystem having transfer

have that

xr(r+1) =-*1(r) -xr(t-1) +u(t)
xr(t+1) = xr(t) + xr(t-1)

Y(t) = xr(t)
These

equatl cr:s can be w ritten

r'(o)

=

[: I

i-n

the form (1.7) with

H(o)

[]

-9-

=F

!

. Defining xt (t) =
have a representation of order two over R[o]
a f our-dimensional representation
x, (t-1) and x,4z(t) = x. (t-1) , 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 computatj-ona1 standpoint to
than the four-dimensional
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 two-dimensional
in one variable
defined over a ring of proper rational functions
systems

122)

'

Lineartime-varyingsystemscanalsobeviewedassystemsoverringis,

inthiscasearingoftimefunctions.However,thealgebraictheory
oftime-varyingsystemsdiffersfromthetheoryoftime-invariantsystems.
from the fact that time-varying
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 time-varying discrete-Lime 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'
ForthethreeclassesofsystemsdefinedinSecti-ons1.2-L.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

Thusi|ispossibletodevelopageneraltheoryofsystemsoverrings
This was the
specified in terms of a triple of matrj-ces 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 thi-s section,

we

fixedpositi-veintegers.Anabstract(free)lineartime-invariantsystem
overAi-satriple(F,G,H)ofnxn,fixlllrPxllmatricesoverA.Theinteger
n is called the dimension of the system (F'G'11) '
Althoughtheconceptofanabstractsystemdoesnotincludeany
explicitreferencetodynamicalbehavior'ana-bstractsystem(F'G'H)
canbeinterpretedasadynamicalsystembyassociatingasetofState
equationsspecifiedintermsofF'G'H'Forinstance'(F'GfH)canbe
interpretedasadiscrete-timesystemovertheringofscalarsA,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 i-ntegral 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) '

-;i-3i3 =x. s--s 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

quotient-field

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
i-I
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 discrete-time 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 i-nput u(t),

A

we have

state x(to) at time

t = ao is given by

t-t ox(to) +-'l
- i'rc-i-I"rr(i),
x(t) = I'

t > to

(2.1)

:

I-L-!

o

If x(t ) = O, the output resPonse is
L-t

y(t) = I
i-

HF

L-r-rcu(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 continuous-time 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(e-as) (sr - r("-u");-161.-t=;u1=1

where

r(e-as),

settingd=.-"",
of u (t)

(v

(t) ) .

G{e-as)

*") 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 Tlsre-as) is given

T(s,"-as) = n(e-as) (sr - F(.-""))-rc(.-t")
we have that
Expanding (sr - F(.-""))-1 i.rto a power series ir,
"-1,

T(s,e-as) = I Hle-as1Ui-1(.--=)G(e-as)s-i
i=1

Hence

T(s,e-as) can be determined from the sequence (Jl(d),J2(d),...),

vhere J. (d) = H(d)ri-l(a)G(d).

-15-

by

operator ring
(c) Consider a discrete-time system over the
(f'7) ' we shall specify the input'/
K[o] with the dynarnical equations
the formal z-transform defined as follows'
output behavior using

LeEzbeasymbol'Givenafunctionf:Z->KwiLhf(t)equaltozero
fort<0,wedefinethe(formal)z-Lransfoxmofftobetheformalpower
-r?-i
series F(z--; = L f(i)z
the z-transform
,::h. that x(t) = O for ts O and take
of (1.7) '

we get
r

y(z-r) = T(z-1-)u(z-1-)
-I.
is lhe transier function matrix'
= H(z ) \zr- - r,(r-t))-lc("-l)
-t
-1-)) -1 into a formal Power series Ln z -, we have that
(z
F
Expanding QI
*)

-1
where T(z

e-L)r-i
,,(r-r) = i
"1"-1;ui-r(r-1)c
i=l

(2. 3)

where J' (o) = H(o)ri-l(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/outputbehaviorofadiscrete-time
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 discrete-time
a ring of delay operators'
and continuous-time 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 = Hlpi-115
for i = I,2,...

A reali-zation (F,G,H) is mi-nimal if its di-mension is

minimal among all possible realizations.
Let us first

consider the realization

of a scalar sequence f

=

(a.,a.,..-),
a-e A" To the sequence f, we associate the formal power
LZa
s
'
-r =
series w(z-r)
I rrr-t in the symbol r-1 rith coefficients in the ring
i=I
A. The power series w(z-l-) is said to be rational if it can be written
as a ratio of the form

cn-1_z n-1 +c n-z^z n-2 f ... + c1z +
w(z ') n
n-l
z+e-z+...+e-z+e^
-l

cO

(2.4)

N-IIU

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 generalJ-zations of the field
case.
PROPOSITfON

2.4

A scalar sequence is realizable if and only if

its associated power series r(r-1)
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(r-1)

contain

factors of degree > 1, then (r,g,h) is a mi_nimal realization

C

1

00

l

t0

r-

,a

0

0

L

e-e

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(r-I)

' 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(z-l) 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(z-I) ' but

teaLizaspecial class of rings, minimal
minimal. As will be seen' for a
Hankel
(J1'J2" ") can be constructed from the
tions of a matri-x 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 fi-eld,
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

domai-n

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 i-s 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 i-f a matrj-x sequence oveg z has a realizatj-on

over the fietd of rati-onal 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-

ti-ng, 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, mj-ni-mal realizatj-ons

can be computed from B(f) using Rouchaleau's algorithm t9l.

-19-

The al-gori-thm

yieldsami-nimalrealizationoverQ(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 p-i.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

greatestcommondivisoroftheelementsinthefi-rstrowofD.Thereis
anA-linearcombinationvrofthecolumnsofDhavingbrasfirstelement;
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

= tv-l)l,t(c-t)v, c = (v-1)n,

-20-

H =B(c-1)v

(2.5)

2.3

Example

Consider the continuous-time system with time delays given by the

transfer function matrix

T(s,e-s1

We

=

)

s

want to

+

(e-c -I) s-e -c

compute

t . "-'"1

e-s s+

[-'

-1

["

a mj-nimal realization of T(",.-=) given by a triple

(F(d), c(d), H(d)) over the operator ring n[d] with
T(s,e-s) = H(e s) (sr -

F

(e-s)

)-lc(.-=)

Si-nce Lhe least common denominator (as a polynomial

in s) of T(sre-s)

has degree equa

to two, it follows that T(=,.-") has a realization over Rldl

of

we

dimensi-on 4.

shall

compute a minimal

realization usi-ng the

algorithm. Fir t, expanding T(sre-s) into a power series i., =-I,
. -s.
T(s,e
)

I

I'

=t

above

we get

-l

1 -3
l- Il"-1* l-I -"-= r+e-JJ
"-r.
|
-s l=
- -1 I "-'*lf-e-2s .'*r-[
o J*
L"-=

.-=

-2I-

Then

t

T

lr

l_,
l---I-

-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'
e-s_

-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
e-e

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(t-1) + xr(t) + xr(t-1) + x2(L-2') + u1(t) + u, (t-1)

= xr(t) + ur(t)

y1(t) = x, (t)
vr(t) = -xr(t) +xr(t-1)

-23-

3. REACHABILITY, OBSERVABILITY,

AND DUALITY

Weshallnowstudytheconceptsofreachabilityandobservability
fordiscrete-ti-meSystemsoveraringofscalarsandcon|inuous-time
Systemsovertheoperatorringn[d].Theresultsobtainedhereleadto
systems over
a definition of reachability and observability for abstract
rings.Inthelastpartof,section3.3,weconsideraconceptofduality
for abstract

systems.

3.1 Discrete-time systems over a ring of scalars'
equations
Consider the discrete-time 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

n-element 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(N-1) thaL drive

the system from the zero state at time t =

O

to the state x at time t
n

Thesystemisreachableinnstepsi-fforanyx€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 i-nvariant-

Let v1'v2 ,..',Yqbe fixed elements belonEing to An . We say
be written
that xeAn is an A-linear combination of vr'vr" " 'vn if x can

in the
i

form
q

x= I? ..n.a
-r
I-I

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 j-n n steps.
(3) Every element of An can be written as an A-linear combi-nation

of the columns of G,FG,...,Ft-lG.
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"-i-ta,rtil

(3.2)

i=0

The equivalence

of condi-tions (2) and (3) follows frorn (3.2)-

The

equivalence of conditions (1) and (2) follows from the Cayley-Hamilton
theorem [8, page 400].
coRoLLARY

3.3 Let

m

= 1 (the single-input case). Then (3.1) is

reachable if and only if the nxn matrix [G,FG,...,Ft-lG] is invertible

over A, which is the case if and only if the determinant of [G'FG,...,Ft-lG]
has an inverse in e.
EXAMPLE

3.4

Suppose

that. (3"1) is a singte-input 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,...,Ft-lG] 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 integer-valued controls.

Again consider the system (3.1) defined over the ri-ng A" Let U de-

note the

nxmn

matrix [G,FG..,.rrt-lc]" and let

ueAmn

denote the control

vector u = [u(n-1) u(n-2) .." 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 single-input case there
__-I
-1
a unique solution given bY u = U X, wnere u l-s the inverse of U' In the
multi-input case (m > 1), the computation of a control u (if one exists) is IN
general a difficult

Problem-

For a cl-ass 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

matri-x U(U') is invertible

u

K, where K is a field with the property that l-rur'/
over K, in which case a solution ,"tf,t of x = Uu is

= (u') Iu(u')l-l '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
fiel-ds 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')l-1x 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 i-s not true:
EXAMPLE

3.6 Consider the discrete-time 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 j-f 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 computati-on of
integer-valued. 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 integer-valued 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 i-nitial

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,...,N-1}.
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')t-l(H';

1 = g.

-21

-

The

can

Proof.
initial

state

From (2.1), the output response y (t)

ILI

[." ,J

S

t < n-l 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 Cayley-Hamilton
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(n-l)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, thi-s 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) i-s 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 observabl-e as a system over the field Q(A). Then apply Theorem 3.10.

3.2 Contj-nuous-time systems over a ring of delay operators
Consider the continuous-time 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 ri-ng
RIdl

.

Given a fixed positive nunber tl , let i,2( to,trJ;Rn) d.enote the Hilbert
space of square-integrable 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 Rn-reachable in ti-me 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 ini-tia1 state function x(t) = 0 for t < 0'
We

shall give a necessary and suffici-ent condition for Rn-reachability

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 Rn-reachable 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)'x-m'(t, - s)X, 0 < ". tl
Here we are using

on any finite

the result that the elements of M(t) are square-integrable

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 grami-an for time-delay systems.
THEOREM

3.14 The system (3.4) is Rn-reachable in time t1 if and only

if B(tl) is invertible, in which case the control r = tr*(tf)B-1(tr)x sets
up the state xeRn at time t = tt. Further, thi-s 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 cri-terion for Rn-reachability specified directly in terms
of F(d), c(d). This can be accomprished by first noting that the system
(3.4) is Rn-reachable in time tl if and onry ir l* 1tr; is one-to-one,
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.
t-I > q(n-])a + ra.

n
There is no nonzero xeR' such that

xt
Proof.

[c(d),F(d)c(d),...,T(a)n-lc(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)n-le(a) I = c'
bY
Then by the cayley-Hamilton theorem, x'F(d)i-Ic(a) = o for all i > 1. Now
Suppose that

definitlon of M(t), it can be

M

expanded

(r) = |

tr tal
i=1

i-t.

into the series

(u)

)

ti-l, t '

o

Thus, x,M(t) = O for all t > 0, so the system is not Rn-reachable.
(3)+(2): Suppose that the system is not Rn-reachable for tl t Q(n-L)a + ra'
+ ra'
Then there exists a nonzero xeRn such that x'M(t) = O for O < t < q(n-1)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(n-l)a+ ra.
for t

=0

0r1,...,q and j = O r.,.. -,r, whi-ch 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.
r-l =

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;n-lc(d)

field of Rldl -

condition for Rn-reachability'

--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 Rn-reachable.
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)

i-n Theorem

3.15 was given

bY

Sontag [24, page 2Bl - Results simj-Iar 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 notj-ons of Rn-reachabi-lity and Rn-controllability

(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 open-loop or closed-loop 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 Rn-reachability

since they deal with the problem of reaching (from zero) or controlling

(to zero) Rn-valued function

segirnents,

rather than points in

Rn.

It is interesting to note that the rank condition in Corollary
is stronger than Rn-reachability:
EXAMPLE

F (d)

3.17: Consider the system(3.4) with

FE

IJ

and

G

(d)

=

I

so that
tt,
bl
l-r

-33-

U

(d)

[-r
_tl
-lt

te

r-T

ql

3.16

)

2
!L^
^.-^!^,
There is no nonzero x€R such that x'u(d) = o, so the system is R--reachable'
But the rank of U(d) is equal to one. Thus Rn-reachabitity 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 equj-valent to one of the various notions of function
Spacereachabilityspecifi-edintermsofsometopologicalstructure.
There i-s 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 nldl-Iinear combination of the columns of U(d). In the single-input
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 matri-x over e[d] '
The last toPic of this section is Rn-observabilitY.
DEFINITION

3.18

if for any nonzero initial

The sYstem (3'4)

is Rn-observable 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 Rn-observabilitY

is dual to

Rn-

reachabilitY.
PROPOSITION 3.

19

ThE

system (3.4) is Rn-observa-ble 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 R---observable in time t I for sorne t, > 0.
n
The system is R---observable in time t, for any t, > g(n-l)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)')n-lu(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 Rn-observable in time tr.

y(t) on lO,trJ resultj-ng from initial

Theorem 3.1-4 we can derj-ve an expression

The straight-forward

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 n-dimensional abstract system

over the commutative ring A. Then (F,G,H) is reachable if any xeAn can
be written as an A-linear combination of the columns of GrFGr...,Ft-lG.
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 i-t is reachable and observable.

is minimal if its input/output
Itr
-JJ-

sequence

f = (HG,HFG,...'H(r'i-l)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 minj-mal, but the converse is not necessarily true:
EXAMPLE

3-22 Consider the one-dimensional 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

necessaril-y true that observability of (F,G,H) implies reachability of
(F, ,Ht ,Gt )

:

EXAMPLE

3.23 Consj-der 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]

:

qq
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

one-to-one. 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 one-to-oner 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 algebrai-c 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,
(F-cB,c,H)wilfbereferredtoasaclosed-Ioopsystemformedfrom(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,... ,bn-l belonging to A' there is a B over A such that
n n-r
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 wi-th zero input'

(a)Consideradiscrete-timesystemoveraringofscalarsAgiven
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 closed-loop

where B

-38-

F

I

t
F-.1

8.

li
lr

i

1

r)

(t)

is given

system

by

x(t+1) = (F-GB)x(r) +cr(r)
y(t) = Hx(t)

(

4. 3a)

(4. 3b)

Let o-1 denote the left-shift

operator defj-ned by (o-lt) (t) = f (t + 1),
where f is a function on Z with'values in A. Then viewj-ng A as a subring
--1_J, we can write (4.3a) in
ot- Ato
the form

(o-1r-F+cB)x=cr

(4.4)

Fron a well-known result in matrix theory [g, page 334), we have that
., -1_
-r
-1
ldet(o--I
- F + cB)llo-'l't - F + GBI-'=
Adj(o-tl
- F + cB)

(4. s)

where Adj (o-1-t

- F + cB) is the transpose of the matrix of cofactors of
s-l tI - F + GB. It follows from (4.4) and (4.5) that if the triple (F,G,o-I)
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(o-lt - F + GB) o-t. 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,,dead-beat,,control.

(b) consider the di-screte-time system over the operator ring K[o]
gi-ven 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 closed-loop 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 o-1 denote the inverse of o, so that o-l i" the left-shift
operator.

Now we can

view K[o] as a subring of the ring f[o, o-1] consisting

ii l,
i-i
of all finite sums I^ .f'ar.o'o-J wi_th the a..<K. It is important to
rhar o-1 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 one-to-one. 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'o-t] ' t" have that

(o-rr - 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), o-f) 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 o-1r - r(o) + G(o)B(o) is equal to o-n' the free
response

x(t) will be zero for t = ar-, where t, is

-40-

some

positive integer'

so

(c) Consider the closed-1oop continuous-time 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..d-D'
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 u-tt fot any a > O (see [14] ) .

4.3 Single-input case.
Let (F'G,H) be an abstract system over A, where now G is an n-element
column vector over A (i.e.,

m

= 1, which is the single-input 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

A-linear co.mbination of gfFgr... rFigr...

It follows from the Cayley-Hamilton theorem that a nxn F is cyclic
wj-th generator g if and, only if the el-ements g,Fg,...,Ft-1g

generate An;

i.e., every element of An can be written as an A-linear combination of
n-l-9. Hence F is
_
t",F7,...,E
cyclic with generator 9 if and only if the
del-erminant 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 single-input 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,

cyclj-city is equivalent Lo the existence of

particular canonical form. As before, let z

be

a

a symbol. Gi-ven a nxn matrix

n-1

t- over Af we have that det (zI - F) = ,n+ | u., - for

some

a=u

F=

01

00

b

00
::
00

10

0

-a-U1

,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 = p-lr'P
P-1 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-]
n-1-" -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 single-input 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) :

beJ-onging to A, fet e denote the row vector [bo--o
n-1

v;hered.et(zl-F)

=zn+

I

Given bO,bI,...,bn_1

b1-u1...brr_l - arr_al,

Thendet(Ol-F+gil

=

n-I
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 Proposi-tion 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,...,Ft-lg]

has an inverse in A. Unfortunately, this condition can be very severe. For
example, in the case of a si-ngle-input continuous-time system over R[d], the

triple

(F(d),g(d),D) i-s zero or coeffici-ent assignable if and only if the

l_.r_
I
I

determinant of [q(d),F(d)S(d),...,F(d)t-1g(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 assignabili-ty with respect to Rtdl.
An interesti-ng example of a ring extension of Rtdl is the ring

consisting of aii- proper rational functj-ons in d-1 which satisfy a stability
cri-terion (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 i-nstance, it is not possible to implement the ideal predictor
given by d-l *.
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

l-r I

le
wlAdj (0r

- F)ls
-44-

=

l:l
t-l

I

[-e"-']

(4.13)

Proof.

Suppose that there is a W satisfying

belonging to A, let B-= [bO - aO

b]-

n-1

det(0r-F)
n-l
F
^n
0--

- -1 . .

(4.13).

Given b.,bl,...,bn_l

brr_I - .rr_11W, where

(4.12) thatdet(Or-F+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) = oi-I.

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 = P-l . where P is the matrix defined in Proposition
44

Proof. rt is easily verified that Adj(or - F);= [I e... et-l]', where
F,{.t. givenby (4.I1). UsingF= p-1r'p, g=
wehave thatW= p-I
"-1g,
satisfies (4.13) .
EXAMPLE

F(o)

4.8 Consider the discrete-time system over R[o] with

=

[-'
l-o

-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 i-n R[o].

For this

is equal to or which does

rhus F(o) i-s not cycli-c with generator g(o).

But since o-1' is algebraic over R[o], cyclicity is not necessary for assign-

a-bility. By Propositron 4.6, (F(o),g(o),o-1) is coefficient assignable
if and only if there is a W over R[o] such that
l-

wtAdj (o-1r

- 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'), o-1)
is coefficient assignable if and only if there
is a W over Rlol such that

n
wi)-;ll=llFl

I lrl

l-q-

t

Sj-nce 1-o and o- are

relatively prime

satisfying (4.15). Further,
algorithm. This yields

a

,ier.ce

(!. (o) , g(o)

, o-1)

IS

so that det(o.-1'r _ r(o)

-))
=o--l-+o-.

+

elements of

solulion

vJ=

using the Euclidean

r-T
I

1l

assignable. Let's compute B(o)

g(o)B(o)1 = o-2. we have thar der(o-1r
- F(o))

Thus

B(o)

=

lb.-ao

br-arlW

B(o)

=

lo+r-o2

o- (o) l

["1

lg*r il
B(o) = [-o3 *

1-ol

o

2

In this case, the feed.back signal _(B(o)x) (t)
is equal to xl(t-3) - xr(t-l)
+ xr(t-2) - x, (t) .
As noted in Example 1.2, this system also
has a four-dimensional
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

Thi-s poi-nt is currently under investigation.

4.4 Multi-input

case.

Given an abstract system (F,G,H) over A, in this section v/e

that

is

assume

with m > 1 (the multi-input 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 4-ro based on the di-agonalization 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 F-cL is cyclic with generator g gu
=
for some ucAm. Then (F,G,O) is coeffi-cient assignable. Further, there
exists an nxn invertible matrix p over A such that, for any b^rb.,...,b