Grbner Bases In Control Theory And Signal Processing Hyungju Park Editor Georg Regensburger Editor

Grbner Bases In Control Theory And Signal
Processing Hyungju Park Editor Georg
Regensburger Editor download
https://ebookbell.com/product/grbner-bases-in-control-theory-and-
signal-processing-hyungju-park-editor-georg-regensburger-
editor-51130382
Explore and download more ebooks at ebookbell.com

Here are some recommended products that we believe you will be
interested in. You can click the link to download.
Grbner Bases In Symbolic Analysis Markus Rosenkranz Editor Dongming
Wang Editor
https://ebookbell.com/product/grbner-bases-in-symbolic-analysis-
markus-rosenkranz-editor-dongming-wang-editor-51130406
Grobner Bases In Symbolic Analysis Rosenkranz Markus Wang Dongming
https://ebookbell.com/product/grobner-bases-in-symbolic-analysis-
rosenkranz-markus-wang-dongming-23595360
The Use Of Dtruncated Grbner Bases In Cryptanalysis Of Symmetric
Ciphers Master Thesis Jensare Amundsen
https://ebookbell.com/product/the-use-of-dtruncated-grbner-bases-in-
cryptanalysis-of-symmetric-ciphers-master-thesis-jensare-
amundsen-5401268
Bifurcations In Hamiltonian Systems Computing Singularities By Grbner
Bases 1st Edition Henk Broer
https://ebookbell.com/product/bifurcations-in-hamiltonian-systems-
computing-singularities-by-grbner-bases-1st-edition-henk-broer-918624

Grbner Bases And The Computation Of Group Cohomology 1st Edition David
J Green Auth
https://ebookbell.com/product/grbner-bases-and-the-computation-of-
group-cohomology-1st-edition-david-j-green-auth-4210822
Grbner Bases Statistics And Software Systems 1st Edition Takayuki Hibi
Auth
https://ebookbell.com/product/grbner-bases-statistics-and-software-
systems-1st-edition-takayuki-hibi-auth-4637362
Grbner Bases Coding And Cryptography 1st Edition Massimiliano Sala
Auth
https://ebookbell.com/product/grbner-bases-coding-and-
cryptography-1st-edition-massimiliano-sala-auth-1146672
Noncommutative Grbner Bases And Filteredgraded Transfer 1st Edition
Huishi Li Auth
https://ebookbell.com/product/noncommutative-grbner-bases-and-
filteredgraded-transfer-1st-edition-huishi-li-auth-4210482
Algorithmic Algebraic Combinatorics And Grobner Bases 1st Edition Aiso
Heinze
https://ebookbell.com/product/algorithmic-algebraic-combinatorics-and-
grobner-bases-1st-edition-aiso-heinze-1435548

Radon Series on Computational and Applied Mathematics 3
Managing Editor
Heinz W. Engl (Linz/Vienna)
Editors
Hansjörg Albrecher (Linz)
Karl Kunisch (Graz)
Ronald H. W. Hoppe (Augsburg/Houston)
Ulrich Langer (Linz)
Harald Niederreiter (Singapore)
Christian Schmeiser (Linz/Vienna)

Gröbner Bases
in Control Theory
and Signal Processing
Edited by
Hyungju Park
Georg Regensburger
≥
Walter de Gruyter · Berlin · New York

Editors
Hyungju Alan Park
School of Computational Sciences
Korea Institute for Advanced Study (KIAS)
207-43 Cheongnyangni
2-dong Dongdaemun-gu
Seoul 130-722
Korea
e-mail: [email protected]
Georg Regensburger
Radon Institute for Computational and
Applied Mathematics
Austrian Academy of Sciences
Altenberger Straße 69
A-4040 Linz
Austria
e-mail: [email protected]
Key words:
Multidimensional systems, Gröbner bases, symbolic computation, polynomial ideals, multivariate
filter banks, multidimensional linear systems, multivariate polynomial matrices, multidimensional
signal processing and control, Quillen-Suslin theorem, polynomial rings, flat systems, stability,
randomized algorithms, input/output systems, orthonormal wavelets, linear systems, time-varying
systems.
Mathematics Subject Classification 2000:
00B25, 11E25, 13C10, 13F20, 13Pxx, 16Sxx, 35B35, 42C40, 47A65, 68Wxx, 93Bxx, 93Cxx,
93Dxx, 94Axx.
Printed on acid-free paper which falls within the guidelines
of the ANSI to ensure permanence and durability.
Library of Congress Cataloging-in-Publication Data
A CIP catalogue record for this book is available from the Library of Congress.
ISBN 978-3-11-019333-6
Bibliographic information published by the Deutsche Nationalbibliothek
The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie;
detailed bibliographic data are available in the Internet at http://dnb.d-nb.de.
Copyright 2007 by Walter de Gruyter GmbH & Co. KG, 10785 Berlin, Germany.
All rights reserved, including those of translation into foreign languages. No part of this book
may be reproduced or transmitted in any form or by any means, electronic or mechanical,
including photocopy, recording, or any information storage or retrieval system, without permission
in writing from the publisher.
Printed in Germany
Cover design: Martin Zech, Bremen.
Typeset using the authors’ TeX-files: Kay Dimler, Müncheberg.
Printing and binding: Hubert & Co. GmbH & Co. KG, Göttingen.

Radon Series Comp. Appl. Math3 cde Gruyter 2007
Preface
Bruno Buchberger’s now well-known article on Gr¨obner bases in the context of control
theory appeared in 1985 inMultidimensional Systems Theory. Motivated by this article,
many researchers have worked on applications of Gr¨obner bases and related methods in
multidimensional control theory and signal processing. While early work was focused
on linear systems theory and partial differential control theory, many interesting new
applications have been found more recently in multidimensional signal processing. In
particular, Gr¨obner bases proved to be a powerful tool in designing multidimensional
ﬁlter banks and wavelets and have also shown potential in solving PDEs.
This volume grew out of the D3 Workshop onGr¨obner Bases in Control Theory
and Signal Processing(May 18–19, 2006) held in Linz, Austria, in the frame of the
Special Semester on Gr¨obner Bases and Related Methods. The special semester was
organized in the spring and summer of 2006 by the Johann Radon Institute for Com-
putational and Applied Mathematics (RICAM), in close cooperation with the Research
Institute for Symbolic Computation (RISC). Directed by Bruno Buchberger (RISC)
and Heinz W. Engl (RICAM), it created a unique atmosphere for interdisciplinary co-
operation on all aspects of Gr¨obner bases.
This volume collects survey articles andoriginal research papers by some of the
leading researchers in the area and offers a glimpse of the state of the art on the subject.
The topics covered include
•Gr¨obner bases in multidimensional systems,
•the Quillen-Suslin theorem and systems theory,
•statistical signal processing,
•parametric problems in control theory,
•stability of multidimensional input/output systems,
•wavelets andﬁlter design,
•synthesis of multidimensional control systems,
•time-varying linear systems.
For the full workshop program we refer to the RICAM special semester website at:
http://www.ricam.oeaw.ac.at/specsem/
It is our pleasure to express our gratitudeto all authors for their enthusiasm that
undoubtedly will make this volume a valuable contribution to the area. We extend our
sincere thanks to Bruno Buchberger, Heinz W. Engl, and the staff at RICAM and RISC
for their warm hospitality during the workshop. We cordially thank Robert Plato and
Kay Dimler from the publishing house Walter de Gruyter for their professional help
from early brainstorming to theﬁnal editing stage.
Hyungju Park and Georg Regensburger Seoul and Linz, October 2007

Table of Contents
H. PARK,G.REGENSBURGER
Preface....................................... v
N. K. BOSE
Two decades (1985–2005) of Gr¨obner bases in multidimensional systems.....1
A. FABIA´NSKA,A.QUADRAT
Applications of the Quillen-Suslin theorem to multidimensional systems theory.23
J. LEBRUN
Normal forms in statistical signal processing................... 107
V. LEVANDOVSKYY ,E.ZERZ
Obstructions to genericity in study of parametric problems in control theory...127
U. OBERST,M.SCHEICHER
A survey of (BIBO) stability and (proper) stabilization of multidimensional
input/output systems............................... 151
G. REGENSBURGER
Applications ofﬁlter coefﬁcients and wavelets parametrized by moments....191
L. XU
Applications of Gr¨obner bases in synthesis of multidimensional control systems 215
E. ZERZ
State representations of time-varying linear systems............... 235

Radon Series Comp. Appl. Math3, 1–22 cde Gruyter 2007
Two decades (1985–2005) of Gr¨obner bases
in multidimensional systems
N. K. Bose
Key words.Multidimensional systems, Gr¨obner bases, polynomial ideals, multivariateﬁlter banks,
multidimensional systems stabilization, multivariate polynomial matrices, multidimensional signal
processing and control.
AMS classiﬁcation.13P10, 93D15, 13F20, 11E25
1 Introduction........................................ 1
2 Buchberger’s algorithm for construction of Gr¨obner bases............... 2
3 Multivariate polynomial equations and inequalities................... 9
4Gr¨obner bases may not always produce the result sought................ 16
5 Bihermitian forms and SOS................................ 18
6 Conclusions........................................ 19
Bibliography.......................................... 21
1 Introduction
The subject of linear shift-invariant multidimensional systems, originally conceptual-
ized (now expanded along other directions, not considered here), is concerned with
a mathematical framework for tackling a broad range of paradigms whose analysis
or synthesis require the use of polynomials, rational functions and matrices with ei-
ther polynomial or rational function entries in several complex variables. Its applica-
tions, which may range from the processing of spatial and temporal signals of diverse
physical origin to the design of linear discrete multidimensional control systems, are
plentiful. The areas of image processing, linear multipass processes, iterative learning
control systems, lumped-distributed network synthesis, nonlinear system analysis via
multidimensional transforms and geophysical signal processing have beneﬁted from
the tools available in the theory of multidimensional systems. The implementation of
various tests of multidimensional systems properties, necessitate the development and
use of tests for global or local positivity of polynomials of several real variables and,
in a broader sense, algebraic as well as semialgebraic sets.
Supported by RICAM (Radon Institute for Computational and Applied Mathematics) and RISC (Research Insti-
tute for Symbolic Computation).

2 N. K. Bose
Some of the fundamental difﬁculties which either complicate the development of
resources for meeting the needs of diverse applications or are responsible for limit-
ing the scopes of attempts at naive generalizations of one-dimensional (1-D) results
to the corresponding
n-dimensional (n-D) situations have been recognized during the
past three decades. Considerable analytical resources are required to go from 1-D to
2-D results and even after the associated bottlenecks are circumvented, the subsequent
generalization from 2-D to 3-D may not be routine. This fact is dramatically illustrated
by the coprime factorability of univariate polynomial matrices whose elements are in
an Euclidean domain [30], the nontrivial generalization of such results to the bivariate
case [19] and the impossibility, in general, of further generalization to the trivariate
case [24]. Some of seminal results in [24] are illustrated with examples in [37].
While discussing the
n-D real Euclidean spaceR
n
,Daniel Asimov [3] states that
“strictly on their own merits, higher-dimensional spaces tend to blur together into mul-
tidimensional sameness.” He goes on to remark that “it is often among low-dimensional
spaces that the most dramatic transitions take place: as the number of dimensions rises,
fundamental properties suddenlyﬂash into existence or vanish forever, never to change
again.” This remark is dramatically illustrated by the celebrated conjecture made in
1904 by the distinguished French mathematician, Henri Poincar´e, on a possible simple
test to classify the 3-sphere among all 3-dimensional manifolds without boundary. Its
generalization wasﬁrst solved in the case of
n-dimensional manifolds in 1960–1961
for
n≥5 (Stephen Smale) and in 1982 forn=4(Michael Freedman) by ingenious
innovative methods. The original conjecture was settled by Grisha Perelman in 2003.
The undeniable challenge and the promised reward have propelled the subject-matters
of multidimensional systems theory and algorithmic computer algebra to a state of ma-
turity that guarantees a continuing proliferation of increasingly complex and diversiﬁed
nature of activities.
While involved with the development of multidimensional systems theory, aware-
ness of the potentials of Gr¨obner bases in computational aspects of the subject was
natural. Such bases for polynomial ideals provide an algorithmic method for solving a
number of computability and decidability problems concerning the ideal; for example,
given a multivariate polynomial
f(z)and an idealIspeciﬁed by aﬁnite number of
generators, one can perform computations in the original polynomial coefﬁcientﬁeld
to decide constructively whether or not
f(z)belongs toI.
2 Buchberger’s algorithm for construction of Gr¨obner
bases
This author’s interest in Gr¨obner bases (Hironaka’s standard bases for polynomial ide-
als) originated during the early nineteen eighties when Professor Buchberger, a former
student of Gr¨obner, visited the University of Pittsburgh as an invitee of the author. On
realizing the relevance of Gr¨obner bases to multidimensional systems theory, this au-
thor’s invitation to contribute a survey chapter on the subject in a book [6] was gladly
accepted by Bruno Buchberger. The highly readable chapter 6 in [5] and its updated

Two decades of Gr¨obner bases in multidimensional systems 3
version (chapter 4 in [6]) are strongly recommended to the readers of this paper. Other
worthwhile readings are the texts [1] and [11], where computational algorithms for the
fast construction of such bases are extensively documented. It is worth mentioning as
a historical fact that the algorithm developed by Buchberger [10] for the solution of a
problem on the multivariate analog of the Euclidean algorithm, posed by Gr¨obner, led
to the naming of Gr¨obner bases by the humble student in deference to his respected
teacher. Justiﬁably, subsequent researchers have, sometimes, referred to Gr¨obner bases
as Gr¨obner-Buchberger bases. Many computational problems that are extremely dif-
ﬁcult for polynomial ideals generated by arbitrary bases are very easy for polynomial
ideals generated by Gr¨obner bases. One of the early results was a formula expressing
the greatest common divisor of a set of polynomials of several variables in terms of a
Gr¨obner basis of the ideal generated by them [16]. More recently, it has been shown
how Gr¨obner bases can be used to investigate zero coprimeness and minor coprimeness
of multivariate polynomial matrices [7, 6] leading up to the difﬁcult problem of factor
coprimeness (for an up-to-date discussion see the recent text [21]).
Let a polynomial ring involving indeterminates
z1,z2,...,znover an arbitrary but
ﬁxed baseﬁeld
Kof coefﬁcients be denoted by R=K[z 1,z2,...,zn].A monomial
z
i1
1
z
i2
2
...z
in
nwill be called aterm(sometimes this is called a power product and then
the term refers to a coefﬁcient times a power product) whose degree is
i1+i2+...+i n.
Deﬁne an order
<Ton the terms as follows:z
i1
1
...z
in
n<Tz
j1
1
...z
jn
nif and only if
deg(z
i1
1
...z
in
n)<deg(z
j1
1
...z
jn
n)ordeg(z
i1
1
...z
in
n)=deg(z
j1
1
...z
jn
n)
andi1=j1,...,ik=jk,ik+1>jk+1for somekwith1≤k+1≤n . The next
example illustrates an order
<Tdeﬁnedontheterms.
Example 2.1
1<z 1<z2<z3<z
2
1
<z1z2<z1z3<z
2
2
<z2z3<z
2
3
<z
3
1
<z
2
1
z2<z
2
1
z3<z1z
2
2
<z1z2z3<z1z
2
3
<z
3
2
<z
2
2
z3<z2z
2
3
<z
3
3
<z
4
1
< ....
The above shows an admissible linear ordering of monomials – the total degree
ordering, with ties broken by a lexicographical (lex) order on the variables. Other
ordering include degree reverse lexicographical [1, pp. 18–25] (degrevlex), antigraded
revlex [14] etc.
2.1 Notations
In the following notationstdenotes a term, taken to be a monomialz
i1
1
z
i2
2
...z
in
nof
degree
i1+i2+...+i nandf,gare polynomials inR[z].
Coef
(t, f)β coefﬁcient of the termtin polynomialf(possibly 0).
Occ
(t, f)←→ Coef(t, f)η =0 .
Hterm
(f)β maximal term infwith respect to ordering<T,iffη =0; 1, otherwise.
Hcoef
(f)β Coef(Hterm(f),f) .
Head
(f)β Hcoef(f)Hterm(f).
Rest
(f)βf− Head(f).
Mult
(z
i1
1
z
i2
2
...z
in
n,z
j1
1
z
j2
2
...z
jn
n)←→i 1≥j1,i2≥j2,...,in≥jn.
LCM(z
i1
1
z
i2
2
...z
in
n,z
j1
1
z
j2
2
...z
jn
n)βz
max(i 1,j1)
1
z
max(i 2,j2)
2
...z
max(i n,jn)
n
.

4 N. K. Bose
In the following notationsFdenotes aﬁnite sequence {f1,f2,...,fr}of polynomials.
L(F)β length of the sequence{f1,f2,...,fr}=r.
Mterm
(t, F)←→ ∃f i∈F, fiη =0,such that Mult(t,Hterm(fi)).
Normal
f(t, F)←→ ∀t with Occ(t, f),¬ Mterm(t, F).
The last two items are expanded below for clarity.
Mterm
(t, F) occurs if and only if∃fi∈F, fiη =0, such that Mult(t,Hterm(fi)),i.e.t
is a multiple of Hterm(fi).
Normal
f(g, F) occurs if and only if∀twith Occ(t, g), there is no Mterm(t, F).
Example 2.2Let
F={f 1,f2}={z
3
1
z2z3−z1z2,z1z2z
2
3
−2z
2
3
}. Then, we get
Head
(f1)=z
3
1
z2z3,Head(f2)=z 1z2z
2
3
,Rest(f1)=−z 1z2,Rest(f2)=−2z
2
3
and LCM(Head(f1),Head(f2)) =z
3
1
z2z
2
3
.
Next, a reduction procedure is deﬁned as follows:
f•>
(1)
F,t,i
g←→1≤i≤L(F),f iη =0,Occ(t, f), Mult(t,Hterm(fi)),g=f−a·s·f i,
where
a=
Coef(t,f)
Hcoef(fi)
,s=
t
Hterm(fi)
.
f•>
(1)
F
g←→ ∃t, i such thatf•>
(1)
F,t,i
g.
f•>
Fg←→ ∃f 0,...,fk,k≥0, such thatf0=f,fk=g, fi•>
(1)
F
fi+1for
i=0,...,k−1 .
(Case
f=g included; iff•> Fg,thenfM-reduces tog).
f•> F˜g←→f•> F˜gand Normalf(˜g, F) .
(That is,
˜gis a normal form offwith respect toF).
f∇
succ
F
g←→ ∃h such thatf•> Fh, g•> Fh.
Spol(f,g)β Hcoef(g)
LCM(Hterm(f),Hterm(g))
Hterm(f)
f
−
Hcoef(f)
LCM(Hterm(f),Hterm(g))
Hterm(g)
g.
IfF=f 1,f2,...,fris aﬁnite sequence of polynomials,j1,j2,...,jkare integers
with
1≤j i≤L(F), thenHF(j1,j2,...,jk)denotes the LCM of the head terms of
fj1
,fj2
,...,fjk.
Example 2.3Let
R=Q[z 1,z2,z3],whereQdenotes theﬁeld of rationals. Let F=
f
1,f2denote a sequence of two polynomials,
f1=z
2
2
+z2z1+z
2
1
,f2=z
2
2
z1+1.
Then, the polynomialf=z 1f1−f2∈I(F), the polynomial ideal set up by the two
polynomials in the sequence
Fof polynomials. However,f=z 2z
2
1
+z
3
1
−1is in
normal form modulo
{f1,f2}with respect to every term order since the head terms,z
2
2
andz
2
2
z1have been lifted to their least common multiplez
2
2
z1and subtracted so that
the head monomials formed in
fcancel out.

