%\documentclass[12pt,thmsa]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%TCIDATA{TCIstyle=Article/article.lat,lart,article}

%\begin{document}

%\newtheorem{example}[equation]{Example}
%\newtheorem{definition}[equation]{Definition}

%\author{Helton, Stankus, Wavrik}
%\title{Automated Simplification of Matrix Expression }

\section{Simplification}

\label{secgist}

The problem of simplification involves a collection of expressions and a
notion of equivalence among expressions. 
A goal is to obtain expressions equivalent to a given 
expression which are simpler in some way.
Another  goal is to find a unique representation for 
equivalent expressions.

When matrix expressions are simplified by hand, they are scanned for
subexpressions which can be replaced by something which is equivalent and
simpler.
For example, the expression
$1-x^{-1}x+x^2$ simplifies to $x^2$ because the subexpression 
$x^{-1}x$ can be replaced by $1$, and then $1-1$ can be replaced by $0$.

In the case above, the occurrence of a matrix expression next to its inverse
leads to a rather obvious simplification. Simplification can also use less
obvious replacements.
For example, $(1-yx)^{-1}-x^{-1}(1-xy)^{-1}x$ simplifies to $0$ even though
no subexpression consists of a matrix adjacent to its inverse. Here we use
the fact that $(1-xy)^{-1}x$ is equivalent to $x(1-yx)^{-1}$so that 
\begin{eqnarray*}
(1-yx)^{-1}-x^{-1}(1-xy)^{-1}x &\rightarrow
&(1-yx)^{-1}-x^{-1}x(1-yx)^{-1}\rightarrow \\
(1-yx)^{-1}-(1-yx)^{-1} &=&0
\end{eqnarray*}

The simplification rule $(1-xy)^{-1}x\rightarrow x(1-yx)^{-1}$ is well known
-- but it is not quite as obvious. We will show that this rule and others of
this sort are generated automatically by the simplification technology
introduced in this paper.

We will examine several classes of matrix expressions. In each case we will
start with a few simple matrix expressions and variables like $x$, $x^{-1}$, 
$(1-x)^{-1}$, and $(1-xy)^{-1}$ which we will call elementary or \textbf{%
atomic} expressions. \textbf{Polynomial expressions} are those which can be
obtained by repeatedly performing arithmetic operations (addition,
subtraction, multiplication and multiplication by scalars) on these atomic
expressions. 
%\footnote{ For example, the expression 
%$1- x^{-1} x +x^2$
%above is the polynomial 
%$1 - b a + a^2$ in $a=x$ and $b =
%x^{-1}$.} 
\footnote{For example, $x^2 (1-x)^{-1}$ and
$2 + x + 3 x^{-1}$ are polynomial expressions
in the atomic expressions $x$, $x^{-1}$ and $(1-x)^{-1}$, while
$sin(x)$ and $x/(2+x)$ are not polynomial expressions in
$x$, $x^{-1}$ and $(1-x)^{-1}$.}
Very complex expressions can be obtained in this way. It is
quite possible for two expressions which look quite different to be
equivalent in the sense that they represent the same matrix. We would like
to find the simplest possible among these representations.

We are drawing a distinction among, for example, the polynomial expressions $%
xx^{-1}$, $x^{-1}x$, and $1$. We regard these as different expressions
because they are formed differently in terms of atomic expressions and
operations. They look different. While they are not identical expressions,
they are \textbf{(strongly) equivalent\footnote{%
We will just say equivalent until we need to distinguish this from another
concept of equivalence.}} in the sense that, for any choice of invertible
matrix $x$ they assume the same value.

Simplification depends on a concept of simplicity and a concept of
equivalence. A \textbf{\ simplifier} is a 
procedure, $\mathcal{S}$, which
takes any expression $E$ to an equivalent and simpler 
expression ${\mathcal{S}} (E)$. 
Thus we have ${\mathcal{S}}(E)\sim E$ 
(indicating that ${\mathcal{S}}(E)$
is equivalent to $E$) and ${\mathcal{S}}(E)\leq E$ 
(indicating that ${\mathcal{S}}(E)$ is simpler, in 
some sense, than $E$). In this paper we will discuss a
simplifier which is based on a non-commutative version of the Gr\"{o}bner
Basis Algorithm. It can be implemented on a computer and shows evidence of
being a very valuable tool. The precise notions of simplicity and
equivalence which we use are discussed in Section 
\ref{section:Formal:Description}.
%comment  -- section number for def of simplicity
We have been able to show, in the cases we have examined, that this
simplifier is a \textbf{canonical simplifier} in the sense that $E_1\sim E_2$
$\Longleftrightarrow $ ${\mathcal{S}}(E_1)={\mathcal{S}}(E_2).$ 
The expression ${\mathcal{S}}(E)$ is a 
\textbf{canonical form} for $E$. In other words,
equivalence of expressions can be tested by reducing them to the canonical
form. A test for equivalence of expressions is a major application for
simplification machinery.

