Effective Algebraic Analysis in Linear Control Theory
Alban Quadrat
University of Leeds (United Kingdom) & Projet
Café,
Inria SophiaAntipolis (France)
Algorithms Seminar
December 4, 2000
[summary by Frédéric Chyzak]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
In the 1960's, Malgrange made use of Dmodule theory for studying
linear systems of PDEs [2]. Several aspects of this
approach, now called algebraic analysis, have then been made
effective in the 1990's, owing to the extension of the theory of
Gröbner bases to rings of differential operators. Correspondingly,
algorithms have also been implemented in several systems. Recently,
the introduction of algebraic analysis to control theory has allowed
to classify linear multidimensional control systems according to
algebraic properties of associated Dmodules, to redefine
their structural properties in a more intrinsic fashion, and to
develop effective tests for deciding these structural properties
[3, 6, 7, 8, 9, 10, 12, 14].
1 From Linear Multidimensional Control Systems to Algebraic
Analysis
A control system relates the state x of a physical process with an
external command u and some output y. Each of u, x, and y
is a vector of functions of the time t, and the system describes
their evolution with t. Several classes of such systems can be
represented by matrices with coefficients in a ring of operators.
Sample classes are the following:

Kalman systems are firstorder linear (ordinary)
differential systems
where A, B, C, and D are matrices with real
entries [5]. For example, RLC circuits can be described by
Kalman systems.
 Polynomial systems are higherorder differential systems
expressed without the help of any state variable, in the form
P(
d/
dt)
y(
t)+
Q(
d/
dt)
u(
t)=0.
(1)
Here P and Q are matrices with coefficients that are scalar linear
differential operators with real coefficients [5]. For
example, a harmonic oscillator commanded by a force is described by a
secondorder polynomial system. By Laplace transform, an equivalent
formulation of (1) is
the matrices P and Q are now matrices of polynomials in s with
real coefficients [5].
 Differentialdelay systems with constant delays
are a generalization common to Kalman systems and polynomial systems
by introducing the constantdelay operators d_{i} defined by
(d_{i}f)(t)=f(tt_{i}) for some real t_{i}. The generalized forms
are


(t)= 

A_{i}x(tt_{i})+B_{i}u(tt_{i}),
y(t)= 

C_{i}x(tt_{i})+D_{i}u(tt_{i}),

and
P(d/dt,d_{1},...,d_{r})y+Q(d/dt,d_{1},...,d_{r})u=0,
respectively. A typical occurrence of delay is when transmitting a
signal u through a channel.
 Multivariate linear differential systems with real
coefficients appear frequently to describe physical phenomena, like
electromagnetism, (linear) elasticity, hydrodynamism, and so on
[7, 8, 12].
In each case, the column vector x=(y,x,u)^{T} satisfies Rx=0 for
a (rectangular) matrix R with coefficients in some ring A.
Thus, we henceforth consider a linear control system as defined by a
matrix R with coefficients in an entire ring A. To give simple
examples, the matrix forms corresponding to Kalman and polynomial
systems respectively are
In these differential cases, the ring A is R[d/dt] or a
multivariate generalization, but more general rings of coefficients
are also considered in place of R in applications, like the
ring R(t) of rational function, or the ring C^{¥}(I) of
infinitely differentiable functions over some real interval I. In
the equivalent formulation by Laplace transform or in the mixed
differentialdelay situation with
constant coefficients, the ring is isomorphic to the
polynomial ring R[s] or a multivariate analogue. Here again, more
general rings of functions often appear in applications, like:
R[s,exp(s)], for situations related to the wave
equation; or the ring H_{¥}(C_{+}) of complexanalytic
functions bounded in the right half complex plane C_{+} (Hardy
space) and its subring RH_{¥}(C_{+}) of real
rational functions with no pole on the right half complex plane, for
the study of the stability of some distributed
systems [11].
Several structural properties of systems are allimportant in control
theory. An observable of a control system is any scalar
function of its command u, state x, and output y and of their
derivatives up to a certain order. An observable is called
autonomous if it satisfies a nontrivial PDE. A control
system is called controllable if no observable is autonomous.
The study of structural properties of a system turns out to lead to
linear algebra: controllability and observability are related to
various notions of primeness of the linear maps
z® Rz and z® zR;
in the polynomial systems case, stability is related to poles and
zeroes of the system, that are invariant factors of the matrix R;
similarly with the existence of generalized Bézout identities and
flatness of a control system; etc.
By associating an Amodule M to the matrix R, another
interpretation of the structural properties is in terms of
moduletheoretic and homological properties of M (torsion,
torsionfree, reflexive, and projective modules; extension and torsion
functors). In fact, a full classification of modules by homological
algebra methods translates into a classification of linear control
systems.
2 Duality Between Differential Operators and DModules
Let us turn to the formal theory of PDEs [13]. Starting
with a naive viewpoint on differential operators (so as to avoid the
formalism of jet bundles), we introduce formally exact sequences
of differential operators. For each k, let F^{k} denote the
algebra of functions in k variables, and consider a differentiel
operator D from F^{m} to F^{l} (of finite order). Given hÎ
F^{n}, the necessary conditions for the existence of xÎ F^{m} such
that Dx=h are called compatibility conditions
of D; they take the form D_{1}h=0 for some differential
operator D_{1}. Writing D_{0}=D, we have D_{1}°D_{0}=0.
When D_{1} encapsulates all compatibility conditions, the sequence
of differential operators is called formally exact
(at F_{l0}). Formally exact sequences can always be extended (to
the right) into longer sequences, so that denoting the solution set
of D=D_{0} in F^{m} by Q, we obtain a formally exact
sequence
0®Q®
F^{m} 