Two decades of Gr¨obner bases in multidimensional systems 5
Consider the polynomial ringR=K[z 1,z2,...,zn].A system of generators of an
ideal
I⊂R is called a Gr¨obner basis if the leading monomials of its elements gen-
erate the same ideal in
Ras the leading monomials of all the polynomials inI.The
notion of a Gr¨obner basis admits a number of equivalent reformulations and serve as
the foundation of the whole of constructive commutative algebra.
Gr¨obner basis algorithms are based on the signiﬁcant fact that if theﬁnitely many
differences of the kind illustrated in the above example all reduce to zero then every
polynomial in
I(F)reduces to zero to makeFaGr¨obner basis, as deﬁned next. The
Gr¨obner basis might not be unique but by putting certain conditions on the polynomials
in the basis, uniqueness can be guaranteed. In that case the basis becomes a reduced
Gr¨obner basis, which exists for aﬁxed term order [1, p. 42].
If
f1,...,fris a Gr¨obner basis for the idealI=<f 1,...,fr>,thentodetermine
whether or not a given polynomial
fis inIoneM-reducesfto normal form which
is unique; if this normal form is zero then
fis clearly inIby the deﬁnition of M-
reduction; if it is not zero then
fis not inI.ToM-reduce a polynomial to normal form
successively eliminate
M-termstfromfby executing a step of the formf•> F,t,ig
until noM-terms are left. To do this in the most efﬁcient way, eliminate at each step the
highest
M-termtwith respect to the ordering<T; it is clear that in aﬁnite number of
steps a normal form will be reached. The theorem below summarizes several equivalent
deﬁnitions for Gr¨obner bases.
Theorem 2.4Let
F=f 1,f2,...,frbe a sequence of polynomials. The following
conditions are equivalent and each provides a deﬁnition for Gr¨obner bases.
1.
g∈I(F)←→g•> F0.
2. For
1≤i<j≤L(F), Spol(fi,fj)•> F0.
3.
h•> Fg, h•> Ff⇒g=f .
4.
h•> Fh1,h•> Fh2⇒h1∇
succ
F
h2.
5.
∀1≤i<j≤L(F)∃ sequencei=j 1,j2,...,jk=j,such that
HF(j1,j2,...,jk)=H F(i, j)
and
Spol
(fj1
,fj
(l+1)
)•> F0,l=1,2,...,k−1.
The S-polynomials in the reduction procedure are keys to the Buchberger algorithm for
basis construction. After the basis is constructed, solutions may be sought regarding
the location or clustering of the common zero-set of the original system of polynomial
equations over the groundﬁeld of interest in a particular application. In systems theory
applications considered here, the groundﬁeld is either theﬁeld of complex numbers
(complex algebraic geometry domain) or theﬁeld of real numbers (real algebraic ge-
ometry domain).
Buchberger’s algorithm for the scalar case goes through mutatis mutandis for the
vector case. Also one can construct an algorithm which will terminate after aﬁnite
number of steps and yield a vector Gr¨obner basis.

6 N. K. Bose
2.2 Why Gr¨obner bases in multidimensional systems?
Linear multidimensional systems for signal processing and control have considerable
use of multivariate polynomials, rational functions, and matrices of multivariate poly-
nomials and rational functions. Basic concepts in such usage include greatest com-
mon divisor extraction, factorization, polynomial ideals, algebraic varieties and semi-
algebraic sets. In the past, tools such as resultants and subresultants [4] as well as
Bezoutiants have been extensively used for the purpose [6]. However Gr¨obner basis
could offer several advantages that will be illustrated through selected examples.The
ﬁrst example is concerned with theﬁnding of common zeros, which are alwaysﬁnite in
number for any two (or more) relatively prime bivariate polynomials. Those common
zeros can be found by resultant theory. But, reduced Gr¨obner bases yield the common
zeros, usually, with lesser computational effort.
Example 2.5Consider two bivariate polynomials (in aﬁlter bank design problem),
that are known to be relatively prime:
a(z1,z2)=−0.075(z
2
1
z2+z1z
2
2
+z1+z2)−0.0375(z
2
1
+z
2
2
+1)+0.85z 1z2,
b(z
1,z2)=0.125(z 1z2+z1+z2+1).
Resultant based calculations could be messy! The reduced Gr¨obner basis for a(z1,z2)
andb(z1,z2), using SINGULAR (computed with respect to degree reverse lexicograph-
ical ordering), is
g0(z1,z2)=3z
3
2
−77z
2
2
−80z 2,
g
1(z1,z2)=z 1z2+z1+z2+1,
g
2(z1,z2)=3z
2
1
+3z
2
2
−80z 1−80z 2−83.
The common zeros ofg0(z1,z2)andg1(z1,z2)are easy toﬁnd at (−1,0),(0,−1),
(−1,80/3) and(80/3,−1) , and these are also the common zeros ofa(z1,z2)and
b(z1,z2).
Similarly, an alternative toﬁnding the common zeros of a set of relatively prime multi-
variate polynomials through the use of multipolynomial resultants [14] is the Gr¨obner
basis approach of successive elimination of more and more variables, followed by ex-
tension.
For a recent survey of the design of multidimensional wavelets andﬁlter banks, see
[22]. For
N-channel analysis
β
{h
i(z)}
N
i=1
α
and
β
{f
i(z)}
N
i=1
α
synthesisﬁlters in a PR
(perfect reconstruction)ﬁlter bank,
N
λ
i=1
hi(z)fi(z)=z
m
,m∈Z
n
+
, (2.1)
z=(z 1,...,zn)andz
m
is the notation for an-variate delayz
m1
1
...z
mn
n. Note that
mis not known a priori and given{hi(z)}the set{fi(z)}plusmhas to be found
satisfying the PR constraint. Without loss of generality, consider the
N=2,n=2

Two decades of Gr¨obner bases in multidimensional systems 7
Figure 2.1Scalar feedback system
(2-channel bivariate case). In this case,
h1(z1,z2)andh2(z1,z2)could have common
zeros at
(0,0),(0,β i)withβiη =0or(αi,0)withαiη =0. The “Rabinowitsch trick”
[28] can be used to solve the problem:
h1(z1,z2)f1(z1,z2)+h 2(z1,z2)f2(z1,z2)=s
r
(z1,z2)
forfi(z1,z2)and positive integerr, given that a polynomials(z1,z2)vanishes on the
variety of the ideal generated by
hi(z1,z2), as was done using Gr¨obner basis in [34]
(this paper also contained matrix equation results). Note that no previous knowledge of
the positive integer
ris needed. Letz3be a new indeterminate. Then(1−z 3s(z1,z2))
andhi(z1,z2),i=1,2 , are zero coprime. As a consequence of Hilbert’s (Weak) Null-
stellensatz, the ideal generated by these three zero-coprime polynomials must be the
unit ideal, i.e there exist polynomials
ˆgi(z1,z2,z3)fori=1,2,3 such that
2
λ
i=1
hi(z1,z2)ˆgi(z1,z2,z3)+(1−z 3s(z1,z2))ˆg3(z1,z2,z3)=1.
Then, substitute1/s(z 1,z2)forz3and clear out denominator to obtain an equation of
the form desired in equation (2.1). This problem is a case of Hilbert’s Nullstellensatz.
Theorem 2.6 (Hilbert’s Nullstellensatz)Let
Kbe aﬁeld, K1an algebraically closed
extension of
Kands, h1,h2,...,hN∈K[z 1,z2,...,zn].For allz∈K
n
1
,h1(z)=
h
2(z)=...=h N(z)=0 impliess(z)=0, if and only if there exists a positive
integer
rsuchs
r
belongs to the ideal generated by then-variate polynomialshkfor
k=1,2,...,N .
2.3 Multidimensional linear control systems and
Gr¨obner bases
Consider the generic plant/compensator feedback system in Figure 2.1. The plant and
compensator could be scalar as in theﬁgure or matrix-valued. In theﬁgure, the com-
pensator could be more general than a quotient of polynomials; in fact it could be a
quotient of elements from a different ring. The stabilization of scalar as well as matrix
feedback systems for the bivariate case has been documented in detail and the class
of all stabilizing compensators have been identiﬁed in [6]. The compensator can be
constructed by using Gr¨obner bases and Hilbert’s Nullstellensatz for both, the scalar

8 N. K. Bose
[5] and the matrix cases [34]. Probably, theﬁrst documentation of the use of Gr¨obner
bases in
n-D systems theory occurred in [5], from where only the more simple partial
results are quoted here. The reader is invited to consult [6] and [5] for details.
Fact 2.7[5, pp. 70–71] Let
h=
n
d
be the transfer function of the plantPin Figure
2.1, such that
nanddare relatively prime polynomials with no common zeros in the
bidisc
¯
U2
. One can constructivelyﬁnd polynomials x, y∈R[z 1,z2]such thatyd+
xn∈R
s[z1,z2], the multiplicatively closed set of bivariate polynomials which have no
zeros in
¯
U2
. Then, the stabilizing compensators are characterized by the expression
C=
−s1d+s 2x
s1n+s 2y
,wheres1∈R[z 1,z2]ands2∈Rs[z1,z2]are arbitrary.
Example 2.8Let
n(z1,z2)=z 1z2−z1−2z 2∗G1(z1,z2),
d(z
1,z2)=z
2
1
z
2
2
−2z 1z
2
2
−2z 1z2+4z 1+4∗G 2(z1,z2),
Spol(G1,G2)=G 2−z1z2G1=z
2
1
z2−2z 1z2+4z 1+4
−z
1G1
·>
z
2
1
+4z 1+4∗G 3(z1,z2).
G
3(z1,z2)is in normal form, i. e. no term ofG3is a multiple of the head terms of
Gi,i<3 . Backtracking,
d(z1,z2)−z 1(z2+1)n(z 1,z2)=z
2
1
+4z 1+4∈R s[z1,z2].
Example 2.9Consider the plant transfer function whose numerator and denominator
polynomials are
n(z1,z2)=z 1+z2,d(z 1,z2)=1−z 1+z2.
Common zeros occur at(1/2,−1/2)∈
¯
U
2
. Therefore, the plant is not stabilizable by
causal compensators (but is stabilizable by weakly causal systems (Guiver-Bose, 1985)
[5]).
Fact 2.10[5, pp. 72–78] In the MIMO bivariate causal case, if
D
−1
L
NLis an irre-
ducible left matrix-fraction description (LMFD) (maximal order minors of
[DLNL]
have no nontrivial common factor and hence have only aﬁnite number of common
zeros) of an unstable bivariate plant
P,andXRY
−1
R
denotes an irreducible right MFD
(maximal order minors of
[X
t
R
Y
t
R
]
t
have no nontrivial common factor) of a bivariate
compensator
C,thenCstabilizesPif and only ifdet(D LYR+NLXR)is zero free in
¯
U2
.
For stabilization of MIMO Weakly Causal systems, and updates on other results, in-
cluding computational methods for determining strong stabilizability of
n-D systems,
see [6] and works of Ying, Xu and Lin [36] and Ying [35]. Research counterparts in
the
n-D case (n>2) for constructing a stabilizing compensator for a MIMO plantus-
ing Gr¨obner bases (following initial work of Xu, Saito and Abe in 1994 [34]) is worth
pursuing.

Two decades of Gr¨obner bases in multidimensional systems 9
n-D System Stabilizability [36]: In the generic feedback system conﬁguration, plant
p(z)=f(z)/g(z) , compensatorc(z)=h(z)/k(z) . Do there exist polynomialsh(z)
andk(z)such that (strong stabilizability),k(z)η =0 andf(z)h(z)+g(z)k(z)η =0 for all
z∈
¯
U
n
? Procedure is based on cylindrical algebraic decomposition of semialgebraic
sets.
Example 2.11The algebraic variety of common zeros of the plant deﬁned by polyno-
mials
fandgwith zero setsV(f),V(g) is speciﬁed to be
V(f)∩V(g)=
∂η
−
1+
√
2
2
,
1−
√
2
2
∃
,
η
−1+
√
2
2
,
1+
√
2
2
∃∈
.
f
andgdo not have common zeros in
¯
U2
. Let, as in Guiver-Bose [6, p. 47],
s(z1,z2)=
η
z 1+
1+
√
2
2

z
2−
1+
√
2
2
∃
.
Then, by Rabinowitsch trick [28, 34], sincef(z1,z2),g(z 1,z2)and1−z 3s(z1,z2)do
not have any common zeros in
R[z1,z2,z3],usingGr¨obner bases (by Hilbert’s (Weak)
Nullstellensatz)
−
1
4
z
3f(z1,z2)−
1+
√
2
2
z
3g(z1,z2)+(1−z 3s(z1,z2)) = 1.
Settingz3=1/s(z 1,z2),
f+2(1+
√
2)g=−4s.
AsV(s)∩
¯
U
2
=Φ, therefore
h=
1
2(1 +
√
2)
is a stable stabilizer.
3 Multivariate polynomial equations and inequalities
Construction of solutions of sets of polynomial equations and inequalities by ele-
mentary decision algebra, with reference to the output feedback stabilization and re-
lated problems, was considered in [2]. There has been a surge of interest during the
last decade in the topics of semideﬁnite programming, semialgebraic sets (deﬁned
by multivariate polynomial equations, inequations and inequalities), robust optimiza-
tion and sum-of-squares representation of classes of nonnegative deﬁnite multivariate
polynomials and forms for applications in analysis and synthesis of control systems
[25, 20, 26].
Deﬁnition 3.1A basic semialgebraic set is a subset of
R
n
deﬁnedbyaﬁnite number
of polynomial equations and inequalities.

10 N. K. Bose
Example 3.2Two basic semialgebraic sets are given by
1.

(x
1,x2)∈R
2

x
2
1
3
2+
x
2 2
2
2≤1,x
2
1
−x2≤0
and,
2. given
f(x)∈R[x] , the set

xβ(x
1,...,xn)∈R
n

f(x)>0

.
Approaches for (2) include
1. Sum of squares (SOS) representation, when possible to do (SOSTOOLS,
SeDuMi), because positive multivariate polynomials or forms may not always
be representable as a sum of squares of forms.
2. Semideﬁnite programming to test feasibility of algebraic sets (C. N. Delzell [15],
P. A. Parrilo and B. Sturmfels in [20]).
3. Elementary decision algebra methods (A. Tarski, A. Seidenberg, G. E. Collins,
N. K. Bose, B. D. O. Anderson, E. I. Jury) [4, chapter 2], [26].
4. Global lower bound approach (N. Z. Shor [31]).
5. Grammatrixmethod(N.K.Bose,C.C.Li,M.D.Choi,T.Y.Lam,B.Reznikin
[25]).
3.1 SOS decomposition by Gram matrix method
[Bose-Li (1968), Choi-Lam-Reznick (1995), Parrilo (2000)] (see [25] for references).
Fact 3.3A multivariate real coefﬁcient polynomial
p(x)innreal variables
xβ(x 1,...,xn)
and of total degree2dis a SOS if and only if it is representable asp(x)=v
T
Qvwith
the

n+d
d

vector of monomials
v
T
=(1x 1x2... xnx1x2... ... x
d
n
)
and a symmetric PSD (positive semideﬁnite) matrix Q.
3.1.1 Nonnegativity of a polynomial
f(x)on an algebraic variety
Let
hi(x)=0 fori=1,...,l be constraints and letIdenote the polynomial ideal
I=⎛h 1(x),...,hl(x)⎜. Then, there exist polynomialsλi(x)∈R[x] such thatf(x)+
√
i
λi(x)h i(x)is a SOS inn-variate polynomial ringR[x]if and only iff(x)+I is a
SOS in the quotient ring
R[x]/I . Under these equivalent conditions,f(x)is nonnega-
tive on the real variety
{x∈R
n
|hi(x)=0,∀i} . [26, pp. 187–188].
Example 3.4This example is considered in [26, pp. 187–188], where an error in the
construction of matrix
Lbelow is corrected.

Two decades of Gr¨obner bases in multidimensional systems 11
Isf(x)=10−x
2
1
−x2nonnegative onx
2
1
+x
2
2
−1=0 ?I=⎛x
2
1
+x
2
2
−1⎜in
this case of one constraint equation,
h(x)=x
2
1
+x
2
2
−1is the Gr¨obner basis of the
corresponding ideal
10−x
2
1
−x2=(1x
1x2)
⎛
⎜
⎝
q
11q12q13
q12q22q23
q13q23q33
⎞
⎟
⎠
⎛
⎜
⎝
1
x
1
x2
⎞
⎟
⎠
=q
11+q22x
2
1
+q33x
2
2
+2q 12x1+2q 13x2+2q 23x1x2.
In the quotient ringR[x]/I ,
f(x)(modI)=(q 11+q22)+(q 33−q22)x
2
2
+2q 12x1+2q 13x2+2q 23x1x2
=9+x
2
2
−x2λv
T
Q1v,
wherevdenotes the vector in Fact 3.3 above corresponding to this example and
Q1=
⎛
⎜
⎝
90 −1/2
000
−1/20 1
⎞
⎟
⎠=L
T
L, L=
η
30 −1/6
00
√
35/6
∃
⇒10−x
2
1
−x2≡

3−
x
2
6

2
+
35
36
x
2
2
(modI)
⇒f(x
1,x2)is a SOS onR[x1,x2]/I.
Therefore, SOS on quotient ringR[x]/I is needed, whereI=⎛h i(x)⎜
l
i=1
is the ideal
generated by equality constraints. The computations can be effectively done in
R[x]/I
after computing the Gr¨obner basis for I[26].
3.2 Multidimensional nonlinear control systems,
performance optimization and Gr¨obner bases
Forsman and Glad [18] considered the following constrained optimization problem.
Given a multivariate polynomial
V(x),x
T
=(x 1x2... xn),andmmultivariate poly-
nomial equations
c1(x)=c 2(x)=...=c m(x)=0,
it is required to determine a maximum valueV(x0),wherex0belongs to the real
algebraic variety formed by the
mpolynomial equations above. Forsman also showed
that, without loss of generality, inequations can also be handled in the same framework
by using the Rabinowitsch trick (embracing auxiliary variables). A condition on a
solution
x=x 0to the optimization problem (when the Jacobian matrix ofcatxis of
full rank) is known to be
c1=c2=...=c m=0,∇V−λ
T
∇c=0,
wherec
T
=(c 1c2... cm)andλ
T
=(λ 1λ2... λm)is the vector of Lagrange
multipliers. Note that the preceding equation is a square system of
n+m scalar

12 N. K. Bose
equations in then+m unknownsx1,x2,...,xn,λ1,λ2,...,λmand hence, gener-
ically, there are aﬁnite number of solutions. This problem may also be solved by
the theory of Gr¨obner bases. The following problem, solved in [23, pp. 315–316]
by classical methods, is tackled with Gr¨obner basis theory. Note that in the example
below, there are inequalities in the constraints, which could be converted to equations
by adding slack variables. Alternatively, discrete-time nonlinear systems described
as constrained polynomial systems in a state-space model and subject to (semialge-
braic) inequality constraints in the joint input-state space can, indeed, be tackled using
Gr¨obner bases.
Example 3.5Consider the problem
minimize
2x
2
1
+2x 1x2+x
2
2
−10x 1−10x 2
subject tox
2
1
+x
2
2
≤5
3x
1+x2≤6.
Theﬁrst order (Karush-Kuhn-Tucker) necessary conditions for optimality in addition
to the constraints are
4x1+2x 2−10 + 2λ 1x1+3λ 2=0,
2x
1+2x 2−10 + 2λ 1x2+λ2=0,
λ
1,λ2≥0,
λ
1(x
2
1
+x
2
2
−5) = 0,
λ
2(3x1+x2−6) = 0,
whereλ1,λ2are Lagrange multipliers.
An inequality constraint
gi(x)α0 is said to be active at the feasible pointxif
gi(x)=0 and inactive ifgi(x)<0 . The equality constrainthi(x)=0 is always
considered active by convention. The active constraints at the feasible point restrict the
domain of feasibility in the neighborhood of
x,whiletheinactiveconstraintshaveno
effect on the neighborhood. It is for this reason, attention is restricted towards active
constraints while studying the properties of the optimum point.
Toﬁnd the solution we consider various combinations of active constraints and
check the sign of the corresponding Lagrange multipliers. We set one, two or no con-
straints to be active for this example. Assuming that theﬁrst constraint is active while
the second is inactive yields
4x1+2x 2−10 + 2λ 1x1=0,
2x
1+2x 2−10 + 2λ 1x2=0,
x
2
1
+x
2
2
−5=0.
Computing the Gr¨obner bases for this system of polynomial equations with respect to