The problem of automatically simplifying matrix expressions and our use of
the non-commutative Gr\"{o}bner technology for this purpose are quite new.
Simplification plays a fundamental role in computer algebra. A treatment of
the general theory of simplification including an extensive set of
references is found in the survey article of Buchberger and Loos 
{\bf [BL]}.
A good general reference on commutative Gr\"obner Basis
is {\bf [CLS]} and on non-commutative Gr\"obner Basis
is {\bf [TMora]}.
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%comment
%Buchberger, B & Loos, R
%    "Algebraic Simplification"  
%    Computer Algebra - Symbolic and Algebraic Computation
%    Springer-Verlag  1982   pp 11-43

\subsection{\protect\medskip\ Replacement Rules}

\label{subsecgist}

For a collection of atomic expressions, there is usually a collection of
replacement rules coming from obvious relations among the expressions. Thus
we have rules like $xx^{-1}\rightarrow 1$ and $x^{-1}x\rightarrow 1$ which
allow us to replace a matrix which occurs next to its inverse. The initial
set of rules is insufficient for producing major simplifications. 
Crucial to
our simplification procedures is a mechanism for extending a set of
simplification rules.

A \textbf{replacement rule} consists of a left hand side ($LHS$), which will
always be a monomial, and a right hand side ($RHS$) which will always be a
polynomial. A replacement rule is applied to an expression by scanning its
terms to find a match for $LHS.$ If we find a term which has $LHS$ as a
factor, we replace the factor by $RHS$. Our notation for a rule is $%
LHS\rightarrow RHS$. Thus, for example, we have the replacement rule $%
xx^{-1}\rightarrow 1.$

Naturally we are unwilling to substitute $RHS$ for $LHS$ unless these are
equivalent. Thus we require $LHS-RHS$ becomes $0$ whenever matrices are
substituted for the matrix variables that occur in the atomic expressions. $%
xx^{-1}\rightarrow 1$ is a valid replacement rule since $xx^{-1}-1$ becomes $%
0$ whenever $x$ is replaced by an invertible matrix and $x^{-1}$ by its
inverse. $(1-xy)^{-1}x\rightarrow x(1-yx)^{-1}$ is also a valid replacement
rule (since $(1-xy)^{-1}x-x(1-yx)^{-1}$ becomes $0$ whenever $x$ and $y$ are
replaced by matrices for which this makes sense)\footnote{%
As mentioned above, this classical rule can be automatically derived from
simpler rules. See Section \ref{subsection:GroebnerBases}.}.

Simplification of a polynomial expression, $p$, using a list, $\mathcal{L}$,
of replacement rules involves repeatedly applying rules in the list until we
arrive at an expression which is\textbf{\ irreducible} (no further rules on
the list are applicable). In Section \ref{subsection:Ordering} 
%\textbf{XXX} 
we will place an ordering
on the terms of polynomial expressions. Our replacement rules will always
have the property that $LHS$ is greater than any of the terms in $RHS$ in
this ordering. This will guarantee that (1) repeated application of the
rules eventually leads to an irreducible expression and that (2) the
irreducible expression is \textit{simpler} in the sense of having terms of
smaller order than the original. If $h$ is irreducible and obtained from $p$
by applying reduction rules in list $\mathcal{L}$, we will say that $h$ is a 
\textbf{normal form} of $p$ and write $h=NForm(p,\mathcal{L})$ or $%
p\rightarrow _{\mathcal{L}}h.$ In general, the normal form is not unique%
\footnote{%
If the reduction rules are applied in different sequences, different normal
forms can be obtained (unless $\mathcal{L}$ has special properties). Even
though the normal form is not uniquely defined, the notation $h=NForm(p,%
\mathcal{L})$ is commonly used.}.

