
This part treats several different topics. 

In Section \ref{section:four}, we will see that GB's 
are useful for the computational
task of simplifying expressions. We will also provide an
example of their use in making deductions.

The Gr\"obner Theory starts with a set of relations and
produces new relations. The primary purpose of the algorithm is
to produce a ``complete'' set of relations.
While it does not  
generate all possible relations,
the new relations it does generate
%produced by the algorithm 
are often
of intrinsic interest.
We show how the
famous formulas of Youla and Tissi  
for system similarity emerge
directly from a GB as does
half of the State Space Isomorphism Theorem.
This is the subject of Section \ref{section:five}.

Section \ref{section:six} concerns efficient computation
of GB for Lyapunov equations. 
%This is the subject of Section \ref{section:six}.


%In Part I we found Gr\"{o}bner Bases for some widely applicable relations.
%In Part II we give applications and illustrations
%of the theory developed in  Part I.
%%simplification using the GBs of Part I.
%simplification using the GBs of Part I.
%{\BF
%In Part II, we will see
%that GBs are not only useful for the computational task of simplifying
%expressions, but they also can assist in the development of theory.
%}

\section{Simplification of formulas: an illustration 
involving $H^\infty$ control.}
\label{section:four}

In this section we will give an application of the simplification machinery
discussed in Part I.  We will also provide an example of the use of 
GB in making deductions.
%Another use of Gr\"obner basis is to verify that formulas
%which you suspect are true are indeed true.
%This goes under the heading of automatic theorem
%proving in the math and computer science communities. 
%We give an illustration of this here.

%{\BF DELETE??
%We will also introduce another use of Gr\"{o}bner
%Bases. Typical theorems in systems theory say that certain relations among
%matrices can be deduced from other relations. We will examine an example in
%which the Gr\"{o}bner reduction process is used to prove a theorem
%computationally. Reduction shows that the conclusion follows from the
%hypotheses.
%}