Two decades of Gr¨obner bases in multidimensional systems 13
lexicographical ordering and orderingx1x2λ1gives
λ
4
1
+6λ
3
1
+λ
2
1
−4λ 1−4=0,
5x
2−3λ
3
1
−16λ
2
1
+6λ 1+3=0,
x
1+x2λ1+x2−5=0.
The solution now could be easily inferred to bex1=1,x2=2,λ1=1(the other
values of
λ1being either negative or complex are not considered). Note that the second
equality constraint is also satisﬁed at the solution point giving
3x1+x2=5.Thevalue
of the function at the solution point is
−20. Considering only the second equation
as active give a negative
λ2. At the minimum point, the Lagrange multiplier must be
positive; so this solution is discarded. Finally, when both constraints are considered to
be active, the Gr¨obner bases contains the polynomial 1 indicating, by Nullstellensatz,
that no solution exists.
When all inequality constraints are active use of Gr¨obner bases is less straightforward
in comparison to the case of equality constraints. Various combinations of inequal-
ity constraints are considered active and then the techniques developed for equality
constraints is applied to solve the problem. The sign of Lagrange multipliers must be
looked into. It is mandatory that at a regular point an optimum is attained only if all the
Lagrange multipliers are of same sign. If the Lagrange multipliers are all positive then
it is a minimum point and a maximum point if all the multipliers are negative. Besides
the sign of Lagrange multipliers, the other inactive constraints must also be satisﬁed
at the optimum point, i. e. it must not violate the inequalities. This process becomes a
somewhat computation intensive as the number of inequality constraints increase.
The following problem, solved in [23, pp. 301–302] by classical methods, is tackled
with Gr¨obner basis theory.
Example 3.6Consider the problem on constructing a cardboard box of maximum vol-
ume with given surface area.
maximize
V=x 1x2x3
subject toh=x 1x2+x2x3+x1x3−c/2=0,
wherex1,x2,x3are the variable dimensions of the box andcis a constant forﬁxed
area. Theﬁrst order necessary conditions gives us
f1=
∂V
∂x1
−λ
∂h
∂x1
=x2x3−λ(x 2+x3),
f
2=
∂V
∂x2
−λ
∂h
∂x2
=x1x3−λ(x 1+x3),
f
3=
∂V
∂x3
−λ
∂h
∂x3
=x1x2−λ(x 1+x2).
Consider the ideal generated by the preceding three polynomials along with the two

14 N. K. Bose
other polynomials
f4=x1x2x3−d,
f
5=x1x2+x2x3+x1x3−c/2,
where the real-valued parameterdis viewed to be an additional variable inf4,which
is introduced to directly obtain the optimal value. Computing the Gr¨obner basis of
the resulting ideal
I=⎛f 1,f2,f3,f4,f5⎜in lexicographic order with the rankingx1⎞
x
2⎞x3⎞λ⎞d one gets the system of polynomials
g1=cλ−3d,
g
2= 216d
2
−c
3
⇒d=
⊗
c
3
/6
3
,
g
3=x3−2λ,
g
4=x2−2λ,
g
5=x1−2λ.
Since the system of polynomial equations are in triangular form it could be easily
inferred that the maximum value of the function is
⊗
c
3
/6
3
and is attained at the point
x1=x2=x3=
⊗
c/6.
Robustness of polynomial nonlinear systems with structured uncertainty.Con-
sider the autonomous nonlinear system with structured uncertainty parameter vector
η
T
=(η 1η2... ηq), characterized by the state-space vector differential equation
˙x=f(x,η),
wherex
T
=(x 1x2... xn)and the componentsfioffare polynomials in both
the components of
xandη. For a given Lyapunov functionV(x)at a nominal value
of the parameter vector, the question regarding the subspace of parameter values that
guarantee stability using
V(x)can be answered by Gr¨obner basis theory [17].
Example 3.7Consider the system
˙x1=−x 1+αx
2
1
x2,
˙x
2=−x 2,
along with the Lyapunov function
V=3x
2
1
+4x 1x2+4x
2
2
.
Deﬁne
Ωv(η)={x∈R
n
|
˙
V(x, η)≤−V}
and
Bd={x∈R
n
|V(x)≤d}.

Two decades of Gr¨obner bases in multidimensional systems 15
The parameter vectorηhere is just the scalarα. The robust performance problem is
the following: Given
V,forwhichηdo we haveBd⊆Ωv(η)?
By tangency condition,
∇V+λ∇(
˙
V)=0 ,where
˙
Vis the derivative of the Lyapunov
function along the system trajectory. This derivative is calculated by the relation
˙
V(x)=
n
λ
j=1
∂V
∂xj
(x)
dx
j
dt
,
wherex=(x 1x2... xn)
T
is the state vector andn=2in this example. Here, the
parameter
disﬁxed andηis varied. Assume that the value ofdis 1 and letλdenote
the Lagrange multiplier. Consider the idealI
=⎛f 1,f2,f3,f4⎜,where
f1=V−d=3x
2
1
+4x 1x2+4x
2
2
−1,
f
2=
˙
V=4x
2
1
x
2
2
α−8x
2
2
+6x 2x
3
1
α−8x 2x1−6x
2
1
,
f
3=
∂V
∂x1
+λ
∂
˙
V
∂x1
=+8x
2
2
x1λα+18x 2x
2
1
λα−8x 2λ+4x 2−12x 1λ+6x 1,
f
4=
∂V
∂x2
+λ
∂
˙
V
∂x2
=+8x 2x
2
1
λα−16x 2λ+8x 2+6x
3
1
λα−8x 1λ+4x 1.
The Gr¨obner basis ofI =⎛f 1,f2,f3,f4⎜with respect to lexicographic order and rank-
ing
x1⎞x2⎞λ⎞α gives a triangular system of four polynomials, theﬁrst of which
is given below, for the sake of brevity:
g1(α)=−8192α
2
−1536α
3
+ 147α
4
−2α
5
.
Fromg1we can infer the interval ofαwithin which exponential stability is guaran-
teed. Let us call this value
αnew. The stability problem for it, i. e.
Ω(α)={x∈R
n
|
˙
V(x, η)≤0}
gives anotherαin a different interval. Let us call itαold. In general,αnew⊂αoldor
the connected region corresponding to exponential stability is a subset of the region
in which the system is stable. Remember this analysis is dependent on the choice of
the Lyapunov function. The obtained bounds are therefore not absolute in nature. It is
possible for a different Lyapunov function to give better bounds and hence assurance
of a more robust performance.
A concept central in real algebraic geometry (like Hilbert’s Nullstellensatz in complex
algebraic geometry) is stated next.
Theorem 3.8 (Stengle’s Positivstellensatz (1974))Given polynomials
{f1,...,fr},
{g1,...,gk}and{h1,...,hl}inx=(x 1,...,xn), the following are equivalent
1.
⎧
⎪
⎨
⎪
⎩
x∈R
n

f
i(x)≥0,i=1,2,...,r
g
i(x)η =0,i=1,2,...,k
h
i(x)=0,i=1,2,...,l
⎫
⎪
⎬
⎪
⎭
is the empty set.

16 N. K. Bose
2. There exist polynomialsf∈(cone generated by{f1,...,fr}),g∈(cone gener-
ated by
{g1,...,gk}) andh∈(cone generated by{h1,...,hl}) such that
f+g
2
+h=0.
Comments
1. The multiplicative monoid
Mgenerated by{gi}
k
i=1
is the set of allﬁnite products
of
gi’s including 1, e. g.
M(g 1,g2)=

g
k1
1
,g
k2
2

k
1,k2∈Z+∪{0}

.
2. The cone generated by{fi}
r
i=1
is
P(f1,...,fr)=
∂
s 0+
l
λ
i=1
sibi

l∈Z
+,si∈Σn,bi∈M(f 1,...,fr)
φ
,
whereΣndenotes the set of SOS polynomials innvariables. Note thatf
2
i
si∈Σn
as well.
3. Positivstellensatz gives a characterization of theinfeasibilityof polynomial equa-
tions and inequalities over the reals.
The Positivstellensatz (P-satz) is useful because it provides a characterization of the
infeasibility (refutation) of a system of polynomial equations and inequalities in con-
junction with polynomial SOS and is beginning to be used in control theory [20].
4Gr¨obner bases may not always produce the result
sought
LetR=K[z 1,z2,z3]. The next example illustrates a fact in algebraic geometry that
the maximal set of linearly independent elements of the Gr¨obner basis for a module
generated by the columns of a multivariate polynomial matrix
Cusing any lexico-
graphical ordering may not form a minimal generating set of the column space of
C.
Its consequence in systems theory is pointed out.
Example 4.1 (Chalie Charoenlarpnopparut (2000))It is known that
C=
η
z
1z
2
2
z3
z
2
1
z
2
3
+z3

0−z
2
1
z
2
2
−1
−z
3−z
3
1
z3−z1
∃
=
ˆ
G(A
1|B1)
(note that the columns of
ˆ
Ggenerate the same module as the columns ofC) has zero
coprime reduced minors and has a GCLF of the submatrices
A1,B1.The2×2minors
are
m1=−z 1z
2
2
z
2
3
,m2=−z
2
1
z
2
2
z3−z3,m3=z
2
1
z
2
3
+z3.

Two decades of Gr¨obner bases in multidimensional systems 17
So, the reduced minors, obtained after extracting the gcdd=z 3, have no common
zeros. To wit, a factorization is
ˆ
G=
η
−z
2
1
z
2
2
−1z 1z
2
2
z3
−z1 z3
∃
,A
1=
η
z
3
1
z
2
2
z
2
3
z
4
1
z
2
2
z3+z
2
1
z3+1
∃
,
B
1=
η
−z
1z
2
2
z3−z
4
1
z
2
2
z3+1
−z
2
1
z
2
2
−1−z
3
1
(z
2
1
z
2
2
+1)
∃
.
Using degree reverse lexicographical orderingz1⎞z2⎞z3, the matrixGwhose
columns are the reduced Gr¨obner basis vectors of the module generated by the columns
of
Care (using SINGULAR)
G=
η
0z
3z
2
1
z
2
2
+1
z
30 z 1
∃
.
The columns of
ˆ
Ggenerate the same module as the columns ofC. However,
ˆ
Gcannot
be computed from
Gby applying the algorithmic theory of Gr¨obner bases because it
can be shown that no proper linearly independent subset of the columns of
Gcan gen-
erate the column space of
C. Thus, the maximal set of linearly independent elements
of the reduced Gr¨obner basis for module
Mmay only generate a proper submodule of
M. Applications of Gr¨obner basis of modules over polynomial rings in wavelets and
ﬁlter bank design with examples has been considered in [12] and [22].
Can a factorization be found by another algorithm? The answer to this question was
provided in the afﬁrmative by Wang and Kwong recently [33]. Let
sibe theith row of

C
−z
3I3

,sinced=z 3. They use CoCoA under the default module term ordering (Deg
Revlex and ToPos) to get three generators of a syzygy module of
si(i=1,...,5) :
f1=

0z
3z
2
1
z
2
3
+z3−z3−z
3
1
z3−z1

,
f
2=

z
3−z1z
2
2
z3−z
3
1
z
2
2
z
2
3
z1z
2
2
z3z
4
1
z
2
2
z3−1

,
f
3=

z
1−z
2
1
z
2
2
−1−z
4
1
z
2
2
z3−z
2
1
z3−1z
2
1
z
2
2
+1z
5
1
z
2
2
+z
3
1

.
LetMbe the module generated byf1,f2,f3. Using a CoCoA command “Minimalized
(
M)”, theyﬁnd that Mhasf2andf3as generators(C∈R
l×m
[z1,z2,z3],l <m) .
Factorization:
C=
η
z
2
1
z
2
2
+1z 1z
2
2
z3
z1 z3
∃
·
η
−z
3
1
z
2
2
z
2
3
z1z
2
2
z3 z
4
1
z
2
2
z3−1
z
4
1
z
2
2
z3+z
2
1
z3+1−z
2
1
z
2
2
−1−z
5
1
z
2
2
−z
3
1
∃
.
Limitation:Does not work if the system of generators of the syzygy module does
not have
∃(2 in this case) elements. Otherwise, more research needed in constructive
(algorithmic algebra)
n-variate factorization problems,n>2.

18 N. K. Bose
5 Bihermitian forms and SOS
Theorem 5.1A bihermitian form H(x, y) is representable as
H(x, y)=
m
λ
u=1
m
λ
v=1
(x
∗
A
uv
x)¯yuyv, (5.1)
where the overbar and star superscript denote, respectively, complex conjugate and
complex conjugate transpose, and
x
∗
=(¯x 1,¯x2,...,¯x n)andA
uv
=((a
uv
ij
))∈C
n×n
are complex matrices such that(A
uv
)
∗
=A
vu
. Furthermore, ifAijrepresents a ma-
trix of order
m×m witha
uv
ij
as its element in the(u, v)th position,H(x, y) can be
equivalently expressed as
H(x, y)=
n
λ
i=1
n
λ
j=1
(y
∗
Aijy)¯xixj. (5.2)
With the above notation, a bihermitian form
H(x, y) is a Hermitian form inxfor eachy
and a Hermitian form inyfor eachx. A bihermitian formH(x, y) is called nonnegative
deﬁnite Hermitian (nndH) if
H(x, y) is nonnegative for each pair of values forxand
y. The fact that every bihermitian formHcan be represented as in (5.1) and the dual
representation (5.2) has been proved elsewhere by the author.
Consider the linear map
L=φ:S∈M n:=C
n×n
−→L(S)∈C
m×m
acting on the space of nonnegative deﬁnite Hermitian (nndH) matrices. For such a
linear operator
L:SnndH−→L(S) nndH when do there exist matricesVk∈C
n×m
so that∀SnndH, there exists aﬁnite sum of congruences representation for L(S)[27]
L(S)=
p
λ
k=1
V
∗
k
SVk.
That the above does not hold over theﬁeld of complex numbers follows from the
counterexample given next.
Counterexample.Consider
L(S)=( trS)I−S so thatL:S nndH−→L(S) is
nndH. Hypothesize,
L(S)=
√
p
k=1
V
∗
k
SVk. ChooseS=xx
∗
,wherexis a column-
vector representation of a complex
m-tuple such thatx
∗
x=1, but could be arbitrary
otherwise. Then,
L(xx
∗
)=I−xx
∗
and
xx
∗
L(xx
∗
)=
λ
k
xx
∗
V
∗
k
xx
∗
Vk=0,
tr
λ
k
xx
∗
V
∗
k
xx
∗
Vk=
λ
k
x
∗
V
∗
k
xx
∗
Vkx=0
⇒x
∗
Vkx=0,∀k Contradiction.

Two decades of Gr¨obner bases in multidimensional systems 19
The feasibility or infeasibility of sum-of-squares representation of distinguished
classes of forms can be linked to the study of linear transformations which map square
matrices into square matrices and preserve hermitian symmetry and positivity.
For compactness of notation, we denote
C
n×n
byMn, the algebra ofn×ncomplex
matrices.
Ejk∈M nis then×nmatrix with 1 at(j, k)-component and zeros elsewhere.
Mn(Mm)=M m⊗Mnis the collection of alln×nblock matrices withm×m matrices
as entries. Clearly,
Mn(Mm)belongs toC
mn×mn
.
Deﬁnition 5.2
φ:M n→M mis positive semideﬁnite (called, positive, for the sake
of brevity in the present context) if
φmaps the set of positive semideﬁnite matrices
into itself (similarly
φ:M n→M p).φisp-positive deﬁnite if φ⊗I pis positive on
Mm⊗M p,whereφ⊗I p:Mp(Mn)→M p(Mm)is given by
φ⊗I p((Ajk))1≤j,k≤p =φ((A jk))1≤j,k≤p .
φ
is completely positive ifφisp-positive for everyp,i.e.φ⊗I pis positive for all
integers
p.
Example 5.3For each
n×m matrixVthe mapL=φ:M n→M mwithA∈M n→
V
∗
AV∈M mis completely positive [32].
The results below are proved in [13].
Fact 5.4Let
φ:M n→M m.Thenφis completely positive iffφis of the form
√
i
V
∗
i
AVifor allA∈M n,whereViaren×m matrices.
An equivalent result is:
Let
φ:M n→M m.Thenφis completely positive if(φ(E jk))1≤j,k≤n is positive.
Comment.Each linear map
φ:M n→M nis determined by its values onEjk∈
M
n,1≤j, k≤n . Henceφis completely determined by the single element
(φ(E jk))1≤j,k≤n ∈M n(Mm).
Completely positive maps and not positive maps provide the answer to SOS represen-
tation.
6 Conclusions
Several problems in multidimensional systems theory require tools from complex al-
gebraic geometry (zero sets of multivariate polynomials in the complex polydomain,
stabilization etc) as well as real algebraic geometry which is the study of real number
solutions to algebraic equations with real number coefﬁcients. Real algebraic geometry
usage in multidimensional systems occurs when considering, for example, either a set

20 N. K. Bose
of multivariate polynomial equations and inequalities in robust stability assessment of
uncertain linear and nonlinear control systems or optimization of a multivariate poly-
nomial cost function subject to equality and nonequality constraints. Such problems
may also be solved by applying the Karush-Kuhn-Tucker conditions (a generalization
of the method of Lagrange multipliers) in nonlinear programming or the method of
cylindrical algebraic decomposition in elementary decision algebra [4]. The theory of
Gr¨obner bases provide a viable alternative and is being increasingly explored for suit-
ability in solving an increasing number of problems in multidimensional systems and
signal processing. This paper provides a snapshot of the progress made to date.
A resurgence of interest in the implementation of algorithmic algebra algorithms
based on elementary decision algebra took place after the emergence of software like
QEPCAD (Quantiﬁer Elimination by Partial Cylindrical Algebraic Decomposition).
The problems tackled include the output stabilization problem, the simultaneous sta-
bilization problem, the robust multiobjective problem, for which no general solutions
exist. However, software packages like QEPCAD were found to be suitable only for
tackling problems of modest complexity. Almost the same appears to be true, in gen-
eral, for obtaining solutions to problems using software for generating Gr¨obner bases
but the possibility for use over a variety of different coefﬁcient domains, and for differ-
ent variable and term orderings offers considerableﬂexibility. The time and memory
required to calculate a Gr¨obner basis depend very much on the variable ordering, term
ordering, and on which variables are regarded as constants.
Though the sum of squares decomposition is a sufﬁcient but not necessary condi-
tion for multivariate polynomial nonnegativity, its bijective correspondence with com-
pletely positive linear maps that map square matrices to square matrices, preserving
hermitian symmetry and positivity uncover the additional constraint on positive linear
maps for such decompositions to materialize. A representation theorem for bihermitian
forms is stated but not proved here. The proof will appear elsewhere and is currently
available from the author. The linear maps associated with the two matrices in the bi-
quadratic (bihermitian) form representation are required to be completely positive for
the form to be representable as a sum of squares of bilinear forms.
Ongoing research efforts that are promising include the work on parametrized com-
pactly supported wavelets with several vanishing moments [29], where a single param-
eter and lower orderﬁlters were considered because of the complexity of the expres-
sions in the Gr¨obner basis. That was the case also in other applications like [8] and
[9]. Nevertheless, the theory of Gr¨obner basis is effective in the study of parametrized
systems in both signal processing and control. In fact the two parameter counterpart of
the results in [29] is under study and the results will be reported later.
Acknowledgements.The author thanks Kamlesh Nahata for working out the three
examples on constrained optimization and performance analysis of nonlinear systems
using Gr¨obner bases. Thanks are also due to Nilesh Ahuja for his ready help with the
computer processing of certain portions of this documentation. My special thanks go
to the reviewer for his very careful reading of the paper and his valuable comments for
improving the clarity and completeness of the presentation. Also, thanks are due to Dr.