\medskip We will now look at an example of simplification. This will
illustrate the process and show what can occur.\ Here is a list of
simplification rules based on the definition of inverse for the atomic
expressions \textrm{$x$, $x^{-1}$ }and\textrm{\ $(1-x)^{-1}$:}\medskip\ 

\begin{tabular}{ll}
Rule 1 & \textrm{$xx^{-1}\rightarrow 1$} \\ 
Rule 2 & \textrm{$x^{-1}x\rightarrow 1$} \\ 
Rule 3 & \textrm{$x(1-x)^{-1}\rightarrow (1-x)^{-1}-1$} \\ 
Rule 4 & \textrm{$(1-x)^{-1}x\rightarrow (1-x)^{-1}-1$}
\end{tabular}

\medskip

\begin{example}
We now apply these rules to the expression:
\end{example}

\begin{equation}
x^{-1}x(1-x)^{-1}-x^{-1}(1-x)^{-1}-(1-x)^{-1}  \label{eq:1pt5}
\end{equation}

We first apply Rule 3 to the first term. This produces

\begin{equation}
x^{-1}((1-x)^{-1}-1)-x^{-1}(1-x)^{-1}-(1-x)^{-1}  \label{eq:1pt6}
\end{equation}
which, after expanding, rearranging, and cancelling terms, produces the
result:
\begin{equation}
-x^{-1}-(1-x)^{-1}  \, .
\label{eq:1pt7}
\end{equation}

None of the rules apply to this expression and, therefore,
it is irreducible. Thus (\ref{eq:1pt7}) 
is a normal form for (\ref{eq:1pt5}).

\subsection{Complete lists of rules}

\label{subseccomplete}