\subsection{An application of a Gr\"{o}bner bases to $H^\infty $ Control}

\subsubsection{Simplification}

In $H^\infty $ control, c.f. {\bf [DGKF]}, one 
deals with a Hamiltonian $H$ on the state space $%
(x,z)$ of the closed loop system. Here $x$ is a state of the plant and $z$
is a state of the compensator. The unknowns in $H$ are a quadratic form $%
\varepsilon $ which is to be a storage function of the closed loop system
and the $a,b,c,d$ which define the unknown compensator. 
As usual, take $d=0$.
Thus $a$, $b$, $c$ and $\varepsilon $ are unknowns. If a solution $%
\varepsilon $ exists, then
one can derive that for some controller, called the
central controller, $a$, $b$ and $c$ must be given by certain formulas. These
formulas do not imply that a solution to the $H^\infty $ control problem
exists. To see if it does, one must plug the central controller formulas back
into $H$ and see if $H\le 0$ for all states $(x,z)$ of the closed loop
system.

We apply the usual normalization to $H$:

\begin{equation}
\varepsilon (x,z)=\pmatrix{ x^T z^T}\pmatrix{ Y^{-1} & -(Y^{-1}-X) \cr
-(Y^{-1}-X) & Y^{-1}-X }\pmatrix{x \cr z}  \label{eq:4pt1}
\end{equation}

The Doyle Glover Khargonekar Francis simplifying assumptions (c.f., 
{\bf [DGKF]}) are then made. These greatly reduce the complexity of the formula
for $H$. We still obtain an expression which is very complicated:

{\tiny {\ 
\begin{verbatim}
 H = 
   tp[x] ** X ** A ** z + tp[x] ** inv[Y] ** A ** x - 
   tp[x] ** inv[Y] ** A ** z + tp[x] ** tp[A] ** X ** z + 
   tp[x] ** tp[A] ** inv[Y] ** x - tp[x] ** tp[A] ** inv[Y] ** z + 
   tp[x] ** tp[C1] ** C1 ** x + tp[z] ** X ** A ** x - 
   tp[z] ** X ** A ** z - tp[z] ** inv[Y] ** A ** x + 
   tp[z] ** inv[Y] ** A ** z + tp[z] ** tp[A] ** X ** x - 
   tp[z] ** tp[A] ** X ** z - tp[z] ** tp[A] ** inv[Y] ** x + 
   tp[z] ** tp[A] ** inv[Y] ** z + tp[x] ** X ** B1 ** tp[B1] ** X ** z - 
   tp[x] ** X ** B2 ** tp[B2] ** X ** z + 
   tp[x] ** inv[Y] ** B1 ** tp[B1] ** inv[Y] ** x - 
   tp[x] ** inv[Y] ** B1 ** tp[B1] ** inv[Y] ** z + 
   tp[z] ** X ** B1 ** tp[B1] ** X ** x - 
   tp[z] ** X ** B1 ** tp[B1] ** X ** z - 
   tp[z] ** X ** B2 ** tp[B2] ** X ** x + 
   tp[z] ** X ** B2 ** tp[B2] ** X ** z - 
   tp[z] ** inv[Y] ** B1 ** tp[B1] ** inv[Y] ** x + 
   tp[z] ** inv[Y] ** B1 ** tp[B1] ** inv[Y] ** z - 
   tp[x] ** X ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** x + 
   tp[x] ** X ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** z + 
   tp[x] ** inv[Y] ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** x - 
   tp[x] ** inv[Y] ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** z - 
   tp[x] ** tp[C2] ** C2 ** Y ** inv[-1 + X ** Y] ** X ** x + 
   tp[x] ** tp[C2] ** C2 ** Y ** inv[-1 + X ** Y] ** X ** z + 
   tp[x] ** tp[C2] ** C2 ** Y ** inv[-1 + X ** Y] ** inv[Y] ** x - 
   tp[x] ** tp[C2] ** C2 ** Y ** inv[-1 + X ** Y] ** inv[Y] ** z + 
   tp[z] ** X ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** x - 
   tp[z] ** X ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** z - 
   tp[z] ** inv[Y] ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** x + 
   tp[z] ** inv[Y] ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** z + 
   tp[z] ** tp[C2] ** C2 ** Y ** inv[-1 + X ** Y] ** X ** x - 
   tp[z] ** tp[C2] ** C2 ** Y ** inv[-1 + X ** Y] ** X ** z - 
   tp[z] ** tp[C2] ** C2 ** Y ** inv[-1 + X ** Y] ** inv[Y] ** x + 
   tp[z] ** tp[C2] ** C2 ** Y ** inv[-1 + X ** Y] ** inv[Y] ** z + 
   tp[x] ** X ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** X ** x - 
   tp[x] ** X ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** X ** z - 
   tp[x] ** X ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** inv[Y] ** x + 
   tp[x] ** X ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** inv[Y] ** z - 
   tp[x] ** inv[Y] ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** X ** x + 
   tp[x] ** inv[Y] ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** X ** z + 
   tp[x] ** inv[Y] ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** inv[Y] ** x - 
   tp[x] ** inv[Y] ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** inv[Y] ** z - 
   tp[z] ** X ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** X ** x + 
   tp[z] ** X ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** X ** z + 
   tp[z] ** X ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** inv[Y] ** x - 
   tp[z] ** X ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** inv[Y] ** z + 
   tp[z] ** inv[Y] ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** X ** x - 
   tp[z] ** inv[Y] ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** X ** z - 
   tp[z] ** inv[Y] ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** inv[Y] ** x + 
   tp[z] ** inv[Y] ** inv[-1 + Y ** X] ** Y ** tp[C2] ** C2 ** Y ** 
    inv[-1 + X ** Y] ** inv[Y] ** z

\end{verbatim}
}}

\centerline{Figure 4.1}

\baselineskip=18pt

Here we have used the same notation that one finds in our NCAlgebra program
to give a feel for this type of computation. {\it tp} stands for
transpose while {\it inv} stands for inverse and `**' for multiply. This
expression has 57 terms. 
The leading term has 10 factors. 
Many of the factors in Figure 4.1 contain inverses of the
type discussed in Part I. 
%All the factors
%are of the type discussed in Part I. 
%Reduction by just the starting rules,
%which is what one might do if simplifying the 
%expression by hand, does not produce a change. 
The rules (RESOL) together with the rules (EB) from Part I
are stored in a
function NCSimplifyRational (NCSR) in NCAlgebra which applies them
repeatedly to an expression until no change occurs. When we apply
NCSimplifyRational to $H$, we get the following considerably simpler
expression.
\footnote{Reduction of $H$ by just the starting rules
does not produce a change.}

{\tiny {\ 
\begin{verbatim}
HYI := NCSimplifyRational[H]=
  tp[x] ** X ** A ** z + tp[x] ** inv[Y] ** A ** x - 
   tp[x] ** inv[Y] ** A ** z + tp[x] ** tp[A] ** X ** z + 
   tp[x] ** tp[A] ** inv[Y] ** x - tp[x] ** tp[A] ** inv[Y] ** z + 
   tp[x] ** tp[C1] ** C1 ** x - tp[x] ** tp[C2] ** C2 ** x + 
   tp[x] ** tp[C2] ** C2 ** z + tp[z] ** X ** A ** x - 
   tp[z] ** X ** A ** z - tp[z] ** inv[Y] ** A ** x + 
   tp[z] ** inv[Y] ** A ** z + tp[z] ** tp[A] ** X ** x - 
   tp[z] ** tp[A] ** X ** z - tp[z] ** tp[A] ** inv[Y] ** x + 
   tp[z] ** tp[A] ** inv[Y] ** z + tp[z] ** tp[C2] ** C2 ** x - 
   tp[z] ** tp[C2] ** C2 ** z + tp[x] ** X ** B1 ** tp[B1] ** X ** z - 
   tp[x] ** X ** B2 ** tp[B2] ** X ** z + 
   tp[x] ** inv[Y] ** B1 ** tp[B1] ** inv[Y] ** x - 
   tp[x] ** inv[Y] ** B1 ** tp[B1] ** inv[Y] ** z + 
   tp[z] ** X ** B1 ** tp[B1] ** X ** x - 
   tp[z] ** X ** B1 ** tp[B1] ** X ** z - 
   tp[z] ** X ** B2 ** tp[B2] ** X ** x + 
   tp[z] ** X ** B2 ** tp[B2] ** X ** z - 
   tp[z] ** inv[Y] ** B1 ** tp[B1] ** inv[Y] ** x + 
   tp[z] ** inv[Y] ** B1 ** tp[B1] ** inv[Y] ** z
\end{verbatim}
}}

\centerline{Figure 4.2}

This expression has 29 terms and the highest order term has only 6 factors.
Notice that everything of the form inv[1-Y**X] and inv[1-X**Y] has been
eliminated
from $H$. This took 27 seconds on a SPARC II using NCAlgebra.
\footnote{%
The same computation took 1.8 secs using the special purpose system we have
used for research (running on a 486/33MHz PC).
\par
}

We expect our simplifier to replace high order terms by lower order terms.
The decrease in the number of factors in each term and the elimination of
complicated factors is the expected behavior. The simplifier can also, as in
this case, reduce the total number of terms. This is a consequence of the
fact that terms are reduced to a standard form. This can produce
cancellation of like terms. In our experience, 
%general we have found 
the Gr\"{o}bner
technology 
has been
very effective for simplifying expressions built from the type of
subexpressions discussed in Part I.

Notice that the transition from Figure 
4.1 to Figure 4.2 involves the use of
general purpose simplification tools. It uses information about the way $H$
is constructed as an algebraic expression, not on specialized information
from $H^\infty $ Control Theory.

\subsubsection{Proving a Theorem}
\label{Proving:a:Theorem}

A major theorem in $H^\infty $ Control Theory is that $H=0$ if the
Doyle-Glover-Khargonekar-Francis {\bf [DGKF]} Riccati relations hold. We
have simplified $H$ to obtain the expression $HYI$ which is still quite
complicated. We now introduce the assumption that the 
{\bf [DGKF]} Riccati
equations $DGKFX=0$ and $DGKFYI=0$ hold
%\footnote{
%As a matter of notation we will
%use $YI$ instead of $inv[Y]$ or $Y^{-1}$ in the 
%following calculations.},
where:

\[
%DGKFX=XA+A^TX+C_1^TC_1+XB_1B_1^TX-XB_2B_2^TX\mbox{\ \ \ \  and \ \ \ } 
DGKFX=-XB_2B_2^TX+XB_1B_1^TX+C_1^TC_1+A^T X + XA\mbox{\ \ \ \  and \ \ \ } 
\]
\[
%DGKFYI=Y^{-1}A+A^TY^{-1}+C_1^TC_1-C_2^TC_2+Y^{-1}B_1B_1^TY^{-1}.%
DGKFYI=Y^{-1}B_1B_1^TY^{-1}-C_2^TC_2+C_1^TC_1+A^TY^{-1}+Y^{-1}A.%
\mbox{\ \ \
\ \ \  } 
\]

An ordering for the variables was chosen essentially at random
by our computer program:

$A<B_1<B_2<C_1<C_2<x<X<Y^{-1}<z<A^T<B_1^T<B_2^T<C_1^T<C_2^T<x^T<z^T$.

This is done in NCAlgebra using the command 
\[
SetMonomialOrder[%
\{A,B1,B2,C1,C2,x,X,inv[Y],z,tp[A],tp[B1],tp[B2],tp[C1],tp[C2],tp[x],tp[z]\}]%
\,. 
\]

The NCAlgebra command 
\[
GroebnerSimplify[HYI,\{DGKFX,DGKFYI\}]
\]
computes the reduction of $HYI$ with respect to the Gr\"{o}bner Basis
generated by $DGKFX$ and $DGKFYI$. The result of the simplification of $HYI$
using the above command was zero. The computation took 116 seconds using
NCAlgebra.\footnote{%
Using the special-purpose research software it took 5.1 secs to calculate
the Gr\"{o}bner Basis and 0.4 secs to perform the reduction. NCAlgebra is
integrated with Mathematica and is therefore slower. 
}

We have just obtained
\footnote{
The idea of the proof is this: 
The fact that $HYI$ reduces to zero using the GB obtained from 
the DGKF Riccati
equations shows that $HYI$ is in the ideal generated by 
$DGKFX$ and $DGKFYI$. That is,
$HYI$ is a sum of terms of the form $c{\cal L}f{\cal R}$ where $c$
is a number, $\cal{L}$ and $\cal{R}$ are monomials, 
and $f$ is either $DGKFX$ or $DGKFYI$. 
Thus, if matrices are substituted for the variables, a
substitution which solves the DGKF equations will also make $HYI=0$.
}
the classic result:

\noindent
{\bf Theorem} {\it The Hamiltonian of the closed loop system based on
the central controller is identically zero if $X$ and $Y$ satisfy the two
Doyle Glover Khargonekar Francis Riccati equations $DGKFX=0$ and $DGKFYI=0$.}


\subsection{Comments}
\label{section:five}

%{\BF Delete and reference part 1??
%It is important to understand why this computation proves the theorem. The
%fact that $HYI$ reduces to zero using the GB obtained from the DGKF Ricatti
%equations shows that $HYI$ is in the ideal generated by $DGKFX$ and $DGKFYI$
%(i.e. it is a sum of terms of the form $c\cal{L}f\cal{R}$ where $c$
%is a number, $\cal{L}$ and $\cal{R}$ are monomials, 
%and $f$ is either $%
%DGKFX$ or $DGKFYI$). If matrices are substituted for the variables, a
%substitution which solves the DGKF equations will also make $HYI=0$.
%}

In the proof in Section \ref{Proving:a:Theorem}
we produce a GB from relations special to the problem. The
goal is to examine consequences of these relations. 
Gr\"{o}bner Bases are applicable in other areas which involve matrix expressions. 
We emphasize that when working in $H^\infty$
control, one often knows the DGKF Riccati equations hold.
It is, therefore, natural to introduce these relations
as hypothesis and seek to draw conclusions from them.
We have used a well known theorem to illustrate
the process. The ideas which we have presented
can be just as useful when the answer is not known
in advance.
%Thus, these methods are valuable for simplifying formulas
%which occur in situations where you do not already know
%the answer at the beginning of the computation.
They can be a valuable tool for exploration. 
They can provide a quick way to check the correctness of 
a tentative set of assumptions. 
They can disclose additional
conditions needed for a theorem to hold. 
They can provide a proof for a
general theorem whose truth is suggested by examples or special cases.

\iffalse
\subsubsection{Appendix -- EDITOR SUGGESTS WE DELETE??}

Here is the Gr\"{o}bner basis for $DGKFX$ and $DGKFYI$ 
automatically computed and used in the previous
section.

{\small {\ 
\[
{X}{B_2}{B_2}^T{X}-{X}{B_1}{B_1}^T{X}-{C_1}^T{C_1}-A^T{X}-{X}A 
\]
%$$ 
%-{ X} A - A^T { X} - { C_{1}}^T { C_{1}} - 
%  { X} { B_{1}} { B_{1}}^T { X} + 
%  { X} { B_{2}} { B_{2}}^T { X}
%$$ 
\smallskip
\[
{Y^{-1}}{B_1}{B_1}^T{Y^{-1}}-{C_2}^T{C_2}+{C_1}^T{C_1}+A^T{Y^{-1}}+{Y^{-1}}A 
\]
%$$ 
%{ Y^{-1}} A + A^T { Y^{-1}} + { C_{1}}^T { C_{1}} - { C_{2}}^T { C_{2}} + 
%  { Y^{-1}} { B_{1}} { B_{1}}^T { Y^{-1}}
%$$ 
\smallskip
\begin{eqnarray*}
&&+{C_1}^T{C_1}{B_2}{B_2}^T{X}-{C_1}^T{C_1}{B_1}{B_1}^T{X}-{X}{B_2}{B_2}^T{%
C_1}^T{C_1}-{X}{B_2}{B_2}^TA^T{X} \\
&&+{X}{B_1}{B_1}^T{C_1}^T{C_1}+{X}{B_1}{B_1}^TA^T{X}+{X}A{B_2}{B_2}^T{X}-{X}A%
{B_1}{B_1}^T{X} \\
&&-{C_1}^T{C_1}A+A^T{C_1}^T{C_1}+A^TA^T{X}-{X}AA
\end{eqnarray*}
\smallskip
\begin{eqnarray*}
&&+{C_2}^T{C_2}{B_1}{B_1}^T{Y^{-1}}-{C_1}^T{C_1}{B_1}{B_1}^T{Y^{-1}}-{Y^{-1}}%
{B_1}{B_1}^T{C_2}^T{C_2}+{Y^{-1}}{B_1}{B_1}^T{C_1}^T{C_1} \\
&&+{Y^{-1}}{B_1}{B_1}^TA^T{Y^{-1}}-{Y^{-1}}A{B_1}{B_1}^T{Y^{-1}}+{C_2}^T{C_2}%
A-{C_1}^T{C_1}A \\
&&-A^T{C_2}^T{C_2}+A^T{C_1}^T{C_1}+A^TA^T{Y^{-1}}-{Y^{-1}}AA
\end{eqnarray*}
}}
\fi

%---------------------------------------------
%---------------------------------------------
%---------------------------------------------
%OLD FILE ch4.tex
%---------------------------------------------
%---------------------------------------------
%chlyp.tex 

\def\wimpfootnote{Because of limitations of the current
version of our computer
program, we only check this for $r=1$ and $s=-1$ ,but expect it to
hold for arbitrary scalars $r$ and $s$.}


\section{The Effects of Ordering: An Illustration with 
Lyapunov Equations }
\label{section:six}

In this section we  
shall examine GBs which arise in the study of Lyapunov equations. 
We shall see that, 
in some cases, the same starting relations will produce either a
finite or an infinite GB, depending on the term ordering. 
Finally, in
section \ref{sec:infty} we make some comments on the description of infinite Gr\"{o}bner
Bases by generating functions.



%%We continue our exploration of GB,
%%%to 
%%%Engineering System Theory, 
%%but now we 
%%investigate the selection of various orders
%%on the resulting GB. 
%%We saw one illustration of the effect of
%%term ordering in Section 5 on the 
%%discovery of the Youla-Tissi formulas. 
%%In part 1, we took the
%%viewpoint that one selected the ordering
%%consistent with a preordained idea of which expressions
%%are complicated and which expressions are simple.
%%In this section, the point is not so much 
%%to produce formulas you would make a permanent part of
%%a noncommutative simplification program, but to 
%%give an idea of the effect of selecting orders on whether
%%you get a finite or infinite GB. 
%%Since a GB can take considerable computer time to generate, it is clear
%%that generating and using a small GB is more efficient than generating a large (or infinite)
%%GB. 
%%Thus in a situation
%%where you do not have a strong bias toward a particular
%%order, you probably would try choosing an order which 
%%produces a finite (small even) GB. 

%%Section 6.1 analyzes GB which naturally arise
%%when studying Lyapunov equations.
%%Our emphasis is on the
%%effect of particular orders on whether or not one
%%obtains a finite GB. Hopefully, the findings in 
%%Section 6.1 give the reader practical intuition 
%%on which orders produce finite GB.

%%To test and illustrate the intuition obtained in Section 6.1
%%about Lyapunov equations, we consider the case of a lossless system
%%in Section 6.2.

%%The authors speculate that the issue as to whether 
%%a GB is finite or infinite may not be relevant in many
%%circumstances. Once an algebraic situation becomes
%%complicated, it is our experience that it is 
%%hard and possibly impossible to find a finite GB
%%(independent of the order one selects).

%----------------------------------------------------



\subsection{Lyapunov Equations}

If the Mora Algorithm terminates with a finite basis, this basis is
automatically a Gr\"{o}bner Basis. 
A finite basis is, therefore, advantageous.
In contrast, if the Mora Algorithm does not
terminate and is interrupted, a truncated list of rules produced
may be useful for simplifying expressions.
Also analysis of such a list can provide a convenient description of
an infinite Gr\"obner Basis.
However this type of analysis is not automated and can be time consuming.
It is often possible to find a convenient description for infinite
bases.
%Such a description is needed  
% but
%to prove the highly desirable 
%Gr\"{o}bner Basis Property.
%it is necessary to find a way to describe the infinite basis.
In this section we examine a situation in which the same set of starting
relations produce both finite and infinite bases depending on the choice of
term ordering. 
We will give some guidelines for obtaining a finite GB in the
case of the Lyapunov Equation and an application to Lossless systems.
The finite Gr\"obner Bases which we find in this
section are very small (e.g., {\bf around 30 relations}) and can
be generated with a computer in less than a minute.
%This is in marked contrast to the situation with infinite
%Gr\"obner Basis.

The Lyapunov Equation is one of the most common 
equations in engineering: 
\begin{equation}
am-mf-q=0\,.  \label{eq:6pt1lyp}
\end{equation}
Here $a$, $f$ and $q$ are typically given and $m$ is unknown, eventually to
be determined numerically. At the algebraic stages of the research,
 one often
is manipulating expressions in: $a$, $f$, $q$, $m$, $m^{-1}$, $a^{-1}$, $%
f^{-1}$ and the resolvents of $a$ and $f$. (We will not treat $e^{at}$ and $%
e^{ft}$ in this paper, although they do commonly arise.)
We take (\ref{eq:6pt1lyp}), together with some invertibility
assumptions as indicated, to be the starting 
relations for the GB process.

%\subsubsection{Term Ordering and the Lyapunov Equation}

The following chart summarizes the results of some experiments with term
ordering:

\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
{\bf Equation} & {\bf Assumptions} & {\bf Behavior} & {\bf Examples} \\ 
\hline
$am-mf-q=0$ & $a$ and $f$ invertible & finite for all & $%
m<a<a^{-1}<f<f^{-1}<q$ \\ 
&  & tested orders & $a<a^{-1}<f<f^{-1}<q<m$ \\ \hline
$am-mf-q=0$ & $a,f,m$ invertible & infinite for all & $q<a<a^{-1}<f<f^{-1}$
\\ 
&  & tested orders & $<m<m^{-1}$ \\ \hline
$am-mf-q_1q_2=0$ & $a,f,m$ invertible & finite for most & all orders in
which $q_1>$ \\ 
&  & tested orders & both $a$ and $f$ \\ \hline
$am-mf-q_1q_2=0$ & $a,f,m$ invertible & infinite for at & $%
q_1<q_2<a<a^{-1}<f $ \\ 
&  & least one order & $<f^{-1}<m<m^{-1}$ \\ \hline
\end{tabular}
\end{center}

\centerline{Table 6.1}

Notice that the finitude of the GB depends on whether or not $m$ is
invertible, whether we use a `$q$' (with total degree 1) or `$q_1q_2$' (with
total degree 2) as the affine term, and the choice of ordering. In many
engineering applications the affine term `$q$' 
in (\ref{eq:6pt1lyp}) is a
quadratic of the form $q_1q_2$. For example, $Am-mA^T=C^TC$ is a familiar
expression which has this property. The results above show that a
Gr\"{o}bner Basis obtained from this relation (together with the defining
relations for the inverses) will be finite for suitably chosen orders.

It is common to manipulate expressions which contain the resolvents $%
(r-a)^{-1}$ and $(s-f)^{-1}$ where $r$ and $s$ are scalars. When we add
these resolvents, similar conclusions are reached. In particular, it seems
that if $m$ and $m^{-1}$ are high in the order, we obtain an infinite
Gr\"obner Basis while if $m$ and $m^{-1}$ are low in the order, the basis is
finite.


\subsection{Infinite Families and Generating Functions}
\label{sec:infty}


%Most of the infinite Gr\"{o}bner Bases which arise in this paper consist of
%one or more families of relations whose elements are produced by changing a
%variable exponent. It should be noted that infinite families parametrized in
%this way can easily be used in reduction. 
%The formula for generating the
%family can be stored as a function of the exponent $n$. Instances of the
%%rules are generated as necessary. Since reduction only uses basis
%polynomials whose leading term occurs in the polynomial being reduced, most
%reductions can also be handled by storing instances of the general rules up
%to a sufficiently high $n$. In this way, a computer system is actually able
%to use an infinite set of reduction rules.

In \S \ref{section:preNF}, we gave
a GB for $(preNF)$ which was infinite. This GB
consisted of a finite set of polynomials together
with 8 infinite collections of polynomials. Each of
these collections of polynomials was parameterizable using
a single integer. 
There are other interesting ways to describe the 
members of an infinite
family. 
Here we will explore the use of generating functions. A generating function
can often be found which has the members of the family 
appearing as coefficients in
its expansion.

Here is an example which is related to the Lyapunov Equations discussed
in this section. We found that we obtain an infinite basis in some
situations (Table 6.1). For example, if one uses the 
starting relation  $a m - m f - q$ with the order
$a<f<q<m<m^{-1}$,
%\[
%\begin{array}{l}
%am-mf-q\text{ \ \ with} \\ 
%a<f<q<m<m^{-1}
%\end{array}
%\]
the Mora Algorithm produces general rules:
\[
\begin{tabular}{l}
$L_1(n)=m^{-1}a^nm-\sum\limits_{k=0}^{n-1}m^{-1}a^kqf^{n-1-k}-f^n$ \\ 
$L_2(n)=\sum%
\limits_{k=0}^{n-1}m^{-1}a^kqf^{n-1-k}m^{-1}-m^{-1}a^n+f^nm^{-1} $%
\end{tabular}
\]
for $n\ge 0$.
If we set
%$\begin{tabular}{l}
$GenFun(\lambda )=m^{-1}(1-\lambda a)^{-1}m-m^{-1}(1-\lambda a)^{-1}\lambda
q(1-\lambda f)^{-1}-(1-\lambda f)^{-1}$
%\end{tabular}$
, 
then
\[
GenFun(\lambda )=\sum\limits_{k=0}^\infty L_1(k)\lambda ^k  \, .
\]

Generating functions like this occur in classical studies of Lyapunov
equations. 
For example, if the spectrum of $a$ and $f$ are
disjoint, then the integral equation
$$
\int_Q \frac{m}{\xi} GenFunc(\frac{1}{\xi}) d\xi = 0
$$
yields
the commonplace formula
\begin{equation}
m = \int_Q 
\left(
\xi - a
\right)^{-1}
q
\left(
\xi - f
\right)^{-1}
d\xi
\end{equation}
for $m$.
Here the contour $Q$ is chosen so that the
spectrum of $a$ 
lies inside
of $Q$ and the spectrum of $f$ lies outside of $Q$.
%PROOF: Look at 
%$$\frac{m}{\lambda} GenFunc(\lambda) d\lambda = 0$$
% Do the change of variables $\mu = \frac{1}{\lambda}
% Use integration.
%
%the the spectrum $
%The famous Kato-Rosenblum 
%formula, c.f. {\bf [??]},
%for $m$ is derived from such a
%generating function expression.

      


%%{\bf WAVRIK WILL REWRITE  2-6-95
%%Most of the infinite Gr\"{o}bner Bases which arise in this paper consist of
%%one or more families of relations whose elements are produced by changing a
%%variable exponent. It should be noted that infinite families parametrized in
%%this way can easily be used in reduction.
%%It has been our practice, for example, to store the formula for
%%generating the family as a function of the exponent $n$. For efficiency, we
%%generate and store instances of the family up to a relatively high value of $%
%%n$. Since reduction only uses basis polynomials whose leading term occurs in
%%the polynomial to be reduced, we handle most reductions using the stored
%%rules. The functional representation of the general rules allows other
%%instances to be generated when necessary. In this way, a computer system is
%%actually able to implement an infinite set of reduction rules.
%%
%%There are other interesting ways to describe the members of an infinite
%%family. Notice that in Section 5, the relations Gen[2], which are part of
%%the GB for (5.1)-(5.3), were taken as the coefficients of powers of $s$ in
%%the expansion of (5.4). This is an example of the representation of a
%%parametrized family by a generating function.
%%
%%Here is an example related to the Lyapunov Equations.
%%}
%%
%%{\bf 
%%WAVRIK WILL WORK ON 2-6-95
%%
%%
%%\subsubsection{Appendix --- Parameterization of GB}
%%
%%This appendix gives two remarks on the GB in section 6.1.
%%The first remark is 
%%that even the infinite lists produced in line 2
%%of the Table 6.1
%%have finite parameterizations. We analyzed
%%line 2 of Table 6.1 with the ordering
%%$ a<f<q < m< Inv[m]$
%%and found that the rules below together with the
%%starting relations explain all of the output
%%from 
%%%our (NCAlgebra) implementation of 
%%Mora's algorithm.
%%%
%% %-q + a ** m + m ** f, -1 + m ** Inv[m],
%% % -1 + Inv[m] ** m, 
%%%
%%%Special rules: 
%%%$f-Inv[m] ** q + Inv[m] ** a ** m$,
%%
%%%MXS VERSON
%%%$$  Relg[n]:=(-1)^{n+1}(f^n) -
%%%     \Sigma_{k=0}^{n-1} (-1)^k 
%%%         m^{-1} \, a^{n-1-k} \,  q \,  f^k +
%%%     m^{-1} \, a^n \, m   
%%%$$
%%% WAVRIK VERSION
%%$$  Relg[n]:= m^{-1} a^n m -
%%     \Sigma_{k=0}^{n-1} 
%%         m^{-1} \, a^{k} \,  q \,  f^{n-k-1}  - f^n
%%%%$$
%%%$$   
%%%(-1)^{n+1} f^n \, m^{-1} -
%%%     \Sigma_{k=0}^{n-1} 
%%%     (-1)^k m^{-1} \, a^{n-1-k} \, q \, f^k \, m^{-1} +
%%%     m^{-1} \, a^n
%%and 
%%%%MXS VERSION
%%%$$  Relg^\prime[n]:=(-1)^{n+1}(f^n) \, m^{-1} - 
%%%m^{-1}
%%%\left[ 
%%%\Sigma_{k=0}^{n-1} (-1)^k 
%%%\, a^{n-1-k} \,  q \,  f^k \right] 
%%%m^{-1} +
%%%     m^{-1} \, a^n  
%%%$$
%%%WAVRIK VERSION
%%$$  Relg^\prime[n]:= m^{-1} q f^n m^{-1} + 
%%\Sigma_{k=1}^{n} m^{-1}
%%\, a^{k} \,  q \,  f^{n-k} m^{-1}  - m^{-1} a^{n+1}
%% + f^{n+1} m^{-1} 
%%$$
%%for $n= 0, 1,2,\ldots$. Notice that $Relg^\prime[n]$ is
%%the expression one gets by replacing $m m^{-1}$ by 1 in 
%%$Relg[n] m^{-1}$.
%%
%%The second remark is more novel.
%%While we did not find natural functional calculus 
%%intreptations a la Section 2, there is a 
%%pretty description of $Relg$ and $Relg^\prime$
%%in terms of generating functions. Namely,
%%$Relg$ corresponds to
%%{\bf NEED TO CHECK a become m in last term??}
%%$$
%%-(1+\lambda f)^{-1} + m^{-1} (1-\lambda a)^{-1} m
%%+ a^{-1} \lambda (1-\lambda a)^{-1} q (1-\lambda f)^{-1}
%%$$
%%while $Relg^\prime$ amounts to  
%%this expression multiplied by $m^{-1}$.
%%In other words, expand these functions in powers of
%%$\lambda$,
%%then the coefficients 
%%of $\lambda ^n$ are 
%%$Relg[n]$ and $Relg^\prime[n]$.
%%{\bf
%%This points out that there are at least two ways of
%%characterizing infinite sets of relations.
%%Some can be easily
%%described in terms of functional calculus while some
%%which are not easily described in terms of the functional
%%calculus, can be described by a generating function.
%%
%%Generating functions like the one above
%%occur in classical studies of Lyapunov
%%equations. For example, the famous
%%Kato-Rosenblum formula for $m$ is derived
%%from such a generating function expression.
%%}
%%
%%
%----------------------------
%I THINK THIS IS FALSE??--DELETE
%
%It is clearer if we begin with the simpest cases.
%
%$a, f$, $q \ \ take it =0 ??$, $m$
%$$ a m -m f-q=0$$
%
%%All S-polynomials the form ??
%
%$a^n m -m f^n $
%- stuff \ \  with \ \ no \ \m \ \in \ \it. 
%What else??
%
%This is the set of equations one sees classically.
%
%However when one reduces this by
%$$ a m \rightarrow m f+q$$
%one gets that only ?? remains
%
%If we add one relation and use the order
%$$m im-1, \ \ im m-1$$
%$$same ??? $$
%%%%then we get 
%$$m^n a m^{-n} -f??$$
%{\it even after reduction}. So in this situation
%whether one gets a finite or infinite 
%GB depends on the reduction step inside the computer
%algorithm. 
%
%Even if we use other orders we find ?? 
%this phenomenon,  falls apart, remains? etc
%}
%---------------------------------------------
%---------------------------------------------
%---------------------------------------------
%OLD FILE ch6_ret*.tex
%---------------------------------------------
%---------------------------------------------

%chlyp.tex 
%
%\def\wimpfootnote{Because of limitations of the current
%version of our computer
%program, we only check this for $r=1$ and $s=-1$ ,but expect it to
%hold for arbitrary scalars $r$ and $s$.}
%
%------------
%%
%

%---------------------------------------------
%---------------------------------------------
%OLD FILE ch5.tex
%---------------------------------------------
%---------------------------------------------


\section{Gr\"obner Bases Spawn Interesting Formulas }
\label{section:yt}

%The Gr\"obner theory starts with a set of relations and
%produces new relations. The primary purpose of the algorithm is
%to produce a ``complete'' set of relations.
%While it does not  
%generate all possible relations,
%the new relations 
%it does generate
%%produced by the algorithm 
%are often
%of intrinsic interest.
%
%Our experience 
%%We now 
%shows how the
%famous formulas of Youla and Tissi {\bf [YT]}
%% {\bf [C]}, 
%for system similarity emerge
%directly from a GB as does
%half of the State Space Isomorphism Theorem.

%This section is somewhat different in spirit than the
%rest of the paper in that it does not treat
%simplification. 
Rather than viewing the Gr\"obner Basis Algorithm as
a means towards the end of simplification, 
we view it in this section as a means
for 
%The technology we have been using for simplification is essentially
%a technology for 
obtaining algebraic consequences 
of a set of equations.
We will provide a simple illustration of how this 
occurs
%can be useful 
in a familiar system engineering context.
Our example
%We now
shows how the
famous formulas of Youla and Tissi {\bf [YT]}
% {\bf [C]},
for system similarity emerge
directly from a GB as does
half of the State Space Isomorphism Theorem.
One thing we shall see is that
the occurrence of an infinite GB in this case is quite natural.
For example, 
%in the example considered, 
the elements of the 
infinite GB appear as coefficients
of the power series expansions of frequency response function.
%Therefore, the infinite GB points toward what 
%%and corresponds roughly to formulasthe 
%what engineers have traditionally done by hand.

\subsection{State Space Isomorphism Theorem}

A basic theorem of system theory, the {\it State Space 
Isomorphism Theorem},  
says that two controllable and observable 
systems with identical frequency response function $T$
are ``similar". 
Systems $(a,b,c,d)$ and $(A,B,C,d)$
are said to be similar if 
there is a map m satisfying

\begin{equation}
m^{-1} A m = a
\label{eq:5pt1}
\end{equation}
\begin{equation}
c m^{-1} = C
\label{eq:5pt2}
\end{equation}
\begin{equation}
m b = B \, .
\label{eq:5pt3}
\end{equation}

It is natural to generate a GB for these relations
in order to 
discover consequences. The defining relations for $m^{-1}$
together with (\ref{eq:5pt1}), (\ref{eq:5pt2}) and
(\ref{eq:5pt3}) 
were used as starting relations for the Mora Algorithm:
%%Let us suppose that (\ref{eq:5pt1}), (\ref{eq:5pt2}) and 
%%(\ref{eq:5pt3}) hold and see what we can conclude
%%from automatic symbol manipulation. 
%%%For example, can we obtain  the obvious fact that the two systems 
%%%have the same frequency response function? 
%%To investigate this, we ran the Mora algorithm  on 
%%symbols $a$, $b$, $c$, $A$, $B$ and $C$
%%with starting relations (\ref{eq:5pt1}), (\ref{eq:5pt2}), 
%%(\ref{eq:5pt3})
%%and 
%%graded lexicographical order 
%%on monomials 
%%induced by
%%$A<B<C<a<b<c<m<m^{-1}$.
%%
%%Mora's algorithm produced an infinite 
%%list. 
%%So the first order of business for understanding
%%what is happening is to try to produce an
%%elegant description of the list.
%%We did this by ad hoc methods.
%%
%%\baselineskip=12pt
\[
\begin{tabular}{l}
$Rel[0]=m^{-1}m-1$ \\
$Rel[1]=mm^{-1}-1$ \\
$Rel[2]=m^{-1}Am-a$ \\
$Rel[3]=cm^{-1}-C$ \\
$Rel[4]=mb-B$%
\end{tabular} \, .
\]
The ordering used was the
graded lexicographical order 
induced by
$A<B<C<a<b<c<m<m^{-1}$.

When we run Mora's Algorithm on $Rel[0]$-$Rel[4]$, the
algorithm does not terminate in a short time and 
so we interrupted it and viewed the set which had been
produced
up to that point (see Section \ref{subsection:GroebnerBases}).
It was apparent that the Gr\"obner Basis was not finite.
Computations by hand showed that the 
%An independent proof produced 
%
%The 
reduced Gr\"obner basis is the starting relations 
$Rel[0]-Rel[4]$
together with the special relations
\[
\begin{tabular}[t]{l}
$Rel[5]=ma-Am$ \\
$Rel[6]=m^{-1}A-am^{-1}$ \\
$Rel[7]=Cm-c$ \\
$Rel[8]=m^{-1}B-b$ 
\end{tabular}
\]
and general rules
\[
\begin{tabular}[t]{l}
$Gen[1]=CA^km-ca^k$ \\
$Gen[2]=ca^kb-CA^kB$ \\
$Gen[3]=ca^km^{-1}-CA^k$%
\end{tabular}
\]
for all $k\ge 0$.

%%\begin{verbatim}
%%     Special Rules
%%Rel[5] = m ** a - A ** m ;
%%Rel[6] = Inv[m] ** A - a ** Inv[m] ;
%%Rel[7] = C**m - c ;
%%Rel[8] = Inv[m] ** B - b ;
%%
%%     General Rules
%%Gen[1] = C ** A^k ** m  - c ** a^k
%%Gen[2] = c ** a^k ** b  - C ** A^k ** B  
%%Gen[3] = c ** a^k ** Inv[m] - C ** A^k
%%\end{verbatim}

%%\baselineskip=18pt
%%\noindent
%%for all $k \ge 0$.

We now recall that two system have the same frequency response function if
\begin{equation}
1+c(s-a)^{-1}b=1+C(s-A)^{-1}B  \label{eq:5pt4}
\end{equation}
for all $s\in \Cplane$ such that both $s-a$ and $s-A$ are
invertible. If (\ref{eq:5pt4}) is expanded in powers of $s$, we find that
the coefficients of the various powers (called Markov parameters)
are precisely the relations $Gen[2]$.
Thus we have shown that similar systems have the same 
%frequency response function; 
Markov parameters;
indeed this is the content of $Gen[2]$.

Also note that if the defining relations for $(s-a)^{-1}$ and $(s-A)^{-1}$ 
are added to the starting relations using the order
$$
A<B<C<a<b<c<m<m^{-1}<(s-a)^{-1}<(s-A)^{-1}\, ,
$$
then (\ref{eq:5pt4}) itself is in the GB. 
Thus we see several ways 
in which the 
Gr\"{o}bner process
could be interpreted as producing formulas
which prove
%give proofs of
one half the Statespace
Isomorphism Theorem. 

\subsubsection{The Youla-Tissi Formulas}

Now we turn to the interpretation of 
$Gen[1]$
and
$Gen[3]$.

Recall the famous formulas 
(due to Youla and Tissi 
{\bf [Y-T]})
for the state space
isomorphism $m$ which say that it intertwines the controllability operators
and observability operators of the system. In our notation these say
$$
\leqno{\mbox{(Y-T)}}
\hspace{.5in}
ma^kb-A^kB=0\ \ \mbox{and}\ \
CA^km-ca^k=0
$$
for all $k\ge 0$.
 
We see that $Gen[1]$ is exactly the second of the (Y-T) formulas
while $Gen[3]$ is a simple variant of it. The first of
the (Y-T) formulas reduces to zero (using Rel[5] and Rel[4]). So both the
controllability and observability formulas have been shown to be a
consequence of the relations which define similarity.

%What is interesting here, is
It is interesting to note that 
that the second 
(Y-T) formula explicitly appears in
the GB while the first (Y-T) formula does not. One might wonder why only one of these
formulas appears in the basis. In the next section we will discuss the
dependence of a GB on the ordering chosen for the variables. It will be
shown that there are term orderings for which the first of the (Y-T)
formulas does appear in the GB.
 


\subsubsection{Term Ordering and Similarity of Systems}

In this subsection  we examine the similarity relations in terms of orders.
We find
that different sets of relations are produced if we choose a different
order in the context of 
the Youla-Tissi relations. 

In Section \ref{section:yt}
we showed that the relations which define similarity of systems
produce a GB in which the second of the Youla-Tissi formulas occurs
explicitly. The term ordering we used was
$$
A<B<C<a<b<c<m<m^{-1} 
$$
\noindent
The first of the (Y-T) formulas reduced to zero. 
It was shown, therefore, to
be an algebraic consequence of the similarity relations, but it 
did not explicitly occur in the GB. 

We now use the same starting relations but change the
ordering to
$$
m<m^{-1}<A<B<C<a<b<c 
$$
making $m$ and $m^{-1}$ lowest in order rather than highest. 
This ordering produces a different set of general relations:
$$
\begin{tabular}{l}
$Gen^{\prime }[1]=ca^kb-CA^kB$ \\ 
$Gen^{\prime }[2]=ma^kb-A^kB$ \\ 
$Gen^{\prime }[3]=m^{-1}A^kB-a^kb$%
\end{tabular}
$$
The first (Y-T)
formula occurs explicitly as $Gen^{\prime }[2]$ for this set of relations
while it did not appear explicitly in the ordering used in 
Section \ref{section:five}. We
see, therefore, that both the Youla-Tissi observability and controllability
formulas are automatically generated by the Mora algorithm applied with 
suitable orderings.

%------------------------------------------------------------------------
%------------------------------------------------------------------------
%------------------------------------------------------------------------
%------------------------------------------------------------------------
%------------------------------------------------------------------------
%------------------------------------------------------------------------
%%Recall that the 
%%famous formula (due to Youla  and Tissi)
%%for the state space isomorphism $m$ which says that it intertwines
%%the controllability operators and observability operators 
%%of the system. 
%%In our notation these say
%%$$
%%\leqno{\mbox{(Y-T)}} 
%%\mbox{\ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }
%%m a^k b - A^k B=0 \ \ \mbox{and} \ \  C A^k m  - c a^k =0
%%$$
%%for all integers $k\ge 0$.
%%
%%We see that Gen[1] is exactly the second of the
%%(Y-T) formulas. 
%%The first of the (Y-T) formulas
%%reduces to zero using Rel[5] and Rel[4] and so
%%does not appear in the output from Mora's algorithm.
%%
%%While this is a very simple situation, it does show that 
%%the relationships which the computer automatically (after 
%%interpretation) generates amount to the Youla Tissi formula for $m$
%%when the systems are observable.
%%Conspicuously missing
%%is the famous controllability formula.
%%%$$ m  a^k  b - A^k B $$ for $m$.
%%Thus we might ask if this would be produced by the Mora
%%algorithm with a different choice of ordering.
%%If, for example, we use the ordering
%%$$
%%m<m^{-1}< A < B<C<a<b<c
%%$$
%%%the Mora algorithm 
%%%applied to the starting relations above
%%%produced the starting relations 
%%%except for 
%%
%%%\baselineskip = 12pt
%%%\begin{verbatim}
%%%Inv[m]**A**m - a
%%%\end{verbatim}
%%
%%%\noindent
%%%plus the relations listed below.
%%
%%%\begin{verbatim}
%%%     Special Relations
%%%
%%%C ** m - c
%%%Inv[m] ** B - b
%%%Inv[m] ** A ** B - a ** b
%%%m ** a - A ** m
%%%Inv[m] ** A - a ** Inv[m]
%%%m ** a ** b - A ** B
%%%
%%%\end{verbatim}
%%\baselineskip = 12pt
%%\begin{verbatim}
%%     General Relations
%%
%%Gen'[1] = Inv[m] ** (A^k)** B - (a^k) ** b
%%Gen'[2] = c ** (a^k) ** b - C ** (A^k) ** B 
%%Gen'[3] = m ** (a^k) ** b - (A^k) ** B
%%\end{verbatim}
%%for all $k \ge 0$.
%%
%%\baselineskip = 18pt
%%
%%Using this order, the first (Y-T) formula occurs as Gen'[2].
%%%This certainly includes the controllability operator based formula for $m$.
%%Intermediate orders produce mixtures of the relations above. 
%%For example,
%%$$
%%m^{-1}< A < B<C<a<b<c< m
%%$$
%%produces both\footnote{The relations generated are 
%%actually
%%the (Y-T) formulas multiplied by $m^{-1}$.}
%%the observability formula for $m$ and the 
%%controllability formula for $m$
%%and some of the other infinite relations found in the previous
%%two examples.
%%{\bf
%%In the next section we investigate the effects of term
%%orders in another class of examples.??}
%%
%%Two systems have the same frequency response function
%%if
%%\begin{equation}
%%\label{eq:5pt4}
%%1+c(s-a)^{-1}b= 1+C(s-A)^{-1}B 
%%\end{equation}
%%for all $s \in \Cplane$ such that both $s-a$ and $s-A$ are
%%invertible. If (\ref{eq:5pt4}) is expanded in powers of $s$,
%%we find that the coefficients of the various powers
%%are precisely the relations $Gen[2]$. The fact that 
%%similar systems have the same frequency response function
%%is obtained from relations generated automatically.
%%If the defining relations for $(s-a)^{-1}$ and $(s-A)^{-1}$
%%are added with the order
%%$$
%%A < B< C < a < b < c < m < m^{-1} < (s-a)^{-1} < (s-A)^{-1}
%%$$
%%then (\ref{eq:5pt4}) itself appears among the 
%%generated relations.
%%
%%Thus a proof of one half the Statespace Isomorphism Theorem
%%comes from examining new relations produced using the
%%Gr\"obner process. 
%%%One can also address the the harder problem of 
%%%assuming the two systems have the same frequency response function
%%%$$
%%%1+b(s-a)^{-1}c= 1+B(s-A)^{-1}C 
%%%$$
%%%for all $s \in \Cplane$ such that both $s-a$ and $s-A$ are
%%%invertible and showing that there exists $m$ such that
%%%(\ref{eq:5pt1}),
%%%(\ref{eq:5pt2}) and 
%%%(\ref{eq:5pt3}) hold.
%%%We approach this problem by deriving the GB for the 
%%%relations produced
%%%by the above equation together with
%%%$$
%%%(s-a)^{-1} (s-a)=1  \ \ \ \ \ 
%%%(s-A)^{-1} (s-A)=1 \,.
%%%$$
%%%We did this and found as expected  that the Mora 
%%%algorithm generated an infinite list of increasingly complicated expressions. 
%%%Naturally, the 
%%%algorithm is incapable of creating a new variable $m$
%%%which when used correctly in the formulas makes them much less complicated.
%%%This illustrates what might ultimately be one of the
%%%main limitations of GB for engineering computations. One needs to 
%%%know all of the objects you are going to use initially. 
%%%The computer is not going to 
%%%construct one.
%%
%%%Now that we have completed an example of purely
%%%pedagogical interest where the GB is essentially
%%%already known and amounts to a standard fact in systems theory.
%%%The rest of the article deals with system similarity
%%%where the GB is are not already known.
%%%%%%

\part{APPENDIX}

\appendix

\setcounter{equation}{0}

\section{Remarks on special situations}

%\noindent
%{\bf Exploiting finite dimensions:}

\subsection{Exploiting finite dimensions}

What we have done in this paper is purely algebraic and a 
formula derived by these methods takes no account of
whether one is working with matrices on an $n$ dimensional space,
operators on a Hilbert space or on a Banach space, be they bounded
or unbounded.
Many of us wish to work with finite dimensional
matrices and are fully willing to use the fact that they are
finite dimensional.
An interesting question
is: can one formulate the finite dimensionality in an algebraic way
which fits well with the techniques of this paper?

%{\bf ------- DELETE -------}
%
%A common suggestion is that if we wish to work on $n$ dimensional
%space for a fixed $n$, then we should use the algebraic fact 
%that each matrix $M$
%satisfies a polynomial  $p$ of degree $n$
%(the Cayley-Hamilton Theorem).
%Unfortunately, the polynomial $p$ itself depends on $M$,
%{\bf ?? HERE} indeed we should write $p_M(M)=0$.
%Moreover, knowning that the atomic variables 
%$x_1,\ldots,x_k$ in a problem,
%each satisfy a polynomial $p_j(x_j)=0$ does not imply that each 
%element of the algebra $x_1,\ldots,x_k$ generate satisfies a polynomial.
%Consequently, using the Cayley-Hamilton Theorem
%to impose finite dimensionality does not fit the mold of the paper.
%Indeed, when a specialist uses the Cayley-Hamilton Theorem
%in a derivations, he typically applies it to one or two
%matrices which he has carefully constructed. In this
%context,
%it might well be useful to adjoin a Cayley-Hamilton
%equation to a computer algebra session.
%
%{\bf ------- END DELETE -------}

A common suggestion is that we use the Cayley-Hamilton 
Theorem if we work in an $n$
dimensional
space for a fixed $n$.
The fact that every matrix $M$
satisfies a polynomial equation of degree $n$ would, at first
glance, seem to
provide a way for reducing higher powers of matrices to
lower powers and
eliminate infinite families of simplification rules. The
main problem with
this is that the characteristic polynomial, $p(M)$, of the
matrix $M$ has
coefficients which depend on $M$.
%There is no simple relationships among the
%characteristic polynomials of a set of matrices and the
%characteristic
%polynomials of sums and products of these matrices. 
%, then we should use the algebraic fact
%that each matrix $M$
%satisfies a polynomial  $p$ of degree $n$
%(the Cayley-Hamilton Theorem).
%There are two immediate problems which occur. 
%First, unless we knew explicitly what the 
%polynomial $p$ was, we would have to construct a
%polynomial of degree $n$ whose coefficients were symbolic
%and this
%would introduce produce a vastly larger problem.
%The second and more fundamental problem
%is that the polynomial $p$ itself depends on $M$.
Thus even if we knew the 
characteristic polynomial for each 
of the atomic variables
$x_1,\ldots,x_k$ in the problem, we would not
necessarily know the characteristic polynomial
for any sum, product, etc. of the atomic variables.
Consequently, using the Cayley-Hamilton Theorem
to impose finite dimensionality does not 
give rules which apply in general.
%fit the mold of the paper.
Indeed, when a specialist uses the Cayley-Hamilton Theorem
in derivations, he typically applies it to one or two
matrices which he has carefully constructed. In this
context,
%it might well be useful to 
one might
adjoin a characteristic
polynomial equation to a computer algebra session
to obtain results for a particular matrix.

%Closer to what a researcher does is to impose the eigenvector
%identity  $A X = \lambda X$ on a few carefully chosen matrices $A$.
%Here $\lambda$ commutes with everything.
%Which $A$ to choose in your particular problem is hardly automatic
%and indeed is a great art. Again note that the atomic expressions
%may all satisfy 
%$A_i X_i = \lambda_i X_i$
%type identities without a particular matrix $A$ in the algebra they generate
%satisfying such an identity.
%

%\noindent
%{\bf Square vs nonsquare matrices:}

\subsection{Square vs nonsquare matrices}

Another question which arises is how do these techniques handle
nonsquare matrices. At first glance it appears that 
there is a problem because the setting for this
paper  is an algebra, to wit we may multiply any two matrices,
while if, for example, $B$ is not a square matrix,
then $B B$ is not meaningful.
In other words,
when the matrices involved
are all square matrices of the same size, the translation
between polynomials and matrix expressions is clear and simple.
Any product of variables makes sense.
On the other hand, when the matrices involved are not all 
square matrices, then
some products and some sums of matrices are 
allowed while others are not.

We begin by considering
a collection of polynomials
which we call
\textbf{allowable}. This is done in a purely algebraic way
by attaching to
each variable, $x$, a pair of numbers $r(x)$ and $c(x)$ 
(which will correspond to the number of rows and columns
for the matrix which will be substituted for $x$ in the 
problem). We allow only
products of elements with compatible dimensions.
We can attach dimensions to any allowable
product\footnote{%
The empty product $1$ is considered to be
allowable, but it is not
assigned dimensions. It acts as if $r(1)=c(1)=n$
for
arbitrary $n$.}. A polynomial is allowable if each term is
allowable and all
the terms have the same dimensions. Intuitively, these are
polynomials
which
produce meaningful matrix expressions when we substitute
matrices of the
proper dimensions for the variables.

%{\bf ------- DELETE ------- }
%
%We can handle this by defining a collection of polynomials
%which we call
%\textbf{allowable}. This is done in a purely algebraic way
%by attaching to
%each variable, $x$, a pair of numbers $r(x)$ and $c(x)$ (the
%dimensions)
%allowing only products whose factors have compatible
%dimensions. We can attach dimensions to any allowable
%product\footnote{%
%The empty product $\varepsilon $ is considered to be
%allowable but it is not
%assigned dimensions. It acts as if $r(\varepsilon
%)=c(\varepsilon )=n$
%for
%arbitrary $n$.}. A polynomial is allowable if each term is
%allowable and all
%the terms have the same dimensions. Intuitively, these are
%polynomials
%which
%produce meaningful matrix expressions when we substitute
%matrices of the
%proper dimensions for the variables. We then prove that if
%the startingrelations for the Mora Algorithm are allowable,
%then any relation it
%produces is allowable.
%
%
%The more general issue involves the following conjecture.
%
%
%Given prespecified sizes for matrices, we first isolate
%the collection of polynomials which yield well-defined
%matrix expressions when the matrices are substituted
%for the variables. This class of  polynomials is formalized
%by the next definition.
%
%%
%\begin{defin}
%\label{defin:valid}
%Let $p\in K[x_1,\ldots,x_n]$ and
%$\sigma : \{1,\ldots,n\} \rightarrow {\bf N}\times {\bf N}$.
%We say that $p$ is valid
%for $\sigma$ if 
%\begin{description}
%\item{(1)}{ one obtains a
%matrix (that is, all of the products and sums are
%well-defined) 
%whenever one substitutes a $r_k \times s_k$ matrix $M_k$
%for $x_k$ in $p-p(0)$ where $\sigma(k) = (r_k,s_k)$
%for $1 \le k \le n$}
%\item{(2)}{ the matrix in (1) is square if $p(0)\not=0$.}
%\end{description}
%%If $p(0)\not=0$, then we say that $p$ is valid
%%for $\sigma$ if $p-p(0)$ is valid for $\sigma$
%%and the substitution in $p-p(0)$
%%of the matrices for the variables yields a square matrix.
%\end{defin}
%
%{\bf -------- END DELETE --------- }

Note that, in our examples, the starting relations
correspond to allowable matrix expressions
and all the relations obtained correspond
to allowable matrix expressions.
This phenomenon is true at a great level of generality 
as is show by the following theorem.

\begin{theorem}
\label{theorem:nogen}
If the starting relations are allowable,
%valid for $\sigma$,
then Mora's algorithm produces only relations which 
are allowable.
%also valid for $\sigma$.
\end{theorem}

The proof requires an analysis of the details of the Mora 
Algorithm at a level beyond the scope
of this paper and is omitted.  
%while routine for a specialist 
%%is not in the spirit of this paper
%%and so is not included.
%and would require some space to
%write down. This proof 


\iffalse

HERE IS AN OUTLINE OF PROOF -- NOT FOR PUBLICATION


This theorem follows easily from Lemmas
\ref{lemma:spoly} and
\ref{lemma:reduction}
below.

\begin{defin}
\label{defin:ijvalid}
Let $p\in K[x_1,\ldots,x_n]$ and
$\sigma : \{1,\ldots,n\} \rightarrow {\bf N}\times {\bf N}$.
If $p(0)=0$, then we say that $p$ is $(i,j)$-valid
for $\sigma$ if one obtains an $i \times j$ matrix
whenever one substitutes a $r_k \times s_k$ matrix $M_k$
for $x_k$ where $\sigma(k) = (r_k,s_k)$
for $1 \le k \le n$.
If $p(0)\not=0$, then we say that $p$ is $(i,j)$-valid
for $\sigma$ if $p-p(0)$ is $(i,j)$-valid for $\sigma$ and
$i=j$.
\end{defin}

Note that $p$ is valid for $\sigma$ if and only if 
there exist $i \ge 1$ and $j \ge 1$ such that 
$p$ is $(i,j)$-valid for $\sigma$.

The following lemma is obvious.

\begin{lemma} 
\label{lemma:obvious}
Let $\sigma :
\{1,\ldots,n\} \rightarrow {\bf N}\times{\bf N}$.
Let $i\ge 1$, $j\ge 1$, 
$p \in K[x_1,\ldots,x_n]$,
$q \in K[x_1,\ldots,x_n]$,
$c \in K$ be a nonzero scalar and 
$\ell$ and $r$ be monic monomials of $K[x_1,\ldots,x_n]$.
The following hold:
\begin{description}
\item{(1)}{ $c \ell p r$ is $(i,j)$-valid  for $\sigma$ if and only
if there exist ${\hat i} \ge 1$
and ${\hat j} \ge 1$ such that
$\ell$ is $(i,{\hat i})$-valid for $\sigma$, 
$p$ is $({\hat i},{\hat j})$-valid for $\sigma$
and $r$ is $({\hat j},j)$-valid for $\sigma$.
}
\item{(2)}{
If both $p_1$ and $p_2$ be $(i,j)$-valid for $\sigma$ and $c\in K$, 
then $p_1 + c p_2$ is $(i,j)$ valid for $\sigma$.
}
\item{(3)}{ If $p$ is $(i,j)$-valid for $\sigma$
and $q$ is $(j,k)$-valid for $\sigma$, 
then $c p q$ is $(i,k)$-valid for $\sigma$.
}
\end{description}
\end{lemma}

\begin{lemma} 
\label{lemma:spoly}
Let $f_1,f_2 \in K[x_1,\ldots,x_n]$
and $\sigma : \{1,\ldots,n\} \rightarrow {\bf N}\times {\bf N}$.
If $f_1$ is valid for $\sigma$ and $f_2$ is valid for $\sigma$, 
then every S-polynomial of $(f_1,f_2)$ is valid for $\sigma$.
\end{lemma}

\noindent
Proof\ \ \ \  If either $f_1$ 
or $f_2$ is constant, then the result is obvious.
Suppose that $f_1$ and $f_2$ are not constant.

Let $i_1\ge 1$, $j_1\ge 1$, $i_2 \ge 1$ and $j_2\ge 1$ be such
that $f_1$ is $(i_1,j_1)$-valid for $\sigma$
and $f_2$ is $(i_2,j_2)$-valid for $\sigma$.

Suppose that 
$c_1 l_1 LM(f_1) r_1 = c_2 l_2 LM(f_2) r_2$ for some
nonzero scalars $c_1$ and $c_2$ and for some monic monomials
$l_1,r_1,l_2,r_2$ such that one of the following four conditions hold.
\itemitem{(1)}
$l_1=r_1=1$, $LM(f_1)=l_2LM(f_2)r_2$.
\itemitem{(2)}
$l_2=r_2=1$, $LM(f_2)=l_1LM(f_1)r_1$.
\itemitem{(3)}
$l_1=r_2=1$, $l_2\ne1$, $r_1\ne1$,
there is a $w\ne1$ with $LM(f_1)=l_2w$, $LM(f_2)=wr_1$. 
\itemitem{(4)}
$l_2=r_1=1$, $l_1\ne1$, $r_2\ne1$,
there is a $w\ne1$ with $LM(f_1)=wr_2$, $LM(f_2)=l_1w$.

\medskip 

By the symmetry of (1) and (2) and  
the symmetry of (3) and (4), we can assume without
loss of generality that (1) or (3) holds.

If (1) holds, then, since $LM(f_1)$ is $(i_1,j_1)$-valid
for $\sigma$,  Lemma \ref{lemma:obvious}(1) 
implies that there exist $k_1 \ge 1$ and
$k_2 \ge 1$ such that $l_2$ is $(i,k_1)$-valid for $\sigma$,
$LM(f_2)$ is $(k_1,k_2)$-valid for $\sigma$ and
and $r_2$ are $(k_2,j_1)$-valid for $\sigma$. 
Since $LM(f_2)$ is $(k_1,k_2)$-valid for
$\sigma$ and $f_2$ is $(i_2,j_2)$-valid for $\sigma$, 
$k_1 = i_2$ and $k_2 = j_2$.
By Lemma \ref{lemma:obvious}(3), $c_1 \l_2 f_2 r_2$  and
$c_2 f_1$ 
are $(i_1,j_1)$-valid
for $\sigma$.
Therefore,  by Lemma \ref{lemma:obvious}(2),
$c_2 f_1- c_1 l_2 f_2 r_2$ is $(i_1,j_1)$-valid
for $\sigma$.

If (3) holds, then, since $LM(f_1)=l_2w$,
Lemma \ref{lemma:obvious}(1) implies that
there exists $k_1 \ge 1$ such that
$l_2$ is $(i_1,k_1)$-valid for $\sigma$
and $w$ is $(k_1,j_1)$-valid for $\sigma$.
Also, since $LM(f_2)=wr_1$,
Lemma \ref{lemma:obvious}(1) implies that
there exists $k_2 \ge 1$ such that
$w$ is $(i_2,k_2)$-valid for $\sigma$ and 
$r_1$ is $(k_2,j_2)$-valid for $\sigma$.
Therefore, $i_2=k_1$ and $k_2 =j_1$. Therefore, by Lemma 
\ref{lemma:obvious}(3),
$c_2 f_1r_1$ is $(i_1,j_2)$-valid for $\sigma$ and $c_1 l_2f_2$ is
$(i_1,j_2)$-valid for $\sigma$. Therefore, by Lemma \ref{lemma:obvious}(2),
$c_2 f_1 r_1 - c_1 l_2 f_2$ is valid for $\sigma$.
This completes the proof of Lemma \ref{lemma:spoly}.
\endproof

The following lemma states that if a reduction is possible,
then a reduction using a valid polynomial is possible.

\begin{lemma} 
\label{lemma:reduction}
Let $i\ge 1$ and $j\ge 1$.
Let $p_1,p_2,q \in K[x_1,\ldots,x_n]$ and
$\sigma : \{1,\ldots,n\} \rightarrow {\bf N}\times {\bf N}$.
If $p_1$ is $(i,j)$-valid for $\sigma$ and 
$p_2$ is $(i,j)$-valid for $\sigma$
and there exists a nonzero scalar
$c \in K$ and monic monomials $\ell$ and $r$ such that
$p_1 = c \ell q r + p_2$ and the leading term of $p_1$
is $c \ell q r$, then $\ell$, $q$, $r$ and $\ell q r$ are valid for $\sigma$.
\end{lemma}

\noindent
Proof\ \ \ \
Since $p_1$ and $p_2$ are $(i,j)$-valid for $\sigma$.
By Lemma \ref{lemma:obvious}(2), $c \ell q r = p_1-p_2$ is
$(i,j)$-valid for $\sigma$. 
By Lemma \ref{lemma:obvious}(1),
there exist $k_1 \ge 1$ and $k_2 \ge 1$ such that
$\ell$ is $(i,k_1)$-valid for $\sigma$, $q$ is $(k_1,k_2)$-valid
for $\sigma$
and $r$ is $(k_1,j)$-valid
for $\sigma$.
This completes the proof of Lemma \ref{lemma:reduction}.
\endproof

\fi

%\end{document}
%\end