Two decades of Gr¨obner bases in multidimensional systems 21
Zhiping Lin and Kay Dimler for pointing out some additional typographical errors in
the revised version.
Bibliography
[1] W. W. Adams and P. Loustanou,An Introduction to Gr¨obner Bases, vol. 3, American Mathe-
matical Society, Providence, R.I., 1994.
[2] B. D. O. Anderson, N. K. Bose, and E. I. Jury,Output feedback stabilization and related
problems-solutions via decision methods, IEEE Transactions on Automatic Control 20 (1975),
pp. 53–56.
[3] D. Asimov,There’s no space like home, The Sciences 35 (1995), pp. 20–25.
[4] N.K.Bose,Applied Multidimensional Systems Theory, Van Nostrand Reinhold Co., N.Y.,
1982.
[5] N. K. Bose (ed.),Multidimensional Systems Theory: Progress, Directions and Open Problems
in Multidimensional Systems, D. Reidel Publishing Company, Dordrecht, Holland, 1985.
[6] N. K. Bose, B. Buchberger, and J. P. Guiver,Multidimensional Systems Theory and Applica-
tions, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2003.
[7] N. K. Bose and C. Charoenlarpnopparut,Multivariate matrix factorization: new results,Math-
ematical Theory of Networks and Systems, Proceedings of the MTNS-98 Symposium (Padova,
Italy) (A. Beghi, L. Finesso, and G. Picci, eds.), Il Poligrafo, 1998, pp. 97–100.
[8]
,Minimax controller design using rate feedback, Circuits, Systems and Signal Process-
ing 18 (1999), pp. 17–25.
[9] ,Minimax controller using rate feedback: latest results, Proceedings of the Interna-
tional Federation Automatic Control G-2e-20-4 (1999), pp. 525–530.
[10] B. Buchberger,An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-
dimensional Polynomial Ideal (German), Ph.D. thesis, Univ. Of Innsbruck (Austria), Math.
Inst., 1965.
[11] B. Buchberger and F. Winkler (eds.),Gr¨obner Bases and Applications, London Mathemat-
ical Society Lecture Notes Series, vol. 251, Cambridge, Cambridge University Press, 1998,
Proceedings of the International Conference “33 Years of Gr¨obner Bases”.
[12] C. Charoenlarpnopparut and N. K. Bose,Multidimensional FIRﬁlter bank design using
Gr¨obner Bases, IEEE Transactions on Circuits and Systems II 46 (1999), pp. 1475–1486.
[13] M. D. Choi,Completely positive linear maps on complex matrices, Linear Algebra and its
Applications 10 (1975), pp. 285–290.
[14] D. A. Cox, J. Little, and D. O’Shea,Using Algebraic Geometry, Springer, New York, 1998.
[15] C. N. Delzell,A constructive, continuous solution to Hilbert’s 17th problem, and other results
in semi-algebraic geometry, Ph.D. thesis, Stanford University, Math. Dept., 1980.
[16] S. V. Dushin and S. V. Chmutov,Gaydar’s formula for the greatest common divisor of several
polynomials, Communications of the Moscow Mathematical Society (1993), pp. 171–172.
[17] K. Forsman,Optimization, Stability and Cylindrical Decomposition, Tech. report, Link¨oping
University, Link¨oping, Sweden, 1993.
[18] K. Forsman and S. Glad,Constructive algebraic geometry in nonlinear control, Proceedings of
the 29th IEEE Conference on Decision and Control (Honolulu), vol. 5, 1990, pp. 2825–2827.

22 N. K. Bose
[19] J. P. Guiver and N. K. Bose,Polynomial matrix primitive factorization over arbitrary coefﬁcient
ﬁeld and related results, IEEE Transactions on Circuits and Systems 29 (1982), pp. 649–657.
[20] D. Henrion and A. Garulli (eds.),Positive Polynomials in Control, Springer-Verlag Berlin Hei-
delberg, 2005.
[21] T. Y. Lam,Serre’s Problem on Projective Modules, Springer-Verlag Berlin Heidelberg, 2006.
[22] Z. Lin, L. Xu, and Q. Wu,Applications of Gr¨obner bases to signal and image processing: a
survey, Linear Algebra and its Applications 391 (2004), pp. 169–202.
[23] D. G. Luenberger,Linear and Nonlinear Programming, 2nd. ed., Addison-Wesley Publishing
Company, Reading, MA, 1984.
[24] U. Oberst,Multidimensional constant linear systems, Acta Applicandae Mathematicae (1990),
pp. 1–175.
[25] P. A. Parrilo,Semideﬁnite programming relaxations for semialgebraic problems, Mathematical
Programming Ser. B 96 (2003), pp. 293–320.
[26] ,Exploiting Algebraic Structure in Sum of Squares Programs, Positive polynomials in
control (D. Henrion and A. Garulli, eds.), Springer, 2005, pp. 181–194.
[27] J. de Pillis,Linear transformations which preserve hermitian and positive semideﬁnite trans-
formations, Paciﬁc Journal of Mathematics (1967), pp. 129–137.
[28] J. L. Rabinowitsch,Zum Hilbertschen Nullstellensatz, Mathematische Annalen 102 (1929),
pp. 520–521.
[29] G. Regensburger and O. Scherzer,Symbolic Computation for Moments and Filter Coeffcients
of Scaling Functions, Annals of Combinatorics 9 (2005), pp. 223–243.
[30] H. H. Rosenbrock,State-Space and Multivariable Theory, John Wiley & Sons Inc., New York,
NY, 1970.
[31] N. Z. Shor,Class of global minimum bounds of polynomial functions, Cybernetics 23 (1987),
pp. 731–734.
[32] W. Stinespring,Positive functions onC
∗
-algebras, Proceedings of the American Mathematical
Society 6 (1955), pp. 211–216.
[33] M. Wang and C. P. Kwong,On multivariate polynomial matrix factorization problem,Mathe-
matics of Control, Signals and Systems 17 (2005), pp. 297–311.
[34] L. Xu, O. Saito, and K. Abe,Output feedback stabilizability and stabilization algorithms for
2-D systems, Multidimensional Systems and Signal Processing 5 (1994), pp. 41–60.
[35] J. Q. Ying,On the strong stabilizability of MIMOn-dimensional linear systems, SIAM Journal
on Control and Optimization 38 (2000), pp. 313–335.
[36] J. Q. Ying, L. Xu, and Z. Lin,A computational method for determining strong stabilizability of
n-D systems, Journal of Symbolic Computation 27 (1999), pp. 479–499.
[37] E. Zerz,Topics in Multidimensional Linear Systems Theory, Lecture Notes in Control and
Information Sciences 256, Springer-Verlag London Limited, London, Great Britain, 2000.
Author information
N. K. Bose, Department of Electrical Engineering,
Pennsylvania State University,
University Park, PA 16203, USA.
Email:[email protected]

Radon Series Comp. Appl. Math3, 23–106 cde Gruyter 2007
Applications of the Quillen-Suslin theorem to
multidimensional systems theory
Anna Fabia´nska and Alban Quadrat
Key words.Constructive versions of the Quillen-Suslin theorem, Lin-Bose conjectures, multidi-
mensional linear systems,ﬂat systems, (weakly) doubly coprime factorizations of rational transfer
matrices, decomposition of linear functional systems, symbolic computation.
AMS classiﬁcation.13C10, 13P99, 93B40, 47A65, 93B40, 93C23
1 Introduction........................................ 23
2 A module-theoretic approach to systems theory..................... 26
3 The Quillen-Suslin theorem................................ 37
4 Flat multidimensional linear systems........................... 54
5 Pommaret’s theorem of Lin-Bose’s conjectures..................... 62
6 Computation of (weakly) doubly coprime factorizations of rational transfer matrices72
7 Decomposition of multidimensional linear systems................... 78
8 Conclusion......................................... 84
9 Appendix: The packageQ
UILLENSUSLIN........................ 85
Bibliography..........................................103
1 Introduction
In 1784, Monge studied the integration of certainunderdeterminednonlinear systems
of ordinary differential equations, namely, systems containing more unknown functions
than differentially independent equations ([29]). He showed how the solutions of these
systems could be parametrized by means of a certain number of arbitrary functions
of the independent variable. This problem was calledthe Monge problemand it was
studied by famous mathematicians such as Hadamard, Hilbert, Cartan and Goursat.
In particular, motivated by problems coming from linear elasticity theory, Hadamard
considered the case of linear ordinary differential equations and Goursat investigated
underdetermined systems of partial differential equations. We refer the reader to [29]
for a historical account on the Monge problem and for the main references.
Within thealgebraic analysisapproach ([2, 21, 28, 33]), the Monge problem was
recently studied for underdetermined systems of linear partial differential equations
in [21, 33, 42, 43, 44] and for linear functional systems in [5, 6] (e. g., differential
time-delay systems, discrete systems). Depending on the algebraic properties of a

24 A. Fabia´nska and A. Quadrat
certain moduleMdeﬁned over a ringDof functional operators and intrinsically as-
sociated with the linear functional system, we can prove or disprove the existence
of different kinds of parametrizations of the system (i. e., minimal parametrizations,
non-minimal parametrizations, chains of successive parametrizations). Constructive
algorithms for checking these algebraic properties (i. e., torsion, existence of torsion
elements, torsion-free, reﬂexive, projective, stably free, free) and computing the dif-
ferent parametrizations were recently developed in [5, 42, 43, 44], implemented in the
package O
REMODULES([5, 6]) and illustrated on numerous examples coming from
mathematical physics and control theory ([5, 6]). Finally, we proved in [5, 42, 43, 44]
how the Monge problem gave answers for the search ofpotentialsin mathematical
physics andimage representationsin control theory ([39, 40, 62, 63]).
The last results show that the Monge problem is constructively solved for certain
classes of linear functional systems up to a last but important point: we can check
whether or not a linear functional system admits injective parametrizations but we are
generally not able to compute one even if some heuristic methods were presented in
[5, 42, 43]. Indeed, the existence of injective parametrizations for a linear functional
system was proved to be equivalent to the freeness of the corresponding module
M.In
the case of a linear functional system with constant coefﬁcients, the corresponding ring
Dof functional operators is a commutative polynomial ring over aﬁeld kof constants.
Using the famous Quillen-Suslin theorem ([52, 55]), also known as Serre’s conjecture
([23, 24]), we then know that free
D-modules are projective ones. Using Gr¨obner or
Janet bases ([5, 10, 42]), we can check whether or not a module over a commutative
polynomial ring is projective. See [3, 10, 20] and the references therein for introduc-
tions to Janet and Gr¨obner bases. Hence, we can constructively prove the existence of
an injective parametrization for a linear functional system. However, we need to use a
constructive version of the Quillen-Suslin theorem ([15, 19, 22, 26, 27, 35, 58, 59]) to
get injective parametrizations of the corresponding system.
The main purpose of this paper is to recall a general algorithm for computing bases
of a free module over a commutative polynomial ring, give four new applications of
the Quillen-Suslin theorem to mathematical systems theory and demonstrate the imple-
mentation of the Q
UILLENSUSLINpackage ([12]) developed in the computer algebra
system MAPLE. To our knowledge, the Q
UILLENSUSLINpackage is theﬁrst pack-
age available which performs bases computations of free modules over a commutative
polynomial ring with rational and integer coefﬁcients and is dedicated to different ap-
plications coming from the mathematical systems theory.
More precisely, the plan of the paper is the following one. In the second section, we
recall how the structural properties of linear functional systems can be constructively
studied within the algebraic analysis approach as well as different results on the Monge
problem. A constructive version of the Quillen-Suslin theorem, which is the main tool
we use in the paper, is presented in the third section and the implementation is illus-
trated on many examples in the appendix of the paper. We also describe some heuristic
methods that highly simplify the computation of a basis of a free module over polyno-
mial rings in certain special cases. The constructive version of the Quillen-Suslin the-
orem and, in particular the patching procedure, gives us the opportunity to make a new
observation concerning linear functional systems which admit injective parametriza-
tions also calledﬂat multidimensional systemsin mathematical systems theory. In the

Applications of the Quillen-Suslin theorem 25
fourth section, we prove that aﬂat multidimensional system is algebraically equivalent
to a 1-Dﬂat linear system obtained by setting all but one functional operator to zero in
the system matrix. This result gives an answer to a natural question onﬂat multidimen-
sional systems. In particular, we prove that everyﬂat differential time-delay system is
algebraically equivalent to the differential system without delays, namely, the system
obtained by setting to zero all the time-delay amplitudes. In theﬁfth section, we con-
sider a generalization of Serre’s conjecture. We recall that Serre’s conjecture, also
known as the Quillen-Suslin theorem, can be expressed in the language of matrices
as follows: every matrix
Rover a commutative polynomial ringD=k[x 1,...,xn]
whose maximal minors generateD(unimodular matrix) can be completed to a square
invertible matrix over
D(i. e., its determinant is a non-zero element of theﬁeld k). The
generalization, stated by Lin and Bose in [25] andﬁrst proved by Pommaret in [41]
by means of algebraic analysis, can be formulated as the possibility of completing a
matrix
Rwhose maximal minors divided by their greatest common divisordgener-
ate
Dto a square polynomial matrix whose determinant equalsd. Serre’s conjecture
is then the special case where
d=1. Using the Quillen-Suslin theorem, we give a
constructive algorithm for computing such a completion. Using the possibility of com-
puting bases of a free module in our implementation Q
UILLENSUSLIN, this algorithm
has been implemented in this package. In the sixth section, we study the existence of
(weakly) left-/right-coprime factorizations of rational transfer matrices using recent re-
sults developed in [48]. We give algorithms for computing such factorizations using the
constructive versions of the Quillen-Suslin theorem. These results constructively solve
open questions in the literature of multidimensional linear systems (see [60, 61] and
the references therein). Finally, we show that the constructive Quillen-Suslin theorem
also plays an important role in the decomposition problem of linear functional systems
studied in the literature of symbolic computation. See [8] and the references therein
for more details. The main idea is to transform the system matrix into an equivalent
block-triangular or a block-diagonal form ([8, 9]).
The different algorithms presented in the paper have been implemented in the pack-
age Q
UILLENSUSLINbased on the library INVOLUTIVE([3]) (an OREMODULES([6])
version will soon be available). The appendix illustrates the main procedures of the
Q
UILLENSUSLINpackage on different examples taken from the literature ([19, 22, 37,
58]). The package Q
UILLENSUSLINalso contains a completion algorithm for uni-
modular matrices over Laurent polynomial rings described in [34, 37]. See also [1]
for a recent algorithm. In [37], Park explains the importance and the meaning of the
completion problem of unimodular matrices over Laurent polynomial rings to signal
processing and gives an algorithm for translating this problem into a polynomial case.
Park’s results can also be used for computingﬂat outputs of
δ-ﬂatmultidimensional
linear systems ([30, 31]). See [5] for another constructive algorithm and [6] for illus-
trations on different explicit examples.
Notation.In what follows, we shall denote by
kaﬁeld,D=k[x 1,...,xn]a commu-
tative polynomial ring with coefﬁcients in
k,D
1×p
theD-module formed by the row
vectors of length
pwith entries inDandD
q×p
the set ofq×p-matrices with entries in
D.Fwill always denote aD-module. We denote byR
T
the transpose of the matrixR
and byIpthep×pidentity matrix. Finally, the symbolδmeans “by deﬁnition”.

26 A. Fabia´nska and A. Quadrat
2 A module-theoretic approach to systems theory
LetD=k[x 1,...,xn]be a commutative polynomial ring over aﬁeld kandR∈D
q×p
.
We recall that a matrix
Rissaidtohavefull row rankif theﬁrst syzygy moduleof the
D-moduleD
1×q
Rformed by theD-linear combinations of the rows ofR, namely,
kerD(.R)δ{λ∈D
1×p
|λR=0},
is reduced to 0. In other words,λR=0 impliesλ=0, i. e., the rows ofRare
D-linearly independent.
The following deﬁnitions ofprimenessare classical in systems theory.
Deﬁnition 2.1[32, 59, 63] Let
D=R[x 1,...,xn]be a commutative polynomial ring,
R∈D
q×p
a full row rank matrix,Jthe ideal generated by theq×qminors ofRand
V(J)the algebraic variety deﬁned by
V(J)={ξ∈C
n
|P(ξ)=0,∀P∈J}.
1.Ris calledminor left-primeif dimCV(J)≤n−2, i. e., the greatest common
divisor of the
q×qminors ofRis 1.
2.
Ris calledweakly zero left-primeif dimCV(J)≤0, i. e., theq×qminors ofR
may only vanish simultaneously in aﬁnite number of points of C
n
.
3.
Ris calledzero left-primeif dimCV(J)=−1, i. e., theq×qminors ofRdo not
vanish simultaneously in
C
n
.
The previous classiﬁcation plays an important role in multidimensional systems theory.
See [32, 59, 63] and the references therein for more details.
The purpose of this section is twofold. Weﬁrst recall how we can generalize the
previous classiﬁcation for general multidimensional linear systems, i. e., systems which
are not necessarily deﬁned by full row rank matrices. We also explain the duality
existing between thebehavioural approachto multidimensional systems ([32, 39, 62,
63]) and themodule-theoretic one([42, 43, 44]). See also [62] for a nice introduction.
In what follows,
Dwill denote a commutative polynomial ring with coefﬁcients
in aﬁeld
k. In particular, we shall be interested in commutative polynomial rings
of functional operators such as partial differential operators, differential time-delay
operators or shift operators. Let us consider a matrix
R∈D
q×p
and aD-moduleF,
namely
∀f1,f2∈F,∀a 1,a2∈D:a 1f1+a2f2∈F.
If we deﬁne the following D-morphism, namely,D-linear map,
.R:D
1×q
.R
−→D
1×p
,
λ=(λ
1... λq)π −→(.R)(λ)=λR,

Applications of the Quillen-Suslin theorem 27
whereD
1×p
denotes theD-module of row vectors of lengthpwith entries inD,then
the cokernel of the
D-morphism.Ris deﬁned by
M=D
1×p
/(D
1×q
R).
TheD-moduleMis said to be presented byRor simplyﬁnitely presented([5, 53]).
Moreover, we can also deﬁne thesystemorbehaviouras follows:
kerF(R.)δ{η∈F
p
|Rη=0}.
As it was noticed by Malgrange in [28], theD-moduleMand the systemkerF(R.)are
closely related. As this relation will play an important role in what follows, we shall
explain it in details. In order to do that, let usﬁrst introduce a few classical deﬁnitions
of homological algebra. We refer the reader to [53] for more details.
Deﬁnition 2.21. A sequence
(Mi,di:Mi−→M i−1)i∈ZofD-modulesMiand
D-morphismsdi:Mi−→M i−1isa complexif we have
∀i∈Z,imd i⊆kerd i−1.
We denote the previous complex by
...
di+2
−−−→M i+1
d
i+1
−−−→M i
d
i
−→M i−1
d
i−1
−−−→... . (2.1)
2. Thedefect of exactness of the complex (2.1) at
Miis deﬁned by
H(M i)=kerd i/imd i+1.
3. The complex (2.1) is said to beexact at Miif we have
H(M i)=0 ⇐⇒ kerd i=imd i+1.
4. The complex (2.1) isexactif
∀i∈Z,kerd i=imd i+1.
5. The complex (2.1) is asplit exact sequenceif (2.1) is exact and if there exist
D-morphismssi:Mi−1−→M isatisfying the following conditions:
∀i∈Z,
δ
s
i+1◦si=0,
s
i◦di+di+1◦si+1=idMi
.
6. Aﬁnite free resolutionof a D-moduleMis an exact sequence of the form
0−→D
1×p m
.Rm
−−−→...
.R2
−−→D
1×p 1
.R1
−−→D
1×p 0
π
−→M−→0, (2.2)
where
pi∈Z+={0,1,2,...} ,Ri∈D
pi×pi−1
,andtheD-morphism.Riis
deﬁned by
.Ri:D
1×p i
−→D
1×p i−1
λ⎝ −→(.R i)(λ)=λR i.

28 A. Fabia´nska and A. Quadrat
The next classical result of homological algebra will play a crucial role in what follows.
Theorem 2.3[53]Let
Fbe aD-module,MaD-module and (2.2) aﬁnite free reso-
lution of
M. Then, the defects of exactness of the following complex
...
R3.
←−−F
p2
R2.
←−−F
p1
R1.
←−−F
p0
←−0, (2.3)
where the
D-morphismRi.:F
pi−1
−→ F
pi
is deﬁned by
∀η∈F
pi−1
,(R i.)(η)=R iη,
only depend on theD-modulesMandF. Up to an isomorphism, we denote these
defects of exactness by
δ
ext
0
D
(M,F)
∼
=ker F(R1.),
ext
i
D
(M,F)
∼
=ker F(Ri+1.)/(R iF
pi
),i≥1.
Finally, we haveext
0
D
(M,F)=hom D(M,F), wherehomD(M,F) denotes theD-
module of
D-morphisms fromMtoF.
We refer the reader to Example 5.3 for explicit computations of
ext
i
D
(N,D) ,i≥0.
Coming back to the
D-moduleM, we have the following beginning of aﬁnite free
resolution of
M:
D
1×q
.R
−→D
1×p
π
−→M−→0,
λ⎝ −→λR
(2.4)
where
πdenotes theD-morphism which sends elements ofD
1×p
to their residue
classes in
M. If we “apply the left-exact contravariant functor”homD(·,F) to (2.4)
(see [53] for more details), by Theorem 2.3, we obtain the following exact sequence:
F
q
R.
←−F
p
←−hom D(M,F)←−0.
Rη←−δη
This implies the following important isomorphism ([28]):
kerF(R.)={η∈F
p
|Rη=0}
∼
=hom D(M,F). (2.5)
For more details, see [5, 28, 32, 44, 62] and the references therein. In particular, (2.5)
gives an intrinsic characterization of the
F-solutions of the systemkerF(R.). It only
depends on two mathematical objects:
1. Theﬁnitely presented
D-moduleMwhich algebraically represents the linear
functional system.
2. The
D-moduleFwhich represents the “functional space” where we seek the
solutions of the system.