We come to one of the more basic points which is the concept of
`completeness' of a list of rules.

The reader may have noticed that there are other possibilities for applying
the replacement rules to (\ref{eq:1pt5}). If we first apply Rule 2 then we
get
\begin{equation}
(1-x)^{-1}-x^{-1}(1-x)^{-1}-(1-x)^{-1}   \, .
\label{eq:1pt8}
\end{equation}
This, after rearranging and cancelling terms, becomes
\begin{equation}
-x^{-1}(1-x)^{-1}  \, .
\label{eq:1pt9}
\end{equation}
We obtain two different expressions, (\ref{eq:1pt7}) and (\ref{eq:1pt9}),
just by changing the sequence in which rules are applied. As a result, we
obtain two expressions which are equivalent but which cannot be reduced to a
common irreducible form. The difference of these two expressions is 
\begin{equation}
x^{-1}(1-x)^{-1}-x^{-1}-(1-x)^{-1}  \, .
\label{eq:1pt10}
\end{equation}
It is equivalent to $0$ but cannot be reduced to $0$ by repeated application
of the rules. A set of rules will be called \textbf{complete} if it is
sufficient for simplifying to $0$ all expressions which are actually
equivalent to $0.$ The set of Rules 1-4 is not complete because they are not
enough to simplify the expression (\ref{eq:1pt10}) to $0$.

This problem can be handled by enlarging the set of rules. The 
expression (\ref{eq:1pt10}) 
%(which an operator theorist 
%calls the resolvent identity)
does not reduce to $0$ using the current set of 
rules, so we add it to the
list of rules. The two rules we obtain in this way are:
\medskip\ 

\begin{tabular}{ll}
Rule 5 & $x^{-1}(1-x)^{-1}\rightarrow x^{-1}+(1-x)^{-1}$ \\ 
Rule 6 & $(1-x)^{-1}x^{-1}\rightarrow x^{-1}+(1-x)^{-1}$%
\end{tabular}
\smallskip

\noindent
Incidentally, Rules 5 and 6 are often called the resolvent
identities.

It will follow from Section 
\ref{subsection:Resol} that 
this expanded list
has several important special properties. First of all, the expanded set of
rules Rule 1-6 is \textbf{complete}\footnote{%
This is not obvious. It follows from the fact that the Mora Algorithm
terminates in this case (see Section 
\ref{subsection:GroebnerBases}).}.
Such a complete set of
rules is said to be a \textbf{Gr\"{o}bner basis} (or GB) for the relations
on $x$, $x^{-1}$ and $(1-x)^{-1}$ (with respect to the given ordering).
Secondly, if the full list is of rules is applied repeatedly to any
polynomial $p$ in $x$, $x^{-1}$ and $(1-x)^{-1}$, then one 
obtains a particular
irreducible polynomial $q$. The same polynomial $q$ is obtained regardless
of the sequence in which the rules are applied. We can show, in this case,
that $q$ is a canonical form for $p$ with respect to algebraic equivalence%
\footnote{%
We will discuss algebraic equivalence in Section 
\ref{subsubsection:GroebnerBases}. It depends on the
choice of starting rules.}: decisions about algebraic equivalence of
expressions $p$ can be made by comparing canonical forms $q$.

We have illustrated the idea of expanding a set of simplification rules to
find a complete set for a particular example. 
We now provide
a more formal description of this process in general.

\subsection{Formal Description}
\label{section:Formal:Description}

It can become very confusing if we sometimes regard $xx^{-1}$and $x^{-1}x$
as different, and, at other times, treat them as the same. 
We can understand
what is at issue here by introducing a bit of formalism. This section will
also make precise the concepts of simplicity and equivalence used in this
work.

\subsubsection{Polynomials}

We will make a polynomial ring with one (non-commuting) variable for each of
our atomic expressions. Let's continue with the example from the previous
section where the atomic expressions are $x$, $x^{-1}$ and\ $(1-x)^{-1}.$ We
introduce three polynomial variables $a$, $b$ and $c$. Since the variables do
not commute, $ab$ and $ba$ are different polynomials. Now take a polynomial
in $a$, $b$ and $c$ and substitute a matrix $M$ for $a$, $M^{-1}$ for $b$
and $(1-M)^{-1}$ for $c$. The result is a matrix. The result of substituting
into $ab$ is $MM^{-1}$ while the result of substituting into $ba$ 
is $M^{-1}M$.
The polynomials are different but the resulting matrices are the same. We
obtain, in this way, one notion of equivalence on polynomials: two
polynomials are (strongly) equivalent if, upon any meaningful substitution,
they produce the same matrix. Here are some polynomials that are equivalent
to $0$ with the substitution as in this example:
\begin{equation}
ab-1,\;ba-1,\;ac-c+1,\;cb-c-b  \label{eq:star}
\end{equation}
because, on substitution, they become
\begin{eqnarray}
&&{MM^{-1}-1,\;M^{-1}M-1,\;M(1-M)^{-1}-(1-M)^{-1}+1,}  \label{eq:starstar} \\
&&{\;(1-M)^{-1}M^{-1}-(1-M)^{-1}-M^{-1}}
\end{eqnarray}
all of which are $0$ for any matrix $M$ for which they make sense. A
polynomial which is equivalent to zero is said to be a \textbf{relation} on
the variables. Therefore, in our example, $ab-1$, $ba-1$, $ac-c+1$ and $%
cb-c-b$ are relations on $a$, $b$ and $c$.

Let $\mathcal{P}$ denote all polynomials in three noncommuting variables $a$%
, $b$ and $c$. Define 
\begin{equation}
p_1=ab-1,\ p_2=ba-1,\ p_3=ac-c+1,\ p_4=ca-c+1  \label{eq:1pt11}
\end{equation}
and observe that if we substitute $M$ for $a$, $M^{-1}$ for $b$ and $%
(1-M)^{-1}$ for $c$, then these polynomials become $0$ and in fact
constitute the definitions of the expressions $x^{-1}$ and $(1-x)^{-1}$.
These relations correspond to the simplification rules 
Rules 1-4. In practice it
is only easy to determine that some very simple polynomials are relations. $%
p_1$, $p_2$, $p_3$ and $p_4$ are relations which result from the definition
of inverse. We often show that a more complicated polynomial is a relation
by showing that it is an ``algebraic consequence'' of known relations. For
example, $p=bc-b-c$ is a relation because:

\begin{equation}
p=bc-b-c=p_2c-bp_3  \label{eq:1pt12}
\end{equation}

Notice that any matrices substituted for $a$,$b$, and $c$ which make $p_2$
and $p_3$ zero will also make $p$ zero. Thus $p$ is a relation since $p_2$
and $p_3$ are relations and because $p$ is an ``algebraic consequence'' of $%
p_2$ and $p_3$.\footnote{%
We call attention to the way that $p$ is obtained from $p_2$ and $p_3$
namely $p=p_2c-bp_3$. This shows that  $p$ can be obtained from $p_2$ and $%
p_3$ by applying certain algebraic operations.}

Since our work involves the notion of ``algebraic consequence'' 
we will
introduce some terminology to make it precise. Let $\mathcal{P}$ be the set
of polynomials in a fixed finite collection of non-commuting variables.
Recall that an \textbf{ideal} of $\mathcal{P}$ is a subset $I$ of $\mathcal{P%
}$ such that whenever $p_1$ and $p_2$ are in $I$ and whenever $q_1$ and $q_2$
are in $\mathcal{P}$, both $p_1+p_2$ and $q_1pq_2$ are in $I$. The \textbf{%
ideal generated by a set of polynomials} $S$ is the smallest ideal of $%
\mathcal{P}$ containing $S$. This ideal consists of finite sums of the form $%
\sum r_ip_is_i$ where $r_i$, $s_i$ are any polynomials and $p_i\in S$.

Suppose that $S$ is a finite set of polynomials, $S$ = $\{p_1,...,p_n\}$, $I$
is the ideal generated by $S$ and $f\in I$. 
If any set of matrices $M_j$
satisfy the equations $p_i(M_1,...,M_m)=0$ then they also satisfy $%
f(M_1,...,M_m)=0.$ If the $p_i$ are relations on some atomic expressions,
then $f$ will also be a relation on these expressions. We say that $f$ is an 
\textbf{algebraic consequence} of $p_1,...,p_n$ if $f$ is in the ideal
generated by the $p_i$. An ideal is the set of all algebraic consequences of
a starting set of polynomials.
\smallskip

\textbf{Notation: }Using the strict polynomial notation, as we have above,
makes it hard to remember which atomic expression is associated with which
variable. We have found it convenient to use the associated atomic
expressions as names for the polynomial variables. Thus, in the case above,
we would use $x$ rather than $a$ and $x^{-1}$ rather than $b$. 
$x$ should be
thought of as a variable for which matrices can be substituted. $xx^{-1}-1$
should be thought of as a polynomial in two variables which is not zero (as
a polynomial) but which becomes zero when any matrix and its inverse are
substituted for the variables. We will specify in advance which atomic
expressions are being used. In the example discussed in this section, we
have three atomic expressions $x$, $x^{-1}$ and $(1-x)^{-1}$. Rather than
use the letters $a$, $b$, and $c$ as names for the polynomial variables (as
we have been doing) we use the names $x$, $x^{-1}$ and 
$(1-x)^{-1}.$ We substitute matrices for these variables with the
understanding that if a matrix $M$ is substituted for $x$, then $M^{-1}$ is
substituted for $x^{-1}$ and $(1-M)^{-1}$ is substituted for $(1-x)^{-1}$.
We are all accustomed to using single letters (usually $x$, $y$ and $z$) to
denote polynomial variables. Making the adjustment to using atomic
expressions as names is rewarded by making it easier to see what our
relations mean and which substitutions are allowed. We use this notation in
the rest of the paper.

\subsubsection{Ordering}
\label{subsection:Ordering}

A replacement rule $LHS\rightarrow RHS$ gives rise to a relation\textit{\ }$%
LHS-RHS$. A relation, on the other hand, could give rise to several possible
replacement rules. For example, the definition of $(1-x)^{-1}$ gives the
relation 
\begin{equation}
x(1-x)^{-1}-(1-x)^{-1}+1  \label{eq:1pt1}
\end{equation}
The 3 replacement rules we could associate to this are 
\begin{equation}
1\rightarrow (1-x)^{-1}-x(1-x)^{-1}  \label{eq:1pt2}
\end{equation}
\begin{equation}
(1-x)^{-1}\rightarrow x(1-x)^{-1}+1  \label{eq:1pt3}
\end{equation}
and 
\begin{equation}
x(1-x)^{-1}\rightarrow (1-x)^{-1}-1\,.  \label{eq:1pt4}
\end{equation}
We wish to use the rule to make expressions less complicated so we choose
the last rule which replaces the ``most complicated'' monomial in (\ref
{eq:1pt1}) by a sum of simpler ones. A choice of a particular replacement
rule for any relation is made by placing an ordering on the terms in
expressions. The ordering will be chosen so that expressions which we
subjectively regard as complicated tend to be higher in the order than those
which we think of as simpler. Once an ordering is imposed, each relation has
a term of highest order. We associate to a relation that replacement rule
for which $LHS$ is the term of highest order.

Let us assume that the variables for the polynomial ring $\mathcal{P}$ are $%
a,b,c,...$ (one letter for each atomic expression). The monomials of $%
\mathcal{P}$ are words in the letters $a,b,c$.... We place an ordering on
these monomials by:

\medskip\ $M\le N$ if and only if\smallskip\ 

\begin{tabular}{ll}
either & $length(M)<length(N)$ \\ 
or & $length(M)=length(N)$ \ and \\ 
& $M$ comes before $N$ in the dictionary
\end{tabular}

This is called \textit{\textbf{graded lexicographic ordering}} of the
monomials.

\label{example:1pt5} \textrm{If $a<b<c$ then the monomials of degree $3$ are
ordered 
\[
\matrix{aaa<aab<aac<aba<abb<abc<aca<acb<acc<baa<bab<\hfill\cr
bac<bba<bbb<bbc<bca<bcb<bcc<caa<cab<cac<cba<\hfill\cr
cbb<cbc<cca<ccb<ccc\hfill\cr} 
\]
These are all taken to be bigger than any monomial of degree 2.}\footnote{%
This ordering is intended to capture our notion of simplicity. When we apply
this machinery, we assign variables higher in the ordering (alphabet) to
atomic expressions which seem more complicated. Terms having fewer factors
are automatically regarded as simpler than terms with more factors.}

Every polynomial $p$ has a unique term whose monomial is of highest order.
This is called the leading term of $p$ and is denoted $LT(p)$. A polynomial
relation is converted to a simplification rule, by setting $LHS$ to be $%
LT(p) $ and $RHS$ to be $p-LT(p)$. One polynomial is \textbf{simpler} than
another if the terms of the first polynomial are smaller in this ordering
than the largest term of the second. Our simplification rules decrease the
order of the terms.

\subsubsection{Definition of Gr\"{o}bner Basis}
\label{subsubsection:GroebnerBases}

\begin{definition}
Let $P$ be a polynomial ring and $O$ an ordering 
on the terms of $P$. A set 
$G$ of polynomials corresponds (using the ordering) 
to a set $\mathcal{L}$ of
replacement rules. Let $h$ and $p$ be polynomials and let $h$ be obtained
from $p$ by applying rules in list $\mathcal{L}$ until no further rules
apply. We will say that $h$ is a \textbf{normal form} of $p$ and write $%
h=NForm(p,G)$ or $p\rightarrow _Gh.$
\end{definition}

\begin{definition}
Let $P$ be a polynomial ring, $I$ an ideal of $P$, and $O$ an ordering on
the terms of $P$. A set $G$ $\subset I$ is called a \textbf{Gr\"{o}bner Basis%
} for $I$ if it generates $I$ and if $p\in I$ implies $p\rightarrow _G0.$
\end{definition}

\ We will also speak of a set of simplifying rules as a Gr\"{o}bner Basis
when the associated set of polynomials is a GB. 
If $G$ is a Gr\"{o}bner
Basis, then $NForm(p,G)$ is independent of the order in which replacement
rules are applied. It is also a canonical form for \textbf{algebraic
equivalence }(that is, $p$ and $q$ are algebraically equivalent if $p-q$ is
in the ideal $I$).
\footnote{If $p$ and $q$ are \textit{algebraically} equivalent 
and if the generators
of $\cal I$ are relations (i.e., become zero upon substitution), 
then $p$ and $q$ are
also \textit{strongly} equivalent. Thus, for most of our Gr\"{o}bner Bases,
which are obtained from somewhat evident starting relations, two expressions
which simplify to the same normal form are equivalent in the usual sense.}

\medskip

\subsection{A Gr\"{o}bner Basis Algorithm}
\label{subsection:GroebnerBases}

Here is a simplified version of Mora's Algorithm used to extend a set, $G$,
of generators for an ideal $\mathcal{I}$ to a larger (and potentially
complete) set of generators.
\smallskip\ 

\begin{description}
\item[Algorithm]  (Simplified Basis Algorithm)
\end{description}

\hspace{0.3in}
Let ${\mathcal{S}}:=\{(g_1,g_2)\;|\;g_1,g_2\in G\}$

\hspace{0.3in}
While ${\mathcal{S}}\neq \emptyset $

\hspace{0.3in}
\hspace{0.3in}
Choose $(g_1,g_2)\in \mathcal{S}$

\hspace{0.3in}
\hspace{0.3in}
$S := S - \{(g_1,g_2)\}$

\hspace{0.3in}
\hspace{0.3in}
For all $f=SPoly(g_1,g_2)$

\hspace{0.3in}
\hspace{0.3in}
\hspace{0.3in}
Let $h=NForm(f,G)$

\hspace{0.3in}
\hspace{0.3in}
\hspace{0.3in}
If $h\neq 0$ then

\hspace{0.3in}
\hspace{0.3in}
\hspace{0.3in}
\hspace{0.3in}
${\mathcal{S}}:={\mathcal{S}}\cup
\{(g,h)\;|\;g\in G\}$

\hspace{0.3in}
\hspace{0.3in}
\hspace{0.3in}
\hspace{0.3in}
$G:=G\cup \{h\}$

\medskip\ 

An $SPoly(g_1,g_2)$ is a combination of the form $a_1l_1g_1r_1-a_2l_2g_2r_2$
where the $a_i$ are numbers and the $l_i$ and $r_i$ are monomials. These are
chosen so that (1) the leading term of $a_1l_1g_1r_1$ equals the leading
term of $a_2l_2g_2r_2$ and (2) this occurs in a ``minimal'' 
way \footnote{In the case of commuting variables, there is a unique minimal match -- and so
a unique $SPoly(g_1,g_2).$ In the non-commutative case, 
there may be none or
several minimal matches for a given pair $(g_1,g_2).$ 
See {\bf [HW]}, {\bf [FMora]} or {\bf [TMora]}
for details.}. $NForm(f,G)$ may depend on the sequence in which the
simplification rules are applied. $h$ can be chosen to be
any normal form of $f$.

Notice that the algorithm is an iterative process which adds new polynomials
to $G$. Notice also that every new element $h$ which is added to $G$ is in
the ideal $\cal I$. So the elements of $G$ at any stage in this algorithm are all
algebraic consequences of the starting $G$. 
Thus, if the original $G$
consists of relations among a set of matrix expressions, all the elements of 
$G$ (at any stage) will also be relations on the matrix expressions.

A criterion for a set $G$ to be a Gr\"{o}bner Basis is $SPoly(g_1,g_2)%
\rightarrow _G0$ for all $g_1,g_2\in G$. If the algorithm terminates,
 then
the criterion shows that the (finite) resulting set $G$ is 
automatically a
Gr\"{o}bner Basis for $\mathcal{I}$. In the case of polynomials in commuting
variables, the algorithm always terminates and so always produces a
Gr\"{o}bner Basis.

%In the non-commutative case, the algorithm may not terminate. We implement
%the algorithm so that it can be interrupted and the current $G$ can be
%recovered and examined. This set can be analyzed and used to determine a
%(infinite) complete set. It can also be valuable as a set of simplification
%rules, even if it is not a complete set.

\subsubsection{Comments on Rules and Notation}

In general, the process of applying rules to simplify a given expression is
very quick once a Gr\"{o}bner Basis has been computed. The process of
computing a Gr\"{o}bner Basis is usually labor intensive and there is a big
advantage to computing it and storing it, once and for all, for a given set of
atomic expressions. As we have noted, if the Mora Algorithm terminates
yielding a finite basis, then this basis is 
automatically a Gr\"{o}bner Basis
{\bf [FMora]}.

In some of our examples, the Gr\"{o}bner Basis is infinite. In this case,
the Mora Algorithm is interrupted after it has produced a reasonable number
of new polynomials. The output can be quite useful. In practice we have
found that it can provide a list of rules which has considerable simplifying
power. We have also found that, in analyzing the output, we could sometimes
obtain recursive formulas for parametrized families of relations.
Application of the SPoly criterion has allowed us to assert that the
infinite families discussed in this paper are 
actually Gr\"{o}bner bases.
See Sections \ref{section:preNF} and \ref{section:NF}
for examples of this.

Although the process of generation and analysis needed to obtain
an
infinite basis is time intensive, parametrized families of rules can be
applied almost as readily as a finite set of rules. Thus, the use of an
infinite set of rules can be quite practical. 
We are using an ordering which
depends on the number of factors in a term. 
If we wish to simplify a particular expression, $f$, 
the only rules which will be applicable are those whose $LHS$ has 
%lower order and, in particular, 
a smaller 
number of factors than the leading term of $f.$ 
%a greater number of factors than those in the terms of $f.$ 
Thus a finite subset of the rules will be sufficient to simplify all
expressions up to a certain complexity. An infinite set of rules has been
implemented by storing all rules up to a sufficiently high degree to handle
most situations. 
This program identifies and generates any instances of yet
higher order rules as needed.

%\end{document}