F^{l0} 

F^{l1}


F^{l2}®···

(at Q and each F^{lk}) where the first two maps denote
inclusions. Under technical conditions (regularity and
involutivity), the formal theory of PDEs proves the existence
of a finite formally exact sequence for D, in the sense
that F^{ln}=0 from some n on, by exhibiting a canonical, formally
exact sequence
0®Q=kerD_{0}®
F^{m} 

F^{l0} 

F^{l1}


F^{l2}®···


F^{lr}®0
(2) 
called the Janet sequence of D, in which each
(nonzero) D_{i} is of order 1 (and involutive) for i³1, and
r is the number of derivatives.
A dual, more algebraic counterpart to this differential viewpoint is
in terms of exact sequences of Dmodules. To this end, we now
view each D_{i} as defined by an l_{i}× l_{i1} matrix R_{i} of
multivariate linear differential operators in
A=R(x_{1}...,x_{r})[¶_{1},...,¶_{r}].
(We set l_{1}=m.) In terms of matrices,
D_{i}=R_{i}·=(x® R_{i}x),
so that R_{i+1}R_{i}·=0. We then consider the maps ·
R_{i} from A^{li} to A^{li1}, whose elements are viewed as
row vectors. To start with, the map · R_{0} defines an
algebraic representation of a generic solution x the PDE
system D_{0}x=0 in the following way. Let (e_{1},...,e_{m}) be
the canonical basis of A^{m} and consider the maps
0¬ M=A^{m}/A^{l0}R_{0} 

A^{m} 

A^{l0},
(3) 
where p denotes the canonical projection p(v)=v+A^{l0}R_{0}.
The cokernel
M=coker(· R_{0})=A^{m}/A^{l0}R_{0}
of · R_{0} contains the announced generic solution:
setting
x_{i}=p(e_{i})=e_{i}+A^{l0}R_{0},
we get D_{0}x=x
R_{0}=0. Other members of M correspond to linear combinations of
the x_{i} and their derivatives, i.e., to the observables defined
above. We now proceed to follow up with the next D_{i}'s. A
sequence
of linear maps (between modules) is said to be exact
(at L') if im u=kerv. (Thus (3) is
exact at M and A_{l0}.) It can be shown that any Janet
sequence (2) gives rise to the exact sequence
0¬ M 

A^{m} 

A^{l0}


A^{l1}


A^{l2}¬···


A^{lr}¬0
(4) 
(at M and each A^{lk}). Here, · R_{i+1}R_{i}=0 by
exactness. Since A has no zero divisor, this means
that R_{i+1}R_{i}=0. The sequence (4) of
(left) Dmodules is called a free resolution of M: it
encapsulates the obstruction of M to be free (as the module
kerp=im(· R_{0})), then the obstruction of kerp to be
free (as the module ker(· R_{0})=im(· R_{1})), etc. (A
module is called free when it is isomorphic to some A^{r},
whence the name ``free resolution.'')
3 Parametrization and Controllability
A problem dual to the search of compatibility conditions is, for a
given differential equation Dx=0, to determine whether the
solutions can be parametrized by certain arbitrary functions which, in
physical systems, play the role of potentials. In other words,
the problem is to determine whether there exists another
operator
D_{1}:F^{l1}® F^{l0}
whose compatibility conditions are described by D=D_{0}, i.e., to
look for a formally exact sequence
In this situation, for any xÎ F^{l0} the existence of pÎ
F^{l1} satisfying D_{1}p=x is equivalent to the fact
that x solves the differential equation D_{0}x=0, and so
D_{1} ``parametrizes''in the usual senseall its solutions.
The existence of a parametrization has a nice application to
optimal command: assume one needs to minimize a cost function
provided by the integral ò_{0}^{t}F(t) dt of an observable F
of some system D_{0}. The optimization problem is then to minimize
over all tuples x=(y,x,u)^{T} of functions constrained
by D_{0}x=0. On the other hand, once the solutions x are
given by a parametrization x=D_{1}p, the optimization problem
reduces to the nonconstrained problem of minimizing the
integral ò_{0}^{t}G(t) dt of a new observable G of D_{1}
over unconstrained p [12].
To study the controltheoretic properties of the differential
operator D, starting with the existence of a parametrization, we
in fact study the moduletheoretic properties of M, which in turn
are derived from the study of the right Dmodule defined by
A^{l1} 