Applications of the Quillen-Suslin theorem 29
IfDis now a ring of functional operators (e. g., differential operators, time-delay
operators, difference operators), then the issue of understanding which
Fis suitable
for a particular linear system has long been studied in functional analysis and is still
nowadays a very active subject of research. It does not seem that constructive algebra
and symbolic computation can propose new methods to handle this functional analysis
problem. However, they are very useful for classifying
homD(M,F) by means of the
algebraic properties of the
D-moduleM. Indeed, a large classiﬁcation of the properties
of modules is developed in module theory and homological algebra. See [53] for more
information. Let us recall a few of them.
Deﬁnition 2.4[53] Let
Dbe a commutative polynomial ring with coefﬁcients in a
ﬁeld
kandMaﬁnitely presentedD-module. Then, we have
1.
Missaidtobefreeif it is isomorphic to D
1×r
for a non-negative integerr,i.e.,
M
∼
=D
1×r
,r∈Z +={0,1,2...}.
2.Mis said to bestably freeif there exist two non-negative integers randssuch
that
M⊕D
1×s∼
=D 1×r
.
3.Missaidtobeprojectiveif there exist a D-modulePand non-negative integerr
such that
M⊕P
∼
=D
1×r
.
4.Missaidtobereﬂexiveif the canonical map
εM:M−→hom D(homD(M,D),D),
deﬁned by
∀m∈M,∀f∈hom D(M,D):ε M(m)(f)=f(m),
is an isomorphism, wherehomD(M,D) denotes theD-module ofD-morphisms
from
MtoD.
5.
Missaidtobetorsion-freeif the submodule of Mdeﬁned by
t(M)={m∈M|∃0ϕ =P∈D:Pm=0}
is reduced to the zero module.t(M)is called thetorsion submoduleof Mand
the elements of
t(M)are thetorsion elementsof M.
6.
Mis said to betorsionif t(M)=M , i. e., every element ofMis a torsion
element.
Let
K=Q(D)=k(x 1,...,xn)be thequotientﬁeldof D([53]) andMaﬁnitely
presented
D-module. We call therankof MoverD, denoted byrankD(M), the di-
mension of the
K-vector spaceK⊗ DMobtained by extending the scalars ofMfrom
DtoK,i.e.,
rankD(M)=dim K(K⊗ DM).

30 A. Fabia´nska and A. Quadrat
We can check that ifMis a torsionD-module, we then haveK⊗ DM=0 , a fact
implying
rankD(M)=0 . See [53] for more details.
Let us recall a few results about the notions previously introduced in Deﬁnition 2.4.
Theorem 2.5[53]Let
D=k[x 1,...,xn]be a commutative polynomial ring with co-
efﬁcients in aﬁeld
k. We have the following results:
1. We have the implications among the previous concepts:
free
=⇒stably free=⇒projective=⇒reﬂexive=⇒torsion-free.
2. IfD=k[x 1],thenDis aprincipal ideal domain−namely, every ideal ofD
isprincipal, i. e., it can be generated by one element ofD−and everyﬁnitely
generated torsion-free
D-module is free.
3.(Serre theorem [10])Every projective module over
Dis stably free.
4.(Quillen-Suslin theorem [52, 55])Every projective module over
Dis free.
The famous Quillen-Suslin theorem will play an important role in what follows. We
refer to [23, 24] for the best introductions nowadays available on this subject.
The next theorem gives some characterizations of the deﬁnitions given in Deﬁni-
tion 2.4.
Theorem 2.6[5, 33, 44]Let
D=k[x 1,...,xn]be a commutative polynomial ring
over aﬁeld
k,R∈D
q×p
and theﬁnitely presented D-modules
M=D
1×p
/(D
1×q
R),N=D
1×q
/(D
1×p
R
T
).
We then have the equivalences between theﬁrst two columns of Figure 2.1.
Combining the results of Theorem 2.6 and the Quillen-Suslin theorem (see 4 of Theo-
rem 2.5), we then obtain a way to check whether or not aﬁnitely presented
D-module
Mhas some torsion elements or is torsion-free, reﬂexive, projective, stably free or
free. We point out that the explicit computation of
ext
i
D
(N,D) can always be done
using Gr¨obner or Janet bases. See [5, 42, 43] for more details and for the descrip-
tion of the corresponding algorithms. We also refer the reader to [4, 6] for the library
O
REMODULESin which the different algorithms were implemented as well as to the
large library of examples of O
REMODULESwhich illustrates them. Finally, see also
[3, 10, 20] and the references therein for an introduction to Gr¨obner and Janet bases.
Remark 2.7The
D-moduleN=D
1×q
/(D
1×p
R
T
)is called thetransposed module
of
M=D
1×p
/(D
1×q
R)even ifNdepends onMonlyuptoaprojective equivalence
([45]), namely, if
M=D
1×r
/(D
1×s
R
λ
)andN
λ
=D
1×s
/(D
1×r
R
λT
), then there exist
two projective
D-modulesPandP
λ
such thatN⊕P
∼
=N
λ
⊕P
λ
([53]). However, for
every
D-moduleF,wehaveext
i
D
(N⊕P,F)
∼
=ext
i
D
(N,F)⊕ext
i
D
(P,F) and, for
i≥1,ext
i
D
(P,F)=0 becausePis a projectiveD-module ([53]). Hence, we then
get
ext
i
D
(N,F)
∼
=ext
i
D
(N
λ
,F),fori≥1. Hence, the results of Theorem 2.6 do not
depend on the choice of a presentation of
M,i.e.,onR. In what follows, we shall
sometimes denote
NbyT(M) .

Applications of the Quillen-Suslin theorem 31
In order to explain why the deﬁnitions given in Deﬁnition 2.4 extend the concepts of
primeness deﬁnedinDeﬁnition 2.1, weﬁrst need to introduce some more deﬁnitions
([2]).
Deﬁnition 2.81. If
Mis a non-zeroﬁnitely presented D-module, then thegrade
jD(M)ofMis deﬁned by
jD(M)=min{i≥0|ext
i
D
(M,D)ϕ =0}.
2. IfMis a non-zeroﬁnitely presented D-module, thedimension dimD(M)ofM
is deﬁned by
dimD(M)=Kdim(D/
λ
annD(M)),
whereKdimdenotes theKrull dimension([53]) and
annD(M)={a∈D|aM=0},
λ
annD(M)={a∈D|∃l∈Z +:a
l
M=0}.
We are now in position to state an important result.
Theorem 2.9[2, 33]If
Mis a non-zeroﬁnitely presented D=k[x 1,...,xn]-module,
where
kis aﬁeld containingQ, we then have
jD(M)+dim D(M)=n.
Let us suppose thatRhas full row rank and let us consider theﬁnitely presented D-
module
M=D
1×p
/(D
1×q
R). Using the notations of Deﬁnition 2.1 and the fact that
dimD(N)=dim CV(J),
whereN=T(M)=D
1×q
/(D
1×p
R
T
)is then a torsionD-module, i. e., it satisﬁes
ext
0
D
(M,D)=hom D(M,D)=0 , by Theorem 2.9, we then obtain
jD(N)=n−dim CV(J)≥1.
Hence, by Theorems 2.6 and 2.9, we obtain thatRis minor left-prime (resp., zero left-
prime) iff the
D-moduleMis torsion-free (resp., projective, i. e., free by the Quillen-
Suslin theorem stated in 4 of Theorem 2.5). See [44] for more details and the extension
of these results to the case of non-commutative rings of differential operators.
Weﬁnally obtain the table given in Figure 2.1 which sums up the different results
previously obtained. We note that the last two columns of this table only hold when
the matrix
Rhas full row rank.
Toﬁnish, we explain what the system interpretations of the deﬁnitions given in
Deﬁnition 2.4 are. In particular, these interpretations solve the Monge problem stated
in the introduction of the paper. In order to do that, we also need to introduce a few
more deﬁnitions (see, e. g., [53]).

32 A. Fabia´nska and A. Quadrat
ModuleM ext
i
D
(N,D)
dimD(N) Primeness
With torsiont(M)
∼
=ext
1
D
(N,D)
n−1 ∅
Torsion-freeext
1
D
(N,D)=0
n−2 Minor left-prime
Reﬂexive ext
i
D
(N,D)=0,
n−3
i=1,2
... ... ... ...
... ext
i
D
(N,D)=0,
0 Weakly zero
1≤i≤n−1 left-prime
Projectiveext
i
D
(N,D)=0,
-1 Zero left-prime
1≤i≤n
Figure 2.1Classiﬁcation of some module properties

Applications of the Quillen-Suslin theorem 33
Deﬁnition 2.101. A D-moduleFis calledinjectiveif, for every D-moduleM,
and, for all
i≥1,wehaveext
i
D
(M,F)=0 .
2. A
D-moduleFis calledcogeneratorif, for every D-moduleM,wehave
homD(M,F)=0 =⇒M=0.
Roughly speaking, an injective cogenerator is a space rich enough for seeking solu-
tions of linear systems of the form
Rη=0 ,whereR∈D
q×p
is any matrix and
η∈F
p
. In particular, using (2.5), ifFis a cogeneratorD-module andMϕ =0 ,then
homD(M,F)ϕ =0 , meaning that the corresponding systemkerF(R.)is not trivial. Fi-
nally, if
Fis an injective cogeneratorD-module, then we can prove that any complex
of the form (2.3) is exact at
F
pi
,i≥1, if and only if the corresponding complex (2.2)
is exact. See [32, 39, 62] and the references therein for more details.
The following result proves that there always exists an injective cogenerator.
Theorem 2.11[53]An injective cogenerator
D-moduleFexists for every ringD.
Let us give important examples of injective cogenerator modules.
Example 2.12If
Ωis an open convex subset ofR
n
, then the spaceC
∞
(Ω)(resp.,
D
λ
(Ω)) of smooth real functions (resp., real distributions) onΩis an injective cogener-
ator module over the ring
R[∂1,...,∂n]of differential operators with coefﬁcients in R,
where we have denoted by
∂i=∂/∂xi([32, 28, 39]).
Example 2.13Let
kbe aﬁeld, F=k
Z
n
+
be the set of sequences with values inkand
D=k[x 1,...,xn]be the ring ofshift operators, namely,
∀f∈F,i=1,...,n,(x if)(μ)=f(μ+1 i),
whereμ=(μ 1,...,μn)∈Z
n
+
andμ+1i=(μ 1,...,μi−1,μi+1,μ i+1,...,μn). Then,
Fis an injectiveD-module ([32, 62]).
We have the following important corollary of Theorem 2.6 which solves the Monge
problem in the case of linear functional systems with constant coefﬁcients. See [64]
and the references therein and the introduction of the paper.
Corollary 2.14[5, 42]Let
Fbe an injective cogeneratorD=k[x 1,...,xn]-module,
R∈D
q×p
andM=D
1×p
/(D
1×q
R). Then, we have the following results:
1. There exists
Q1∈D
q1×q2
,wherep=q 1, such that we have the exact sequence
F
qR.
←−F
q1
Q1.
←−−F
q2
,
i. e.,kerF(R.)=Q 1F
q2
,ifftheD-moduleMis torsion-free.
2. There exist
Q1∈D
q1×q2
andQ2∈D
q2×q3
such that we have the exact sequence
F
qR.
←−F
q1
Q1.
←−−F
q2
Q2.
←−−F
q3
,
i. e.,kerF(R.)=Q 1F
q2
andkerF(Q1.)=Q 2F
q3
,ifftheD-moduleMis reﬂex-
ive.

34 A. Fabia´nska and A. Quadrat
3. There exists a chain ofnsuccessive parametrizations, namely, fori=1,...,n ,
there exist
Qi∈D
qi×qi+1
such that we have the following exact sequence
F
qR.
←−F
q1
Q1.
←−−...
Qn−1.
←−−−−F
qn
Qn.
←−−F
qn+1
,
i. e.,kerF(R.)=Q 1F
q2
andkerF(Qi.)=Q i+1F
qi+1
,i=1,...,n−1 ,iffthe
D-moduleMis projective.
4. There exist
Q∈D
p×m
andT∈D
m×p
such thatTQ=I mand the sequence
F
qR.
←−F
p
Q.
←−F
m
←−0, (2.6)
is exact, i. e.,
kerF(R.)=QF
m
, and iff theD-moduleMis free.
We refer the reader to [5, 42, 43, 44, 49, 50] for the solutions of the Monge problem for
different classes of linear functional systems with variables coefﬁcients such as partial
differential, differential time-delay or difference equations.
The matrices
Qideﬁned in Corollary 2.14 are calledparametrizations([5, 42, 43,
44]). Indeed, from 1 of Corollary 2.14, if
Mis torsion-free, then there exists a matrix
of operators
Q1∈D
q1×q2
which satisﬁes kerF(R.)=Q 1F
q2
. This means that every
solution
η∈F
p
satisfyingRη=0 is of the formη=Q 1ξfor a certainξ∈F
q2
.In
thebehaviour approach([40]), the parametrization is called animage representationof
kerF(R.)([39, 62, 63]). We point out that the parametrizationsQiare obtained by com-
puting
ext
i
D
(N,D) (see Theorem 2.6). Hence, checking whether or not aD-module
is torsion-free, reﬂexive or projective gives the corresponding successive parametriza-
tions. We refer to [5, 42, 43, 44] for more details, the extension of the previous results
to non-commutative algebras of functional operators and the implementation of the
corresponding algorithms in the library O
REMODULES. Finally, the matrixQdeﬁned
in 4 of Corollary 2.14 is called aninjective parametrizationof
kerF(R.)as everyF-
solution of
kerF(R.)has the formη=Qξ for a certainξ∈F
m
and we have
ξ=(TQ)ξ=Tη,
i. e.,ξis uniquely deﬁned by η∈ker F(R.). At this stage, it is important to point out
that no general algorithm has been developed to get injective parametrizations when
the
D-moduleMis free. It is the main purpose of this paper to constructively study
this question and to apply the computation of injective parametrizations to some open
questions appearing in mathematical systems theory.

Applications of the Quillen-Suslin theorem 35
Finally, we point out that, ifMis a freeD-module, then there always exist matrices
Q∈D
p×m
andT∈D
m×p
such that, for everyD-moduleF, we have the exact
sequence (2.6). Indeed, let us recall two standard arguments of homological algebra
([53]).
Proposition 2.151. Let us consider the following short exact sequence:
M
λ
f
−→M
g
−→M
λλ
−→0.
IfM
λλ
is a projectiveD-module, then the previous exact sequence splits (see 5 of
Deﬁnition 2.2).
2. Let
Fbe aD-module. The functorhomD(·,F) transforms split exact sequences
of
D-modules into split exact sequences ofD-modules.
By 1 of Proposition 2.15, we obtain that
D
1×q
.R
−→D
1×p
.Q
−→D
1×m
−→0 is a splitting
exact sequence and applying the functor
homD(·,F)to it, by 2 of Proposition 2.15, we
obtain the splitting exact sequence (2.6). Hence, the assumption that
Fis an injective
cogenerator
D-module is only important for the converse implication of 6 of Corol-
lary 2.14.
Explicit examples of computation of parametrizations can be found in [5, 6, 42, 43,
44] as well in the O
REMODULESlarge library of examples ([4]). We refer the reader
to these references and to section 4 for the computation of injective parametrizations.
However, let us give a simple example in order to illustrate the previous results.
Example 2.16Let us consider the ring
D=Q[∂ 1,∂2,∂3]of differential operators with
rational coefﬁcients (
∂i=∂/∂x i), the matrixR=(∂ 1∂2∂3)deﬁning the so-called
divergent operatorin
R
3
and theﬁnitely presented D-moduleM=D
1×3
/(DR) .Let
us check whether or not the
D-moduleMhas some torsion elements or is torsion-free,
reﬂexive or projective, i. e., free by the Quillen-Suslin theorem. In order to do that, we
deﬁne the
D-moduleN=D/(D
1×3
R
T
).Aﬁnite free resolution ofNcan easily be
computed by means of Gr¨obner or Janet bases. We obtain the following exact sequence
0−→D
.P3
−−→D
1×3.P 2
−−→D
1×3.R
T
−−→D
σ
−→N−→0,
whereσdenotes the canonical projection ontoNand
P2=
⎛
⎜
⎜
⎝
0−∂
3∂2
∂3 0−∂ 1
−∂2∂1 0
⎞
⎟
⎟
⎠
,P
3=R.
We note thatP2corresponds to the so-calledcurl operatorwhereas R
T
is thegradient
operator. Then, the defects of exactness of the following complex
0←−D
.P
T
3
←−−D
1×3
.P
T
2
←−−D
1×3.R
←−D←−0 (2.7)

36 A. Fabia´nska and A. Quadrat
are deﬁned by
⎧
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎩
ext
0
D
(N,D)
∼
=ker D(.R),
ext
1
D
(N,D)
∼
=ker D(.P
T
2
)/(DR),
ext
2
D
(N,D)
∼
=ker D(.P
T
3
)/(D
1×3
P
T
2
),
ext
3
D
(N,D)
∼
=D/(D
1×3
P
T
3
).
Using the fact thatRhas full row rank, we obtain thatext
0
D
(N,D)
∼
=ker D(.R)=0 ,
which is equivalent to say that
Nis a torsionD-module. Now computing the syzygy
modules
kerD(.P
T
2
)andkerD(.P
T
3
)by means of Gr¨obner or Janet bases, we obtain that
kerD(.P
T
2
)=DR,ker D(.P
T
3
)=D
1×3
P
T
2
,
which shows thatext
1
D
(N,D)=ext
2
D
(N,D)=0 . Finally, we can easily check that 1
does not belong to the ideal
I=D∂ 1+D∂ 2+D∂ 3ofD, and thus, we have
ext
3
D
(N,D)
∼
=D/Iϕ =0.
Using Theorem 2.6, we obtain thatMisareﬂexive but not a projective, i. e., not a free
D-module. This last fact can also be checked asRhas full row rank and the dimension
dimD(N)is 0 as the corresponding system is deﬁned by the gradient operator, namely,
∂iy=0,i=1,2,3,
whose solution is a constant, i. e., the solution of the system only depends on “a
function of zero independent variables”. Hence, by Theorem 2.9, we obtain that
jD(N)=3, meaning that theﬁrst non-zero ext
i
D
(N,D) has index 3. By Theorem 2.6,
we then get that
Mis a reﬂexive D-module but not a projective one.
Finally, if we consider the
D-moduleF=C
∞
(Ω),whereΩis an open convex
subset of
R
3
, using Example 2.12, we obtain thatFis an injective cogeneratorD-
module. Hence, if we apply the functor
homD(·,F) to the complex (2.7), we then
obtain the following exact sequence:
F
P
T
3
.
−−→F
3
P
T
2
.
−−→F
3R.
−→F−→ 0.
Weﬁnd again the classical results in mathematical physics that the smooth solutions
on an open convex subset of
R
3
of the divergence operator are parametrized by the
curl operator and the solutions of the curl operator are parametrized by the gradient
operator.
The only point left open is to constructively compute injective parametrizations of
linear functional systems deﬁning free modules over a commutative polynomial ring
D. Indeed, checking the vanishing of theext
i
D
(N,D) , we generally obtain a successive
chain of
nparametrizations but not an injective one. In the case of linear systems of
partial differential equations with polynomial or rational coefﬁcients, we have recently
solved this problem in [49, 50, 51] using a constructive proof of a famous result in non-
commutative algebra due to Stafford. However, the same technique cannot be used if

