Chapter 9
Simple Demos of Basic Commands

In this chapter, we will give a number of demonstrations of how one would use our computer program to simplify expressions. Demonstrations for proving theorems using this program are given in Chapters 14, 15 and 17.

Throughout this document, we shall use the word “relation” to mean a polynomial in noncommuting indeterminates.1

9.1 To start a C++ GB session

The first step is to start Mathematica:

% math  
Mathematica 2.2 for SPARC  
Copyright 1988-93 Wolfram Research, Inc.

The next step is to load the appropriate software. 2

In[1]:= <<NCGB.m

Hi there !!!!!!!  
NCSetRule.m loaded  
NCPInverses.m loaded  
NCMono.m loaded  
NCSolve.m loaded  
NCMatMult.m loaded  
NCAliasFunctions.m loaded  
NCAlias.m loaded  
Starting Main  
LinkObject[p9c, 1, 1]

9.1.1 NCGBSetIntegerOverflow[False]

Here is a technical point which has implications. By default, C + + stores only a small number of integers and if longer integers occur in a computer run it will make a mistake. NCGB, which you are using, does not have this problem because of some potentially time consuming dynamic storage allocation. If you are sure your runs have small integers (between ±2 billion on a Sun), then you might want to override this NCGB feature to save run time. There are two ways to do this. One is type the command NCGBSetIntegerOverflow[True] before loading NCGB.m. The other is to edit a line in the file NCGB.m to read $NCGB$IntegerOverflow=True. These commands actually switch which code you are using. If you are in the middle of a session and wish to switch to just type NCGBSetIntegerOverflow[True] or NCGBSetIntegerOverflow[True] and reload NCGB.m.

9.2 Simplifying Expressions

Suppose we want to simplify the expression a3b3 - c assuming that we know ab = 1 and ba = b.

First NCAlgebra requires us to declare the variables to be noncommutative.

In[2]:= SetNonCommutative[a,b,c]

Now we must set an order on the variables a, b and c.

In[3]:= SetMonomialOrder[{a,b,c}]

Later we explain what this does, in the context of a more compliated example where the command really matters. Here any order will do. We now simplify the expression a3b3 - c by typing

In[4]:= NCSimplifyAll[{a**a**a**b**b**b -c}, {a**b-1,b**a- b}, 3]

After messages appear on the screen (which indicate that the computation is taking place), you get the answer as the following Mathematica output.

Out[4]= {1 - c}

The number 3 indicates how hard you want to try (how long you can stand to wait) to simplify your expression.

9.3 Making a Groebner Basis

A reader who has no explicit interest in Groebner Bases might want to skip this section. Readers who lack background in Gröbner Basis may want to read [CLS]. This section does indicate what underlies the simlification commands in Chapter 9. For more on the subject see 10.2.

Before making a Gröbner Basis, one must declare which variables will be used during the computation and must declare a “monomial order” which can be done using the commands described in Chapter 18. A user does not need to know theoretical background related to monomials orders. Indeed, as we shall see in Chapter 14, for many engineering problems, it suffices to know which variables correspond to quantities which are known and which variables correspond to quantities which are unknown. If one is solving for a variable or desires to prove that a certain quantity is zero, then one would want to view that variable as unknown. For simple mathematical problems, one can take all of the variables to be known. At this point in the exposition we assume that we have set a monomial order.

In[1]:= <<NCGB.m  
In[2]:= SetNonCommutative[a,b,x,y]  
In[3]:= SetMonomialOrder[a,b,x,y]  
In[4]:= ourGB = NCMakeGB[{y**x - a, y**x - b, x**x - a, x**x**x - b}, 10]

The result is:

Out[5]= {-a+x**x,-a+b,-a+y**x,-a+a**x,-a+x**a,-a+y**a,-a+a**a}

Our favorite format (as can be seen from the output to the screen) for displaying lists of relations is ColumnForm.

In[5]:= ColumnForm[%]  
Out[5]= -a + x ** x  
        -a + b  
        -a + y ** x  
        -a + a ** x  
        -a + x ** a  
        -a + y ** a  
        -a + a ** a

Someone not familiar with GB’s might find it instructive to note this output GB triangularizes the input equations to the extent that we have a compatibility condition on a, namely a2 -a = 0; we can solve for b in terms of a; there is one equation involving only y and a; and there are three equations involving only x and a. Thus if we were in a concrete situation with a and b, given matrices, and x and y, unknown matrices we would expect to be able to solve for large pieces of x and y independently and then plug them into the remaining equation yx - a = 0 to get a compatibility condition.

9.4 Reducing a polynomial by a GB

Now we reduce a polynomial or ListOfPolynomials by a GB or by any ListofPolynomials2. First we convert ListOfPolynomials2 to rules subordinate to the monomial order which is currently in force in our session.

For example, let us continue the session above with

In[9]:= ListOfRules2 = PolyToRule[ourGB];  
Out[9]= {x**x->a,b->a,y**x->a,a**x->a,x**a->a,y**a->a,  

To reduce ListOfPolynomials by ListOfRules2 use the command

             Reduction[ ListofPolynomials, ListofRules2]

For example, to reduce the polynomial poly = a**x**y**x**x + x**a**x**y + x**x**y**y in our session type

In[10]:= Reduction[ { poly }, ListOfRules2 ]

9.4.1 Simplification via GB’s

The way the previously described command NCSimplifyAll works is

    NCSimplifyAll[ ListofPolynomials, ListofPolynomials2] =  
                 Reduction[ ListofPolynomials,