A^{l0}®
N=coker(R_{0}·)=A^{l0}/R_{0}A^{l1}®0
(5) 
(recall that l_{1}=m and compare
with (3)). The key ingredient to be used
comes from linear algebra: dualization, which maps a left
Amodule L to the right module hom_{A}(L,A)
of Alinear applications from L to A. Correspondingly,
any linear map LL' induces a map from the
dual of L' to the dual of L: to lÎhom_{A}(L',A),
one associates l° uÎhom_{A}(L,A). This takes a
simple form when the modules are free and of finite rank (i.e.,
L=A^{m} and L'=A^{l}, viewed as left modules of row vectors).
Indeed, the linear map u is just the application of an m×
l matrix U: u=· U. Elements µÎhom_{A}(A^{k},A)
are defined by their values on the canonical basis (e_{i}) of A^{k}
by
µ=· 
( 
µ(e_{1}),...,µ(e_{k}) 
) 
^{T},

so that the dual of A^{k} is isomorphic to A^{k} (now viewed as a
right module of column vectors). In this setting, the dual of a map
A^{m}A^{l}
is A^{m}A^{l}. The same ideas apply
mutatis mutandis for the dual of right modules.
To search for a parametrization, one thus extends the exact
sequence (5) into an exact sequence
A^{l2}


A^{l1}


A^{l0}
® N®0.

An algorithm for this purpose will be given in
Section 5. By dualization (i.e., application
of the hom_{A}(·,A) functor), it becomes a sequence
A^{l2}


A^{l1}


A^{l0}
¬hom_{A}(N,A)¬0

of left Dmodules that is usually no longer exact. In
particular, we may well have ker(· R_{1}) strictly larger
than im(· R_{0}). Upon forgetting the map · R_{0} and
prolonging · R_{1} into
we obtain an ``exact'' representation of ker(· R_{1})
as im(· R'_{0}). It can be proved that the quotient
im(· R'_{0})/im(· R_{0})Í M
is the torsion module t(M) of M, i.e., the set of all its
members m for which there exists a nonzero scalar aÎA such
that am=0. Thus we have obtained that a (linear) control system
system is controllable if and only if its associated module M of
observables is torsionfree, which can be tested algorithmically.
Moreover, a basis for the module t(M) of autonomous elements is
obtained from the rows of R'_{0} (that are elements of im(·
R'_{0})), viewed modulo im(· R_{0}).
4 More Structural Properties of Control Systems as Extension
Modules
Other structural properties of D will be described in terms of the
extension modules of N, a central tool in homological
algebra. Consider a free resolution
··· 

A^{ln}


···


A^{l2}


A^{l1}


A^{l0}
® N®0
(6) 
(as obtained, for example, with the algorithms of
Section 5). This is an exact sequence of
right Dmodules. By dualization it becomes a sequence
··· 

A^{ln}


···


A^{l2}


A^{l1}


A^{l0}
¬hom_{A}(N,A)¬0
(7) 
of left Dmodules that, again, is usually no longer exact. By
dropping hom_{A}(N,A) from (7), we obtain
another nonexact sequence, but of free modules only,
··· 

A^{ln}


···


A^{l2}


A^{l1}


A^{l0}
¬0.

Its defects of exactness are encapsulated by its cohomology
sequence, that is to say, by the quotients
ker(· R_{i})/im(· R_{i+1}).
An allimportant fact is that this
family depends on N only, and not of the choice of a free
resolution (6). This motivates the
notation
ext_{A}^{i}(N,A)=ker(· R_{i})/im(· R_{i+1})
for extension modules (with in particular
ext_{A}^{0}(N,A)=ker(· R_{0})=hom_{A}(N,A)).
The nullity or nonnullity of the ext^{i}'s provides with the
classification of modules in
Theorem 1 below; in turn this
classification provides with the classification of control systems in
Theorem 3 below. Here are two more
moduletheoretic notions missing to state
Theorem 1. A module L is
projective whenever there exists a module L' such that
LÅ L' is free; it is reflexive whenever it is
isomorphic to the dual of its dual through the linear map
e:M®hom_{A} 
( 
hom_{A}(M,A),A 
) 
defined by
e(m)(f)=f(m).
Then, a free module is always projective, a projective module always
reflexive, and a reflexive module always torsionfree. (For modules
over a principal ideal, these notions coincide; for modules over a
multivariate polynomial ring with coefficients over a field, free and
projective are equivalent, a theorem by Quillen and Suslin.)
The following theorems [1, 4] make the link
between properties of a module and the nullity of the extension
modules of its transposed module.
Theorem 1 [Palamodov, Kashiwara]
For the modules M and N defined by (3)
and (5), we have:

M is torsionfree if and only if ext_{A}^{1}(N,A)=0;
 M is reflexive if and only if
ext_{A}^{1}(N,A)=ext_{A}^{2}(N,A)=0;
 M is projective if and only if
ext_{A}^{1}(N,A)=...=ext_{A}^{r}(N,A)=0.
Theorem 2 [Palamodov, Kashiwara]
Let M and N be the two modules defined by
(3) and (5).
Then there exists an exact sequence
0® M®A^{p1}®A^{p2}
®...®A^{pr}
if and only if ext_{A}^{i}(N,A)=0 for i=1,...,r.
We finally obtain the following classification of linear control
systems, which admits some refinements in the case of differential
operators with constant coefficients, i.e., matrices with entries in
R[¶_{1},...,¶_{r}]ÌA
[7, 8, 12].
Theorem 3
For a control system defined by the differential
operator D=R· where R is an l× m matrix with l£
m and entries in
A=R(x_{1}...,x_{r})[¶_{1},...,¶_{r}],
introduce the two left Dmodules M=coker(· R) and
N=coker(R·) of the maps between the free modules A^{m}
and A^{l}. Then:

if M has torsion, the control system has autonomous elements,
and in the event R has constant coefficients and full row module, it
has no primality property;
 M is torsionfree if and only if ext_{A}^{1}(N,A)=0. In
this case, the control system is controllable, and in the event
R has constant coefficients and full row module, it is prime in the
sense of minors, i.e., there is no common factor between the minors
of R of order l;
 M is reflexive if and only if
ext_{A}^{1}(N,A)=ext_{A}^{2}(N,A)=0;
 in the event R has constant coefficients and full row module,
and if
ext_{A}^{1}(N,A)=...=ext_{A}^{r1}(N,A)=0
while
ext_{A}^{r}(N,A)¹0,
the control system is weakly prime in the sense of zeroes, i.e., all
minors of order l simultaneously vanish at finitely many points
only;
 M is projective if and only if
ext_{A}^{1}(N,A)=...=ext_{A}^{r}(N,A)=0.
In this case the control system has an inverse generalized Bézout
identity, and in the event R has constant coefficients and full row
module, it is prime in the sense of zeroes, i.e., all minors of
order l simultaneously vanish at no point;
 if M is free, the control system is flat and has direct and
inverse generalized Bézout identities.
Further intermediate situations,
ext_{A}^{1}(N,A)=...=ext_{A}^{k1}(N,A)=0 and
ext_{A}^{k}(N,A)¹0, correspond to further intermediate primeness
conditions (described in terms of the dimension of the algebraic
variety defined by the l× l minors of R).
5 Gröbner Basis Calculations for Compatibility Conditions and
Parametrizations
The whole machinery of the previous sections crucially bases on
prolongations of exact sequences. A point that is important in view
of computations is that these can be obtained by Gröbner basis
calculations for free modules over A.
The prolongation of a map A^{m}A^{l}
into an exact sequence A^{m}A^{l}A^{k} is done in the
following fashion. Let (e_{1},...,e_{m}) and (f_{1},...,f_{l}) be the
canonical bases of A^{m} and A^{l}, respectively, and denote the
ith row of R=(r_{i,j}) by h_{i}. Thus
h_{i}=å_{j=1}^{m}r_{i,j}e_{j}. Prolonging the map amounts to
finding nontrivial relations å_{i=1}^{l}s_{i}h_{i}=0. Now
introduce the submodule Z of A^{m+l} generated by the formal
linear combinations f_{i}h_{i}. We contend that computing a
Gröbner basis for this module and for a term order that
eliminates the e_{i} results in linear combinations
å_{i=1}^{l}s_{i}f_{i}Î Z, each of which corresponds to a relation
between the h_{i}. Additionally, any relation can be obtained as a
linear combination of the relations thus obtained.
In effect, consider an element z=å_{i=1}^{l}s_{i}f_{i}Î Z; thus
å_{i=1}^{l}s_{i}h_{i} is in Z and is a combination
å_{i=1}^{l}l_{i}(f_{i}h_{i}), which is only possible, in view
of the coefficients of the f_{i}, if the l_{i} are zero, thus
if å_{i=1}^{l}s_{i}h_{i}=0; the converse property is also true.
Since the Gröbner basis calculation precisely computes a finite
generating set, say of k elements, for all the z's free of
the e_{i}, it suffices to consider each of those k elements as a
row, and to glue them in column to obtain a new matrix S=(S_{i,j})
such that the sequence A^{m}A^{l}A^{k} is exact.
Now, existing packages often contain facilities to compute Gröbner
bases for left modules only; some of our computations require to deal
with right modules. A last ingredient, adjunction, enables one
to turn any left module into a right module, and vice versa, in a way
that preserves the exactness of sequences. Indeed, the adjoint
map P®P^{~} defined by associativity from the rules x_{i}^{~}=x_{i}, ¶_{i}^{~}=¶_{i}, and (PQ)
^{~}=Q^{~}P^{~}, is an (anti)automorphism of the algebra A
which extends to matrices by mapping itself to the entries of the
transpose matrix. Thus, for example, the exact
sequence (5) of right Dmodules of columns
in Section 3 is replaced with the exact
sequence
A^{l1} 

A 
^{l0}®


=coker(· 

)®0

of left Dmodules of lines, for the purpose of explicit calculations.
References
 [1]

Kashiwara (Masaki). 
Algebraic study of systems of partial differential equations. Mémoires de la Société Mathématique de France, n°63,
1995. 
Japanese translation of the author's thesis (1970). xiv+72p.
 [2]

Malgrange (Bernard). 
Systèmes différentiels à coefficients constants. In Séminaire Bourbaki, Vol. 8, pp. 7989. 
Société Mathématique de France, Paris, 1995.
Exposé n°246.
 [3]

Oberst (Ulrich). 
Multidimensional constant linear systems. Acta Applicandae
Mathematicae, vol. 20, n°12, 1990, pp. 1175.
 [4]

Palamodov (V. P.). 
Linear differential operators with constant coefficients. 
SpringerVerlag, New York, 1970. viii+444 pages.
 [5]

Polderman (Jan Willem) and Willems (Jan C.). 
Introduction to mathematical systems theory. 
SpringerVerlag, New York, 1998. A behavioral
approach. xxx+424 pages.
 [6]

Pommaret (J. F.) and Quadrat (A.). 
Generalized Bézout identity. Applicable Algebra in
Engineering, Communication and Computing, vol. 9, n°2,
1998, pp. 91116.
 [7]

Pommaret (J. F.) and Quadrat (A.). 
Algebraic analysis of linear multidimensional control systems. IMA Journal of Mathematical Control and Information, vol. 16, n°3,
1999, pp. 275297.
 [8]

Pommaret (J. F.) and Quadrat (A.). 
Localization and parametrization of linear multidimensional control
systems. Systems & Control Letters, vol. 37, n°4,
1999, pp. 247260.
 [9]

Pommaret (J. F.) and Quadrat (A.). 
Formal elimination for multidimensional systems and applications to
control theory. Mathematics of Control, Signals, and Systems, vol. 13,
n°3, 2000, pp. 193215.
 [10]

Pommaret (J. F.) and Quadrat (A.). 
A functorial approach to the behaviour of multidimensional control
systems. In The Second International Workshop on Multidimensional (nD)
Systems (Czocha Castle, 2000), pp. 9196. 
Tech. Univ. Press, Zielona Góra, 2000.
 [11]

Quadrat (Alban). 
A fractional representation approach of synthesis: an algebraic
analysis point of view. SIAM Journal on Optimization and Control. 
To appear.
 [12]

Quadrat (Alban). 
Analyse algébrique des systèmes de contrôle linéaires
multidimensionnels. 
Thèse de doctorat, École nationale de Ponts et Chaussées,
September 1999.
 [13]

Spencer (D. C.). 
Overdetermined systems of linear partial differential equations. Bulletin of the American Mathematical Society, vol. 75, 1969,
pp. 179239.
 [14]

Wood (Jeffrey). 
Modules and behaviours in nd systems theory. Multidimensional Systems and Signal Processing, vol. 11, n°12,
2000, pp. 1148. 
Recent progress in multidimensional control theory and applications.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.