Applications of the Quillen-Suslin theorem 37
we want an injective parametrizationQofkerF(R.)to have only constant coefﬁcients.
The main purpose of this paper is to solve this problem using a constructive proof of the
Quillen-Suslin theorem and to show some applications of this result to mathematical
systems theory.
3 The Quillen-Suslin theorem
Since Quillen and Suslin independently proved Serre’s conjecture stating that projec-
tive modules over commutative polynomial rings with coefﬁcients in aﬁeld are free,
some algorithmic versions of the proof have been proposed in the literature in order to
constructively compute bases of free modules ([15, 19, 26, 27, 35, 56, 57, 58, 59]). We
refer the interested reader to Lam’s nice books [23, 24] concerning Serre’s conjecture.
3.1 Projective and stably free modules
In module theory, it is well known that aﬁnitely presented D=k[x 1,...,xn]-module
M=D
1×p
/(D
1×q
R),wherekis aﬁeld andR∈D
q×p
, admits aﬁnite free resolution.
This is a result is due to Hilbert ([10]). Moreover, if
kis acomputableﬁeld, we can
even construct aﬁnite free resolution of
Musing Gr¨obner or Janet basis ([3, 10, 20]).
A classical result due to Serre proves that every projective
D-module is stably free
(a stably free module always being a projective
D-module). See [10, 23, 24] for more
details. In [49, 51], a constructive proof of this result was given and the corresponding
algorithm was implemented in O
REMODULES. Let us recall these useful results.
Proposition 3.1[49, 51]Let
Mbe aD-module deﬁned by theﬁnite free resolution
0−→D
1×p m
.Rm
−−−→...
.R2
−−→D
1×p 1
.R1
−−→D
1×p 0
π
−→M−→0. (3.1)
1. If
m≥3 and there existsSm∈D
pm−1×pm
such thatRmSm=Ipm
,then we
have the followingﬁnite free resolution of
M
0−→D
1×p m−1
.Tm−1
−−−−→D
1×(p m−2+pm)
.T
m−2
−−−−→D
1×p m−3
.Rm−3
−−−−→...
π
−→M−→0,
(3.2)
with the following notations:
⎧
⎪
⎪
⎨
⎪
⎪
⎩
T
m−1=(R m−1 Sm)∈D
pm−1×(pm−2+pm)
,
T
m−2=
κ
R
m−2
0
ζ
∈D
(pm−2+pm)×pm−3
.
2. Ifm=2 and there existsS2∈D
p1×p2
such thatR2S2=Ip2
,then we have the
followingﬁnite free resolution of
M
0−→D
1×p 1
.T1
−−→D
1×(p 0+p2)τ
−→M−→0, (3.3)

38 A. Fabia´nska and A. Quadrat
with the notationsT1=(R 1S2)∈D
p1×(p0+p2)
and
τ=π⊕0:D
1×(p 0+p2)
−→M
λ=(λ
1λ2)π −→τ(λ)=π(λ 1).
Remark 3.2We note that Proposition 3.1 holds for every ringD.
Let
R∈D
q×p
and let us suppose that theD-moduleM=D
1×p
/(D
1×q
R)is pro-
jective (using the results summed up in Figure 2.1, we can constructively check this
result). Using 1 of Proposition 2.15, we obtain that the exact sequence (3.1) splits (see
5ofDeﬁnition 2.2), and thus, there exists
Sm∈D
pm−1×pm
such thatRmSm=Ipm.
Repeating inductively the same method with the newﬁnite free resolution of
M,we
can assume that we have theﬁnite free resolution of
M:
0−→D
1×p
δ
3.R
δ
3
−−→D
1×p
δ
2.R
δ
2
−−→D
1×p 1
.R1
−−→D
1×p 0
π
−→M−→0.
AsMis a projectiveD-module, by 1 of Proposition 2.15, the previous exact sequence
splits and thus, there exists a matrix
S
λ
3
∈D
p
δ
2
×p
δ
3
satisfyingR
λ
3
S
λ
3
=Ip
δ
3. By1of
Proposition 3.1, we then get theﬁnite free resolution of
M:
0−→D
1×p
δ
2.(R
δ
2
S
δ
3
)
−−−−−−−→D
1×(p 1+p
δ
3
)
.(R
T
1
0
T
)
T
−−−−−−−−→D
1×p 0
π
−→M−→0.
LetusdenotebyT1=(R
T
1
0
T
)
T
.Again,asMis a projectiveD-module, by 1 of
Proposition 2.15, the previous exact sequence splits and there exists
S
λ
2
∈D
(p1+p
δ
3
)×p
δ
2
such that(R
λ
2
S
λ
3
)S
λ
2
=Ip
δ
2. Using 2 of Proposition 3.1, we obtain the followingﬁnite
free presentation of the
D-moduleM
λ
=D
1×(p 0+p
δ
2
)
/(D
1×(p 1+p
δ
3
)
(T1S
λ
2
))
0−→D
1×(p 1+p
δ
3
)
.(T
1S
δ
2
)
−−−−−−→D
1×(p 0+p
δ
2
)π
δ
−→M
λ
−→0,
whereπ
λ
denotes the standard projection ontoM
λ
andτ:M
λ
−→M is deﬁned by
τ(m)=π(λ 1), for allλ=(λ 1λ2)∈D
1×(p 0+p
δ
2
)
satisfyingm=π
λ
(λ). Moreover,
2 of Proposition 2.15 says that
τis an isomorphism, i. e.,M
λ∼
=M
, a fact that can be
also directly checked. We then obtain the following result.
Corollary 3.3Let
D=k[x 1,...,xn]be a commutative polynomial ring over aﬁeld k
andR∈D
q×p
.IftheD-moduleM=D
1×p
/(D
1×q
R)is projective, then there exists
a full row rank matrix
R
λ
∈D
q
δ
×p
δ
such that
M
∼
=D
1×p
δ
/(D
1×q
δ
R
λ
). (3.4)
We refer to Example 5.5 for an illustration of Corollary 3.3. See also [49, 50, 51].
We note that
rankD(M)=rank D(M
λ
)=p
λ
−q
λ
. Finally, we have the following
short exact sequence of
D-modules
0−→D
1×q
δ.R
δ
−−→D
1×p
δπ
δ
−→M
λ
−→0,

Applications of the Quillen-Suslin theorem 39
and using the fact thatM
λ∼
=M
andMis a projectiveD-module, by 1 of Proposi-
tion 2.15, we obtain that the previous exact sequence splits and we then get ([5, 53])
M
λ
⊕D
1×q
δ
∼
=D 1×p
δ
,
which, by 2 of Deﬁnition 2.4, shows that M
∼
=M
λ
is a stably freeD-module.
Corollary 3.4 (Serre)[10, 23, 24]Let
Mbe aﬁnitely generated projectiveD=
k[x
1, ..., xn]-module. Then,Mis stably free.
3.2 Stably free and free modules
LetMbe a stably free module overD=k[x 1,...,xn],wherekis aﬁeld. Using
Corollary 3.3, we can always suppose that
Mhas the formM=D
1×p
/(D
1×q
R),
where
R∈D
q×p
admits a right-inverseS∈D
p×q
. We note thatRhas then full row
rank (
λR=0⇒λ=λRS=0 ). Let us characterize whenMis a freeD-module.
In order to do that, weﬁrst need to introduce a deﬁnition.
Deﬁnition 3.5Let
Dbe a ring. Thegeneral linear group GLp(D)is deﬁned by
GLp(D)={U∈D
p×p
|∃V∈D
p×p
:UV=VU=I p}.
An elementU∈GL p(D)is called aunimodular matrix.
In the case where
D=k[x 1,...,xn], we note thatU∈GL p(D)iff the determinant
detU ofUis invertible inD, i. e., is a non-zero element ofk. The following result
holds for every ring
D.
Lemma 3.6Let
R∈D
q×p
be a matrix which admits a right-inverse overD. Then, the
D-moduleM=D
1×p
/(D
1×q
R)is free if and only if there existsU∈GL p(D)such
that
RU=(I q0).
Indeed, let us suppose that there exists
U∈GL p(D)such thatRU=(I q0)and let
us denote by
J=(I q0)∈D
q×p
. We easily check thatD
1×p
/(D
1×q
J)=D
1×(p−q)
.
Moreover, using the fact that
RU=J andU∈GL p(D), we obtain the following
commutative exact diagram
00
↓↓
0−→D
1×q
.R
−→D
1×p
π
−→ M −→0
↓
.U
0−→D
1×q
.J
−→D
1×p
κ
−→D
1×(p−q)
−→0,
↓↓
00
which proves thatM
∼
=D
1×(p−q)
,i.e.,Mis a freeD-module of rankp−q.

40 A. Fabia´nska and A. Quadrat
Conversely, let us suppose thatM
∼
=D
1×(p−q)
. Then, combining the isomorphism
ψ:M−→D
1×(p−q)
and the short exact sequence
0−→D
1×q.R
−→D
1×pπ
−→M−→0,
we obtain the following exact sequence:
0−→D
1×q.R
−→D
1×p
ψ◦π
−−→D
1×(p−q)
−→0.
If we consider the matrix which corresponds to theD-morphismψ◦πin the canonical
bases of
D
1×p
andD
1×(p−q)
, we then obtain a matrixQ∈D
p×(p−q)
such that
∀λ∈D
1×p
:(ψ◦π)(λ)=λQ.
By 1 of Proposition 2.15, the previous exact sequence splits, i. e., we have
0−→D
1×q
.R
−→D
1×p
.Q
−→D
1×(p−q)
−→0,
.S
←−
.T
←−
or, equivalently, there exists a matrixT∈D
(p−q)×p
such that the following B´ezout
identities hold (see [5, 42, 48, 53] for more details):
κ
R
T
ζ
(SQ)=
κ
I
q0
0I
p−q
ζ
,(SQ)
κ
R
T
ζ
=I
p.
In particular, we obtain that there exists a matrixU=(SQ)∈GL p(D)satisfying
RU=(I q0).
Finally, the family{π(T i)}1≤i≤p−q forms a basis of the freeD-moduleM,whereTi
denotes thei
th
row ofT∈D
(p−q)×p
.
We are now in position to state the famous Quillen-Suslin theorem ([23, 24, 53]).
Theorem 3.7 (Quillen-Suslin theorem)[52, 55]Let
Abe a principal ideal domain
(e. g., aﬁeld
k) andD=A[x 1,...,xn]a polynomial ring with coefﬁcients in A.More-
over, let
R∈D
q×p
be a matrix which admits a right-inverseS∈D
p×q
,i.e.,RS=I q.
Then, there exists a unimodular
U∈GL p(D)satisfying
RU=(I q0). (3.5)
Using Lemma 3.6 and Theorem 3.7, we obtain the following important corollary.
Corollary 3.8 (Quillen-Suslin)[52, 55]Let
Abe a principal ideal domain (e. g., a
ﬁeld
k) andD=A[x 1,...,xn]. Then, every stably freeD-module is free.
Moreover, the problem ofﬁnding a basis of a freeﬁnitely generated
D-moduleMcan
be reformulated in terms of matrices as follows:

Applications of the Quillen-Suslin theorem 41
Problem 1Let R∈D
q×p
be a matrix which admits a right-inverse overD.Finda
matrix
U∈GL p(D)such thatRU=(I q0).
The previous problem is equivalent to completing
Rto a square invertible matrix
U
−1
=
κ
R
T
ζ
∈D
p×p
.
The Quillen-Suslin theorem states that Problem 1 has always a solution over a poly-
nomial ring
D=A[x 1,...,xn]with coefﬁcients in a principal ringAand, in particular,
in aﬁeld
k. In what follows, an algorithm which computes such a matrixUwill be
called aQS-algorithm.
Let us consider a matrix
R∈D
q×p
which admits a right-inverse overDand let
us denote by
Rithei
th
row ofR. We note that the rowR1∈D
1×p
admits a right-
inverse over
D. Let us suppose that we canﬁnd a matrix U1∈GL p(D)satisfying
R1U=(10...0). Then, we have
RU1=
κ
10
R
2
ζ
,
whereR2∈D
(q−1)×(p−1)
anddenotes a certain element ofD
(q−1)×1
. Hence, we
restrict our considerations to the new matrix
R2, which can easily be shown to admit a
right-inverse over
D, and reduce Problem 1 to the following one:
Problem 2Let
R∈D
1×p
be a row vector which admits a right-inverse overD.Find
a matrix
U∈GL p(D)such thatRU=(10...0) .
The purpose of the next paragraphs is to recall a QS-algorithm solving Problem 2 over
a commutative polynomial ring
D=k[x 1,...,xn]over a computableﬁeld k(for in-
stance,
k=Q ). This algorithm was implemented in the package QUILLENSUSLIN
([12]). See also the appendix. We also point out that a QS-algorithm has also been im-
plemented in Q
UILLENSUSLINfor the caseD=Z[x 1,...,xn]. Even though there are
some differences in the constructive proofs of the Quillen-Suslin theorem developed in
[15, 19, 23, 26, 35, 56, 57, 59], we note that our algorithm is based on the same main
idea, i. e., it proceeds by induction on the number of variables
xiinD=k[x 1,...,xn].
Each inductive step of the general QS-algorithm reduces the problem to the case with
one variable less. A more global and interesting approach has recently been developed
in [27, 58] which needs to be studied with care in the future.
3.3 Solution of Problem 2 in some special cases
Although the tedious inductive method, which will be explained in the next section,
cannot generally be avoided, there are cases where simpler and faster heuristic methods
can be used. We shallﬁrst consider such cases.

42 A. Fabia´nska and A. Quadrat
3.3.1 Matrices over a principal ideal domainD
Weﬁrst consider the special case of matrices over a principal ideal domainD(e. g.,
D=k[x 1],wherekaﬁeld,Z). LetR∈D
q×p
be a matrix which admits a right-inverse
over
D. Then, computing theSmith canonical formof R([40]), we obtain two matrices
F∈GL q(D)andG∈GL p(D)satisfying
R=F(I q0)G.
If we denote byr=p−q ,G=(G
T
1
G
T
2
)
T
,whereG1∈D
q×p
,G2∈D
r×p
and
G
−1
=(H 1H2)∈D
p×p
,whereH1∈D
p×q
,H2∈D
p×r
,thenwegetR=FG 1,
i. e.,
G1=F
−1
R, and thus, we get
κ
F
−1
R
G
2
ζ
(H
1H2)=I p⇒
κ
F
−1
0
0I
r
ζκ
R
G
2
ζ
(H
1H2)=I p
⇒
κ
R
G
2
ζ
(H
1H2)
κ
F
−1
0
0I
r
ζ
=I
p
⇒
κ
R
G
2
ζ
(H
1F
−1
H2)=I p,
which solves Problem 1 as we can takeU=(H 1F
−1
H2)∈GL p(D)andT=G 2.
3.3.2
(p−1)×p matrices over an arbitrary commutative ringD
Let us consider the case of a matrixR∈D
(p−1)×p
which admits a right-inverse over a
commutative ring
D. If we denote bymithe(p−1)×(p−1) minor ofRobtained by
removing the
i
th
column ofR, then, using the factRadmits right-inverse, we get that
the family
{mi}1≤i≤p satisﬁes a B´ezout identity
ϕ
p
i=1
nimi=1for certainni∈D
andi=1,...,p. Let us denote by
V=
κ
R
(−1)
p+1
n1...(−1)
2p
np
ζ
∈D
p×p
.
Expand the determinant ofValong the last row, using the Laplace’s formula, we then
get
detV=1 . Hence, if we denote byU∈D
p×p
the inverse of the matrixV,wethen
obtain
RU=(I p−1 0), which solves Problem 1.
3.3.3
1×prows over an arbitrary commutative ringD
We now consider Problem 2, i. e., the case of a row vectorf=(f 1... fp)∈D
1×p
which admits a right-inverse over an arbitrary commutative ringD.
Remark 3.9 (Special form of the row)1. We note that if one of the components of
fis an invertible element ofD, we can then transform the rowfinto(1 0...0)

Random documents with unrelated
content Scribd suggests to you:

— Meidän menettelymme ei vaikuta lainkaan tähän asiaan — me
emme voisi pidättää Owen Fordia tulemasta Neljään tuuleen, jos
tahtoisimmekin, sanoi Anna nopeasti.
Naimakauppojen välittäminen oli Annasta vastenmielistä ja täti
Cornelian kuiskutus ja tähdellinen ilme herätti hänessä erinäisiä
ajatusyhtymiä. Mutta hän ei voinut kumminkaan vastustaa halua
jatkaa tuota keskustelua.
— Pidä hänen tulonsa salassa Leslieltä, kunnes hän on täällä,
sanoi hän. — Jos hän saisi siitä tiedon, olen varma, että hän
matkustaisi pois. Hän aikoo joka tapauksessa muuttaa täältä
syksyllä, — sen sanoi hän minulle äskettäin eräänä päivänä. Hän
aikoo lähteä Montrealiin oppiaksensa sairaanhoitoa ja
järjestääksensä elämänsä niin hyvin kuin voi.
— No, tuohan kuuluu ymmärtäväiseltä ja hyvältä, rakkaani —
ainahan sopii laatia suunnitelmia, sanoi täti Cornelia, nyökäten
rikkiviisain ilmein. — Nyt olemme me tehneet tehtävämme, — nyt
saa kaitselmus ryhtyä jatkamaan.

XXXV.
POLITIIKKAA JA SEN SEURAUKSIA.
Kun Anna jälleen pääsi laskeutumaan alakertaan huoneestansa,
tuskaili sekä Prinssi Edvardin saari että Kanada tuollaisen
levottomuuden ja eripuraisuuden vallassa, joka käy yleisten vaalien
edellä. Gilbert, joka oli innokas oikeistolainen, huomasi joutuneensa
mukaan pyörteeseen, ja hänen täytyi usein esiintyä puhujana niillä
seuduin pidettävissä kokouksissa. Neiti Cornelia ei hyväksynyt hänen
sekaantumistaan politiikkaan, ja hän ilmaisi Annalle ajatuksensa
tavalliseen suorasukaiseen tapaansa.
— Tohtori Dave ei tehnyt sitä koskaan. Tohtori Blythe huomaa
kyllä erehtyneensä menettelyssään, sen saat uskoa! Valtiollisiin
asioihin ei kenenkään kunnon miehen pidä sekaantua.
— Pitäisikö maan hallituksen sitten jäädä lurjusten ja konnien
käsiin? kysyi Anna.
— Miksikä ei — kun ne vain ovat oikeistolurjuksia, sanoi täti
Cornelia, kasvoillaan ilme sellainen, kuin olisi noihin hänen
sanoihinsa sisältynyt maailmanarvoituksen selvitys. — Neuvoisin

tohtori Blytheä joka tapauksessa välittämään vähät kaikesta
politiikasta. Jos hän saa jatkaa samaan tapaan kuin nyt, Jumala
paratkoon, näyttää alkaneen, käy niin, että hän jonakin päivänä
matkustaa Ottawaan puoleksi vuodeksi ja veisaa viisi koko
lääkärintoimestansa.
— Riittäköön kullekin päivälle oma huolensa, sanoi Anna. —
Älkäämme huolehtiko turhaan tulevista asioista, vaan katsokaamme
mieluummin pikku Jemiä. Eikös hän ole niin viehättävä, että hänet
voisi syödä suuhunsa? Katsopa noita kuoppia hänen kyynärpäissään!
Me kasvatamme hänestä oikeistolaisen, eikö niin, täti Cornelia?
— Kasvata hänestä ylimalkaan hyvä mies, sanoi täti Cornelia. —
Niitä ei tosiaankaan kasva joka oksalla. Mutta puhuakseni totta — en
tahtoisi nähdä häntä vapaamielisten palopuhujana. Nyt ovat vaalit
tulossa — voimme kiittää onneamme, ettemme ole lahden tuolla
puolen. Siellä ovat näinä päivinä kuumat ottelut käynnissä. Jokainen
Elliott ja Crawford ja Mac Allister on täydessä taistelutouhussa.
Täällä meidän puolellamme on verrattain rauhallista, siksi että täällä
asuu niin vähän miesväkeä. Kapteeni Jim kuuluu vapaamielisiin,
mutta luulen melkein, että hän häpeää sitä, sillä hän ei puhu
koskaan valtiollisista asioista. On täysin varmaa, että vanhoilliset
tulevat voittamaan suurella ääntenenemmistöllä.
Täti Cornelia erehtyi. Vaalien jälkeisenä aamuna tuli kapteeni Jim
käväisemään tuossa pienessä talossa kermaksensa uutisia. Niin
voimakkaasti vaikuttaa puoluepolitiikan basilli, yksin rauhalliseen
vanhaan mieheenkin, että kapteeni Jimin poskilla näkyi kiihkeä puna
ja hänen silmissään säihkyi entisaikojen hehku.
— Rouva Blythe, vapaamieliset ovat voittaneet valtavalla
ääntenenemmistöllä. Kahdeksantoistavuotisen oikeistohallituksen

jälkeen alkanevat tässäkin kurjassa, sorretussa maassa puhaltaa
raikkaammat tuulet!
— En koskaan ole kuullut teidän käyttävän niin katkeraa
puoluekieltä, kapteeni Jim. En luullut, että teillä olisi niin paljon
valtiollista myrkkyä suonissanne, naureskeli Anna, joka vastaanotti
tuon tuiki tärkeän uutisen suurella levollisuudella.
Pikku Jem oli sanonut aamulla "ä-dä". Mitä merkitsivät ruhtinaat ja
suurvallat, hallitsijasukujen valtaanpääsyt ja kukistumiset,
vanhoillisten tai vapaamielisten vaalitappiot noin ihmeellisen
tapahtuman rinnalla!
— Se on kokoontunut vähitellen, sanoi kapteeni Jim hymyillen
anteeksianovasti. — Luulin olevani maltillinen vapaamielinen, mutta
kun sanoma voitostamme tuli, silloin tunsin olevani kiihkoliberaali.
— Tiedättehän kaiketi, että mieheni ja minä olemme oikeistolaisia?
— Kyllä — ja se onkin teidän ainoa virheenne, rakas lapseni.
Cornelia on samaa maata. Käväisin hänen luonaan The Glenistä
tullessani ilmoittaakseni hänelle tuon uutisen.
— Eikö se merkinnyt teille suoranaista hengenvaaraa?
— Kyllä kai, mutta en voinut vastustaa kiusausta.
— No, miten hän otti vastaan tuon tiedon?
— Verrattain tyynesti, pikku rouva, verrattain tyynesti! Hän puhui
tähän tapaan: "No niin, kaitselmus lähettää nöyryytyksen ja
koettelemuksen aikoja maille kuten yksityisillekin. Te vapaamieliset
olette saaneet kestää kylmää ja nälkää vuosikausia. Pitäkää nyt

varanne ja lämmitelkää ja pistäkää hiukan poskeenne, sillä kauan
ette tule pysymään vallassa." — "Mutta, rakas ystävä", sanoin minä,
"kenties Kanada Herran mielestä tarvitsee oikein pitkällisen
nöyryytyskauden." — Mutta silloin… Kas, hyvää iltaa, Susan!
Oletteko kuullut uutisen? Vapaamieliset ovat voittaneet.
Susan oli juuri tullut sisään keittiöstä, tuoden mukanaan
maukkaiden ruokien tuoksun, joka aina tuntui ympäröivän häntä.
— Vai niin, sanoi hän miellyttävän välinpitämättömästi. — Mikäli
olen huomannut, on leipäni aina kohonnut yhtä hyvin, hallitsivatpa
maata vapaamieliset taikka niinsanotut vanhoilliset. Ja jos
jompikumpi puolue, rakas pikku tohtorinna, voi toimittaa meille
kunnollisen sadekuuron ennen viikon loppua ja pelastaa
kasvitarhamme tykkänään turmeltumasta, niin Susan äänestää sitä
puoluetta. Mutta nyt ensi aluksi pyytäisin teitä katsomaan, mitä
arvelette piparjuurilihasta, joka oli aiottu huomiseksi päivälliseksi.
Pelkään, että se on aika sitkeätä ja että olisi parasta vaihtaa
teurastajaa, samalla kuin vaihdamme hallitusta.
Eräänä iltana viikkokautta myöhemmin meni Anna niemen
majakalle tiedustelemaan, voisiko hän saada kapteeni Jimiltä hiukan
tuoretta kalaa. Ensi kerran hän nyt lähti pois pikku Jimin luota.
Jäähyväiset muodostuivat täydelliseksi murhenäytelmäksi. Ja entä
jos poikanen alkaisi itkeä? Kenties Susan ei tiennyt oikein, mitä siinä
tapauksessa oli tehtävä?
Susan tuntui tyyneltä ja luotettavalta.
— Olenhan minä hoidellut häntä yhtä paljon kuin pikku tohtorinna
itse — vai mitä?

— Niin, häntä kyllä — mutta ette muita pikkulapsia. Pienenä
ollessani minulla oli hoidettavanani kolme kaksois-paria, näettekös,
Susan. Kun ne huusivat, niin annoin niille lusikallisen
kalanmaksaöljyä. Tuntuu varsin hullunkuriselta nyt jälkeenpäin
ajatella, kuinka aristelematta minä käsittelin noita tenavia ja heidän
kipujansa.
— Olkaa aivan levollinen. Jos pikku Jem alkaa huutaa, panen minä
lämpimän vesipussin hänen pienelle vatsallensa, sanoi Susan.
— Mutta se ei saa olla liian lämmin, sanoi Anna levotonna. Eiköhän
sittenkin ollut ajattelematonta lähteä hänen luotansa?
— Älkää olko huolissanne, pikku tohtorinna! Ei olisi Susanin
tapaista polttaa tuollaisen pikku herran vatsa. Jumala tiunakkoon
häntä — eihän hänen talvitte huutaa!
Lopuksi Anna sitten joutui matkaan, ja kävelyretki tuotti hänelle
suurta huvia. Aurinko oli laskemaisillaan ja varjot kävivät pitkiksi.
Kapteeni Jim ei ollut majakan arkihuoneessa, vaan siellä istui muuan
toinen henkilö — keski-ikäinen, komea mies, jolla oli sileäksiajettu
vahvarakenteinen leuka ja jota Anna ei tuntenut. Siitä huolimatta
alkoi muukalainen keskustella hänen kanssaan vanhan tuttavan
tavoin. Hänen juttelunsa ja esiintymisensä oli täysin hyvän tavan
mukaista, mutta tuollainen tuttavallisuus vieraan henkilön puolelta,
joka ei edes ollut välittänyt esitellä itseänsä, vaikutti Annaan
kumminkin vastenmielisesti. Hän vastasi perin kylmähkösti ja oli niin
harvasanainen, kuin kohteliaisuus suinkin salli. Mutta tuo outo mies
ei näyttänyt siitä joutuvan hämilleen, vaan jatkoi vielä hetkisen
rohkeasti jutteluansa. Sittenhän sanoi jäähyväiset ja lähti pois. Anna
olisi voinut vannoa, että hänen silmissänsä näkyi veitikkamainen
välkähdys, ja se harmitti häntä yhä enemmän. Kuka kumma tuo

mies olikaan? Hänen olentonsa tuntui hiukan tutulta, mutta Anna oli
vakuutettu, ettei hän ollut nähnyt häntä koskaan maailmassa.
— Kapteeni Jim, kuka tuo oli, joka juuri tuli täältä ulos? kysyi hän,
kun kunnon kapteeni tuli sisään, sydämellisesti tervehtien.
— Marshall Elliott, vastasi kapteeni.
— Marshall Elliott? huudahti Anna. — Oi, kapteeni Jim — eihän se
voi olla mahdollista — aivan niin, ääni oli hänen — ja ajatelkaas,
minä en tuntenut häntä — olin hänelle oikein epäkohtelias! Miksi hän
ei sanonut mitään! Täytyihän hänen huomata, ettei minulla ollut
aavistustakaan siitä, kuka hän oli.
— Sen hän tahallansa piti salassa — hänestä se oli huvittavaa.
Älkää välittäkö siitä, jos te kohtelitte häntä ynseästi — se tuotti
hänelle vain hauskuutta. Niin, Marshall on nyt vihdoinkin ajanut pois
pitkän partansa ja leikkauttanut tukkansa. Hänen puolueensa on
päässyt voitolle, kuten kyllä tiedätte. Minä en myöskään tuntenut
häntä nähdessäni hänet ensi kerran. Hän oli The Glenissä Carter
Flaggin puodissa vaalipäivän illalla, odottaen yhdessä lukemattomien
muiden kanssa tietoja vaalien tuloksesta. Noin keskiyön tienoilla tuli
puhelimitse sana — vapaamieliset olivat voittaneet. Marshall nousi
vain paikaltaan ja meni ulos — huutamatta ja hurraamatta — sen
hän jätti toisten tehtäväksi, ja vähällä pitikin, etteivät ne
lennättäneet ilmaan Carterin pienen rihkamapuodin kattoa. Kaikki
oikeistolaiset olivat Raymond Russellin vastapäätä sijaitsevassa
sekatavarakaupassa. Siellä ei liioin hurrattu. Marshall astelee
pääkatua pitkin suoraa tietä Augustus Palmerin parturitupaan.
Augustus makasi kuorsaten sängyssään, mutta Marshall jymisytti
hänen oveansa, kunnes hän nousi ja tuli ulos sekä kysyi hyvin
happamella äänellä, mitä mokoma melu merkitsi.

— Mene parturitupaasi suorittamaan paras työ, minkä ikinä olet
tehnyt, Gus, sanoi Marshall. — Vapaamieliset juhlivat rummuin ja
torvin voittoansa, ja nyt sinun pitää lyhentää kunnon
vasemmistolaisen tukka ja parta ennen auringonnousua.
Gus oli pakahtua kiukusta — osittain siksi, että hänen oli täytynyt
nousta mukavasta vuoteestansa, mutta ennen kaikkea sentähden,
että hän itse oli oikeistolainen. Hän vakuutti lujasti ja pyhästi, ettei
hänelle ikinä voinut pälkähtää päähän pitää liikettänsä avoinna
kahdentoista jälkeen yöllä.
— "Nyt sinä teet kuten sanon, poikaseni", tuumiskeli Marshall,
"sillä muutoin panen sinut poikkipuolin polvelleni ja annan sinulle
selkäsaunan, jonka äitisi jätti sinulle antamatta."
Hän olisi pitänyt sanansa, sitä ei käynyt epäileminenkään — ja sen
Gus kyllä tiesi, sillä Marshall on väkevä kuin karhu, ja Gus on vain
pieni hintelä rahjus. Hän ei siis rohjennut panna vastaan, vaan
toimitti Marshallin parturitupaan ja tuoliin istumaan ja saippuoi
hänet. Ja sitten hän sanoi: "Jokainen on heikompansa herra — ja nyt
minä kyllä lyhennän takkusi, mutta jos hiiskahdat sanankaan
vapaamielisten voitosta sill'aikaa, niin leikkaan kaulasi poikki tällä
partaveitsellä korvasta korvaan." Kukapa olisi aavistanut, että tuo
pieni säyseä parturi olisi niin verenhimoinen. Siitä näkee, mihin tuo
siunattu politiikka johtaa… Marshall istui hiljaa ja tyynenä, ja tukka ja
parta katkesi kuin vilja syksyllä viikatteen taittamana, ja sitten meni
Marshall kotiin. Kun hänen vanha taloudenhoitajattarensa kuuli
hänen nousevan portaita ylös, katsoi hän ulos ovestansa
nähdäksensä, hänkö siellä tuli vai renkipoika. Nähdessään
ventovieraan miehen tulevan eteisestä, kädessä kynttiläjalka, jossa
oli palava kynttilä, alkoi taloudenhoitajatar kirkua jotakin ryöväreistä

ja murhaajista, ja sitten hän meni tainnoksiin. Lääkäri oli noudettava,
ennenkuin he saivat hänet tointumaan, ja vasta monen päivän
perästä hän voi nähdä Marshallia, alkamatta väristä koko
ruumiistansa.
Kapteeni Jimillä ei ollut kalaa. Tänä kesänä hän teki vain harvoin
veneretkiä ja hänen pitkät kävelyretkensä olivat myös lopussa. Hän
istui enimmäkseen merellepäin olevan akkunansa ääressä, silmäillen
lahtea ja satamansuuta, nopeasti vaikeneva pää nojattuna käteen.
Niin istui hän tänäkin iltana pitkän aikaa vaieten, menneisyyden
muistojen kuvastuessa hänen mieleensä. Anna ei raskinut häiritä
häntä. Vihdoin viittasi kapteeni läntisen taivaan sammuvaan
hohteeseen ja sanoi:
— Tuo on kaunista, rouva Blythe! Mutta jospa olisitte nähnyt
auringonnousun tänä aamuna! Se oli ihana — ihana. Minä olen ollut
melkein kaikkialla maailmassa, mutta kauniimpaa auringonnousua
kuin kesäisin tämän lahden varrella en ole koskaan nähnyt.
Kuolinhetkeänsä ei kukaan voi määrätä, vaan on itsekunkin oltava
valmis matkaan, silloin kun Suuri kapteeni antaa lähtökäskyn. Mutta
jos riippuisi itsestäni, tahtoisin erota täältä aamun lähetessä yli
ulapan. Olen lukemattomia kertoja istunut tuota näytelmää katsoen
ja ajatellut itsekseni, kuinka ihanaa olisi liidellä tuon valkoisen
hohteen läpi kohden sitä, joka odottelee tuolla kaukana — merelle,
joka ei ole merkittynä millekään inhimilliselle kartalle. Siellä, rouva
Blythe, luulen löytäväni kadonneen Margaretani.
Sen jälkeen kun kapteeni Jim oli kertonut Annalle tuon liikuttavan
nuoruudentarinansa, oli hän usein puhunut hänen kanssaan
kuolleesta morsiamestansa. Jokainen hänen äänenväreensä puhui

tuosta rakkaudesta — rakkaudesta, joka ei voinut heiketä eikä
unhottaa.
— Toivon kumminkin, että kun hetkeni tulee, kaikki käy nopeasti ja
helposti. En luule olevani pelkuri, rouva Blythe — olen lukemattomia
kertoja katsonut kammottavaa kuolemaa suoraan kasvoihin silmää
räpäyttämättä. Mutta pitkä kuolinkamppailu tuntuu minusta
kammottavalta — se herättää mielessäni pelkoa.
— Älkää puhuko sellaista, että lähtisitte luotamme, rakas, rakas
kapteeni Jim, pyysi Anna äänellä, joka puolittain tukahtui kyyneliin,
ja hän hyväili tuota vanhaa ruskeata kättä, joka kerran oli ollut niin
voimakas, vaan nyt ei enää pystynyt paljoonkaan. — Kuinka
voisimme tulla toimeen ilman teitä!
Kaunis hymy levisi kapteeni Jimin kasvoille.
— Ah, se käy kyllä varsin hyvin… Mutta te ette sentään unohda
tykkänään vanhusta, rouva Blythe — ei, sitä en luule… Muistoni ei
tule tuottamaan tuskaa ystävilleni — päinvastoin toivon ja uskon,
että heistä on oleva mieluista säilyttää se ja väliin omistaa sille joku
hetki… Ei kestä enää kauan, ennenkuin kadonnut Margaretani
kutsuu minua viimeisen kerran. Ja minä valmistaudun noudattamaan
heti hänen kutsuansa. Mutta olen ottanut tämän asian puheeksi
siksi, että tahtoisin pyytää teiltä yhtä ainoata pientä palvelusta. Se
koskee Ensi perämiestä — tuota vanhusparkaa…
Kapteeni Jim kurotti kätensä, taputtaakseen hellävaroen tuota
suurta lämpöistä karvapalloa, joka loisti sohvassa niin korean
punakeltaisena. Ensi perämies pyörähti suoraksi, kuin olisi ponninta
painettu, ja se päästi mielihyvästä äännähdyksen, joka kuului
puolittain kehruulta, puolittain nau'unnalta, ojensi kaikki neljä

käpäläänsä ilmaan, paneutui jälleen kyljelleen ja kääriytyi taas
kerälle.
— Se tulee kaipaamaan minua, kun minä lähden viimeiselle
retkelleni. En kestä ajatusta, että tuo eläinparka kenties joutuu
näkemään nälkää, kuten silloin, kun sen löysin. Jos minulle
tapahtuisi jotakin — annatteko silloin Ensi perämiehelle palan ruokaa
ja matonpätkän, jolla se voi loikoa nurkassaan, rouva Blythe?
— Lupaan sen. Olen oikein kiltti Ensi perämiehelle — sekä sen
itsensä että sen rakkaan kapteenin tähden.
— No, sitten olen levollinen, saatuani nyt lausutuksi sen, mikä on
ahdistanut sydäntäni… Teidän pikku Jim saa nuo muutamat
ihmeelliset esineet, jotka olen koonnut matkoillani — siitä olen
huolehtinut.
Mutta nyt en enää tahdo saattaa kyyneleitä pikku tohtorinnan
kauniisiin silmiin. Ehkä eloani jatkuu vielä kauankin… Kuulin teidän
viime talvena eräänä päivänä lukevan kauniin runon — sanoitte sen
olevan Tennysonin sepittämän. Tahtoisin mielelläni kuulla sen
uudelleen, jos ehkä osaatte sen ulkoa ja tahdotte lausua sen minulle.
Merituulen hiljaisten henkäysten käydessä sisään avoimesta
akkunasta lausui Anna lempeällä, raikkaalla äänellänsä nuo kauniit
säkeet Tennysonin ihanasta joutsenlaulusta, joka on saanut nimen
"Taa tyrskyjen". Vanha kapteeni nyökäytteli hiljaa päätänsä runon
poljennon tahdissa.
— Niin, rouva Blythe, sanoi hän Annan ehdittyä loppuun, — tuo oli
kaunista… Hän ei ollut merimies, olette te sanonut minulle, mutta on
ihmeellistä, kuinka hän on osannut tuolla tavoin pukea sanoihin

vanhan merikarhun tunteet… "Hyvästelyt haikeat" eivät ole hänen
mielensä mukaiset eivätkä myöskään minun — sillä kun vain pääsen
"taa tyrskyjen", silloin ei ole enää hätää…

XXXVI.
ANNA PUHUU LASTENKIELTÄ JA TERVETTÄ JÄRKEÄ.
— Mitä uutta kuuluu Vihervaarasta, Anna?
— Ei mitään erikoista, vastasi Anna, taittaen kokoon Marillan
kirjeen. — Jake Donnel on ollut siellä laittamassa uusia päreitä
katolle. Hän on nyt täysinoppinut nikkari, joten hän siis ilmeisesti on
saanut noudattaa omaa makuansa elämänuransa valinnassa.
Muistathan kaiketi, että hänen äitinsä olisi tahtonut saada hänet
professoriksi. En unohda ikinä sitä päivää, jolloin hän tuli kouluun,
nuhtelemaan minua siitä, etten nimittänyt hänen poikaansa S:t
Clairiksi.
— Vieläköhän häntä sanotaan siksi?
— Tuskinpa vain. Hän ei itse ole koskaan liioin välittänyt tuosta
ranskalaisesta romaaninimestä. Äiti näyttää myöskin tyytyneen asiain
nykyiseen tilaan. Olinkin aina vakuutettu, että poika, jolla oli Jaken
voimakas leuka, lopuksi saisi tahtonsa täytäntöön. Diana kirjoittaa
myöskin ja kertoo, että Doralla on "ystävä". Ajatteles vain, — hänhän
on vasta lapsi.

— Dora on seitsemäntoista vuoden vanha, sanoi Gilbert. — Kun
sinä olit seitsemäntoistavuotias, Anna, olimme me, Charlie Sloane ja
minä, hullautuneet sinuun.
— Me olemme nähtävästi jo ikäihmisiä, Gilbert, sanoi Anna,
hymyillen puolittain surunvoittoisesti, — kun pikkutytöt, jotka olivat
kuusivuotisia, silloin kun me mielestämme jo olimme aikuisia,
hankkivat itsellensä ihailijoita. Doran "ystävä" on Ralph Andrews,
Janen veli. Minä muistan hänet pienenä palleroisena ja
liinatukkaisena poikana, joka aina istui luokan alapäässä. Mutta nyt
hän taitaa olla oikein komean näköinen nuori mies.
— Dora menee varmaankin nuorena naimisiin. Hän on samaa
laatua kuin Charlotta Neljäs — hän ei uskalla päästää käsistänsä
ensimmäistä tilaisuutta, vaan pelkää, että uutta ei enää ilmaantuisi.
— Jos noista kahdesta on tuleva pari, niin toivon, että Ralphissa
on enemmän tarmoa kuin hänen veljessänsä Billyssä, sanoi Anna
miettiväisesti.
— Niin, naureskeli Gilbert, — toivokaamme, että hän pystyy itse
kosimaan. Anna, olisitko sinä ottanut Billyn, jos hän olisi itse
ilmaissut hellät tunteensa, sen sijaan että jätti sen sisar Janen
tehtäväksi?
— Kenties se ei olisi ollut niin aivan mahdotonta, sanoi Anna,
tyrskähtäen hillittömään nauruun muistellessaan tuota ensimmäistä
kosintaa, joka oli tullut hänen osaksensa. — Ken tietää, mitä olisin
tehnyt ensi hämmästyksen vallassa! Olkaamme iloisia siitä, että hän
kosi asiamiehen välityksellä.

— Minä sain eilen kirjeen George Moorelta, sanoi Leslie
nurkastansa, missä hän istui lukemassa.
— Vai niin, kuinkas hänen laitansa on? tiedusteli Anna hiukan
välinpitämättömästi.
Hänestä tuntui, että oli puhe hänelle täysin vieraasta henkilöstä.
— Hän voi hyvin, mutta hänen on hankala perehtyä kaikkiin
muutoksiin, joita on tapahtunut hänen kodissansa ja hänen
ystäviensä keskuudessa. Keväällä hän aikoo jälleen mennä merille.
Luonto vetää häntä siihen, sanoo hän, ja sitä elämää hän ikävöi.
Mutta hän kertoi minulle erään seikan, josta olen iloissani tuon
miesparan puolesta. Ennen lähtöänsä purjehdusretkelle "Neljällä
sisarella" hän oli kihloissa erään kotiseutunsa tytön kanssa. Hän ei
maininnut hänestä mitään minulle Montrealissa, siksi että hän, kuten
myöhemmin kertoi, oli ollut varma, että tyttö oli unohtanut hänet ja
jo aikoja mennyt naimisiin jonkun toisen kanssa, mutta hän
puolestansa, jonka käsitteet ajasta olivat aivan sekaisin, tunsi vielä
olevansa täysin rakastumisensa ja kihlaustunnelmansa vallassa.
Häntä täytyi oikein sääliä — mutta kun hän sitten tuli kotiin, kävi
ilmi, ettei tyttö ollutkaan mennyt naimisiin, vaan oli yhä edelleen
kiintynyt häneen. Syksyllä he menevät naimisiin. Minä pyydän häntä
tuomaan vaimonsa hiukan vierailemaan, ja hän on itsekin halukas
näkemään paikan, missä hän on viettänyt niin monta vuotta
voimatta käyttää järkeänsä.
— Minä pidän tuosta hänen ihmeellisten vaiheittensa
romantillisesta lisästä, sanoi Anna hyvillään, hän kun aina oli niin
ihastuksissaan kaikesta, mikä tuoksahti romantiikalle. — Ja
ajatelkaas, lisäsi hän katuvaisena huoaisten, — jos olisi käynyt
minun tahtoni mukaan, ei George Moore koskaan olisi päässyt esiin

siitä haudasta, mihin tuo tieto, ken hän on, oli kätkettynä. Kuinka
minä vastustinkaan Gilbertin ehdotusta! Niin, minä olen saanut
rangaistukseni! Tästä puoleen en koskaan enää rohkene olla toista
mieltä kuin Gilbert. Jos milloin yritänkään ajatella omin päin — silloin
saan tuota pikaa kuulla: kuinkas olikaan George Mooren laita? Minä
tulen tuntemaan itseni täysin nolatuksi.
— Naista ei ole niinkään helppo nolata, kiusoitteli Gilbert. — Mutta
pyydän sinua — älä muutu minun kaiukseni, Anna! Elämään
tarvitaan höysteeksi hiukan vastaaninttämistä. En tahdo saada
sellaista vaimoa kuin on Mac Allisterilla, joka asuu lahden tuolla
puolen. Mitä hän ikinä sanookaan, niin säestää vaimo häntä heti
kimeällä rääkkyvällä äänellänsä: "Niin juuri, olet aivan oikeassa,
ukkoseni."
Anna ja Leslie nauroivat. Annan nauru helkähteli hopealta, Leslien
kajahteli kullalta, ja ne sointuivat yhteen niin viehkeästi kuin mitä
kaunein musiikkiakordi.
Susan tuli sisään, mutta hän ei yhtynyt siellä vallitsevaan
hilpeyteen, vaan kevensi ahdistettua sydäntänsä raskaalla,
huokauksella.
— Mikäs nyt on, rakas Susan? kysyi Gilbert.
— Eihän vain pikku Jemille ole tapahtunut mitään, Susan? huusi
Anna, kavahtaen pystyyn.
— Ei, ei suinkaan — rauhoittukaa toki, pikku tohtorinna! Mutta
voihan tapahtua muita asioita, ja seikkoja… En ymmärrä, miksikä
kova onni on seurannut minua koko tämän viikon… Leipä ei
kohonnut — no niin, senhän jokainen voi nähdä, niin tahmaista se oli

— ja silittäessäni poltin tohtorin parhaan paidan rintamuksen — ja
rikoin tohtorinnan suuren paistivadin… Ah, hyvä Jumala… Ja nyt
saan kaiken lisäksi sisareltani Matildalta kirjeen, että hän on taittanut
jalkansa, ja nyt hän tahtoo, että minä tulisin sinne joksikin aikaa
häntä hoitamaan.
— Sehän on kauhean ikävää, — tarkoitan sitä, että sisarellesi on
sattunut sellainen onnettomuus, huudahti Anna.
— Niin, sanokaapa muuta… Mutta suremassa ja kärsimässähän
täällä maailmassa ollaan, ja jos ei satu yhtä niin toista. Mitä nyt
Matildaan tulee, niin tuntuu minusta perin oudolta, että hän muka
olisi taittanut jalkansa. Meidän suvussamme ei sellaista ole
tapahtunut vielä koskaan. Mutta olipa kuinka tahansa, niin onhan
hän sentään sisareni, ja tunnen olevani velvollinen lähtemään häntä
hoitamaan, jos tohtorinna tulee muutaman viikon toimeen ilman
minua.
— Tietysti, Susan. Voinhan hankkia jonkun toisen apulaisen siksi
aikaa, kun sinä olet poissa.
— Jos siitä tulee hankaluutta, niin minä en lähde, pikku
tohtorinna, käyköön Matildan jalan sitten kuinka tahansa. En
kaikkien koko maailman taittuneiden jalkojen takia sallisi, että
tohtorinna tulee levottomaksi ja meidän rakas pikku poikalapsemme
saa vihreän vatsan.
— Kiitos, pikku Susan, mutta matkusta sinä vain heti sisaresi luo!
Minä voin kyllä saada kalastajakylästä jonkun tytön, johon voin
tyytyä toistaiseksi.

— Anna, enkö minä voi tulla sinun luoksesi siksi aikaa, kun Susan
on poissa? huudahti Leslie. — Oi, se olisi minusta niin hauskaa —
tekisit minulle todellisen laupeudentyön. Olen niin äärettömän yksin
tuossa suuressa autiossa talossa. Siellä on niin vähän tehtävää — ja
illoin minua niin kammottaa ja säpsähdän alinomaa pelästyksestä,
vaikka kaikki ovet ja akkunat ovat kiinni. Pari päivää sitten tapasin
keittiönovellani maankiertäjän.
Anna suostui ilolla tuohon ehdotukseen, ja seuraavana päivänä
muutti
Leslie kimssuineen kamssuineen tuohon pieneen haavekotiin. Neiti
Cornelia oli peräti hyvillään siitä, että asiat kehittyivät tuolla
tavoin.
— Tämä tuntuu minusta aivan kaitselmuksen johdatukselta, sanoi
hän salavihkaa Annalle. — Onhan sääli Matilda Clowia, mutta kun
hänen nyt kerran oli taitettava jalkansa, ei se olisi voinut tapahtua
sopivampana ajankohtana. Leslie asuu täällä sen aikaa kun Owen
Ford on minun luonani täysihoidossa, ja The Glenin vanhat kissat
eivät saa tilaisuutta naukua koko asiasta, kuten ne olisivat tehneet,
jos Leslie olisi asunut yksin ja Owen Ford olisi käynyt häntä
tervehtimässä. Täällä juorutaan ja pidetään jo tarpeeksi ääntä
siitäkin, ettei Leslie käy surupuvussa. Minä sanoin eräällekin
äskettäin: "Jos tarkoitatte, että hänen pitäisi pukeutua surupukuun
George Mooren takia, niin minun mielestäni hän on pikemmin
kuolleista noussut kuin haudattu, ja jos taas tarkoitatte, että hänen
olisi surtava Dickiä, niin en käsitä, miksi hänen olisi pukeuduttava
mustiin miehen takia, joka kuoli yksitoista vuotta sitten — eikä siitä
ollut vahinkoa silloinkaan…" Ja kun muori Louisa Baldwin myöskin
piti touhua tuosta asiasta ja sanoi minulle, että oli sangen merkillistä,
ettei Leslie koskaan epäillyt, ettei tuo hoidokki ollutkaan hänen

miehensä, silloin vastasin minä: "Sinäkään et yhtään epäillyt, ettei
hän ollut Dick Moore, ja kumminkin olit ollut kaiken ikäsi hänen
naapurinsa ja olet luonnostasi kymmenin verroin epäluuloisempi kuin
Leslie Moore." Mutta toisten ihmisten täytyy saada panetella,
rakkaani, muutoin ne eivät voi hyvin… Olen joka tapauksessa oikein
kiitollinen siitä, että Leslie saa asua kattosi alla sen aikaa, kun Owen
on täällä häntä kosiskelemassa.
Owen Ford tuli tuohon pieneen valkoiseen taloon eräänä elokuun
iltapäivänä, juuri Annan ja Leslien haltioituneina ihaillessa
pienokaista. Hän pysähtyi arkihuoneen avoimelle ovelle,
huoneessaolijain sitä havaitsematta, ja hän jäi kaihoisin katsein
silmäilemään tuota kaunista kuvaa. Leslie istui lattialla pienokainen
polvillaan ja tavoitellen ihastuneena hänen lihavia pikku käsiänsä,
jotka huitoivat ilmassa.
— Oi sinä herttainen, rakas lapsukainen! kuiskasi Leslie, tarttuen
toiseen noista pienistä kätösistä ja peittäen sen suuteloilla.
— Että voikin olla niin hilveän pieni ja helttainen ja tuloinen! piipitti
Anna, joka tuolin selkänojaa vastaan riipuksissa ihaili tuota
näytelmää. — Nuo pienet lihavat tassut ovat maailman tievimmät
tattut, ja ne ovat pojun omat tattut.
Anna oli pikku Jeniin saapumisen edellisinä kuukausina lukenut
useita opettavaisia kirjoja ja erittäinkin omannut sen viisauden, jota
teos "Pikkulasten hoidon ja kasvatuksen ohjeita" tarjosi. Siinä
varoitettiin vanhempia, vedoten kaikkeen, mikä on pyhää,
puhumasta tenavillensa "pikkulastenkieltä". Pienokaisia olisi
ehdottomasti puhuteltava kieliopillisesti mallikelpoisin sanoin, aina
siitä saakka, kun he tulevat maailmaan. Sillä tavoin he oppisivat
alunpitäin puhumaan äidinkieltänsä virheettömästi. "Kuinka voikaan

äiti odottaa, että hänen lapsensa myöhemmin oppisi puhumaan
huolellista kieltä", tuumiskeli kirjan tekijä, "jos hän itse totuttaa sen
herkän kielen ja korvan sellaisiin virheellisiin puhetapoihin ja jalon
kielemme vääristelyihin, joihin ajattelemattomat äidit päivä päivältä
itsepintaisesti totuttavat noita avuttomia olentoja, jotka on uskottu
heidän hoitoonsa. Voiko lapsi, jota alati nimitetään 'hellanteltuksi' ja
'kultamuluksi', koskaan saada oikeata käsitettä omasta olennostaan,
kehitysmahdollisuuksistaan ja siitä asemasta, joka sille maailmassa
kuuluu."
Tuo oli vaikuttanut Annaan valtavasti, ja hän oli ilmoittanut
Gilbertille aikovansa mitä ankarimmin noudattaa sääntöä, ettei
koskaan missään olosuhteissa puhuisi pienokaisillensa "lastenkieltä".
Gilbert oli samaa mieltä, ja he tekivät asiasta juhlallisen sopimuksen
— jonka Anna rikkoi heti mitä häpeällisimmällä tavalla, kun pikku Jim
ensi kerran laskettiin hänen käsivarrellensa. "Oi tuloinen pieni
tydänkäpyni!" huudahti hän, ja hän jatkoi sittemminkin aivan
empimättä tuota kielilakien rikkomista välittämättä vähääkään
juhlallisista lupauksistansa.
— Äh, tuolla kirjailijalla ei ole koskaan ollut omia lapsia, Gilbert,
sanoi Anna, — siitä voit olla varma, muutoin hän ei varmaankaan
olisi ikinä kirjoittanut tuonlaista pötyä. Tietysti täytyy kapalovauvalle
puhua pikkulastenkieltä! Muu olisi luonnotonta. Olisi suorastaan
epäinhimillistä puhua noille pienille hennoille palleroisille samalla
tavoin kuin pitkä-koipisille tytöille ja pojille. Pikkulapset kaipaavat
hyväilyä ja hemmottelua ja haluavat kuulla niin paljon helttaitia ja
tuloitia pikku tanoja kuin tuinkin, ja pikku Jem taa kuulla niitä niin
paljon kuin ikinä tahtoo — oma pikku halakanvalpaani!

— Mutta sinähän olet pahimpia pahimmista, Anna, sanoi Gilbert,
joka ollen ainoastaan isä, eikä äiti, ei vielä ollut ehtinyt tulla täysin
vakuutetuksi tuon oppineen kirjailijan suunnattomasta erehdyksestä.
— En ole ikimaailmassa kuullut sellaista sekamelskaa kuin tuo, jolla
sinä puhuttelet poikaamme.
— Etpä suinkaan — sitä ei käy ihmetteleminen — sinähän et ole
liioin nähnyt äitejä etkä pikkulapsia… Sinun ei maksa vaivaa
ylvästellä, — minähän kasvatin Hammondilla kolme paria kaksosia
ennenkuin olin täyttänyt yksitoista vuotta — mitäs siihen sanot? Sinä
ja sinun arvoisa kirjailijasi — te olette pelkkiä kamarioppineita.
Gilbert, rukoilen sinua, katsopa pienokaista! Hän hymyilee minulle —
hän tietää, mistä me puhumme. Ja tinä olet tamaa mieltä kuin äiti,
sen voin nähdä sinusta, eikö totta, kullannuppuseni?
Gilbert laski kätensä heidän molempain ympärille. — Oi, te äidit!
Jumala tiesi, mitä hän teki, luodessaan teidät!
Tällä tavoin juteltiin pikku Jemin kanssa, ja häntä hyväiltiin ja
hemmoteltiin, ja hän viihtyi ja vaurastui, kuten pikkulapsen sopii ja
tulee tehdä haavekodissa. Leslie oli aivan yhtä ihastunut häneen kuin
Anna. Kun he olivat päättäneet talousaskareensa eikä Gilbert ollut
lähettyvillä, panivat he toimeen todellisia palvonnan ja hellän
lörpöttelyn juhlahetkiä, — ja juuri tällaisena hetkenä Owen Ford nyt
yllätti heidät.
Leslie huomasi hänet ensiksi. Vaikka jo hämärsi, voi Anna nähdä,
kuinka äkillinen kalpeus levisi noille kauniille kasvoille, haihduttaen
poskien ja huulten helakan punan.
Owen lähestyi häntä, mieli täynnä kiihkeätä kaihoa, ja ensi
hetkenä ei hän havainnut Annaa.

— Leslie! sanoi hän kurottaen kätensä esiin.
Ensi kerran hän oli kutsunut Leslietä nimeltä. Mutta Leslien
ojentama käsi oli kylmä, ja hän oli koko illan hyvin vähäpuheinen,
jota vastoin Anna, Gilbert ja Owen juttelivat ja laskivat leikkiä kilvan
— melkein kuten ennen. Ennenkuin Owenin vierailu oli päättynyt,
poistui Leslie omaan huoneeseensa, lausuen muutaman
anteeksipyynnön sanan. Owenin hilpeys oli poissa, ja hän sanoi pian
jäähyväiset, poistuen alakuloisin ilmein.
Gilbert katsoi Annaan.
— Anna, mitä tämä kaikki merkitsee? Täällä on tekeillä jotakin,
jota minä en ymmärrä. Koko ilma on tänään ollut sähkötettyä. Leslie
istuu murhenäytelmän runottaren kaltaisena, Owen Ford koettaa
näyttää iloiselta ja ylläpitää hilpeätä ja leikillistä keskustelua — mutta
Leslie täyttää hänen mielensä. Ja sinä puolestasi näytät olevan
pakahtumaisillasi salaiseen mielenliikutukseen, jota töin tuskin pystyt
hillitsemään. Suusi puhtaaksi! Mitä salakähmäisyyttä täällä
harjoitetaan, josta sinä koetat pitää herkkäuskoisen ja
hyväluontoisen miehesi erillään?
— Älä nyt ole typerä, Gilbert, vastasi Anna aviovaimon
suorasukaisuudella. — Mitä Lesliehin tulee, niin on hän mieletön
pikku hölmö, ja sen minä totta totisesti saatan hänen tietoonsa.
Anna tapasi Leslien tuon pienen kodikkaan ullakkokamarin
akkunan ääressä. Meren vahveneva ja heikkenevä kohina täytti koko
huoneen. Leslie istui kädet ristissä kalpeassa kuutamossa —
viehkeänä ilmiönä, jonka ryhdissä sentään oli syytöksen ja nuhteen
ilme.

— Anna, sanoi hän hillityllä äänellä, — tiesitkö sinä, että Owen
Ford tulisi Neljään tuuleen?
— Tiesin kyllä, lapsukaiseni, vastasi Anna rohkeasti.
— Oi, olisit kertonut siitä minulle, huudahti Leslie kiihkeästi. — Jos
olisin tiennyt sen, olisin lähtenyt tieheni — en olisi tahtonut jäädä
tänne häntä tapaamaan. Sinun olisi pitänyt kertoa siitä minulle. Et
ole menetellyt hienotunteisesti — Anna — etkä oikein.
Leslien huulet vapisivat — nähtävästi oli hermostunut itkukohtaus
tulossa. Mutta Anna tyrskähti mitä sydämettömimpään nauruun,
kumartui häntä kohden ja suuteli hänen ylöspäin kohotettuja,
nuhtelevia kasvojansa.
— Leslie, sinä olet varmaankin oikein harvinaisen suuri tyhmyri —
viehkeä ja suloinen tyhmyri. Kuvitteletko tosiaankin, että Owen on
lähtenyt matkaan Tyyneltämereltä Atlantille halusta saada tavata
minua? En myöskään luulisi, että ystävämme, täti Cornelia, on
herättänyt hänessä niin hurjan ja äkillisen intohimon. Nuo
surunvoittoiset kasvojenilmeesi joutavat siis pois — voit panna ne
sievästi kokoon laventelissa säilytettäviksi — et tarvitse niitä enää.
On ihmisiä, jotka voivat katsoa myllynkiven lävitse, jos siinä on kolo
keskellä, mutta sinulla ei näy olevan sitä kykyä. Minulla ei tosin ole
profeetan lahjoja, mutta uskallan kumminkin ennustella hiukan
tulevaisuudestasi. Elämäsi raskas ja katkera osa on takanasi.
Vastedes odottavat sinua onnellisen naisen riemut ja toiveet —
joskin myös hiukan suruilla sekoitettuina — se on uskoni. Muistatko
tuon onnea ennustavan Venuksen varjon, Leslie? Sinuun nähden se
toteutui. Se vuosi, jolloin sen näit, tuotti sinulle elämän parhaan
lahjan — rakkautesi Owen Fordiin. Mene nyt levolle ja nuku hyvin —
enempää en sano.

Welcome to our website – the perfect destination for book lovers and
knowledge seekers. We believe that every book holds a new world,
offering opportunities for learning, discovery, and personal growth.
That’s why we are dedicated to bringing you a diverse collection of
books, ranging from classic literature and specialized publications to
self-development guides and children's books.
More than just a book-buying platform, we strive to be a bridge
connecting you with timeless cultural and intellectual values. With an
elegant, user-friendly interface and a smart search system, you can
quickly find the books that best suit your interests. Additionally,
our special promotions and home delivery services help you save time
and fully enjoy the joy of reading.
Join us on a journey of knowledge exploration, passion nurturing, and
personal growth every day!
ebookbell.com

Grbner Bases In Control Theory And Signal Processing Hyungju Park Editor Georg Regensburger Editor

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

Grbner Bases In Control Theory And Signal Processing Hyungju Park Editor Georg Regensburger Editor

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 5

Slide 7

Slide 8

Slide 9

Slide 11

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77

Slide 78

Slide 79

Tags

Categories