NONCOMMUTATIVE GROEBNER BASIS PACKAGE

Version 0.0 (Mathematica 2.2 and g++2.6.3 compatible)

M. Stankus Math Dept., UCSD

J. William Helton Math Dept., UCSD La Jolla, California 92093

Copyright by Helton and Stankus on May 1995 all rights reserved.

If you would like to try the NonCommutative Gröbner Basis package or want updates contact ncalg@osiris.ucsd.edu. The program was written by Mark Stankus, Victor Shih, Mike Moore and Kurt Schneider. This program was written with support from the AFOSR, the NSF, the Lab for Mathematics and Statistics at UCSD,the UCSD Faculty Mentor Program and the US Department of Education.

Contents

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1 Simple Demos of Basic Commands 10 1.1 To start a C++ GB session . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Simplifying Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2.1 Saving time when typing relations for things like inverses . . . . . . . . . . 13 1.3 Using an input file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Making A Gröbner Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.4.1 First Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.2 Changing polynomials to rules . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.3 Changing rules to polynomials . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4.4 Simplifying using a GB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4.5 Second Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 NCProcess: The concepts 16 2.1 Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 What is a strategy? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2.1 NCProcess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2.2 Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.3 When to stop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2.4 Redundant Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3 A Simple Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.2 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.3 Solution via a Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.4 The end game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3 NCProcess: The command 27 3.1 SetKnowns and SetUnknowns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 NCProcess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2.1 NCProcess[aListOfPolynomials,iterations,fileName] . . . . . . . . . . . . . . 28

3.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3 NCProcess Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.4 NCCollectOnVars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.4.1 NCCollectOnVars[aListOfExpressions,aListOfVariables] . . . . . . . . . . . 29 3.4.2 UserSelect → aListOfPolynomials . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4.3 Reduction algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4.4 DegreeCap and DegreeSumCap . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4.5 DegreeCapSB and DegreeSumCapSB . . . . . . . . . . . . . . . . . . . . . . 32 3.4.6 TeX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.5 Typical use of the NCProcess command . . . . . . . . . . . . . . . . . . . . . . . . 32 3.6 NCProcess Summary Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4 Another Example: Solving the H^{∞} Control Problem 39

4.1 Engineering motivation for the problem . . . . . . . . . . . . . . . . . . . . . . . . 39 4.1.1 System definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.1.2 Energy balance equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.2 The Demo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.2.1 The key relations: executable form . . . . . . . . . . . . . . . . . . . . . . . 43 4.3 Solving (H^{∞}CNTRL) using NCProcess . . . . . . . . . . . . . . . . . . . . . . . . 44

4.3.1 Step 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.3.2 Step 2: The user attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.3.3 Step 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.3.4 Step 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.4 End game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5 Finding a small (non-Gröbner) basis 53 5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.2 First Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.3 Second Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.4 Smaller Bases and the Spreadsheet command . . . . . . . . . . . . . . . . . . . . . 57

6 How to Run These Packages 58

6.1 Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 6.1.1 GNU C++ Version ≥ 2.6.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 6.1.2 Obtaining NCGB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 6.1.3 Compiling the C++ part of NCGB . . . . . . . . . . . . . . . . . . . . . . 59 6.1.4 How to set up if someone else compiled the code — UNIX (or It is easy to

bum off of a friend who is running on the same system) . . . . . . . . . . . 59

6.2 Running the code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

6.2.1 Loading NCGB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6.3 Testing this package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6.4 Testing this package – In house . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

6.4.1 TestIt[testnumber,functionname,iterations] . . . . . . . . . . . . . . . . . . 61 6.4.2 WhatAreTests[argument(optional)] . . . . . . . . . . . . . . . . . . . . . . . 61 6.4.3 TimedGBTest[start,end] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.4.4 GBTest[start,end] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.4.5 CheckRun[aCharString] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

7 Commands for Making and Using GB’s 63

7.1 Simplification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 7.1.1 NCSimplifyAll[expressions, startRelations, iterations] . . . . . . . . . . . . . 63 7.1.2 NCSR6[expressions, startRelations, iterations] . . . . . . . . . . . . . . . . . 63 7.1.3 NCSR6[expressions,startRelations] . . . . . . . . . . . . . . . . . . . . . . . 64 7.1.4 NCSR6[expressions,iterations] . . . . . . . . . . . . . . . . . . . . . . . . . . 64 7.1.5 NCSR6[expressions] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 7.1.6 Correspondence to sections ‘Making a Gröbner Basis and various options’

and ‘Reduction’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

7.2 Making a Gröbner Basis and various options (with their defaults) . . . . . . . . . . 65 7.2.1 NCMakeGB[aListOfPolynomials, iterations] . . . . . . . . . . . . . . . . . . 65 7.2.2 ReturnRelationsToMma→True – need to rename . . . . . . . . . . . . . . . 66 7.2.3 SupressCOutput→ False (less output to the screen) . . . . . . . . . . . . . 66 7.2.4 SupressAllCOutput→ False (very little output to the screen) . . . . . . . . 66 7.2.5 UserSelect→ {}(Distinguishing important relations) . . . . . . . . . . . . . 67 7.2.6 ClearUserSelect[] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7.2.7 Deselect→ {} (Preventing certain S-Polynomials from being created) …. 67 7.2.8 NCCleanUpPolys[aListOfPolynomials] . . . . . . . . . . . . . . . . . . . . . 68 7.2.9 ReorderInput . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.2.10 CleanUp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.2.11 FinishedComputingBasisQ[] . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.2.12 NCMakeRelations[aSpecialList, aSpecialList, …] . . . . . . . . . . . . . . . 69 7.2.13 NCContinueMakeGB[iterationNumber] . . . . . . . . . . . . . . . . . . . . . 70 7.2.14 Correspondence to sections ‘Simplification’ and ‘Reduction’ . . . . . . . . . 70

7.3 Simple Order Maintenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 7.3.1 SetKnowns[aListOfVariables] — not yet implemented . . . . . . . . . . . . 70 7.3.2 SetUnKnowns[aListOfVariables] — not yet implemented . . . . . . . . . . . 70 7.3.3 SetMonomialOrder[aVariable,…] . . . . . . . . . . . . . . . . . . . . . . . . 71

7.4 Complicated Order Maintenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 7.5 NCProcess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

7.5.1 NCProcess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 7.6 Options for NCMakeGB and NCProcess . . . . . . . . . . . . . . . . . . . . . . . . 72

7.6.1 DegreeCap→ n (directing NCMakeGB’s effort) . . . . . . . . . . . . . . . . 72 7.6.2 DegreeSumCap→ n (directing NCMakeGB’s effort) . . . . . . . . . . . . . . 72 7.6.3 NCGBDebug→ False (True for debugging – creates files) – not implemented

yet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

7.7 Coping with the answer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7.7.1 If the answer is too big… – fill this in . . . . . . . . . . . . . . . . . . . . . 72 7.7.2 RegularOutput[aListOfPolynomials,“fileName”] . . . . . . . . . . . . . . . . 72 7.7.3 WhatIsPartialGB[] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.7.4 IterationNumber[aList] or IterationNumber[aNumber] . . . . . . . . . . . . 73

7.8 Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 7.8.1 Reduction[aListOfPolynomials, aListOfRules] . . . . . . . . . . . . . . . . . 74 7.8.2 PolyToRule[aPolynomial] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 7.8.3 RuleToPoly[aRule] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 7.8.4 Correspondence to sections ‘Simplification’ and ‘Making a Gröbner Basis

and various options’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

8 Ordering on variables 75 8.1 Lex Order: The simplest elimination order . . . . . . . . . . . . . . . . . . . . . . . 75 8.2 Graded lex ordering: A non elimination order . . . . . . . . . . . . . . . . . . . . . 76 8.3 Multigraded lex ordering : A variety of elimination orders . . . . . . . . . . . . . . 77 8.4 The list of commands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

8.4.1 SetMonomialOrder[aListofIndeterminants, n] . . . . . . . . . . . . . . . . . 78 8.4.2 ClearMonomialOrderN[n] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 8.4.3 ClearMonomialOrderAll[] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 8.4.4 PrintMonomialOrder[] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 8.4.5 WhatIsMultiplicityOfGrading[] . . . . . . . . . . . . . . . . . . . . . . . . . 79 8.4.6 WhatIsSetOfIndeterminants[n] . . . . . . . . . . . . . . . . . . . . . . . . . 79

9 Commands for Making Small Bases for Ideals – Mma version – name changes 80

9.1 Removing excess relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 9.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 9.1.2 RemoveRedundent[] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 9.1.3 RemoveRedundent[aListOfPolynomials,history] . . . . . . . . . . . . . . . . 81 9.1.4 RemoveRedundentByCategory[] . . . . . . . . . . . . . . . . . . . . . . . . . 82 9.1.5 RemoveRedundentByCategory[aListOfPolynomials,history] . . . . . . . . . 82

9.2 Discussion of RemoveRedundent command . . . . . . . . . . . . . . . . . . . . . . 83 9.3 Brute Force: Shrinking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

9.3.1 SmallBasis[aListOfPolynomials,anotherListOfPolynomials,iter] . . . . . . . 84 9.3.2 SmallBasisByCategory[aListOfPolynomials,iter] . . . . . . . . . . . . . . . . 85 9.3.3 ShrinkOutput[aListOfPolynomials,fileName] . . . . . . . . . . . . . . . . . . 85

9.4 Brute Force: Many shrinks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 9.4.1 ShrinkBasis[aListOfPolynomials,iterations] . . . . . . . . . . . . . . . . . . . 86 10 Commands for Making Small Bases for Ideals – C++ version 87

11 Commands to Create and Retrieve Categories — Mma version 88 11.0.2 CreateCategories[aListOfPolynomials,aName] . . . . . . . . . . . . . . . . . 88 11.0.3 GetCategory[aListOfVariables,aName] . . . . . . . . . . . . . . . . . . . . . 88 11.0.4 GetCategory[aCharString,aName] . . . . . . . . . . . . . . . . . . . . . . . 89

12 Commands to Create and Retrieve Categories — C++ version 94

13 History of the production of a GB and Playing By Numbers 95

13.1 Play By Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 13.1.1 WhatAreGBNumbers[] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 13.1.2 WhatAreNumbers[] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 13.1.3 WhatIsPartialGB[aListOfIntegers] . . . . . . . . . . . . . . . . . . . . . . . 96 13.1.4 NumbersFromHistory[aPolynomial,history] . . . . . . . . . . . . . . . . . . 96

13.2 History of the production of a GB . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 13.2.1 WhatIsHistory[aListOfIntegers] . . . . . . . . . . . . . . . . . . . . . . . . . 97 13.2.2 WhatIsKludgeHistory[aListOfIntegers] . . . . . . . . . . . . . . . . . . . . . 97 13.2.3 More on the History of how NCMakeGB produced its answer . . . . . . . . 97 13.2.4 The DAG associated with a History . . . . . . . . . . . . . . . . . . . . . . 98

14 Other stuff 100

14.1 Starting Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 14.1.1 ClearStartingRelations[] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 14.1.2 SetStartingRelations[data] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 14.1.3 WhatAreStartingRelations[] . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

14.2 Experiment recording stuff — not fully implemented . . . . . . . . . . . . . . . . . 101 14.3 Sort commands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

14.3.1 SortRelations[aListOfRules] . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 14.3.2 SortMonomials[aListOfVariables] . . . . . . . . . . . . . . . . . . . . . . . . 101 14.3.3 SetMonomialOrderSymmetric[aListOfIndeterminates,anInteger] . . . . . . . 101

14.4 Changing the default options for NCMakeGB . . . . . . . . . . . . . . . . . . . . . 102

14.4.1 ChangeNCMakeGBOptions[option,value] — need to update description . . 102 14.5 An idea for the future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

14.5.1 MultipleTrips – not yet implemented . . . . . . . . . . . . . . . . . . . . . . 102 14.6 Small Basis Type Commands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

14.6.1 SmallBasis[firstList, keepList,anInteger] — documented elsewhere . . . . . . 102 14.6.2 SmallMakeBasis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 14.6.3 Specialcomplement[aList,item] . . . . . . . . . . . . . . . . . . . . . . . . . 103 14.6.4 SmallBasisByCategory[aListOfPolynomials,iterations] . . . . . . . . . . . . 103 14.6.5 SmallBasisOnEliminationIdeal[ProcessedBasis, topElimLevel,iterations] . . 103

14.6.6 SmallBasisOnMultElimIdeals[ProcessedBasis, topElimLevel,anInteger] … 103 14.7 Technical . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

14.7.1 GroenbnerCutOffFlag[n Integer] . . . . . . . . . . . . . . . . . . . . . . . . 103 14.7.2 GroebnerCutOffMin[n Integer] . . . . . . . . . . . . . . . . . . . . . . . . . 104 14.7.3 GroebnerCutOffSum[n Integer] . . . . . . . . . . . . . . . . . . . . . . . . . 104 14.7.4 unExp[anExpression] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 14.7.5 unBase[anExpression] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 14.7.6 CreateSubCategories[aListOfPolynomials,aSymbol] — not yet implemented 104 14.7.7 UserSelects[aInteger] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 14.7.8 UserSelectedQ[aInteger] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 14.7.9 NumberOfFactorsOnLeftHandSide[anInteger] . . . . . . . . . . . . . . . . . 105 14.7.10 VariablesOfGBPolynomial[anInteger] . . . . . . . . . . . . . . . . . . . . . . 105 14.7.11 ReinstateOrder[] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 14.7.12 PartialBasis[aNumber] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 14.7.13 SetCleanUpBasis[n] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 14.7.14 CleanUpBasisQ[] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

15 A notebook like environment under unix: NCSetNb 107 .1 The Commutative Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 .2 The Noncommutative case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

Introduction

This package joins with the package NCAlgebra.m to add powerful automatic methods

for handling systems of equations in noncommuting variables. All commutative algebra packages contain commands based on Gröbner Bases and uses of them. For example in Mma the Solve command put systems of equations in a “cannonical” form which for simple systems readily yields a solution. Likewise the Mma Eliminate command tries to convert a system of equations in unknowns x_{1}, x_{2},… x_{3} to a “triangular” form in unknowns, that is, a new system of equations like

q_{1}(x_{1}) = 0 (0.1) q_{2}(x_{1}, x_{2}) = 0 (0.2) q_{2}^{2}(x_{1}, x_{2}) = 0 (0.3) q_{3}(x_{1}, x_{2}, x_{3}) = 0 (0.4) … (0.5) q_{k}(x_{1},…, x_{n}) = 0 (0.6)

Here the polynomials {q_{j} : j = 1,… k} generate the same ideal that the polynomials {p_{j} : 1 ≤ j ≤ k} do. Therefore, the set of solutions to the system the polynomial equations p_{j} = 0 equals the set of solutions to the system of polynomial equations q_{j} = 0. This canonical form greatly simplifies the task of solving systems of polynomial equations by allowing one to backsolve for x_{j} in terms of x_{1},…, x_{j−1}.

A brief mathematical discussion of Groebner bases appears in Appendix 15. The user

who is not acquainted at all with Gröbner Basis should still be able to read and use much of the material which is contained within this document.

In [FMora] , c.f. [TMora], F. Mora described a version of the Gröbner basis algorithm

which applied to noncommutative free algebras. We refer to this algorithm as Mora’s algorithm. It too puts systems of equations into a ”cannonical form” which we believe has considerable possibilities in the noncommutative case. This package implements the Mora algorithm and these applications as well.

We think of this package as being useful for at least 4 things.

1 Simplifying complicated expressions 2 Making the process of discovering algebraic theorems and appealing formulas semi-automatic 3 Producing GB’s in noncommuting situations 4 Finding small bases for ideals in a noncommuting algebra

We begin by giving simple examples which are sufficient to show how this package is

used. They begin with applications and move to the GB algorithm itself.

We then describe the Mathematica commands in subsequent chapters. We refer the user

to [HW],[HWS1] and [HWS2] for which describe in detail our approach to simplification of noncommutative expressions. [HS] describes our approach to discovering theorems and formulas as does this document to some extent.

Another document describes a version of Mora’s algorithm which allows the generation

of and the manipulation of infinite collections of polynomials (which are often unavoidable in the noncommutative setting).

Chapter 1

Simple Demos of Basic Commands

We recommend that the reader read the first four pages of the first chapter of the NCAlgebra manual.

In this chapter, we will give a number of demos of how one would use the computer

program to perform computations. Demos for proving theorems using this program are given in Chapters 2 3 and 4. Complete descriptions of the commands demonstrated in these chapter are given in Chapter 7.

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

noncommuting indeterminates.^{1}

1.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

1If an analyst saw the equation AB = 1 for matrices A and B, then he might say that A and B satisfy the polynomial equation x y − 1 = 0. An algebraist would say that x y − 1 is a relation.

2When the file “NCGB.m” is loaded, it either loads the file NCAlgebra.m or the file shortNCAlgebra.m. If one plans on using NCAlgebra commands, then one should set the file NCGB.m up so that it loads NCAlgebra.m. If one wants to run only the Gröbner Basis code, then one should set the file NCGB.m up so that it loads shortNCAlgebra.m. The way in which one uses one versus the other is to edit the file NCGB.m and set the variable longLoadTime to either True or False (i.e., if one wants all of NCAlgebra, then move the statement ‘longLoadTime = True;’ after the statement ‘longLoadTime = False;’).

\underline{1.2. Simplifying Expressions} 11

NCPInverses.m loaded
NCMono.m loaded
NCSolve.m loaded
NCMatMult.m loaded
NCAliasFunctions.m loaded
NCAlias.m loaded
Starting Main
LinkObject[p9c, 1, 1]
0

1.2 Simplifying Expressions

Suppose we want to simplify the expression A^{3}b^{3} − c assuming that we know Ab = 1. First NCAlgbra.m requires us to declare the variables as noncommutative.

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

Now we must set an order on the indeterminates 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.

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

We now simplify the expression a^{3}b^{3} − c by typing

In[5]:= NCSimplifyAll[a**a**a**b**b**b -c, a**b-1, 10];

Quantities of formulas scroll by on the screen when this command is executed. The C++ version of the code prints preliminary answers to the screen. One must wait until the printing of the preliminary answers stops and the answer is returned to Mathematica. You get the answer as the following Mathematica output.

Out[5]= {1 - c}

Now we turn to an example with more complicated (though mathematically intuitive)

notation. We shall use the variables y, Inv[y], Inv[1 − y], a and x . (1.1) Actually, in NCAlgebra, lower case letters are noncommutative by default, and functions of noncommutative indeterminates are noncommutative, so the SetNonCommutative command while harmless is not necessary.

We want to simplify a polynomial in the indeterminates (1.1). We must give the computer

a precise idea of what we mean by simple verses complicated. This formally corresponds to specifying an order on the indeterminates. If Inv[1 − y] is going to stand for the inverse of 1 − y, etc, as the notation suggests, then the order

y < Inv[y] < Inv[1 − y] < a < x

is sensible. To set this order input ^{3}

In[6]:= SetMonomialOrder[{ y, Inv[y], Inv[1-y], a, x}]

Suppose that we want to connect the Mathematica variables Inv[y] with the mathematical idea of the inverse of y and Inv[1 − y] with the mathematical idea of the inverse of 1 − y. ^{4} Then just type in the defining relations for the inverses involved.

In[7]:= resol = {
                  y ** Inv[y] == 1,   Inv[y] ** y == 1,
                 (1 - y) ** Inv[1 - y] == 1,   Inv[1 - y] ** (1 - y) == 1}
Out[3]= {y ** Inv[y] == 1, Inv[y] ** y == 1,
>       (1 - y) ** Inv[1 - y] == 1, Inv[1 - y] ** (1 - y) == 1}

As an exercise we simplify the two expression x ∗ ∗x and x + Inv[y] ∗ ∗Inv[1 − y] assuming that y satisfies resol and x ∗ ∗x = a. Experts will note that since we use a Gröbner Basis for resol together with x ∗ ∗x − a = 0, we must set a limit on how many iterations we permit; here we specify at most 10 iterations.

In[8]:= NCSimplifyAll[{x**x,x+Inv[y]**Inv[1-y]},Join[{x**x-a},resol],10];
Out[8]= {a, x + Inv[1 - y] + Inv[y]}

Despite the suggestive and complicated form of Inv[y], it has the same status as a single

letter with regard to all of the commands which we have just demonstrated.

Next we illustrate an extremely valuable simplification command. The following example

performs the same computation as the previous command, although one does not have to type in resol explicitly. More generally one does not have to type in relations involving the definition of inverse explicitly.

In[9]:= <<NCSR6.m
In[10]:= NCSR6[{x**x**x,x+Inv[z]**Inv[1-z]},{x**x-a},10]
Out[11]= {a ** x, x + inv[1 - z] + inv[z]}

3This sets a graded lexicographic on the monic monomials involving the variables y, Inv[y], Inv[1 − y], a and x with y < Inv[y] < Inv[1 − y] < a < x.

4See also §7.2.12

\underline{1.3. Using an input file} 13

1.2.1 Saving time when typing relations for things like inverses

One can save time in inputting various types of starting relations easily by using the command NCMakeRelations. See §7.2.12.

In[12]:= <<NCMakeRelations.m
In[13]:= NCMakeRelations[{Inv,y,1-y}]
Out[13]= {y ** Inv[y] == 1, Inv[y] ** y == 1, (1 - y) ** Inv[1 -
y] == 1,
>    Inv[1 - y] ** (1 - y) == 1}

WARNING

It is traditional in mathematics to use only single characters for indeterminates (e.g., x,

y and α). However, we allow these indeterminate names as well as more complicated constructs such as

Inv[x], Inv[y], Inv[1 − x ∗ ∗y] and Rt[x] .

In fact, we allow f[expr] to be an indeterminate if expr is an expression and f is a Mathematica symbol which has no Mathematica code associated to it (e.g., f = Dummy or f = Joe, but NOT f = List or f = P lus). Also one should never use inv[m] to represent m^{−1} because NCAlgebra has already assigned a meaning to inv[m]. It knows that inv[m] ∗ ∗m is 1 which will transform your starting set of data prematurely. Likewise tp[m], aj[m] and rt[x] should never be used.

1.3 Using an input file

Because Mathematica is interpretive, it is tempting to perform computations by starting Mathematica and start typing. Often, however, we have found that it is often the case that it is helpful to construct an auxilary file and then load that file. This has the benefit of allowing one to modify the computation slightly and be able to rerun it again and the benefit of recording the computation.

A common input file may have the form First version of the file

Get["NCGB.m"];
start = {x**x-a,
         Inv[y]**y-1,y**Inv[y]-1,
         (1-x)**Inv[1-x]-1,
         Inv[1-x]**(1-x)-1
};
start = NCE[start];
Print["start:",start];

After the file is run, one can see whether or not the file executed correctly. It does not

— we forgot the SetNonCommutative command. The new files would look like:

Second version of the file

\underline{1.4. Making A Gröbner Basis} 14

Get["NCGB.m"];
SNC[a,x,y,Inv[x],Inv[1-y]];
start = {x**x-a,
         Inv[y]**y-1,y**Inv[y]-1,
         (1-x)**Inv[1-x]-1,
         Inv[1-x]**Inv[1-x]-1
};
start = NCE[start];
Print["start:",start];

After restarting Mathematica and running this command, we find that start is what we

expect it to be. We can then remove the P rint statement and add more code.

At this point, some readers may want to skip to Chapter 2.

1.4 Making A Gröbner Basis

A reader who has no explicit interest in GB’s might want to skip this section, however it does say what underlies the simlification commands above. Readers who lack background in Gröbner Basis may want to read Appendix 15 first.

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 earlier. A user does not need to know theoretical background related to monomials orders. Indeed, as we shall see in the next chapter, 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 desire 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. However at this point in the exposition we assume that we have set a monomial order.

1.4.1 First Example

The following commands makes a Gröbner Basis for resol with respect to the monomial order which has been set.

In[7]:= NCMakeGB[resol,10]
Out[7]= {1 - Inv[1 - y] + y ** Inv[1 - y], -1 + y ** Inv[y],
>    1 - Inv[1 - y] + Inv[1 - y] ** y, -1 + Inv[y] ** y,
>    -Inv[1 - y] - Inv[y] + Inv[y] ** Inv[1 - y],
>    -Inv[1 - y] - Inv[y] + Inv[1 - y] ** Inv[y]}

1.4.2 Changing polynomials to rules

The following command converts a list of relations to a list of rules subordinate to the monomial order specified above.

In[8]:= PolyToRule[%]
Out[8]= {y ** Inv[1 - y] -> -1 + Inv[1 - y], y ** Inv[y] -> 1,
>    Inv[1 - y] ** y -> -1 + Inv[1 - y], Inv[y] ** y -> 1,
>    Inv[y] ** Inv[1 - y] -> Inv[1 - y] + Inv[y],
>    Inv[1 - y] ** Inv[y] -> Inv[1 - y] + Inv[y]}

1.4.3 Changing rules to polynomials

The following command converts a list of rules to a list of relations. Note that Out[9] is the same as Out[7]. In fact, if p is a polynomial, then PolyToRule[RuleToPoly[p] is p/LC(p) where LC(p) is the leading coefficient of p. Also, if r is a rule, then RuleToPoly[PolyToRule[r]] is r.

In[9]:= PolyToRule[%]
Out[9]= {1 - Inv[1 - y] + y ** Inv[1 - y], -1 + y ** Inv[y],
>    1 - Inv[1 - y] + Inv[1 - y] ** y, -1 + Inv[y] ** y,
>    -Inv[1 - y] - Inv[y] + Inv[y] ** Inv[1 - y],
>    -Inv[1 - y] - Inv[y] + Inv[1 - y] ** Inv[y]}

1.4.4 Simplifying using a GB

We can apply the rules in §1.4.2 repeatedly to an expression to put it into “canonical form”. Often the canonical form is simpler than what we started with.

In[10]:= Reduction[{Inv[y]**Inv[1-y] - Inv[y]},Out[8]]
Out[10]= {Inv[1 - y]}

1.4.5 Second Example

Another example which will make a Gröbner Basis is NCMakeGB §7.2.1.

In[11]:= NCMakeGB[{x**y - a, x**y - b, x**x - a, x**x**x - b}, 10]

There is extensive output to the screen while the program is running. The result is:

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

Our favorite format (as can seen from the output to the screen) for displaying lists of

relations is ColumnForm.

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

NCProcess: The concepts

We recommend that the reader read the first four pages of the first chapter of the NCAlgebra manual.

We turn to a much more adventurous pursuit which is in a primitive stage. This is a

highly computer assisted method for discovering certain types of theorems.

At the beginning of “discovering” a theorem, an engineering or math problem is often

presented as a large system of matrix or operator equations. The point is to isolate and to minimize what the user must do by running heavy algorithms. Often when viewing the output of the algorithm, one can see what additional hypothesis should be added to produce a useful theorem and what the relevant matrix quantities are.

We are under the impression that many theorems in engineering systems, matrix and

operator theory amount to giving hypotheses under which it is possible to solve large collections of equations. (It is not our goal to reprove already proven theorems, but rather to develop technique which will be able to be used to discover new theorems.)

Rather than use the word “algorithm”, we call our method a strategy since it allows for

modest human intervention. We are under the impression that many theorems might be derivable in this way.

Unlike in Chapter 1, we will not be providing the code which one would use to implement

these ideas. The description of the code is provided in Chapter 3.

We begin by describing a facet of noncommutative Gröbner Basis which have not yet

described. GB’s are very effective for eliminating, or solving for, variables.

2.1 Elimination

We use the abbreviations GB and GBA to refer to Gröbner Basis and Gröbner Basis Algorithm respectively. Since we will not always let the GBA algorithm run until it finds a Gröbner Basis, we will often be dealing with sets which are not Gröbner Basis, but rather an intermediate result. We call such sets of relations partial GB’s.

\underline{2.2. What is a strategy?} 17

Commutative Gröbner Basis Algorithms can be used to systematically eliminate variables from a collection (e.g., p_{j}(x_{1},…, x_{n}) = 0) of polynomial equations soas to put it in triangular form. One specifies and order on the variables (x_{1} < x_{2} < x_{3} < … < x_{n} ) ^{1} which corresponds to ones priorities in eliminating them. Here a GBA will try hardest to eliminate x_{n} and try the least to eliminate x_{1}. The output from it is a list of equations in “a canonical form” which is triangular: ^{2}

q_{1}(x_{1}) = 0 (2.1) q_{2}(x_{1}, x_{2}) = 0 (2.2) q_{3}(x_{1}, x_{2}, x_{3}) = 0 (2.3) … (2.4) q_{k}(x_{1},…, x_{n}) = 0 . (2.5)

Here the polynomials {q_{j} : j = 1,… k} generate the same ideal that the polynomials {p_{j} : 1 ≤ j ≤ k} do. Therefore, the set of solutions to the system the polynomial equations p_{j} = 0 equals the set of solutions to the system of polynomial equations q_{j} = 0. This canonical form greatly simplifies the task of solving systems of polynomial equations by allowing one to backsolve for x_{j} in terms of x_{1},…, x_{j−1}. The effect of the ordering is to specify that variables high in the order will be eliminated while variables low in the order will be kept.

In the noncommutative case, again a GB for a collection of polynomial equations is

a collection of noncommuting polynomial equations in triangular form (see [HSstrat]). There are some difficulties which don’t occur in the commutative case. For example, there is often a high level of redundency between the polynomials in a noncommutative GB. However, we present software here based on the noncommutative GBA which might prove to be extremely valuable in some situations.

2.2 What is a strategy?

Any method which assumes that all of the hypothesis can be stated algebraically and are known at the beginning of the computation will be of limited practical use.

What we shall describe is a method which allows one to add (algebraic) hypotheses as one

proceeds with the computation. These hypotheses would be motivated by insights gained in the course of a computer session and the user would have to record and justify them independently of the computer run. However, we do want to be extremely systematic so we shall propose a structure which is algorithm like but a bit looser.

2.2.1 NCProcess

The program which we shall use which is based upon a GBA will be called NCProcess and will be described in §2.2.4. A person can use this practical approach to performing computations and proving theorems without knowing anything about GBA’s. Indeed, this chapter is a self-contained description of our method.

1From this ordering on indeterinates one induces a order on polynomials which is different than we used before.

There we used a graded order here we use a strict lexicographic order.

2There need not be ≤ n equations in this list and there need not be any equation in just one variable.

The input to NCProcess is:

I1. A list of knowns.

I2. A list of unknowns (together with an order which gives you priorities eliminating them).

I3. A collection of equations in these knowns and unknowns.

The knowns (I1) are set using the SetKnowns command §7.3.1 The unknowns (I2) are

set using the SetUnknowns command §7.3.2. For example, SetKnowns[A, B, C] sets A, B and C known and SetUnknowns[x, y, z] sets x, y and z unknown. Also, in this case, the algorithms sets the highest prioirity on eliminating z, then y and then x.

The output of NCProcess is a list of expressions which are mathematically equivalent

to I3, hopefully have solved for some unknowns and are presented to the user as

O1. Unknowns which have been solved for and equations which yield these unknowns.

O2. Equations selected or created by the user. ^{3} For example, in the context of S1 below, one would want to select the equation E_{17}. There are also times during a strategy when one wants to introduce new variables and equations. This is illustrated in §2.3.

O3. Equations involving no unknowns.

O4. Equations involving only one unknown.

O5. Equations involving only 2 unknowns. etc.

2.2.2 Strategy

The idea of a strategy is :

S1. Run NCProcess which creates a display of the output (see O1-O5 in §2.2.1) and look at the list of equations involving only one unknown (say a particular equation E_{17} contains only x_{3}).

S2. The user must now make a decision about equations in x_{3} (e.g., E_{17} is a Riccati equation so I shall not try to simplify it, but leave it for Matlab). Now the user declares the unknown x_{3} to be known and runs the GB algorithm again.

S3. The user must again make a decision and the process repeats.

S4. Knowing when a strategy stops is discussed in §2.2.3.

3These do not exist in the first run. A user-selected equation is a polynomial equation which the user has selected. An effect which this has is to make the algorithm described in §2.2.5 treat these equations as “digested”.

This, for example, implies that they are given the highest priority in eliminating other equations when NCProcess runs. For example, equations which one knows can be solved by Matlab can be selected.

The above listing is, in fact, a statement of a 1-strategy. Sometimes one needs a 2-strategy

in that the key is equations in 2 unknowns.

The point is to isolate and to minimize what the user must do. This is the crux of a

strategy.

2.2.3 When to stop

There are various criteria for stopping.

The digested equations (those in items O1, O2 and O3) often contain the hypotheses of

the desired theorem and the main flow of its proof. If the starting equations follow as algebraic consequences of the digested relations, then we should stop. This last statement is true if and only if the GB generated by the digested equations reduce (in a standard way) the set of starting equations to 0. Checking this on a computer is a purely mechanical process.

2.2.4 Redundant Equations

We mentioned earlier that we are using the Gröbner Basis algorithm (GBA), i.e. NCMakeGB. GBA and the formatted output (§2.2.1) alone are not enough to generate solutions to engineering or math problems. This is because they generate too many equations. It is our hope and our experience that these equations which it generates contain all of the equations essential to solution of whatever problem you are treating. On the other hand, it contains equations derived from these plus equations derived from those derived from these as well as precursor equations which are no longer relevant. That is, a GB contains a few jewels and lots of garbage. In technical language a GB is almost never a minimal basis for an ideal and what a human seeks in discovering a theorem is a minimal basis for an ideal. Thus we have algorithms and substantial software for finding small (or smallest) sets of equations associated to a problem. The process of running GBA followed by an algorithm for finding small sets of equations is what constitutes NCProcess.

2.2.5 Summary

More Here?

We have just given the basic ideas. As a strategy proceeds, more and more equations

are digested by the user and more and more unknowns become knowns. Thus we ultimately have two classes of knowns: original knowns K_{0} and user designated knowns K_{U}. Often a theorem can be produced directly from the output by taking as hypotheses the existence of knowns K_{U} ∪ K_{0} which are solutions to the equations involving only knowns.

Assume that we have found these solutions. To prove the theorem, that is to construct

solutions to the original equations, we must solve the remaining equations. Fortunately, the digested equations often are in a block triangular form which is amenable to backsolving. This is one of the benefits of “digesting” the equations.

An example, makes all of this more clear.

\underline{2.3. A Simple Example} 20

2.3 A Simple Example

We derive a theorem due to Bart, Gohberg, Kaashoek and Van Dooren. The reader can skip the statement of this theorem (§2.3.1) if he wishes and go directly to the algebraic problem statement.

2.3.1 Background

Theorem([BGKvD]) A minimal factorization

[figure: [e, f, g, 1]; state dim = n2; state dim = n1; [a, b, c, 1]]

of a system [A, B, C, 1] corresponds to projections P_{1} and P_{2} satisfying P_{1} + P_{2} = 1,

AP_{2} = P_{2}AP_{2} (A − BC)P_{1} = P_{1}(A − BC)P_{1} (2.6)

provided the state dimension of the [A, B, C, 1] system is n_{1} + n_{2}. (which has the geometrical interpretation that A and A − BC have complimentary invariant subspaces).

We begin discussing how one might derive this theorem by giving the algebraic statement

of the problem. Suppose that these factors exist. By the statespace isomorphism theorem (Youla -Tissi), there is map

(2.7) (m_{1}, m_{2}) : Statespace of the product ⟶ Statespace of the original

which intertwines the original and the product system. Also minimality of the factoring is equivalent to existence of left and right inverses (im_{1}^{T} , im_{2}^{T})^{T} to (m_{1}, m_{2}). These requirements combine to imply that each of the following expressions is zero.

2.3.2 The Problem

(F AC) \begin{matrix}Am_{1} − m_{1}a − m_{2}fc & Am_{2} − m_{2}e \\ B − m_{1}b − m_{2}f & −c + C m_{1} \\ im_{1}m_{1} − 1 & im_{2}m_{2} − 1 \\ im_{1}m_{2} & im_{2}m_{1} \\ −g + C m_{2} & m_{1}im_{1} + m_{2}im_{2} − 1 \end{matrix}

Each of these expressions must equal 0. Indeed minimal factors exist iff there exist solutions m_{1}, m_{2}, im_{1}, im_{2}, a, b, c, e, f and g to these equations. Here A, B and C are known.

The problem is to solve these equations. That is, we want a constructive theorem which

says when and how they can be solved.

2.3.3 Solution via a Strategy

We now apply a strategy to see how one might discover this theorem.

We run NCP rocess (§7.5.1). The input is the equations (F AC), together with dec-

laration of A, B, C as knowns and the remaining variables as unknowns. Here is the output displayed in what we call a spreadsheet. The “**” below denotes matrix multiplication and -> can be read as an equal sign. We give a list of the commands used to show what is involved in doing a computation, but we will explain little about them in this chapter. The commands will be explained in Chapter 3.

In[1]:=Get["NCGB.m"];
In[2]:=SetNonCommuative[A,B,C0,m1,m2,im1,im2];
In[3]:=SetKnowns[A,B,C];
In[4]:=SetUnknowns[{m1,m2},{im1,im2},{a,b,c,e,f,g}];
In[5]:=FAC = {A**m1 - m1**a - m2**f**c,
              A**m2 - m2**e,
              B - m1**b - m2**f,
              -c + C0**m1,
              -g + C0**m2,
              im1**m1 - 1,
              im1**m2,
              im2**m1,
              im2**m2 - 1,
              m1**im1 + m2**im2 - 1};

The command which produces the output in the file Spreadsheet1 is the following.

In[6]:= result = NCProcess[FAC,2,"Spreadsheet1",SBByCat->True];

Here NCP rocess is being applied to the set of relations F AC for 2 iterations. The

NCP rocess command has two outputs, one will be stored in result and the other will be stored in the file Spreadsheet1. The output of the file is below and is likely to be more interesting and useful than the value of result. Also, the option SBByCat can be set to T rue or F alse. The reader who wishes to experiment by replacing F AC with a different set of relations or by changing T rue to F alse above may do so before reading the next chapter. No matter which option is used, the file created by NCP rocess is a list of equations whose solution set is the same as the solution set for F AC.

The file Spreadsheet1.dvi appears below.

THE ORDER IS NOW THE FOLLOWING: A < B < C << m_{1} < m_{2} << m_{1}^{−1} < m_{2}^{−1} << a < b < c < d < e < f < g

YOUR SESSION HAS DIGESTED THE FOLLOWING RELATIONS The corresponding rules are the following: a → m_{1}^{−1} A m_{1} b → m_{1}^{−1} B c → C m_{1} e → m_{2}^{−1} A m_{2} f → m_{2}^{−1} B g → C m_{2}

USER CREATIONS APPEAR BELOW

SOME RELATIONS WHICH APPEAR BELOW MAY BE UNDIGESTED

THE FOLLOWING VARIABLES HAVE NOT BEEN SOLVED FOR: {m_{1}^{−1}, m_{2}^{−1}, m_{1}, m_{2}}

The expressions with unknown variables {m_{1}^{−1}, m_{1}} and knowns {A, B, C}

m_{1}^{−1} m_{1} → 1

m_{1} m_{1}^{−1} B C m_{1} → −A m_{1} + B C m_{1} + m_{1} m_{1}^{−1} A m_{1}

The expressions with unknown variables {m_{1}^{−1}, m_{2}} and knowns {A}

m_{1}^{−1} m_{2} → 0

m_{1}^{−1} A m_{2} → 0

The expressions with unknown variables {m_{2}^{−1}, m_{1}} and knowns {A, B, C}

m_{2}^{−1} m_{1} → 0 m_{2}^{−1} B C m_{1} → m_{2}^{−1} A m_{1}

The expressions with unknown variables {m_{2}^{−1}, m_{2}} and knowns {}

m_{2}^{−1} m_{2} → 1

The expressions with unknown variables {m_{2}^{−1}, m_{1}^{−1}, m_{2}, m_{1}} and knowns {}

m_{2} m_{2}^{−1} → 1 + −m_{1} m_{1}^{−1}

The unknowns a,b,c,e, f and g are solved for. There are no equations in 1 unknown.

There are 4 categories of equations in 2 unknowns. There is one category of equations in 4 unknowns. A user must observe that the first equation which we marked with <=== is an equation in the unknown quantity m_{1} ** im_{1}. One makes the assignment: P_{1} = m_{1} im_{1} . (2.8)

Then the user may notice that the second equation marked with <=== in an equation in only one unknown quantity m_{2} ** im_{2} once the above assignment has been made and P_{1} is considered known^{4}. These observations lead us to “select” (see footnote corresponding to O2 in §2.2.1) the equations m_{1} im_{1} − P_{1}, im_{1} m_{1} − 1, m_{2} im_{2} − 1 + P_{1} and im_{2} m_{2} − 1.

Run NCP rocess again with (2.8) added and P_{1} declared known as well as A,B and C

declared known.

THE ORDER IS NOW THE FOLLOWING: A < B < C < P_{1} << m_{1} < m_{2} << m_{1}^{−1} < m_{2}^{−1} << a < b < c < e < f < g

YOUR SESSION HAS DIGESTED THE FOLLOWING RELATIONS

THE FOLLOWING VARIABLES HAVE BEEN SOLVED FOR: {a, b, c, e, f, g}

The corresponding rules are the following: a → m_{1}^{−1} A m_{1} b → m_{1}^{−1} B c → C m_{1} e → m_{2}^{−1} A m_{2} f → m_{2}^{−1} B g → C m_{2}

4If the user does not notice it at this point, it will become very obvious with an additional run of NCP rocess.

The expressions with unknown variables {} and knowns {A, B, C, P_{1}}

P_{1}^{2} → P_{1}

P_{1} A P_{1} → P_{1} A

P_{1} B C P_{1} → −A P_{1} + P_{1} A + B C P_{1}

USER CREATIONS APPEAR BELOW

m_{1} m_{1}^{−1} → P_{1}

m_{1}^{−1} m_{1} → 1

m_{2}^{−1} m_{2} → 1

m_{2} m_{2}^{−1} → 1 − m_{1} m_{1}^{−1}

SOME RELATIONS WHICH APPEAR BELOW MAY BE UNDIGESTED

THE FOLLOWING VARIABLES HAVE NOT BEEN SOLVED FOR: {m_{1}^{−1}, m_{2}^{−1}, m_{1}, m_{2}}

The expressions with unknown variables {m_{1}^{−1}, m_{1}} and knowns {P_{1}}

\underline{2.4. The end game} 25

m_{1}^{−1} m_{1} → 1 is a user select m_{1} m_{1}^{−1} → P_{1} is a user select

The expressions with unknown variables {m_{2}^{−1}, m_{2}} and knowns {}

m_{2}^{−1} m_{2} → 1 is a user select

The expressions with unknown variables {m_{2}^{−1}, m_{1}^{−1}, m_{2}, m_{1}} and knowns {}

m_{2} m_{2}^{−1} → 1 + −m_{1} m_{1}^{−1} is a user select

Note that the equations in the above display which are in the undigested section (i.e.,

below the lowest line of equal signs) are repeats of those which are in the digested section (i.e., above the lowest line of equal signs). We relist these particular equations simply as a convenience for categorizing them. We will see how this helps us in §2.4. Since all equations are digested, we have finished using NCP rocess (see S4). As we shall see, this output spreadsheet leads directly to the theorem about factoring systems.

2.4 The end game

Note that all equations in the spreadsheet are necessary for a factoring to exist, since they are implied by the original equations. The equations involving only knowns play a key role. In particular, they say precisely that, there must exist a projection P_{1} such that

P_{1} A P_{1} = P_{1} A and P_{1} B C P_{1} = P_{1} A − A P_{1} + B C P_{1} (2.9)

are satisfied.

The converse is also true and can be verified with the assistance of the above spreadsheet.

We now prove this. We begin by assuming a projection P_{1} exists which satisfies (2.9).

• First, solve the two equations in the category {im_{1}, m_{1}} for the matrices m_{1} and im_{1}.

• Next, solve the expressions in the category {im_{2}, m_{2}} for the matrices m_{2} and im_{2}.

• Finally, one uses the computed formulas to solve for a, b, c, e, f and g.

Here we used the fact that we are working with matrices and not elements of an abstract

algebra. Thus by backsolving through the spreadsheet, we have constructed the factors of the original system [A, B, C, I]. This proves

Theorem:[BGKvD] The system A, B, C, I can be factored if and only if there exists a projection P_{1} such that P_{1} A P_{1} = P_{1} A and P_{1} B C P_{1} = P_{1} A − A P_{1} + B C P_{1} are satisfied.

Note the known equations can be neatly expressed in terms of P_{1} and P_{2} = 1 − P_{1}.

Indeed, it is easy to check with a little algebra that these are equivalent to (2.6). It is a question of taste, not algebra, as to which form one chooses.

Our efforts are in a primitive stage and the brevity of this presentation suppresses some

of the advantages and some of the difficulties. For example, one might not instantly have all of the insight which lead to the second spreadsheet. In practice a session in which someone “discovers” this theorem might use many spreadsheets. All that matters is that one makes a little bit of progress with each step.

NCProcess: The command

Now that the user has a feel for what we are doing we describe the command one runs over and over again to produce the example in Chapter 2. We are currently working on this command so it is changing with time.

3.1 SetKnowns and SetUnknowns

In most mathematics and engineering appications, certain quantities are considered known and others are considered unknown. The goal is usually to solve for unknowns in terms of the knowns, or to solve for some unknowns in terms of others. In a Strategy session, one must declare what variables are known and what ones are unknown. While this declaration evolves through the course of a session it is at any moment a part of the environment. Indeed before the NCP rocess command can be called, it is necessary to set all variables to be either known or unknown. Mathematically, the variables which are declared unknown are those which one wants to solve for.

An example is :

Example 3.1 SetNonCommutative[A,B,C,a,b,c];
SetKnowns[A,B,C];
SetUnknowns[{a,b,c}];

After this you can run NCP rocess on any equations in the variables A, B, C, a, b, c.

A, B, C are knowns and a, b, c to be unknowns which has the effect that NCP rocess will try to solve for a, b, c and produce equations from which they have been eliminated. Also the spreadsheet displayed by NCP rocess keeps books based on what is known and unknown.

A more subtle fact is that we have also imposed an order on variables A, B, C, a, b, c

which expresses our priorities for eliminating them. We use the notation

A < B < C << a < b < c

to denote the order imposed in the example. NCP rocess tries hardest to eliminate c and the least to solve for A.

\underline{3.2. NCProcess} 28

If you are running a Strategy session and stop making progress one of the first things to

try is changing the order.

The << means that NCP roccess goes to much greater lengths ^{1} to eliminate a, b, c

before turning to A, B, C.

A fancier example of such prioritizing is :

Example 3.2 SetNonCommutative[A,B,C,a,b,c,e,f,g];
SetKnowns[A,B,C];
SetUnknowns[{a,b,c},{d,e,f}];

This produces the ordering

A < B < C << a < b < c << d < e < f ,

There is an alternative to SetKnowns and SetUnknowns. The command SetMonomialOrder[a, b, c, d, e, f]

has exactly the same effect as the commands in Example 2.

Only after an ordering is set can one proceed with the NCP rocess command.

3.2 NCProcess

3.2.1 NCProcess[aListOfPolynomials,iterations,fileName]

Aliases: None

Description: NCProcess[aListOfPolynomials,iterations,fileName] finds a new generating set for the ideal generated by aListOfPolynomials along the lines of the demo presented in Chapter

2. The spreadsheets presented in §2.2.2 are the contents of the files fileName, and are produced by the command NCP rocess. In addition to creating the file fileName, NCP rocess returns as Mathematica output a list consisting of three lists.

(1) A partial GB for the digested relations.

(2) The digested relations in the simplified second partial GB.

(3) The undigested relations in the simplified second partial GB.

In practice, the user runs NCP rocess, then looks at the file fileName in order to get ideas for the next step. When the user decides on the next step he can use some of the lists of Mathematica output in addition to some new relations as inputs to the next NCP rocess call.

1<< is called a multigraded lexicographic order. Intuitively, we think of A, B and C as corresponding to variables in some engineering problem which represent quantities which are known and a, b, c, d, e and f to be unknown. The fact that d, e and f are in the top level indicates that we are very interested in solving for d, e and f in terms of A, B, C, a, b and c, but are not willing to solve for b in terms of expressions involving either d, e or f.

More precise discussion of mulitgraded lex orderings are in Chapter ?? Where are they? or in Chapter ?? in [CLS].

\underline{3.3. NCProcess Options} 29

Arguments: aListOfP olynomials is a list of polynomials. iterations is a natural number. ^{2} fileName is a character string.

Comments \ Limitations: Not available before NCAlgebra 1.2

The command NCProcess calls NCMakeGB[aListOfP olynomials, iters], which is an

algorithm for producing a partial Gröbner basis. This produces many new relations whose solution set is the same as the solution set for aListOfP olynomials. Typically, many of the relations follow from other relations within the same output. There are many options for NCP rocess which remove “mathematically redundent” relations before generating the spreadsheet in fileName and lists (2) and (3) of the Mathematica output. The various options as well as the default options for NCP rocess are described in §3.4.3.

3.2.2 Examples

Here are some examples of how the NCP rocess command is called.

NCProcess[aListOfPolys,2,"filname"]
list = NCProcess[aListOfPolys,2,"filname",SBByCat->True,
             DegreeCap->8, DegreeSumCap->12]

3.3 NCProcess Options

3.4 NCCollectOnVars

An extremely important option for NCProcess is NCCollectOnVars. It is also an option for RegularOutput???? In addition to being an option, it can be called as a stand-alone command.

3.4.1 NCCollectOnVars[aListOfExpressions,aListOfVariables]

Aliases: NCCOV

Description: ??

Arguments: aListOfExpressions is a list of expressions. aListOfVariables is a list of variables.

Comments \ Limitations: Not available before NCAlgebra1.2

??

2Up to four iteration numbers can be specified. When only one is given, NCP rocess uses that number to choose default values for the other iteration numbers. If the user specifies four values, I_{1}, I_{2}, I_{3}, I_{4}, then I_{1} is the iterations for NCMakeGB. I_{2} is the iterations for NCMakeGB on the digesteds. I_{3} is the iterations for SmallBasis, and I_{4} is the iterations for the knowns in SmallBasis.

\underline{3.4. NCCollectOnVars} 30

This is a command which “collects” knowns and products of knowns out of expressions.

NCCollectOnV ars[X∗∗A∗∗B∗∗Z+Y ∗∗A∗∗B∗∗Z+A∗∗X+A∗∗Y, {A, B}] = (X+Y)∗∗A∗∗B∗∗Z+A∗∗(X+Y) .

Also note a fancier usage is that if we are in an environment where A and B have been

set A and B are known and X,Y and Z are unknowns, then one may omit the list of variables {A, B} in the call above. In other words,

In[2]:= SetKnowns[A,B];
In[3]:= SetUnknowns[X,Y,Z];
In[4]:= NCCollectOnVars[X**A**B**Z + Y**A**B**Z + A**X+A**Y,{A,B}]
Out[4] := (X+Y)**A**B**Z + A**(X+Y)

Another example is if A,T p[A], B1, T p[B1] B2, T p[B2] C1, T p[C1] C2 and T p[C2] are

knowns and all other variables are unknowns, then:

In[2] := long = E21 ** A ** iE21 ** E22 - E21 ** B1 ** Tp[B1] ** E12 +
>    E21 ** B2 ** Tp[B2] ** E12 + E22 ** iE12 ** Tp[A] ** E12 -
>    E21 ** B2 ** C1 ** iE21 ** E22 -
>    E22 ** iE12 ** Tp[C1] ** Tp[B2] ** E12 +
>    E21 ** B1 ** Tp[B1] ** E11 ** iE21 ** E22 -
>    E21 ** B2 ** Tp[B2] ** E11 ** iE21 ** E22 -
>    E22 ** iE12 ** E11 ** A ** iE21 ** E22 +
>    E22 ** iE12 ** E11 ** B1 ** Tp[B1] ** E12 -
>    E22 ** iE12 ** E11 ** B2 ** Tp[B2] ** E12 -
>    E22 ** iE12 ** Tp[A] ** E11 ** iE21 ** E22 +
>    E22 ** iE12 ** E11 ** B2 ** C1 ** iE21 ** E22 +
>    E22 ** iE12 ** Tp[C1] ** Tp[B2] ** E11 ** iE21 ** E22 -
>    E22 ** iE12 ** E11 ** B1 ** Tp[B1] ** E11 ** iE21 ** E22 +
>    E22 ** iE12 ** E11 ** B2 ** Tp[B2] ** E11 ** iE21 ** E22
In[3] := NCCollectOnVariables[long]
Out[3]:= E22 ** iE12 ** Tp[A] ** (E12 - E11 ** iE21 ** E22) +
>    (E21 - E22 ** iE12 ** E11) ** A ** iE21 ** E22 -
>    (E21 - E22 ** iE12 ** E11) ** B1 ** Tp[B1] **
>    (E12 - E11 ** iE21 ** E22) +
>    (E21 - E22 ** iE12 ** E11) ** B2 ** Tp[B2] **
>    (E12 - E11 ** iE21 ** E22) -
>    E22 ** iE12 ** Tp[C1] ** Tp[B2] ** (E12 - E11 ** iE21 ** E22) -
>    (E21 - E22 ** iE12 ** E11) ** B2 ** C1 ** iE21 ** E22

3.4.2 UserSelect → aListOfPolynomials

A valuable option for NCP rocess is UserSelect. Using the option

UserSelect → aListOfP olynomials

forces the polynomials in the list aListOfPolynomials to appear in a “User Selected” part of the spreadsheet generated during this call to NCP rocess. It also affects the order in which the polynomials are used inside NCMakeGB as well as reduction algorithms described in the next section. The user selected polynomials are processed early and polynomials processed later tend to be eliminated.

3.4.3 Reduction algorithms

These options for the NCP rocess command allow the user to remove relations from a (partial Gröbner) Basis for an ideal. The goal is to present a small and if one is lucky a minimal generating set for the ideal. The various options are

NCRR , NCSB etc ??– names too short??

RR, RRByCat, SB, SBByCat, RRSB, RRSBByCat .

These actually abbreviate longer names like RemoveRedundent. See §3.6. Any combination of options will leave the output of NCProcess a generating set for the ideal generated by the input relations. The more (redundant) relations you try to remove, the slower NCP rocess runs. The options indicate which algorithms will be used to remove the redundant relations. RemoveRedundent, for instance, runs very quickly, but does not do a very thorough job.

A complete list of options together with indications of their speed can be found at the

end of the chapter. If two overlapping options are set to True, like RR and RRByCat, then only one of them is actually run. The amount of time that it takes to run NCP rocess depends on which options are set.

The defaults for NCP rocess are: RR is set to True while the rest, which include Small-

Basis, SmallBasisByCategory, and several others are set to False by default.

3.4.4 DegreeCap and DegreeSumCap

One way to reduce run time for NCP rocess is to use the options capping the degree of the polynomials that are produced in the course of running NCP rocess. Also these are options which cap the degree of polynomials occurring in NCMakeGB . Indeed calling DegreeCap in NCP rocess just sets the DegreeCap for running NCMakeGB inside of NCP rocess.

This is valuable since the user will ordinarily know that a polynomial of a very high

\underline{3.5. Typical use of the NCProcess command} 32

degree will not be useful to him, there is no reason to produce it. It is not the time that it takes to produce a large polynomial that is the primary factor. Rather it is the reduction algorithms that will get bogged down trying to remove it. Degree caps can prevent the algorithm from ever producing polynomials over a certain degree, or combining polynomials over a certain degree, and the user will still be left with a generating set for the ideal generated by the input relations. There are two different options associated with degree caps.

DegreeCap → 8

for instance, would prevent a polynomial of degree 8 or higher from combining with a polynomial of higher degree.

DegreeSumCap → 10

would prevent two polynomials whose degrees add up to 10 or more from combining. Degree caps could prevent an important relation from being created, so when there is a lack of progress, raising the degree caps as well as the iteration number would be the next step.

WE URGE USE OF DEGREE CAPS. THEY SAVE A LOT OF TIME.

3.4.5 DegreeCapSB and DegreeSumCapSB

Beginners should skip this and rely on the NCP rocess defaults. The reducing algorithms SmallBasis (§9.3.1) and SmallBasisByCategory (§9.3.2) call NCMakeGB (§7.2.1). Thus DegreeCaps are valuable in limiting the time they consume. NCP rocess[polys, iters, ”filename”, DegreeCapSB → j_{1}, DegreeSumCapSB → j_{2}, OtherOptions] produces the call

NCMakeGB[polys, iters + 1??, DegreeCap → j_{1}, DegreeSumCap → j_{2}, OtherOptions]

inside SmallBasis (§9.3.1) and SmallBasisByCategory (§9.3.2). More appears on this in §9.3 describing the commands (not just options) SmallBasis and SmallBasisByCategory.

The defaults at the moment inside of NCP rocess are

DegreeCapSB → DegreeCap + 1
DegreeSumCapSB → DegreeSumCap + 1

3.4.6 TeX

This option gives spreadsheets a LaTEXappearance. The default is T eX− > T rue.

3.5 Typical use of the NCProcess command

Now we demonstrate the NCP rocess command by “solving ” FAC as we did in Chapter 2. While we show an interactive session the user probably will want to type the commands into a file and load them into your session. This is standard practice among Mathematica users and saves lots of time.

In[1]:=Get["NCGB.m"];
In[2]:=SetNonCommutative[A,B,C0,m1,m2,im1,im2];
In[3]:=SetKnowns[A,B,C];
In[4]:=SetUnknowns[{m1,m2},{im1,im2},{a,b,c,e,f,g}];
In[5]:=FAC = {A**m1 - m1**a - m2**f**c,

              A**m2 - m2**e,
              B - m1**b - m2**f,
              -c + C0**m1,
              -g + C0**m2,
              im1**m1 - 1,
              im1**m2,
              im2**m1,
              im2**m2 - 1,
              m1**im1 + m2**im2 - 1};
In[6]:= result = NCProcess[FAC,2,"Spreadsheet1",SBByCat->True];

The first command simply loads the noncommutative Gröbner basis package into Math-

ematica. Then we set the variables that we are going to use to be noncommutative.

The third and fourth input commands sets the monomial order that will be used in

solving for and eliminating variables as explained in Chapter 8. The list FAC is the set of relations that describe the problem as explained in §2.3.2. The call to NCP rocess will run two iterations on FAC and clean up the result using the option SBByCat before creating the file “Spreadsheet1” and returning the final result as Mma output.

Here is the file “Spreadsheet1”

THE ORDER IS NOW THE FOLLOWING: A < B < C << m_{1} < m_{2} << m_{1}^{−1} < m_{2}^{−1} << a < b < c < d < e < f < g

YOUR SESSION HAS DIGESTED THE FOLLOWING RELATIONS

THE FOLLOWING VARIABLES HAVE BEEN SOLVED FOR: {a, b, c, e, f, g}

The corresponding rules are the following: a → m_{1}^{−1} A m_{1} b → m_{1}^{−1} B c → C m_{1} e → m_{2}^{−1} A m_{2} f → m_{2}^{−1} B g → C m_{2}

USER CREATIONS APPEAR BELOW THE FOLLOWING VARIABLES HAVE NOT BEEN SOLVED FOR: {m_{1}^{−1}, m_{2}^{−1}, m_{1}, m_{2}}

The expressions with unknown variables {m_{1}^{−1}, m_{1}} and knowns {A, B, C} m_{1}^{−1} m_{1} → 1

• (1 − m_{1} m_{1}^{−1}) A m_{1} − (1 − m_{1} m_{1}^{−1}) B C m_{1} m_{1} m_{1}^{−1} B C m_{1} → −A m_{1} + B C m_{1} + m_{1} m_{1}^{−1} A m_{1}

The expressions with unknown variables {m_{1}^{−1}, m_{2}} and knowns {A} m_{1}^{−1} m_{2} → 0 m_{1}^{−1} A m_{2} → 0

The expressions with unknown variables {m_{2}^{−1}, m_{1}} and knowns {A, B, C} m_{2}^{−1} m_{1} → 0 m_{2}^{−1} B C m_{1} → m_{2}^{−1} A m_{1}

The expressions with unknown variables {m_{2}^{−1}, m_{2}} and knowns {} m_{2}^{−1} m_{2} → 1

The expressions with unknown variables {m_{2}^{−1}, m_{1}^{−1}, m_{2}, m_{1}} and knowns {}

m_{2} m_{2}^{−1} → 1 − m_{1} m_{1}^{−1}

The file above is the same as the first one that was discussed in the previous chapter

except that NCCOV − > T rue,T eX− > F alse. It sits outside of Mma, so it is only for viewing and it is not directly executable. The strategy that the user follows at this point was described in §2.3.3. Recall that it led the user to select the relations

m1 ∗ ∗im1 − P 1, im1 ∗ ∗m1 − 1, im2 ∗ ∗m2 − 1, m2 ∗ ∗im2 − 1 + m1 ∗ ∗im1

and to declare the new variable P_{1} to be known. Next we describe how this is input to NCP rocess in order to produce the second spreadsheet from §2.3.3.

The Mma output of the NCP rocess command above is a list named result containing

three lists. Recall that in Mma the way to get sublist number j inside result is to type result[[j]]. The second round of this strategy session is

In[7]:= SetKnowns[A,B,C,P1];
In[8]:= digested = result[[2]]
In[9]:= undigested = result[[3]]
In[10]:= discovered = {m1**im1-P1,im1**m1-1,im2**m2-1,m2**im2-1+m1**im1};
In[11]:= nextinput = Union[digested,discovered,undigested]
In[12]:= NCProcess[nextinput,2,"Spreadsheet2",
                     UserSelect->discovered,
                     SBByCat->True,DegreeCap->3,DegreeSumCap->6];

Now we discuss the input to NCP rocess above. Digested and undigested are the last

two lists from the list result which the previous NCP rocess command returned, and discovered includes the new definition of P_{1}. The union of these three lists is taken as the input for the second NCP rocess run. Once again we used two iterations. This is a good number of iterations to start with. More iterations can be used if there is a lack of progress. The next argument is a string which refers to a file name which will store the spreadsheet. The options, however, are different than the first NCP rocess call. The UserSelect option as described in §3.4.2 causes the discovered relations to be given high priority. SBByCat is set to true as it was in the first run. The DegreeCaps are set in order to save time as explained in §3.4.4 above.

Here is the file “Spreadsheet2”

THE ORDER IS NOW THE FOLLOWING: A < B < C < P_{1} << m_{1} < m_{2} << m_{1}^{−1} < m_{2}^{−1} << a < b < c < d < e < f < g

YOUR SESSION HAS DIGESTED THE FOLLOWING RELATIONS The corresponding rules are the following: a → m_{1}^{−1} A m_{1} b → m_{1}^{−1} B c → C m_{1} e → m_{2}^{−1} A m_{2} f → m_{2}^{−1} B g → C m_{2}

The expressions with unknown variables {} and knowns {A, B, C, P_{1}}

P_{1}^{2} → P_{1}

• −P_{1} A (1 − P_{1})

P_{1} A P_{1} → P_{1} A

• A P_{1} − P_{1} A − (1 − P_{1}) B C P_{1}

P_{1} B C P_{1} → −A P_{1} + P_{1} A + B C P_{1}

USER CREATIONS APPEAR BELOW

m_{1} m_{1}^{−1} → P_{1}

m_{1}^{−1} m_{1} → 1

m_{2}^{−1} m_{2} → 1

m_{2} m_{2}^{−1} → 1 − m_{1} m_{1}^{−1} THE FOLLOWING VARIABLES HAVE NOT BEEN SOLVED FOR: {m_{1}^{−1}, m_{2}^{−1}, m_{1}, m_{2}}

The expressions with unknown variables {m_{1}^{−1}, m_{1}} and knowns {P_{1}}

m_{1}^{−1} m_{1} → 1 is a user select

m_{1} m_{1}^{−1} → P_{1} is a user select

The expressions with unknown variables {m_{2}^{−1}, m_{2}} and knowns {}

m_{2}^{−1} m_{2} → 1 is a user select

The expressions with unknown variables {m_{2}^{−1}, m_{1}^{−1}, m_{2}, m_{1}} and knowns {}

m_{2} m_{2}^{−1} → 1 − m_{1} m_{1}^{−1} is a user select

As we saw in §2.4, this spreadsheet leads directly to the main theorem about factoring

systems. Since this does not involve further use of the NCP rocess command, this concludes the demonstration of NCP rocess. For another demonstration of Strategies using NCP rocess see Chapter 4.

\underline{3.6. NCProcess Summary Table} 38

3.6 NCProcess Summary Table

NCProcess[aListOfP olynomials, iter, “F ilename”, Options]

UserSelect → {}

Deselect → {}

RR → T rue

RRByCat → F alse

SB → False

SBByCat → F alse

RRSB → False

RRSBByCat → False

DegreeCap → −1

DegreeSumCap → −1

NCGBDebug → F alse This list of polynomials will appear in the UserSelects category in the file “F ilename”.

Polynomials in this list will not be used to do something or other.

Setting RR → T rue will cause the algorithm to use RemoveRedundent to reduce partial Gröbner bases. Very fast.

Specifies whether or not to use RemoveRedundantBy-Category. It is slower than RemoveRedundant, but it is more careful??

Specifies whether or not to use the most generic form of SmallBasis.

Specifies whether or not to use SmallBasisByCategory, which is a slower but more particular form of SmallBasis. Very very slow.

Specifies whether or not to use the hybrid reduction algorithm within the spreadsheet command. Faster than SmallBasis. NIY ^{a}

Specifies the use of SmallBasisRemoveRedundentBy-Category, which is one of the longest function names we have. Faster than SBByCat. NIY

Sets the DegreeCap for NCMakeGB within NCProcess. The DegreeCap for SmallBasis is set to one higher.

Sets the DegreeSumCap for NCMakeGB within NCProcess. The DegreeSumCap for SmallBasis is set to one higher.

Setting Slow → T rue will cause the partial GB to be called into Mathematica, output to the screen and saved to files at intermediate steps.

aNot implemented yet

Another Example: Solving the H^{∞} Control Problem

In this section we give a more extensive example of a strategy and illustrate a extremely useful tool. This is a command which “collects” knowns and products of knowns out of expressions. For example, suppose that A and B are knowns and X,Y and Z are unknowns. The collected form of

X ∗ ∗A ∗ ∗B ∗ ∗Z + Y ∗ ∗A ∗ ∗B ∗ ∗Z + A ∗ ∗X + A ∗ ∗Y

is (X + Y) ∗ ∗A ∗ ∗B ∗ ∗Z + A ∗ ∗(X + Y). This is discussed more in Chapter 3.

The demonstration in this section will repeatedly call the NCProcess command with the

option NCCONV→True (which is the default). This displays formulas in the spreadsheet in a more informative way than before. Whenever NCCONV produces a new form of a relation, it displays both the new form and the old form on the spreadsheet. We use LaTEX bullets (•) to indicate the collected version of a relation.

A basic problem in systems engineering is to make a given system dissipative by designing

a feedback law. We now give a demonstration of how one discovers the algebraic part of the solution to this problem. The enginnering motivation is in the next section and many readers may want to skip it. The section after that is a pure algebra demo which is reasonably self contained.

4.1 Engineering motivation for the problem

We start with a slight modification of an executable file SYSDefIA.m in the package SYStems.m which runs under NCAlgebra.m.

4.1.1 System definitions

This file loads in basic definitions of the system and of the energy balance relations various connections of the systems satisfy.

\underline{4.1. Engineering motivation for the problem} 40

[figure: U; W; Y; out_{1}; F; G_{1}; G_{2}; U; Y; g; f; \frac{dx}{dt} =; out1 =; Y =; \frac{dz}{dt} =; U =; F [x, W, U]; G_{1}[x, W, U]; G_{2}[x, W, U]; f[z, Y]; g[z, Y]]

(* An Input Affine (IA) one port system is *)
SetNonCommutative[f,g,a,b,c,dd,z]
    f[z_,Y_]:=a[z]+b[z]**Y
    g[z_,Y_]:=c[z]+dd[z]**Y
(* An Input Affine (IA) two port system is *)
SetNonCommutative[W,U,Y,DW,DU,DY]
SetNonCommutative[A,x,B1,B2,C1,C2,G1,G2]
SetNonCommutative[D11,D22,D12,D21]
  D11[x_]:=0
  D22[x_]:=0
  D12[x_]:=1
  D21[x_]:=1
F[x_,W_,U_]:=A[x]+B1[x]**W+B2[x]**U
G1[x_,W_,U_]:=C1[x]+D11[x]**W+D12[x]**U;
         out1=G1[x,W,U];
G2[x_,W_,U_]:=C2[x]+D21[x]**W+D22[x]**U;
         out2=G2[x,W,U];
         G2I[x_,Y_,U_]:=inv[D21[x]]**Y-inv[D21[x]]**C2[x];

4.1.2 Energy balance equations

We begin with notation for analyzing the DISSIPATIVITY of the systems obtained by connecting f, g to F, G in several different ways. The energy function on the statespace is denoted by ε. HW UY below is the preHamiltonian of the two decoupled systems where inputs are W, U and Y.

HW UY = out_{1} − W^{2} + P f(z, Y) + pF (x, W, U)

SetNonCommutative[F,G1,G2,f,g,p,P];
HWUY = tp[out1]**out1-tp[W]**W+
                       (p**F[x,W,U]+tp[F[x,W,U]]**tp[p])/2+
                                     (P**f[z,Y]+tp[f[z,Y]]**tp[P])/2;

Connecting the two systems in feedback, that is tieing off U and Y, mathematically

means

Y → G_{2}(x, W, U) U → g(z, Y).

and the preHamiltonian with this substitution becomes H

H=HWUY/. {Y -> G2(x,W,U),   U -> g(z,Y)}

By definition the closed loop system being DISSIPATIVE corresponds to the energy

balance function H above being negative. This is the same as

Ham := max_{W} H ≤ 0

We refer to Ham as the Hamiltoinian for the problem. Since H is quadratic in W we can optimize W by hand and write down a formula for Ham. The main problem becomes:

(H^{∞}CNTRL) Is there a system a, b, c, d, so that Ham ≤ 0 has a solution ε ≥ 0

Theory (see [PAJ]) tells us that (CNTRL) has a positive solution ε > 0 only if

(H^{∞}CNTRL=) There is a system a, b, c, d, so that Ham = 0 has a solution ε ≥ 0 .

Note that the function Ham contains both state and dual variables. Dual variables are

defined by the gradient of the energy function, as follows:

p = ∇_{x}ε(x, z)^{T} and P = ∇_{z}ε(x, z)^{T}

In a moment we shall write down Ham explicitly, but first we shall make assumptions

to simplify the exposition. They are not essential for the demo. The outline here should work for nonlinear as well as linear systems and at a high level of generality:

d[z] = 0

The system is linear.

The storage function ε is quadratic. Thus it corresponds to the

ε[x, z] = x^{T} E_{11} x + z^{T} E_{21} x + x^{T} E_{12} z + z^{T} E_{22} z

\underline{4.2. The Demo} 42

We now write out energy balance formulas for the plant (1.4) and compensator (1.5)

(under these assumptions) purely in terms of state space variables x and z (designated by the prefix s for state space). This can be done in SYStems using a command which specializes systems to the linear case. Ham is a quadratic form on the statespace (x, z) of the closed loop system and so it can be expressed by its components H_{xx}, H_{xz}, H_{zx}, H_{zz} with respect to the x statespace and z statespace. We run NCAlgebra to find that these are and list the equations obtained in the next section.

4.2 The Demo

The math problem we address in this demo is:

Given the relations:

H_{xx} = E_{11} A + A^{T} E_{11} + C_{1}^{T} C_{1} + E_{12}^{T} b C_{2} + C_{2}^{T} b^{T} E_{12}^{T}
+E_{11} B_{1} b^{T} E_{12}^{T} + E_{11} B_{1} B_{1}^{T} E_{11} +
E_{12} b b^{T} E_{12}^{T} + E_{12} b B_{1}^{T} E_{11}

H_{xz} = E_{21} A + \frac{a^{T} (E_{21} + E_{12}^{T})}{2} + c^{T} C_{1} + E_{22} b C_{2} + c^{T} B_{2}^{T} E_{11}^{T} +

\frac{E_{21} B_{1} b^{T} (E_{21} + E_{12}^{T})}{2} + E_{21} B_{1} B_{1}^{T} E_{11}^{T} +

\frac{E_{22} b b^{T} (E_{21} + E_{12}^{T})}{2} + E_{22} b B_{1}^{T} E_{11}^{T}

H_{zx} = A^{T} E_{21}^{T} + C_{1}^{T} c + \frac{(E_{12} + E_{21}^{T}) a}{2} + E_{11} B_{2} c + C_{2}^{T} b^{T} E_{22}^{T} +

E_{11} B_{1} b^{T} E_{22}^{T} + E_{11} B_{1} B_{1}^{T} E_{21}^{T} +

\frac{(E_{12} + E_{21}^{T}) b b^{T} E_{22}^{T}}{2} + \frac{(E_{12} + E_{21}^{T}) b B1^{T} E_{21}^{T}}{2}

H_{zz} = E_{22} a + a^{T} E_{22}^{T} + c^{T} c + E_{21} B_{2} c + c^{T} B2^{T} E_{21}^{T} +
E_{21} B_{1} b^{T} E_{22}^{T} + E_{21} B_{1} B_{1}^{T} E_{21}^{T} +
E_{22} b b^{T} E_{22}^{T} + E_{22} b B_{1}^{T} E_{21}^{T}

(HGRAIL) A, B_{1}, B_{2}, C_{1}, C_{2} are given. Solve H_{xx} = 0, H_{xx} = 0, H_{xz} = 0, H_{zx} = 0, and H_{zz} = 0 for a, b, c and for E_{11}, E_{12}, E_{11} and E_{22}. When can they be solved? Find formulas for the solution. Note we do not address the inequality constraints on ε.

4.2.1 The key relations: executable form

The first step is to assemble all of the key relations in executable form:

The properties of E_{ij}

We make the strong assumption that each E_{ij} is invertible. While this turns out to be valid, making it at this point is cheating. Ironically we recommend strongly that the user make heavy invertibility assumptions at the outset of a session. Later after the main ideas have been discovered the user can selectively relax them and thereby obtain more general results.

Creating an input file

It is a good idea to create an input file for the strategy session before starting Mathematica. There are several preliminary steps which may have to be done several times before the desired results are obtained. Setting the monomial order, setting variables noncommutative and defining the starting relations can all be done before hand. This way, if the user wants to try the same run with a slightly different ordering, he only needs to edit the input file and load it again.

In this case, the input file is called “cntrl”. Notice that we are using Tp[ ] to denote

transpose and i to denote inverse, which is inconsistent with the NCAlgebra package which uses tp[ ] and inv[ ] respectively. This is done intentionally to ensure that actual transposes and inverses are not taken within the GB algorithms. The relations can be easily converted later if it is necessary to do mathematical operations on them.

This is the file “cntrl”.

SetNonCommutative[E11,E22,E12,E21,iE11,iE22,iE12,iE21,
                  Tp[iE11],Tp[iE22],Tp[iE12],Tp[iE21],
                  Tp[E11],Tp[E22],Tp[E12],Tp[E21]];
(* These relations imply that the Eij  generate a symmetric quadratic form. *)
transE = {
Tp[E21]-E12,
Tp[E11]-E11,
Tp[E22]-E22,
Tp[E12]-E21,
Tp[iE21]-iE12,
Tp[iE11]-iE11,
Tp[iE22]-iE22,
Tp[iE12]-iE21};
(* These relations assume that everything is invertable *)
inverseE = {
E11**iE11 -1,
iE11**E11 -1,
E12**iE12 -1,
iE12**E12 -1,
E21**iE21 -1,
iE21**E21 -1,
E22**iE22 -1,
iE22**E22 -1,
Tp[E11]**Tp[iE11] -1,

\underline{4.3. Solving (H^{∞}CNTRL) using NCProcess} 44

Tp[iE11]**Tp[E11] -1,
Tp[E12]**Tp[iE12] -1,
Tp[iE12]**Tp[E12] -1,
Tp[E21]**Tp[iE21] -1,
Tp[iE21]**Tp[E21] -1,
Tp[E22]**Tp[iE22] -1,
Tp[iE22]**Tp[E22] -1};
SetNonCommutative[A,Tp[A],B1,Tp[B1],B2,Tp[B2],
                  C1,Tp[C1],C2,Tp[C2],
                  b,Tp[b],c,Tp[c],a,Tp[a]];
(* These are the Hamiltonian equations *)
Hxx=E11 ** A + Tp[A] ** Tp[E11] + Tp[C1] ** C1 +
  Tp[C2] ** Tp[b] ** (E21 + Tp[E12])/2 + (E12 + Tp[E21]) ** b ** C2/2 +
  E11 ** B1 ** Tp[b] ** (E21 + Tp[E12])/2 + E11 ** B1 ** Tp[B1] ** Tp[E11] +
  (E12 + Tp[E21]) ** b ** Tp[b] ** (E21 + Tp[E12])/4 +
  (E12 + Tp[E21]) ** b ** Tp[B1] ** Tp[E11]/2;
Hxz=E21 ** A + Tp[a] ** (E21 + Tp[E12])/2 + Tp[c] ** C1 + E22 ** b ** C2 +
  Tp[c] ** Tp[B2] ** Tp[E11] + E21 ** B1 ** Tp[b]** (E21 + Tp[E12])/2 +
  E21 ** B1 ** Tp[B1] ** Tp[E11] + E22 ** b ** Tp[b] ** (E21 + Tp[E12])/2 +
  E22 ** b ** Tp[B1] ** Tp[E11];

Hzx=Tp[A] ** Tp[E21] + Tp[C1] ** c + (E12 + Tp[E21]) ** a/2 + E11 ** B2 ** c +
  Tp[C2] ** Tp[b] ** Tp[E22] + E11 ** B1 ** Tp[b] ** Tp[E22] +
  E11 ** B1 ** Tp[B1] ** Tp[E21] +
  (E12 + Tp[E21]) ** b ** Tp[b] ** Tp[E22]/2 +
  (E12 + Tp[E21]) ** b ** Tp[B1] ** Tp[E21]/2;

Hzz=E22 ** a + Tp[a] ** Tp[E22] + Tp[c] ** c + E21 ** B2 ** c +
  Tp[c] ** Tp[B2] ** Tp[E21] + E21 ** B1 ** Tp[b] ** Tp[E22] +
  E21 ** B1 ** Tp[B1] ** Tp[E21] + E22 ** b ** Tp[b] ** Tp[E22] +
  E22 ** b ** Tp[B1] ** Tp[E21];
Hameq = {Hxx,Hxz,Hzx,Hzz};
(* Set the knowns and the order of the unknowns *)
SetKnowns[A,Tp[A],B1,Tp[B1],B2,Tp[B2],C1,Tp[C1],C2,Tp[C2]];
SetUnknowns[{E12,Tp[E12],E21,Tp[E21],E22,Tp[E22],E11,Tp[E11]},
            {iE12,Tp[iE12],iE21,Tp[iE21],iE22,Tp[iE22],iE11,Tp[iE11]},
            {b,Tp[b]},{c,Tp[c]},{a,Tp[a]}];
result1 = NCProcess[startingrels,2,"cntrlans1"]

Now when we load this file, we will be ready to begin the strategy session.

4.3 Solving (H^{∞}CNTRL) using NCProcess

4.3.1 Step 1

In[1]:= Get["NCGB.m"];
In[2]:= Get["cntrl"];
In[3]:= result1

We can ignore the Mathematica output Out[3] of the NCP rocess command for now, but remember that it is labeled Out[3] so we can get a hold of it later. What is important is the spreadsheet file that NCP rocess produces which is in the file “cntrlans1”. There is no need to record all of it, since the only work which we must do is on the undigested relations.

This is the undigested portion of the file “cntrlans1.dvi’

SOME RELATIONS WHICH APPEAR BELOW MAY BE UNDIGESTED

THE FOLLOWING VARIABLES HAVE NOT BEEN SOLVED FOR: {b, c, E_{11}, E_{12}, E_{22}, E_{11}^{−1}, E_{12}^{−1}, E_{22}^{−1}, b^{T} , c^{T} , E_{12}^{T}, E_{12}^{−1T} }

The expressions with unknown variables {E_{11}^{−1}, E_{11}} and knowns {}

E_{11} E_{11}^{−1} → 1

E_{11}^{−1} E_{11} → 1

The expressions with unknown variables {E_{12}^{−1}, E_{12}} and knowns {}

E_{12} E_{12}^{−1} → 1

E_{12}^{−1} E_{12} → 1

The expressions with unknown variables {E_{21}^{−1}, E_{21}} and knowns {}

E_{21} E_{21}^{−1} → 1

E_{21}^{−1} E_{21} → 1

The expressions with unknown variables {E_{22}^{−1}, E_{22}} and knowns {}

E_{22} E_{22}^{−1} → 1

E_{22}^{−1} E_{22} → 1

The expressions with unknown variables {b^{T} , b, E_{21}^{−1}, E_{12}^{−1}, E_{11}} and knowns {A, B_{1}, C_{1}, C_{2}, A^{T} , B_{1}^{T} , C_{2}^{T} , C_{2}^{T} }

• b b^{T} + b C_{2} E_{21}^{−1} + E_{12}^{−1} C_{2}^{T} b^{T} + E_{12}^{−1} E_{11} A E_{21}^{−1} + E_{12}^{−1}

• E_{11} B_{1} b^{T} + E_{12}^{−1} A^{T} E_{11} E_{21}^{−1} + E_{12}^{−1} C_{2}^{T} C_{1} E_{21}^{−1}

• +(b + E_{12}^{−1} E_{11} B_{1}) B_{1}^{T} E_{11} E_{21}^{−1}

b b^{T} → −b C_{2} E_{21}^{−1} − E_{12}^{−1} C_{2}^{T} b^{T} − b B_{1}^{T} E_{11} E_{21}^{−1} − E_{12}^{−1} E_{11} A E_{21}^{−1} − E_{12}^{−1} E_{11} B_{1} b^{T} − E_{12}^{−1} A^{T} E_{11} E_{21}^{−1} − E_{12}^{−1} C_{2}^{T} C_{1} E_{21}^{−1} − E_{12}^{−1} E_{11} B_{1} B_{1}^{T} E_{11} E_{21}^{−1}

The expressions with unknown variables {c^{T} , c, E_{21}^{−1}, E_{12}^{−1}, E_{11}, E_{22}, E_{21}, E_{12}} and knowns {A, B_{1}, B_{2}, C_{1}, A^{T} , B_{1}^{T} , B_{2}^{T} , C_{2}^{T} }

• c^{T} c + (E_{21} − E_{22} E_{12}^{−1} E_{11}) B_{2} c + c^{T} B_{2}^{T} (E_{12} − E_{11}

• E_{21}^{−1} E_{22}) − E_{22} E_{12}^{−1} A^{T} (E_{12} − E_{11} E_{21}^{−1} E_{22}) − E_{22} E_{12}^{−1} C_{2}^{T}

• (c − C_{1} E_{21}^{−1} E_{22}) − (E_{21} − E_{22} E_{12}^{−1} E_{11}) A E_{21}^{−1} E_{22} + (E_{21} − E_{22}

• E_{12}^{−1} E_{11}) B_{1} B_{1}^{T} (E_{12} − E_{11} E_{21}^{−1} E_{22}) − c^{T} C_{1} E_{21}^{−1}

• E_{22}

c^{T} c → −E_{21} B_{2} c − c^{T} B_{2}^{T} E_{12} + E_{21} A E_{21}^{−1} E_{22} − E_{21} B_{1} B_{1}^{T} E_{12} + E_{22} E_{12}^{−1} A^{T} E_{12} + E_{22} E_{12}^{−1} C_{2}^{T} c + c^{T} C_{1} E_{21}^{−1} E_{22} + E_{22} E_{12}^{−1} E_{11} B_{2} c + c^{T} B_{2}^{T} E_{11} E_{21}^{−1} E_{22} + E_{21} B_{1} B_{1}^{T} E_{11} E_{21}^{−1} E_{22} − E_{22} E_{12}^{−1} E_{11} A E_{21}^{−1} E_{22} + E_{22} E_{12}^{−1} E_{11} B_{1} B_{1}^{T} E_{12} − E_{22} E_{12}^{−1} A^{T} E_{11} E_{21}^{−1} E_{22} − E_{22} E_{12}^{−1} C_{2}^{T} C_{1} E_{21}^{−1} E_{22} − E_{22} E_{12}^{−1} E_{11} B_{1} B_{1}^{T} E_{11} E_{21}^{−1} E_{22}

4.3.2 Step 2: The user attacks

As we can easily see from the spreadsheet file, there are only two nontrivial relations left undigested by the NCP rocess command. The user can ignore the rest of the spreadsheet for now. Further iterations of NCP rocess would probably not help. At this point, we need to be more clever.

We begin by assigning variables to the relations that we are interested in. We can see

from Out[3] that the b rule is the first element of the third list in the result1, and the c rule is the last element of that list. These relations are in the form of rules which need to be converted to polynomials before we can continue. This is done with the command RuleT oP oly. The next step is to convert the Tp[ ] in these rules to tp[ ], which will be recognized as transpose by NCAlgebra.

In[4]:= bpoly = RuleToPoly[result1[[3,1]]]
Out[4]:= b ** Tp[b] + b ** C2 ** iE21 + iE12 ** Tp[C2] ** Tp[b] +
>    b ** Tp[B1] ** E11 ** iE21 + iE12 ** E11 ** A ** iE21 +
>    iE12 ** E11 ** B1 ** Tp[b] + iE12 ** Tp[A] ** E11 ** iE21 +
>    iE12 ** Tp[C1] ** C1 ** iE21 + iE12 ** E11 ** B1 ** Tp[B1] ** E11 ** iE21
In[5]:= cpoly = RuleToPoly[result1[[3,-1]]]
Out[5]:= Tp[c] ** c + E21 ** B2 ** c + Tp[c] ** Tp[B2] ** E12 -
>    E21 ** A ** iE21 ** E22 + E21 ** B1 ** Tp[B1] ** E12 -
>    E22 ** iE12 ** Tp[A] ** E12 - E22 ** iE12 ** Tp[C1] ** c -
>    Tp[c] ** C1 ** iE21 ** E22 - E22 ** iE12 ** E11 ** B2 ** c -
>    Tp[c] ** Tp[B2] ** E11 ** iE21 ** E22 -
>    E21 ** B1 ** Tp[B1] ** E11 ** iE21 ** E22 +
>    E22 ** iE12 ** E11 ** A ** iE21 ** E22 -
>    E22 ** iE12 ** E11 ** B1 ** Tp[B1] ** E12 +
>    E22 ** iE12 ** Tp[A] ** E11 ** iE21 ** E22 +
>    E22 ** iE12 ** Tp[C1] ** C1 ** iE21 ** E22 +
>    E22 ** iE12 ** E11 ** B1 ** Tp[B1] ** E11 ** iE21 ** E22
In[6]:= bpoly = bpoly /. Tp->tp;
In[7]:= cpoly = cpoly /. Tp->tp;

Observe that the polynomials Out[4] is quadratic in b. We could complete the square and get to put the polynomial in theform

bterm^{2} + nob.

There are many unknowns in the problem so probably excess freedom. Let us investigate what happens when we take bterm = 0. We also have cterm = 0.

NCAlgebra is very good with quadratics so this is easy to execute, but since this is not

a general NCAlgebra tutorial we shall not go into that but just write down the answer.

Out[8]:=      -iE12 ** tp[C2]   tp[iE21] ** tp[C2]
          b -> --------------- - ------------------ -
                      2                  2
    iE12 ** E11 ** B1   tp[iE21] ** tp[E11] ** B1
>   ----------------- - -------------------------

           2                        2
Out[9]:=      -tp[B2] ** E12   tp[B2] ** tp[E21]   C1 ** iE21 ** E22
         c -> -------------- - ----------------- + ----------------- +
                    2                  2                   2
      C1 ** tp[iE12] ** tp[E22]   tp[B2] ** E11 ** iE21 ** E22
>     ------------------------- + ---------------------------- +
                  2                            2
      tp[B2] ** tp[E11] ** tp[iE12] ** tp[E22]
>     ----------------------------------------
                         2

Next we do some petty bookeeping to get transposes of the rules.

In[10]:= bpoly = RuleToPoly[brule];
In[11]:= cpoly = RuleToPoly[crule];
In[12]:= newpolys = {bpoly,cpoly,tp[bpoly],tp[cpoly]};
In[13]:= newrules = PolyToRule[newpolys];
In[14]:= newrules = newrules /. tp->Tp;
In[15]:= newrules = newrules /. PolyToRule[transE]
Out[15]:= {b -> -iE12 ** Tp[C2] + -iE12 ** E11 ** B1,
   Tp[b] -> -C2 ** iE21 + -Tp[B1] ** E11 ** iE21,
   c -> -Tp[B2] ** E12 + C1 ** iE21 ** E22 + Tp[B2] ** E11 ** iE21 ** E22,
   Tp[c] -> -E21 ** B2 + E22 ** iE12 ** Tp[C1] + E22 ** iE12 ** E11 ** B2}

Once we have solved for b and c, we can then take the transpose of each of these rules to

solve for tp[b] and tp[c]. In our strategy session, these are simply two additional unknowns which we can now eliminate. Then we take these four rules and replace tp[ ] with Tp[ ]. The final step is to simplify these equations by making the substitutions for the transposes of E which we have been using. Now we have four additional relations which can be added to the input for the next call to NCP rocess.

4.3.3 Step 3

The starting relations for step 3 will be the output from the first NCP rocess call which was result1, as well as the four new equations that we have just derived. Just as we did in the first step, we will create a file to be read in to the Mma session.

This is the file “cntrl2”.

digested=RuleToPol[result1[[2]]];
undigested=RuleToPol[result1[[3]]];
relations=Join[digested,newpolys,undigested];
result2=NCProcess[relations,2,"cntrlans2",SB->True,
                  DegreeCap->6,DegreeSumCap->9];

Now if we do not like the results, we can change the DegreeCap options or the iteration

count and simply read the file again, without typing the entire sequence of commands again. Then in the Mma session we simply type

In[16]:= Get["cntrl2"];

Once again we go directly to the file which NCP rocess created. There is no need to

record all of it, since at this stage we shall be concerned only with the undigested relations. This is the undigested portion of the file “cntrlans2.dvi”.

SOME RELATIONS WHICH APPEAR BELOW MAY BE UNDIGESTED

THE FOLLOWING VARIABLES HAVE NOT BEEN SOLVED FOR: {E_{11}, E_{12}, E_{22}, E_{11}^{−1}, E_{12}^{−1}, E_{22}^{−1}, E_{12}^{T}, E_{12}^{−1T} }

The expressions with unknown variables {E_{11}} and knowns {A, B_{1}, C_{1}, C_{2}, A^{T} , B_{1}^{T} , C_{2}^{T} , C_{2}^{T} }

E_{11} B_{1} C_{2} → E_{11} A + A^{T} E_{11} + C_{2}^{T} C_{1} − C_{2}^{T} C_{2} + −C_{2}^{T} B_{1}^{T} E_{11}

The expressions with unknown variables {E_{11}^{−1}, E_{11}} and knowns {}

E_{11} E_{11}^{−1} → 1

E_{11}^{−1} E_{11} → 1

The expressions with unknown variables {E_{12}^{−1}, E_{12}} and knowns {}

E_{12} E_{12}^{−1} → 1

E_{12}^{−1} E_{12} → 1

The expressions with unknown variables {E_{21}^{−1}, E_{21}} and knowns {} E_{21} E_{21}^{−1} → 1

E_{21}^{−1} E_{21} → 1

The expressions with unknown variables {E_{22}^{−1}, E_{22}} and knowns {}

E_{22} E_{22}^{−1} → 1

E_{22}^{−1} E_{22} → 1

The expressions with unknown variables {E_{21}^{−1}, E_{12}^{−1}, E_{11}, E_{22}, E_{21}, E_{12}} and knowns {A, B_{1}, B_{2}, C_{1}, A^{T} , B_{1}^{T} , B_{2}^{T} , C_{2}^{T} }

• E_{22} E_{12}^{−1} A^{T} (E_{12} − E_{11} E_{21}^{−1} E_{22}) + (E_{21} − E_{22} E_{12}^{−1} E_{11}) A E_{21}^{−1} E_{22} −

• (E_{21} − E_{22} E_{12}^{−1} E_{11}) B_{1} B_{1}^{T} (E_{12} − E_{11} E_{21}^{−1} E_{22}) +

• (E_{21} − E_{22} E_{12}^{−1} E_{11}) B_{2} B_{2}^{T} (E_{12} − E_{11} E_{21}^{−1} E_{22}) −

• E_{22} E_{12}^{−1} C_{2}^{T} B_{2}^{T} (E_{12} − E_{11} E_{21}^{−1} E_{22}) − (E_{21} − E_{22} E_{12}^{−1} E_{11}) B_{2} C_{1} E_{21}^{−1} E_{22}

E_{22} E_{12}^{−1} E_{11} B_{2} B_{2}^{T} E_{11} E_{21}^{−1} E_{22} → −E_{21} A E_{21}^{−1} E_{22} + E_{21} B_{1} B_{1}^{T} E_{12} − E_{21} B_{2} B_{2}^{T} E_{12} − E_{22} E_{12}^{−1} A^{T} E_{12} + E_{21} B_{2} C_{1} E_{21}^{−1} E_{22} + E_{22} E_{12}^{−1} C_{2}^{T} B_{2}^{T} E_{12} − E_{21} B_{1} B_{1}^{T} E_{11} E_{21}^{−1} E_{22} + E_{21} B_{2} B_{2}^{T} E_{11} E_{21}^{−1} E_{22} + E_{22} E_{12}^{−1} E_{11} A E_{21}^{−1} E_{22} − E_{22} E_{12}^{−1} E_{11} B_{1} B_{1}^{T} E_{12} + E_{22} E_{12}^{−1} E_{11} B_{2} B_{2}^{T} E_{12} + E_{22} E_{12}^{−1} A^{T} E_{11} E_{21}^{−1} E_{22} − E_{22} E_{12}^{−1} E_{11} B_{2} C_{1} E_{21}^{−1} E_{22} − E_{22} E_{12}^{−1} C_{2}^{T} B_{2}^{T} E_{11} E_{21}^{−1} E_{22} + E_{22} E_{12}^{−1} E_{11} B_{1} B_{1}^{T} E_{11} E_{21}^{−1} E_{22}

Once again, we have two relations worth looking at. The first is a Ricatti is E_{11}. We

have other methods for solving Ricatti equations, so we can consider E_{11} to be known. It is not obvious at this point that the last equation in the spreadsheet is what we are looking for, but since this is all we have to work with, we will see what we can make of it.

We notice that the same products of unknowns appear over and over. It is likely that

we can factor or group this equation in such a way that we can understand it a little better.

4.3.4 Step 4

We start by grabbing the relation which we want to explore. In this case, it is the last element in the third list of result2.

============= BREAK =========== REDO======== DELETE?? Then we use the NCCollectOnV ariables command, which will collect on maximal prod-

ucts of knowns. Since it collects on monomials all elements of which are known it typically presents important combinations of knowns in its factors.

In[17]:= equ = RuleToPoly[result2[[3,-1]]]
Out[17]= E21 ** A ** iE21 ** E22 - E21 ** B1 ** Tp[B1] ** E12 +
>    E21 ** B2 ** Tp[B2] ** E12 + E22 ** iE12 ** Tp[A] ** E12 -
>    E21 ** B2 ** C1 ** iE21 ** E22 -
>    E22 ** iE12 ** Tp[C1] ** Tp[B2] ** E12 +
>    E21 ** B1 ** Tp[B1] ** E11 ** iE21 ** E22 -
>    E21 ** B2 ** Tp[B2] ** E11 ** iE21 ** E22 -
>    E22 ** iE12 ** E11 ** A ** iE21 ** E22 +
>    E22 ** iE12 ** E11 ** B1 ** Tp[B1] ** E12 -
>    E22 ** iE12 ** E11 ** B2 ** Tp[B2] ** E12 -
>    E22 ** iE12 ** Tp[A] ** E11 ** iE21 ** E22 +
>    E22 ** iE12 ** E11 ** B2 ** C1 ** iE21 ** E22 +
>    E22 ** iE12 ** Tp[C1] ** Tp[B2] ** E11 ** iE21 ** E22 -
>    E22 ** iE12 ** E11 ** B1 ** Tp[B1] ** E11 ** iE21 ** E22 +
>    E22 ** iE12 ** E11 ** B2 ** Tp[B2] ** E11 ** iE21 ** E22
??DELETEIn[18]:= equ2 = NCCollectOnVariables[equ]
-----------========= BREAK=========
CHECK THIS
In[18] := result2[[3,-1]]
Out[18]:= E22 ** iE12 ** Tp[A] ** (E12 - E11 ** iE21 ** E22) +
>    (E21 - E22 ** iE12 ** E11) ** A ** iE21 ** E22 -
>    (E21 - E22 ** iE12 ** E11) ** B1 ** Tp[B1] **
>    (E12 - E11 ** iE21 ** E22) +
>    (E21 - E22 ** iE12 ** E11) ** B2 ** Tp[B2] **
>    (E12 - E11 ** iE21 ** E22) -
>    E22 ** iE12 ** Tp[C1] ** Tp[B2] ** (E12 - E11 ** iE21 ** E22) -
>    (E21 - E22 ** iE12 ** E11) ** B2 ** C1 ** iE21 ** E22

Now we can see that this equation is symmetric. It would not take an experienced mathematician long to realize that by multiplying this equation on the left by E_{12} iE_{22} and on the right by iE_{22} E_{21}, we will have an equation in one unknown.

In[19]:= equ3 = NCExpand[E12**iE22**equ2**iE22**E21];
In[20]:= equ4 = Transform[equ3,
       {iE22**E22->1,E12**iE12->1,E22**iE22->1,iE21**E21->1}];
In[21]:= equ5 = NCCollectOnVariables[equ4]
Out[21]:= -(E11 - E12 ** iE22 ** E21) ** A -
>   Tp[A] ** (E11 - E12 ** iE22 ** E21) +
>   (E11 - E12 ** iE22 ** E21) ** B2 ** C1 +
>   Tp[C1] ** Tp[B2] ** (E11 - E12 ** iE22 ** E21) -

\underline{4.4. End game} 52

>   (E11 - E12 ** iE22 ** E21) ** B1 ** Tp[B1] ** (E11 - E12 ** iE22 ** E21) +
>   (E11 - E12 ** iE22 ** E21) ** B2 ** Tp[B2] ** (E11 - E12 ** iE22 ** E21)

Now we can replace (E_{11} − E_{12} E_{22}^{−1} E_{21}) with a new variable X.

In[22]:= Transform[equ5,(E11 - E12 ** iE22 ** E21)->X]
Out[22]:= -X ** A -  Tp[A] ** X +  X ** B2 ** C1 + Tp[C1] ** Tp[B2] ** X -
>   X ** B1 ** Tp[B1] ** X + X ** B2 ** Tp[B2] ** X

Observe that this is an equation in the one unknown X. Of course, the only other

undigested equation was in the one unknown E11 and the previous spreadsheet featured an equation in the single unknown b (and its transpose) and an equation in the single unknown c (and its transpose). Thus we have solved (HGRAIL) with a (symmetrized??) liberalized 1strategy.

4.4 End game

Now let us compare what we have found to the well known solution to the (H^{∞}CNTRL=). In that theory there are two Ricatti equations due to Dolye, Glover, Kargonekar and Francis. These are the DGKF X and Y equations. One can read off that the E_{11} equation which we found is the DGKF equation for Y^{−1}, while the Ricatti equation which we just analyzed in Out[20] is the DGKF X equation.

Indeed what we have proved is that if (H^{∞}CNTRL=) has a solution, ε (not necessarily

positive), then the DGKF X and Y^{−1} equations must have a solution.

Now we mention the converse. The first step is to prove that the relations that we

derived in the final spreadsheet imply the starting relations. This is done by taking take result2[[2]] result2[[3]] Use NCSR6 to reduce the starting relations by these.

fill in

Finding a small (non-Gröbner) basis

In this chapter we give demos of software designed to assist a researcher in discovering theorems and formulas in operator theory, systems engineering and matrix theory.

5.1 Motivation

The Gröbner Basis algorithm can generate a large (often infinite) number of relations from a very small number of them. If one is working on a problem where the objective is to present an intuitively understandable basis to a user, as was the case in the previous section with spread sheets, then one wants a small or even minimal basis for the ideal. The commands in this section play a heavy role as ingredients of the spreadsheet command in the previous section. In a typical GB only a few of the relations are useful since there is tremendous redundancy. This is illustrated by the following example.

Example 5.1 A GB generated by the set {P T P − T P, P^{2} − P } is the set {P T^{n}P − T^{n}P : n ≥ 1} ∪ {P^{2} − P } regardless of the term order used. No smaller GB exists.

Here just two relations generate infinitely many. One way to view this example is that

the computer discovers that if a subspace (represented by ran(P)) is invariant for a linear transformation T, then it is invariant for T^{n} for every n ≥ 1.

The Mora algorithm tries to generate these relations and at any time has generated

a finite subset of them. When we are trying to discover a theorem and {P T P − T P, P^{2} − P } emerges, often these relations involving higher powers are irrelevant and clutter the output which merely serves to confuse the user.^{1}

This introduces the next topic which is shrinking a set of relations to eliminate redun-

dancy. Our desire is to take the generated basis and to remove mathematical redundency from \underline{5.2. First Example} 54

1We will discuss what we call a spreadsheet later in this document. This will serve to organize the output of Mora’s algorithm to some extent. Our next topic shrinking goes further in making the possibly large outputs from Mora’s algorithm more understandable.

the generating set without destroying the information which was gained while running the GB algorithm.

This shrinking is done using the commands RemoveRedundent and SmallBasis.

5.2 First Example

For example, after loading the files NCGB.m, SmallBasis3.m (§9.3.1) and RemoveRedundent.m (§9.1.2), we can execute the commands to compute a subset of a Gröbner Basis for the set of relations {p ∗ ∗p − p, p ∗ ∗a ∗ ∗p − a ∗ ∗p}:

In[2]:= SetKnowns[a,p]
In[3]:= {p**p-p,p**a**p - a**p}
Out[3]= {-p + p ** p, -a ** p + p ** a ** p}
In[4]:= NCMakeGB[%,4]
Out[4]= {-p + p ** p, -a ** p + p ** a ** p, -a ** a ** p + p ** a ** a ** p,
>    -a ** a ** a ** p + p ** a ** a ** a ** p,
>    -a ** a ** a ** a ** p + p ** a ** a ** a ** a ** p,
>    -a ** a ** a ** a ** a ** p + p ** a ** a ** a ** a ** a ** p,
>    -a ** a ** a ** a ** a ** a ** p + p ** a ** a ** a ** a ** a ** a ** p,
>    -a ** a ** a ** a ** a ** a ** a ** p +
>     p ** a ** a ** a ** a ** a ** a ** a ** p,
>    -a ** a ** a ** a ** a ** a ** a ** a ** p +
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** p,
>    -a ** a ** a ** a ** a ** a ** a ** a ** a ** p +
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p,
>    -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p +
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p,
>    -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p +
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p,
>    -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p +
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p,
>    -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p +
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p\
>     , -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a **
>       a ** p + p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a **
>      a ** a ** a ** p, -a ** a ** a ** a ** a ** a ** a ** a ** a ** a **
>       a ** a ** a ** a ** a ** p +
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a **
>      a ** a ** p, -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a **
>       a ** a ** a ** a ** a ** p +
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a **
>      a ** a ** a ** p}

The command SmallBasis takes this (or any) set of relations and shrinks it down to

a smaller set of relations which generate the same ideal. One must have a monomial order set because SmallBasis (§9.3.1) calls NCMakeGB. SmallBasis returns a subset of the original set of relations. In the example below the SmallBasis command shows that the ideal generated by the set Out[4] equals the ideal generated by {−p + p ∗ ∗p, −a ∗ ∗p + p ∗ ∗a ∗ ∗p}. ^{2} \underline{5.2. First Example} 55

2It takes 113 seconds. The present implementation of the code involves alot of interaction with Mathematica.

We expect future versions of the code to be faster.

In[5]:= SmallBasis[%4,{},4];
Out[5]= {-p + p ** p, -a ** p + p ** a ** p}

Unfortunately in larger examples, SmallBasis is very slow which prompts the develop-

ment of a more specialized command RemoveRedundant. This can be run only after NCMakeGB has been run because it uses the history of how the GB was produced. This history is equivalent to a tree which tells what relation came from what other relations RemoveRedundant uses only tree search methods so it is faster than SmallBasis.

As one sees below the information required for RemoveRedundant is a subset of the last

GB produced in your session.

Before calling RemoveRedundent, one must acquire the history of the last GB produced

in your section. This takes 2 commands which we now illustrate and which we explain afterward.

In[5]:= WhatAreNumbers[]
Out[5]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17}
In[6]:= WhatIsHistory[%]
Out[6]= {{1, p ** p -> p, {0, 0}, {}},
>    {2, p ** a ** p -> a ** p, {0, 0}, {}},
>    {3, p ** a ** a ** p -> a ** a ** p, {2, 2}, {2}},
>    {4, p ** a ** a ** a ** p -> a ** a ** a ** p, {3, 2}, {2}},
>    {5, p ** a ** a ** a ** a ** p -> a ** a ** a ** a ** p, {3, 3}, {3}},
>    {6, p ** a ** a ** a ** a ** a ** p -> a ** a ** a ** a ** a ** p,
>     {5, 2}, {2}}, {7, p ** a ** a ** a ** a ** a ** a ** p ->
>      a ** a ** a ** a ** a ** a ** p, {5, 3}, {3}},
>    {8, p ** a ** a ** a ** a ** a ** a ** a ** p ->
>      a ** a ** a ** a ** a ** a ** a ** p, {5, 4}, {4}},
>    {9, p ** a ** a ** a ** a ** a ** a ** a ** a ** p ->
>      a ** a ** a ** a ** a ** a ** a ** a ** p, {5, 5}, {5}},
>    {10, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p ->
>      a ** a ** a ** a ** a ** a ** a ** a ** a ** p, {9, 2}, {2}},
>    {11, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p ->
>      a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, {9, 3}, {3}},
>    {12, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p ->
>      a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, {9, 4}, {4}}\
>     , {13, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a **
>       p -> a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p,
>     {9, 5}, {5}}, {14, p ** a ** a ** a ** a ** a ** a ** a ** a ** a **
>       a ** a ** a ** a ** p ->
>      a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p,
>     {9, 6}, {6}}, {15, p ** a ** a ** a ** a ** a ** a ** a ** a ** a **
>       a ** a ** a ** a ** a ** p ->
>      a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p
>      , {9, 7}, {7}}, {16, p ** a ** a ** a ** a ** a ** a ** a ** a ** a **
>       a ** a ** a ** a ** a ** a ** p ->
>      a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a **
>       a ** p, {9, 8}, {8}}, {17,
>     p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a **
>       a ** a ** a ** p ->
>      a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a **
>       a ** a ** p, {9, 9}, {9}}}

\underline{5.3. Second Example} 56

The call to RemoveRedundent is:

In[7]:= RemoveRedundent[Out[4],Out[6]];
Out[7]= {-p + p ** p, -a ** p + p ** a ** p}

The first command recalls the number associated to all of the relations which occurred

during the previous run of Mora’s algorithm. The second command gives the ancestory and other information related to relations 1, 2, . . .. One could have used any list of numbers (between 1 and 17) as the argument to the W hatIsHistory command and obtained only the history of those relations.

5.3 Second Example

As a second example, after loading the files NCGB.m, SmallBasis3.m and RemoveRedundent.m, we can execute the following commands to compute a Gröbner Basis for the set of relations {x^{2} − a, x^{3} − b}:

In[3]:= SetKnowns[a,b,x]
In[4]:= NCMakeGB[{x**x-a,x**x**x-b},10]
Out[4]= {-a + x ** x, -b + a ** x, -b + x ** a, -a ** a + b ** x,
>    -a ** b + b ** a, -a ** a + x ** b, -b ** b + a ** a ** a}

Now, one might want to find a smaller generating set for the ideal specified above. The following command does that and took 9 seconds using the C++ version of the code.

In[5]:= SmallBasis[%4,{},3]
Out[5]= {a ** x -> b, x ** x -> a}

Alternatively, one can use the command RemoveRedundent to generate the same result in 2 seconds. There are two steps which need to be performed before calling RemoveRedundent.

In[6]:= WhatAreNumbers[]
Out[6]= {1, 2, 3, 4, 5, 6, 7}
In[7]:= WhatIsHistory[%]
Out[7]= {{1, a ** x -> b, {0, 0}, {}}, {2, x ** x -> a, {0, 0}, {}},
>    {3, b ** x -> a ** a, {1, 2}, {}}, {4, x ** a -> b, {2, 2}, {1}},
>    {5, x ** b -> a ** a, {4, 1}, {3}}, {6, b ** a -> a ** b, {3, 2}, {1}},
>    {7, a ** a ** a -> b ** b, {3, 4}, {}}}

The call to RemoveRedundent is:

In[8]:= RemoveRedundent[%4,Out[12]]
Out[8]= {a ** x -> b, x ** x -> a}

\underline{5.4. Smaller Bases and the Spreadsheet command} 57

5.4 Smaller Bases and the Spreadsheet command

MXS: Stopped proofreading here

Here is a session which does roughly what the spreadsheet command does. For more detail see Chapter 3

?? MARK a high level listing of Spreadsheet[] No options –no digested

tracking. Here is a shot at it??

In[11]:=NCMakeGB[FAC,2];
In[11]:=SmallBasisByCategory[RemoveRedundant[%] ];

The next command tries to see if any of the undigested relations can be made simpler using the digested relationsBILL: We have to rethink this.... I don’t think anything happens here unless you take a GB of the digested relations. ?? seems OK to bill

In[12]:=NCSimplifyAll[%11??,  DigestedRelations[%11??] ];

Finally we output the result to the file “SecondOutputForDemo”??.

In[13]:=RegularOutput[%12, "SecondOutputForDemo"];

Now we return to the strategy demos of Chapter 3.

Inserting the command RemoveRedundant inside of small basis may change the answer,

but it yields the same answer as SmallBasis would have given with one particular order on the set of relations given as input. All this assumes that the number of iterations is large. Inserting RemoveRedundant saves much computer time.

How to Run These Packages

In order to run the C++ version of the code, one must first compile it. Before one does that one must get a copy of the Gnu C++ compiler with version number at least 2.6.3.

6.1 Installation

6.1.1 GNU C++ Version ≥ 2.6.3

The freely-distributable GNU C++ compiler is available by anonymous ftp from prep.ai.mit.edu. The GNU C++ compiler is (1) freely-distributed, (2) continually upgradable by the GNU orgainization. GNU is responsible for producing many high quality software programs for free including the popular GNU Emacs. Every system administrator anywhere in the world will know of their existence. The easiest way for most people to do to install the compiler is to see their system administrator. You can see if you have the GNU compiler version 2.6.3 or better by typing ‘g++ -v’.

6.1.2 Obtaining NCGB

To obtain our C++ code and related Mathematica code for computing noncommutative Gröbner Bases, get the code from anonymous ftp from osiris.ucsd.edu in the directory pub/mstankus/C++/src. This location will change??? most likely to a subdirectory of pub/mstankus/C++/src. At the moment the document is not in this directory. We can send it seperately. Please e-mail ncalg@osiris.ucsd.edu.

To obtain the NCAlgebra code, please consult the NCAlgebra manual. One can get the

code from anonymous ftp from osiris.ucsd.edu in the directory pub/ncalg/Version1.1. or earlier versions from Mathsource –mathsource@wri.com When you get it, printout NCDOCUMENT.dvi on your printer (on UNIX, this is done by typing ‘lpr -d NCDOCUMENT.dvi’). If you can not print out the manual, contact us and we will try to provide it in a different form.

\underline{6.1. Installation} 59

6.1.3 Compiling the C++ part of NCGB

First type ”g++ -V”. You should get a response similar to the following:

 gcc -v
Reading specs from /software/common/gnu/lib/gcc-lib/sparc-sun-sunos4.1.2/2.6.3/specs
gcc version 2.6.3

The crucial thing is the version number. It must be 2.6.3 or higher^{1}. If you do not have

version 2.6.3 or better, talk to your system administrator.

Once you have the correct version of the code, type “make p9c” and wait for a while (at

least 20 minutes). If there are any compiler errors — if so, email them to mstankus@oba.ucsd.edu.^{2}

If the program compiled succesfully, there will be a file called p9c in your directory. You

can copy this file and other files with the suffix ‘.m’ to another directory and do a “chmod u+x p9c” if you wish.

6.1.4 How to set up if someone else compiled the code — UNIX (or It is easy to bum off of a friend who is running on the same system)

Suppose that your friend on the same computer system has compiled the C++ program and has all of the mathematica files in the directory

/home/joeShmo/NCGBCode/

Also, suppose NCAlgebra is installed in the directory‘

/usr/NCAlgebra/

Do the following:

(1) Have your friend type:

(a) cd

(b) chmod go+rx ./

(c) chmod -R go+rx NCGBCode

(2) Make a directory called WORK

(3) Type ’cd WORK’

(4) Create a file called init.m which contains the one line of text \underline{6.2. Running the code} 60

1We know that 2.6.0 will not work. We have not tried 2.6.1 or 2.6.2

2As of the time of this writing, there are two warnings. They may or may not be fixed at the time you are reading this.

     $Path = Join[{"/home/joeShmo/NCGBCode"},$Path,{"/usr/NCAlgebra"}];

This code will automatically be loaded in whenever you start Mathematica from this directory.

Now, just start Mathematica and type Get[”NCGB.m”];.

6.2 Running the code

Most of the document discusses how to run the code. The following subsection just shows how to load the code so that one may see that the installation of the code was correct. If the loading works, one may proceed as in Section 6.3 to see if the code works correctly for a variety of test cases.

6.2.1 Loading NCGB

The file NCGB.m is used to load all necessary files into Mathematica. The command is:

       Get["NCGB.m"]

There are two configurations of this file; it can load either NCAlgebra.m or shortNCAl-

gebra.m, depending on the user’s needs. If shortNCAlgebra.m is used, the complete package can still be loaded without restarting; the command used is:

       Get["laterNCAlgebra.m"]

Both configurations load the necessary files newC++MoraAlg.m, newReduction.m, and

toc2.m.

6.3 Testing this package

The method for testing your instalation if you suspect there are problems is the same as one finds in NCAlgebra.m. Immediately after loading in the package load in

In[2]:= <<NCTESTGB.m

this loads and executes 20 different examples. The end of the output should provide a

list with a number of statements of the form GBtest[1] = T rue, GBtest[2] = T rue, …. If any of them are F alse, send mail to ncalg@osiris.ucsd.edu. One can review these values by typing ‘??GBtest’.

6.4 Testing this package – In house

The purpose of this section is to have a record of how the code is tested in our development group.

\underline{6.4. Testing this package – In house} 61

6.4.1 TestIt[testnumber,functionname,iterations]

Aliases: None Description: T estIt tests a command like RemoveRedundent, SmallBasis or NCMakeGB. It

compares the result to the stored result of a previously verified run. If there is no difference, then it returns True. Otherwise it prints the difference and returns False. In order to see what results are stored, use the W hatAreT ests command.

Arguments: testnumber is an integer. functionname is a function name. iteretions is an

integer. Comments \ Limitations: Not available before NCAlgebra 1.2

6.4.2 WhatAreTests[argument(optional)]

Aliases: None Description: W hatAreT ests is used to find out what results are available for the T estIt com-

mand. The T estIt command can only verify the result of a command if the corresponding answer file exists.

Arguments: If the argument is the string containing exactly the character S, N or R, then the result is the available answers for SmallBasis, NCMakeGB or RemoveRedundent respectively. If the argument is an integer, then the result is all of the answers using that particular set of input data. With no argument, all of the answer files are displayed.

Comments \ Limitations: Not available before NCAlgebra 1.2

6.4.3 TimedGBTest[start,end]

Aliases: None Description: Arguments: start is an integer and end is an integer. Comments \ Limitations: Not available before NCAlgebra 1.2

6.4.4 GBTest[start,end]

Aliases: None Description: Arguments: start is an integer and end is an integer. Comments \ Limitations: Not available before NCAlgebra 1.2

6.4.5 CheckRun[aCharString]

Aliases: None Description: Arguments: aCharString is a character string. Comments \ Limitations: Not available before NCAlgebra 1.2

Commands for Making and Using GB’s

This section contains a glossary of commands available for generating and using non-commutative Gröbner Basis.

7.1 Simplification

Before using these commands, a monomial order must be specified. See the section after this for information on how to set the monomial order.

7.1.1 NCSimplifyAll[expressions, startRelations, iterations]

Aliases: GroebnerSimplify, NCGroebnerSimplify

Description: NCSimplifyAll[expressions, startRelations, iterations] calls NCMakeGB[startRelations, iterations] and uses the result to reduce the expressions in expressions. This is useful when the form the Gröbner Basis is irrelevant and is only used to simplify some set of predetermined equations.

Arguments: exprs can be either an expression or a list of expressions. startRelations is a list of polynomials. iterations is a positive integer.

Comments \ Limitations: Not available before NCAlgebra 1.2

7.1.2 NCSR6[expressions, startRelations, iterations]

Aliases: None \underline{7.1. Simplification} 64

Description: NCSR6[expressions, startRelations, iterations] is (essentially) equivalent to NCSimplifyAll[expressions, Join[startRelations, inverses], iterations] where inverses is a list of polynomials. inverses consists of the defining relations of all inverses (elements with inv[...]) in expressions and startRelations. NCSR6 simplifies expressions with startRelations together with some additional innocuous relations. NCSR6 is different from NCSimplifyAll with the following adjustment: first all instances of inv are converted to Inv before calling NCSimplifyAll, and are converted back afterwards. This overrides NCAlgebra’s automatic handling of inverses. For example, the command NCSR6[{inv[x] ∗ ∗inv[1 − x] + y}, {z ∗ ∗inv[y] − a}, 10] equals NCSimplifyAll[{Inv[x] ∗ ∗Inv[1 − x] + y}, {z ∗ ∗Inv[y] − a, y ∗ ∗Inv[y] − 1, Inv[y] ∗ ∗y − 1, Inv[x] ∗ ∗x − 1, x ∗ ∗Inv[x] − 1, (1 − x) ∗ ∗Inv[1 − x] − 1, Inv[1 − x] ∗ ∗(1 − x) − 1}, 10]. This call to NCSimplifyAll returns Inv[x] + Inv[1-x] + y. The call to NCSR6 returns inv[x] + inv[1-x] + y.

Arguments: expressions is a list of polynomials. startRelations is a list of polynomials. iterations is a natural number.

Comments \ Limitations: Not available before NCAlgebra 1.2.

7.1.3 NCSR6[expressions,startRelations]

Aliases: None

Description: NCSR6[expressions,startRelations] is the same as NCSR6[expressions,startRelations,3].

Arguments: expressions is a list of polynomials. startRelations is another list of polynomials.

Comments \ Limitations: Not available before NCAlgebra 1.2

7.1.4 NCSR6[expressions,iterations]

Aliases: None

Description: NCSR6[expressions,iterations] is the same as NCSR6[expressions,{},iterations].

Arguments: expressions is a list of polynomials. iterations is an integer.

\underline{7.2. Making a Gröbner Basis and various options (with their defaults)} 65

7.1.5 NCSR6[expressions]

Aliases: None

Description: NCSR6[expressions] is the same as NCSR6[expressions], {}, 3].

Arguments: expressions is a list of polynomials.

Comments \ Limitations: Not available before NCAlgebra 1.2

7.1.6 Correspondence to sections ‘Making a Gröbner Basis and various options’ and ‘Reduction’

This subsection is a brief note to bring out the conceptual connection between simplification commands presented above and the rest of the commands. The simplification commands presented abov ecombine the steps of computing a partial Gröbner Basis (§7.2) and applying (§Reduction7.8).

7.2 Making a Gröbner Basis and various options (with their defaults)

See Appendix 15 for more infomation of Gröbner Basis. Before using any of these commands, you must set a monomial order. See the next section.

7.2.1 NCMakeGB[aListOfPolynomials, iterations]

Aliases: NCMakeRules, MorasAlgorithm

Description: The GB algorithm proceeds through at most iterations iterations until a Groebner basis is found for the list of polynomials aListofPolynomials with respect to the order imposed by SetMonomialOrder, see §8.4.1. NCMakeGB calls a C++ program and while the C++ program is running, it prints intermediate lists of rules to the screen. When the C++ program finishes, it is either because it has run iterations number of iterations or it has found a Gröbner Basis. If it has found a Gröbner Basis, it prints a message saying so. One may also use the command FinishedComputingBasisQ[] in §7.2.11. The Mathematica output of NCMakeGB is a list of polynomials.

The following computes the Gröbner basis for the ideal generated by x^{2} − a and x^{3} − b.

NCMakeGB[{x^{2} − a, x^{3} − b}, 20]

For options which can be used inside NCMakeGB, see ReturnRelationsToMma, Supress-COutput, SupressAllCOutput, UserSelect and Deselect.

Arguments: aListofPolynomials is a list of polynomials. iterations is a natural number.

Comments \ Limitations: Not available before NCAlgebra 1.2

7.2.2 ReturnRelationsToMma→True – need to rename

Aliases:

Description: ReturnRelationsToMma is an option of NCMakeGB. As one of the last arguments of NCMakeGB you may include either the rule ReturnRelationsToMma→True or ReturnRelationsToMma→False. If False is used, then the result of the NCMakeGB run will be stored in C++ but not returned to Mathematica. One can then retrieve the result using WhatIsPartialGB[] or a subset of the result using WhatIsPartialBasis[aListOfNumber] where aListOfNumber is a subset of the numbers returned from WhatAreNumbers[]. The default value is True. An example is NCMakeGB[aListOfPolynomials, iterations, ReturnRelationsToMma→False]

Arguments: None

Comments \ Limitations: Not available before NCAlgebra 1.2

7.2.3 SupressCOutput→ False (less output to the screen)

Aliases: None

Description: SupressCOutput is an option of NCMakeGB. As one of the last arguments of NC-MakeGB you may include either the rule SupressCOutput→True or SupressCOutput→False. If True is used, then the C++ code will decrease the amount of information it prints to the screen during the run of NCMakeGB. This option only effects the amount of information displayed to the screen. The default value is False. For example,NCMakeGB[aListOfPolynomials, iterations, SupressCOutput→True]

Arguments: None

Comments \ Limitations: Not available before NCAlgebra 1.2

7.2.4 SupressAllCOutput→ False (very little output to the screen)

Aliases: None

Description: SupressAllCOutput is just like SupressCOutput, but when this option is on, even more on the display to the screen will be supressed.

Arguments: None

Comments \ Limitations: Not available before NCAlgebra 1.2

7.2.5 UserSelect→ {}(Distinguishing important relations)

Aliases: None

Description: UserSelect is an option for NCMakeGB and for Spreadsheet. If UserSelect→aListOfPolynomials is given as an option, then the main effect is on the display produced by RegularOuput throughout the rest of the session. UserSelect is cumulative and more and more polynomials fall into the selected category as the user puts them in. The command RegularOutput automatically scans for selected polynomials to display in the collection of relations labelled USER SELECTS. It finds them only after NCMakeGB has been run with the user selects (since RegularOutput searches for the selected polynomials by there number. Henceforth, aListOfPolynomials is displayed as a special category. The default value is {}.

Arguments: None

Comments \ Limitations: Not available before NCAlgebra 1.2

7.2.6 ClearUserSelect[]

Aliases: None

Description: Clears the UserSelected polynomials, that is, it makes the USER SELECTED empty

Arguments: None

Comments \ Limitations: Not available before NCAlgebra 1.2

7.2.7 Deselect→ {} (Preventing certain S-Polynomials from being created)

Aliases: None

Description: Deselect is an option for NCMakeGB. If DeSelectPoly→aListOfPolynomials is given as an option for NCMakeGB, then certain S-polynomials will not be computed. Specifically, no S-polynomial will be formed between two deselected polynomials. Deselect is NOT cumulative. The default value is {}.

Arguments: None

Comments \ Limitations: Not available before NCAlgebra 1.2. Bug: Only the deselected polynomials which are also members of the first argument for NCMakeGB are deselected.

7.2.8 NCCleanUpPolys[aListOfPolynomials]

Aliases: NCCleanUpPoly,CleanUpBasis Description: NCCleanUpPolys[aListOfPolynomials] returns a list of polynomials result such that

the ideal generated by aListOfPolynomials equals the ideal generated by result, such that the normal form of any polynomial p with respect to result is the same as the normal form with respect to aListOfPolynomials (see PolyToRule and Reduction) and such that the normal form of any polynomial p of the list result with respect to the set result\{p} is p.

Arguments: aListOfPolynomials is a list of polynomials Comments \ Limitations: Not available before NCAlgebra 1.2

7.2.9 ReorderInput

Aliases: None Description: Arguments: ?? Comments \ Limitations: ??

7.2.10 CleanUp

Aliases: None Description: Arguments: ?? Comments \ Limitations: ??

7.2.11 FinishedComputingBasisQ[]

Aliases: None Description: FinishedComputingBasisQ[] returns 0 or 1. If it returns 1, then NCMakeRules

stopped because it obtained a Gröbner Basis. If it returns 0, then NCMakeRules stopped because it ran the maximal number of iterations and did not find a Gröbner Basis.

Arguments: None Comments \ Limitations: Not available before NCAlgebra 1.2 .

7.2.12 NCMakeRelations[aSpecialList, aSpecialList, …]

Aliases: None

Description: This command allows the user to easily generate certain lists of polynomials which can be used as input to NCMakeRules. We begin with some examples and then explain the command in the third paragraph of this subsection. Suppose that z1, z2, z3 and z4 have been set to be noncommutative (if not, just type SetNonCommutative[z1,z2,z3,z4]). If one types

NCMakeRelations[{Inv, a, b, c},
{SelfAdjoint, x, y, {{z1, z2}, {z3, z4}}}]

then this function returns the list

{a ∗ ∗Inv[a] == 1, Inv[a] ∗ ∗a == 1, b ∗ ∗Inv[b] == 1, Inv[b] ∗ ∗b == 1,
c ∗ ∗Inv[c] == 1, Inv[c] ∗ ∗c == 1, −x + aj[x] == 0, −y + aj[y] == 0,
−z1 + aj[z1] == 0, −z2 + aj[z3] == 0,
−z3 + aj[z2] == 0, −z4 + aj[z4] == 0}

NCMakeRelations takes any number of arguments and each of its arguments is a List. For each list, the first word describes the type of relations and the other elements can be either simple expressions (like x, y, 1 − y ∗ ∗x, 1 − x ∗ ∗y, etc.) or square matrices with symbolic entries (such as in the example above) or any mixture of these two types of data. We now list the allowed types of relations. Some of the relations are stated in terms of the hereditary functional calculus of Jim Agler (see HereditaryCalculus.m).

1. Isometry (i.e., T such that T^{∗}T − 1 = 0 or equivalently (yx − 1)(T) = 0)

2. CoIsometry

3. Isosymmetry (i.e., T such that (yx−1)(y −x)(T) = 0 or equivalently T^{∗2}T −T^{∗}T^{2} −T^{∗} +T = 0)

4. CoIsosymmetry

5. Isometry[aInteger] (where aInteger is a natural number) (i.e., T such that (yx−1)^{aInteger}(T) = 0)

6. SelfAdjoint (i.e., T such that T^{∗} − T = 0 or equivalently (y − x)(T) = 0)

7. Symmetry[aInteger] (where aInteger is a natural number) (i.e., T such that (y − x)^{aInteger}(T) = 0)

8. Projection (i.e., T such that T^{2} − T = 0)

9. InvL (i.e., T such that InvL[T] ∗ ∗T = 1)

10. InvR (i.e., T such that T ∗ ∗InvR[T] = 1)

11. Inv (i.e., T such that Inv[T] ∗ ∗T = 1 and T ∗ ∗Inv[T] = 1)

12. Rt (i.e., T such that Rt[T]^{2} = T)

Arguments: aSpecialList is a list whose first element is one of the allowed types above and the rest of whose elements are either simple expressions or square matrices.

\underline{7.3. Simple Order Maintenance} 70

7.2.13 NCContinueMakeGB[iterationNumber]

Aliases: None Description: This command allows you to continue running NCMakeGB without resetting

the starting relations. The command NCMakeGB[aList, n, ReturnRelationsT oMma− >

F alse] is equivalent to executing the command NCMakeGB[aList, k, ReturnRelationsT oMma− >

F alse] and then the command NCContinueMakeGB[n] (for any k ≤ n. The command

NCMakeGB[aList, n] is equivalent to executing the command NCMakeGB[aList, k, ReturnRelationsT oMma− >

F alse] and then the command NCContinueMakeGB[n] and then W hatIsP artialGB[] for
any k ≤ n.

Arguments: iterationNumber is an integer. Comments \ Limitations: Not available before NCAlgebra 1.2

7.2.14 Correspondence to sections ‘Simplification’ and ‘Reduction’

This subsection is a brief note to bring out the conceptual connection between making a Gröbner Basis and the simplification commands and the Reduction commands. Making a Gröbner Basis is the first step in the simplification commands presented above. Making a Gröbner Basis is also the main step in the the command SmallBasis in §9.3.1 and Spreadsheet in §7.5.1.

7.3 Simple Order Maintenance

7.3.1 SetKnowns[aListOfVariables] — not yet implemented

Aliases: None Description: SetKnowns[aListOfVariables] records the variables in the list of variables aListOf-

Variables to be corresponding to known quantities. Arguments: aListOfVariables is a list of Mathematica variables. Comments \ Limitations: Not available before NCAlgebra 1.2. This is equivalent to SetMono-

mialOrder[aListOfVariables,1].

7.3.2 SetUnKnowns[aListOfVariables] — not yet implemented

Aliases: None Description: SetUnKnowns[aListOfVariables] records the variables in the list of variables aL-

istOfVariables to be corresponding to unknown quantities.

\underline{7.4. Complicated Order Maintenance} 71

Arguments: aListOfVariables is a list of Mathematica variables. Comments \ Limitations: Not available before NCAlgebra 1.2. This is equivalent to Do[SetMonomialOrder[aListOfVariables[[i]],i+1],

{i, 1, Length[aListOfV ariables]}]

7.3.3 SetMonomialOrder[aVariable,…]

Aliases: None Description: SetMonomialOrder[a,b,c,…] sets the lex order with a < b < c < · · ·. If one uses a

list of variables rather than a single variable as one of the arguments, then multigraded lex order is used.

Arguments: aVaraible is a list of Mathematica variable or a list of Mathematica variables. ??

pull in discussion from ch4 Comments \ Limitations: Not available before NCAlgebra 1.2.

7.4 Complicated Order Maintenance

See Chapter ??.

7.5 NCProcess

Move in from chapter 3.

7.5.1 NCProcess

Aliases: None Description: ?? Arguments: ?? Comments \ Limitations: ?? ?? ??

\underline{7.6. Options for NCMakeGB and NCProcess} 72

7.6 Options for NCMakeGB and NCProcess

7.6.1 DegreeCap→ n (directing NCMakeGB’s effort)

Aliases: None Description: ?? Arguments: ?? Comments \ Limitations: ??

7.6.2 DegreeSumCap→ n (directing NCMakeGB’s effort)

Aliases: None Description: ?? Arguments: ?? Comments \ Limitations: ??

7.6.3 NCGBDebug→ False (True for debugging – creates files) – not

implemented yet

Aliases: None Description: ?? Arguments: ?? Comments \ Limitations: ??

7.7 Coping with the answer

7.7.1 If the answer is too big… – fill this in 7.7.2 RegularOutput[aListOfPolynomials,“fileName”]

Aliases: None Description: RegularOutput[aListOfPolynomials,“fileName”] takes the list of polynomials in

aListOfPolynomials and organizes this list in a certain way, and places the organized information in a file called “fileName”. Examples produced by RegularOutput appear in Chapters 2 and 3. The organization performed is based on the monomial order which was \underline{7.7. Coping with the answer} 73

specified using SetMonomialOrder. Think of every variable in aList1 declared, via Set-MonomialOrder[aList1,1], to be lowest in the ordering as a known. The unknowns are the remaining variables denoted var which are defined, via SetMonomialOrder[aList,n] where aList is a list of variables and var in a member of this list and n ≥ 2. For RegularOutput the only thing that counts is unknowns. RegularOutput sorts polynomials in aListOfPolynomials into categories consisting of polynomials having the same unknowns. This command executes fully in Mathematica. It does not use any C++ code.

Arguments: “fileName” is a character string. aListOfPolynomials is a list of polynomials.

Comments \ Limitations: Not available before NCAlgebra 1.2

7.7.3 WhatIsPartialGB[]

Aliases: None

Description: Since we do not require GB algorithm to run until it obtains a Gröbner Basis, the output of the algorithm need not be a Gröbner Basis. We call the output of the algorithm a partial basis. WhatIsPartialGB[] returns a list of all of the elements in the partial groebner basis. See PartialBasis[n].

Arguments: None

Comments \ Limitations: Not available before NCAlgebra 1.2. See also §13.1.3

7.7.4 IterationNumber[aList] or IterationNumber[aNumber]

Aliases: None

Description: It might be interesting to find out which relations are generated during which iteration of the algorithm. The command IterationNumber returns these numbers. The most common applications of this command will probably be IterationNumber[W hatAreGBNumbers[]] and IterationNumber[W hatAreNumbers[]].

Arguments: aList is a list of integers. aNumber is an integer

Comments \ Limitations: Not available before NCAlgebra 1.2.

\underline{7.8. Reduction} 74

7.8 Reduction

7.8.1 Reduction[aListOfPolynomials, aListOfRules]

Aliases: None Description: Reduction[aListOfPolynomials, aListOfRules] computes the Normal Forms of aL-

istOfPolynomials with respect to the rules aListOfRules. Arguments: aListOfPolynomials is a list of polynomials. aListOfRules is a list of rules. That

is the rules are applied repeatedly to the polynomials in the list until no further reduction occurs

Comments \ Limitations: Not available before NCAlgebra 1.2

7.8.2 PolyToRule[aPolynomial]

Aliases: PolToRule,ToGBRule,ToGBRules Description: PolyToRule[aPolynomial] returns the replacement rule corresponding to aPolyno-

mial, assuming the order of monomials has been set. Arguments: aPolynomial is a polynomial Comments \ Limitations: Not available before NCAlgebra 1.2

7.8.3 RuleToPoly[aRule]

Aliases: None Description: RuletoPoly[aRule] returns aPolynomial corresponding to the replacement rule aRule. Arguments: aPolynomial is a polynomial Comments \ Limitations: Not available before NCAlgebra 1.2

7.8.4 Correspondence to sections ‘Simplification’ and ‘Making a Gröbner

Basis and various options’

This subsection is a brief note to bring out the conceptual connection between Reduction and the commands for simplification and the commands for making a Gröbner Basis §7.2. The second step of a simplification command is the use of a reduction command.

Ordering on variables

As was mentioned above (page ??), one needs to declare a monomial order. There are various monomial orders which can be used when computing Gröbner Basis. The most common are called lexicographic and graded lexicographic orders. In the previous section, we used only graded lexicographic orders. See Section 8.1 for a discussion of lexicographic orders.

We will be considering lexicographic, graded lexicographic and multi-graded lexico-

graphic orders. Lexicographic and multi-graded lexicographic orders are examples of elimination orderings. An elimination ordering is an ordering which is used for solving for some of the variables in terms of others.

We now discuss each of these types of orders.

8.1 Lex Order: The simplest elimination order

To impose lexicographic order a << b << x << y on a, b, x and y, one types

In[14]:=SetMonomialOrder[a,b,x,y];

This order is useful for attempting to solve for y in terms of a, b and x, since the highest

priority of the GB algorithm is to produce polynomials which do not contain y. If producing high order polynomials is a consequence of this fanaticism so be it. Unlike graded orders, lex orders pay little attention to the degree of terms. Likewise its second highest priority is to eliminate x.

Once this order is set, one can use all of the commands in the preceeding section in

exactly the same form.

We now give a simple example how one can solve for y given the facts that a,b,x and y

satisfy the equations:

−b x + x y a + x b a a = 0
x a − 1 = 0
a x − 1 = 0 .

\underline{8.2. Graded lex ordering: A non elimination order} 76

In[15]:= NCMakeGB[{-b ** x + x ** y ** a + x ** b ** a ** a,
x**a-1,a**x-1},4];
Out[15]= {-1 + a ** x, -1 + x ** a, y + b ** a - a ** b ** x ** x}

If the polynomials above are converted to replacement rules, then a simple glance at the

results allows one to see that y has been solved for.

In[16]:= PolyToRule[%]
Out[16]= {a ** x -> 1, x ** a -> 1, y -> -b ** a + a ** b ** x ** x}

Now, we change the order to

In[20]:=SetMonomialOrder[y,x,b,a];

and do the same NCMakeGB as above:

In[21]:= NCMakeGB[{-b ** x + x ** y ** a + x ** b ** a ** a,
x**a-1,a**x-1},4];
In[22]:= PolyToRule[%];
In[23]:= ColumnForm[%];
Out[23]= a ** x -> 1
         x ** a -> 1
         x ** b ** a -> -x ** y + b ** x ** x
         b ** a ** a -> -y ** a + a ** b ** x
         b ** x ** x ** x -> x ** b + x ** y ** x
         a ** b ** x ** x -> y + b ** a
         x ** b ** b ** a ->
         >   -x ** b ** y - x ** y ** b ** x ** x + b ** x ** x ** b ** x ** x
         b ** a ** b ** a ->
         >   -y ** y - b ** a ** y - y ** b ** a + a ** b ** x ** b ** x ** x
         x ** b ** b ** b ** a ->
         >   -x ** b ** b ** y - x ** b ** y ** b ** x ** x -
         >    x ** y ** b ** x ** x ** b ** x ** x +
         >    b ** x ** x ** b ** x ** x ** b ** x ** x
         b ** a ** b ** b ** a ->
         >   -y ** b ** y - b ** a ** b ** y - y ** b ** b ** a -
         >    y ** y ** b ** x ** x - b ** a ** y ** b ** x ** x +
         >    a ** b ** x ** b ** x ** x ** b ** x ** x

In this case, it turns out that it produced the rule a ∗ ∗b ∗ ∗x ∗ ∗x → y + b ∗ ∗a which

shows that the order is not set up to solve for y in terms of the other variables in the sense that y is not on the left hand side of this rule (but a human could easily solve for y using this rule). Also the algorithm created a number of other relations which involved y. If one uses the lex order a << b << y << x, the NCMakeGB call above generates 12 polynomials of high total degree which do not solve for y.

See [CoxLittleOShea].

8.2 Graded lex ordering: A non elimination order

This is the ordering which was used in all demos appearing before this section. It puts high degree monomials high in the order. Thus it tries to decrease the total degree of expressions.

\underline{8.3. Multigraded lex ordering : A variety of elimination orders} 77

8.3 Multigraded lex ordering : A variety of elimination orders

There are other useful monomial orders which one can use other than graded lex and lex. Another type of order is what we call multigraded lex and is a mixture of graded lex and lex order. This multigraded order is set using SetMonomialOrder SetKnowns and SetUnknowns which are described in Section 8.4. As an example, suppose that we execute the following commands:

SetMonomialOrder[{A,B,C},{a,b,c},{d,e,f}];

We use the notation

A < B < C << a < b < c << d < e < f ,

to denote this order.

For an intuitive idea of why multigraded lex is helpful, we think of A, B and C as

corresponding to variables in some engineering problem which represent quantities which are known and a, b, c, d, e and f to be unknown^{1} The fact that d, e and f are in the top level indicates that we are very interested in solving for d, e and f in terms of A, B, C, a, b and c, but are not willing to solve for b in terms of expressions involving either d, e or f.

For example,

(1) d > a ∗ ∗a ∗ ∗A ∗ ∗b

(2) d ∗ ∗a ∗ ∗A ∗ ∗b > a

(3) e ∗ ∗d > d ∗ ∗e

(4) b ∗ ∗a > a ∗ ∗b

(5) a ∗ ∗b ∗ ∗b > b ∗ ∗a

(6) a > A ∗ ∗B ∗ ∗A ∗ ∗B ∗ ∗A ∗ ∗B

This order induces an order on monomials in the following way. One does the following

steps in determining whether a monomial m is greater in the oreder than a monomial n or not.

(1) First, compute the total degree of m with respect to only the variables d, e and f.

(2) Second, compute the total degree of n with respect to only the variables d, e and f.

(3) If the number from item (2) is smaller than the number from item (1), then m is smaller than n. If the number from item (2) is bigger than the number from item (1), then m is bigger than n. If the numbers from items (1) and (2) are equal, then proceed to the next item.

(4) First, compute the total degree of m with respect to only the variables a, b and c.

(5) Second, compute the total degree of n with respect to only the variables a, b and c.

1If one wants to speak very loosely, then we would say that a, b and c are unknown and d, e and f are “very unknown”.

\underline{8.4. The list of commands} 78

(6) If the number from item (5) is smaller than the number from item (4), then m is smaller than n. If the number from item (5) is bigger than the number from item (4), then m is bigger than n. If the numbers from items (4) and (5) are equal, then proceed to the next item.

(7) First, compute the total degree of m with respect to only the variables A, B and C.

(8) Second, compute the total degree of n with respect to only the variables A, B and C.

(9) If the number from item (8) is smaller than the number from item (7), then m is smaller than n. If the number from item (8) is bigger than the number from item (7), then m is bigger than n. If the numbers from items (7) and (8) are equal, then proceed to the next item.

(10) At this point, say that m is smaller than n if and only if m is smaller than n with respect to the graded lex order A < B < C < a < b < c < d < e < f

For more information on multigraded lex orders, consult [HSStrat].

8.4 The list of commands

Many order maintenance tasks can be accomplished using SetKnowns in subsection 7.3.1, SetUn-Knowns in subsection 7.3.2 and SetMonomialOrder in subsection ??.

Here are more commands regarding monomial orders.

8.4.1 SetMonomialOrder[aListofIndeterminants, n]

Aliases: None

Description: SetMonomialOrder[aListOfIndeterminates,n] sets the order of monomials (e.g., if aListOfIndeterminates is {a, b, c, d, f, e}, then the order is a < b < c < d < f < e) and assigns them grading level n. To obtain a graded lexicographic order, one can use n = 1.

Arguments: aListofIndeterminants is a list of indeterminates, n is a natural number

Comments \ Limitations: See Chapter ??. Not available before NCAlgebra 1.2

8.4.2 ClearMonomialOrderN[n]

Aliases: None

Description: ClearMonomialOrderN[n] clears the order having level n. This command is equivalent to SetMonomialOrder[{}, n]

Arguments: n is an integer.

Comments \ Limitations: Not available before NCAlgebra 1.2.

8.4.3 ClearMonomialOrderAll[]

Aliases: None Description: ClearMonomialOrderAll[] effectively executes ClearMonomialOrderN[n] for all pos-

itive integers n. Arguments: None Comments \ Limitations: Not available before NCAlgebra 1.2.

8.4.4 PrintMonomialOrder[]

Aliases: None Description: PrintMonomialOrder[] prints the order to the screen. Arguments: None Comments \ Limitations: See Chapter ??. Not available before NCAlgebra 1.2

8.4.5 WhatIsMultiplicityOfGrading[]

Aliases: None Description: WhatIsMultiplicityOfGrading[] returns a positive integer which is the multiplicity

of the grading. If the value is 1, then one is using graded lexicographical order. Arguments: None Comments \ Limitations: See Chapter ??. Not available before NCAlgebra 1.2

8.4.6 WhatIsSetOfIndeterminants[n]

Aliases: None Description: WhatIsSetOfIndeterminants[n] gives the n-th set of indeterminates. Arguments: None Comments \ Limitations: See Chapter ??. Not available before NCAlgebra 1.2

Commands for Making Small Bases for Ideals – Mma version – name changes

SmallBasis-¿NCSmallBasis Spell RemoveRedundent correctly

A Gröbner Basis can be infinite. Even when a Gröbner Basis is finite, it can be very

large and therefore difficult for a person to digest. One often finds that there are many relations which are generated which do not enhance our understanding of the mathematics. In many cases we want a basis for an ideal which is minimal (i.e., has smallest cardinality) or which is minimal as a subset of a given basis. We, therefore, find it helpful to take a list of rules which are generated by the GB algorithm and make them smaller. Consider the following example.

Example 9.1 A GB generated by the set {P T P − T P, P^{2} − P } is the set {P T^{n}P − T^{n}P : n ≥ 1} ∪ {P^{2} − P } regardless of the term order used. No smaller GB exists.

Here just two relations generate infinitely many. One way to view this example is that

the computer discovers that if a subspace (represented by ran(P) in the computation) is invariant for a linear transformation T, then it is invariant for T^{n} for every n ≥ 1.

The GB algorithms tries to generate this infinite set of relations and at any time has

generated a finite subset of them. When we are trying to discover a theorem or elegant formulas, often these relations having higher powers are irrelevant and clutter the spreadsheet which merely serves to confuse the user.

This introduces the next topic which is shrinking a set of relations to eliminate redun-

dancy. Our desire is to take the generated basis and to remove mathematical redundancy from the generating set without destroying the information which was gained while running the GB algorithm.

We have two lines of attack on this problem.

\underline{9.1. Removing excess relations} 81

9.1 Removing excess relations

9.1.1 Introduction

Our first line of attack works only when the set of relations under consideration has been generated by NCMakeGB and then only either

(1) The history was recorded right after using NCMakeGB via the WhatIsHistory command. OR

(2) There have been no calls to NCMakeGB (either directly or indirectly) since the set of relations was generated.

This approach is very fast.

If one has created a set of relations G by using NCMakeGB, then one can use history

(gotten by the WhatIsHistory command — see ?? recorded during the run of NCMakeGB to find a smaller subset of G which generates the same basis. The essential idea is to take the history from the previous run of NCMakeGB and use it to construct a directed acyclic graph (DAG) representing the information. Then a fast combinatorial DAG search can be done.

Note that the WhatIsHistory command only records one way in which a certain relation

is generated. For example, suppose that p_{5} is an S-polynomial of p_{1} and p_{2} and p_{5} is not reduced. It may also be the case the p_{5} is an S-polynomial of p_{3} and p_{4} and p_{5} is not reduced. If the program computed p_{5} by taking the S-ppolynomials of p_{1} and p_{2} first, then the fact that p_{5} is an S-polynomial of p_{3} and p_{4} will not be recorded.

9.1.2 RemoveRedundent[]

Aliases: None

Description: RemoveRedundent[] calls RemoveRedundent[aListOfPolynomials,history] with the default correct choices for aListOfPolynomials and history.

Arguments: None

Comments \ Limitations: WARNING: The execution of this command depends upon the last NCMakeGB run which was executed. Some commands call NCMakeGB as they run such as SpreadSheet (subsection ??) and SmallBasis 9.3.1.

9.1.3 RemoveRedundent[aListOfPolynomials,history]

Aliases: None

Description: RemoveRedundent[aListOfP olynomials, history] generates a subset P of aListOfP olynomials which generates the same ideal as aListOfP olynomials. ??We conjecture that this is a smallest such set whose descendents in the history dag contain aListOfP olynomials.?? ??We conjecture that this property charachterizes P uniquely. This command is faster while maybe not as powerful at reducing as ShrinkBasis since this command relies on the history of how the GB was generated and it just extracts key ancestors. That is why the list history is included to tell the routine how the various polynomials were generated. History must have been recorded using the WhatIsHistory command from the run of GB algorithm which produced aListOfPolynomials.

Arguments: history is an output from the WhatIsHistory command. aListOfPolynomials is a list of polynomials.

Comments \ Limitations: WARNING: The history one gets from the WhatIsHistory command comes from the last run of the NCMakeGB command. The NCMakeGB command is called by several other commands such as SpreadSheet (subsection ??) and SmallBasis and its variants 9.3.1.

9.1.4 RemoveRedundentByCategory[]

Aliases: None

Description: RemoveRedundentByCategory[] calls RemoveRedundentByCategory[aListOfPolynomials, history] with the default correct choices for aListOfPolynomials and history.

Arguments: None

Comments \ Limitations: It is wise to execute WhatIsHistory to set history right after you call NCMakeGB. WARNING: This command executes on the last NCMakeGB run which was executed. Some commands call NCMakeGB as they run, like SpreadSheet (subsection ??)

9.1.5 RemoveRedundentByCategory[aListOfPolynomials,history]

Aliases: None

Description: RemoveRedundentByCategory[aListOfPolynomials,history] generates a subset P of aListOfPolynomials which generates the same ideal as aListOfPolynomials. It is best thought of in the context of RegularOutput or a spreadsheet. Recall?? the digested relations are the polynomials involving no unknowns, single variable expressions, together with user selected relations. Let the digested relations from the list aListOfPolynomials be called D. Suppose we denote each category of undigested polynomials by X_{j} where j runs from 1 to the number of these categories. Then RemoveRedundentByCategory[aListOfPolynomials, history] is the union over j of RemoveRedundent[Union[D, X_{j}], history].

Arguments: aListOfPolynomials is a list of polynomials. history is a list from the command WhatIsHistory.

\underline{9.2. Discussion of RemoveRedundent command} 83

Comments \ Limitations: It is wise to execute WhatIsHistory to set history right after you call NCMakeGB. WARNING: The history one gets from the WhatIsHistory command comes from the last run of the NCMakeGB command. The NCMakeGB command is called by several other commands such as SpreadSheet (subsection ??) and ??.

9.2 Discussion of RemoveRedundent command

MAYBE PUT AFTER HSTORY SEC

RemoveRedundant requires a history and a list of polynomials. NCMakeGB records part

of what it is doing during its computation and that can be used to determine some facts about ideal membership. This history can be though of as a directed acyclic graph (abbreviated as dag)^{1}. The the list of polynomials is a subset V of all of the nodes and the output of RemoveRedundant is another set R of nodes v in V. Let √ denote a connected path which runs from v backward in time until it reaches a leaf. Now P ends at v in the set V and may as we go backwards along it in time leave V then come back etc. Let v(P) denote the earliest node of P in V. It belongs to R. Indeed, R = {v(P) for all maximal connected forward flowing paths ending in V }. For example, if some path P ends in v and the node immediately before v is not in V, then v is in R. Now we give more formal statements and about how the RemoveRedundant algorithm works.

Let p_{1},…, p_{n} ∈ K[x_{1},…, x_{n}]. Let T be a tree on the nodes {1,…, n}. We say that

the tree represents the development of p_{1},…, p_{n} if it is the case that for every j = 1,…, n either

(1) j is a leaf of the tree OR

(2) there exists a S-polynomial s coming from p_{a} and p_{b} and k_{1},…, k_{r} ∈ {1,…, n} such that

(a) {a, b, k_{1}, k_{2},…, k_{r}} is the set of children of j in the tree T, and

(b) there exist polynomials q_{1},…, q_{r} such that s →^{p_{k_{1}}} q_{1} →^{p_{k_{2}}} ⋯ →^{p_{kr}} q_{k_{r}} = p_{j}.

OR

(3) there exist a and {k_{1},…, k_{r}} such that {a, k_{1},…, k_{r}} are the children of j and there exist polynomials q_{1},…, q_{r} such that p_{a} reduces to q_{1} by applying the rule associated to the polynomial p_{k_{1}}, q_{1} reduces to q_{2} by applying the rule associated to the polynomial p_{k_{2}}, …, q_{r−1} reduces to q_{r} by applying the rule associated to the polynomial p_{k_{r}} such that p_{a} →_{p_{k_{1}}} q_{1} →^{p_{k_{2}}} ⋯ →_{p_{kr}} q_{r} = p_{j}.

Now suppose that T is a tree on {1,…, n} and it represents the development of p_{1},…, p_{n}.

If j is the root of the tree and k_{1},…, k_{r} are the leafs of T, then p_{j} lies in the ideal generated by p_{k_{1}},…, p_{k_{r}}. In fact, p_{a} lies in the ideal generated by p_{k_{1}},…, p_{k_{r}} for every a such that both 1 ≤ a ≤ n.

1A common and canonical example of a dag is a tree

\underline{9.3. Brute Force: Shrinking} 84

Now, if a tree T represents the development of p_{1},…, p_{n} and one chooses a subset

{k_{1},…, k_{r}} ∈ {1,…, n}, then one can consider the largest subgraph of T for which each node k_{ℓ} has no edge leading from it. Each connected component of this subgraph will be a tree. Let T_{o} be such a connected component of T and {ℓ_{1},…, ℓ_{w}} be the nodes of T_{o}. It is clear that the tree T_{o} represents the development of p_{ℓ_{1}},…, p_{ℓ_{w}}.

This is the key to the function RemoveRedundent. This function takes a tree T which

represents the development of p_{1},…, p_{n} and a list of nodes {ℓ_{1},…, ℓ_{w}}. The algorithm proceeds as follows. Let result = {ℓ_{1},…, ℓ_{w}}; Let unchanged = F alse; while(unchanged)

unchanged = False; temp = result; while(unchanged is False and temp is not the empty set)

Pick ℓ ∈ temp;

Let temp = temp\{ℓ};

More here ?? MARK whats this mean end while

end while

9.3 Brute Force: Shrinking

Our second line of attack can be slower. It finds a subset of the set of relations by applying the GB machinery. For example, if one knows that p_{n} is a member of the ideal generated by {p_{1},…, p_{n−1}}, then the set {p_{1},…, p_{n}} can be shrunk to {p_{1},…, p_{n−1}}. Determining whether or not p_{n} is a member of the ideal generated by {p_{1},…, p_{n−1}} can be partially decided by running the GB algorithm for several iterations.

9.3.1 SmallBasis[aListOfPolynomials,anotherListOfPolynomials,iter]

Aliases: None

Description: SmallBasis[aListOfP olynomials, , iter] computes and returns a list aList which is a subset of aListOfP olynomials such that the ideal generated by aList equals the ideal generated by aListOfPolynomials . anotherListOfPolynomials adds the feature that when one includes it in the call it just joins to the answer above without being changed. In other words, SmallBasis computes and returns a list aList which is a subset of aListOfP olynomials such that the ideal generated by Join[aList, anotherListOfPolynomials] equals the ideal generated by Join[aListOfPolynomials, anotherListOfPolynomials]. This is done via calls to NCMakeGB. NCMakeGB iterates at most iter times. Here is how it works: Let LP denote {p_{1}, p_{2},…, p_{u}}. First SmallBasis[LP,{},iter] generates a partial GB for p_{1}, p_{2}, and reduces p_{3}, p_{4},…, p_{3} with this GB. If the result is 0, then SmallBasis stops and returns {p_{1}, p_{2}}. If not SmallBasis generates GB(p_{1}, p_{2}, p_{3}) and reduces the remaining polynomials. Etc. Finally, SmallBasis returns {p_{1}, p_{2},…, p_{k}} with the property that the partial Göbner Basis GB(p_{1},…, p_{k}) reduces {p_{1}, p_{2},…, p_{n}} to zero. Clearly, the result is very dependent on the order if the entries lie in LP. The integer iter determines the number of iterations used to produce the partial GB’s. SmallBasis[LP1,LP2,iter] has the same functionality as Complement[ SmallBasis[ Join[LP1,LP2], {}, iter], LP2], (i.e., SmallBasis[Join[LP1,LP2], {}, iter] minus the set LP2) but is much faster.

Arguments: aListOfP olynomials and anotherListOfP olynomials are lists of polynomials. iter is a natural number.

Comments \ Limitations:

WARNING: This command calls NCMakeGB which effects the output of the WhatIsHistory command which in turn can effect the use of the command RemoveRedundent and its variants (subsections 9.1.2, 9.1.3, 9.1.4 and 9.1.5) or the use of the command SmallBasis and its variants (subsections 9.3.1 and 9.3.2).

9.3.2 SmallBasisByCategory[aListOfPolynomials,iter]

Aliases: None

Description: under development –low priority SmallBasisByF orCategory returns a list aList which is a sorted subset of aListOfP olynomials such that the ideal generated by Join[aList, anotherListOfP olynomials] equals the ideal generated by Join[aListOfP olynomials, anotherListOfP olynomials]. This is done via calls NCMakeGB.

Arguments: aListOfP olynomials is a list of polynomials. iter is a natural number.

Comments \ Limitations: Not available before NCAlgebra 1.2

9.3.3 ShrinkOutput[aListOfPolynomials,fileName]

Aliases: None

Description: ShrinkOutput can take a very long time to run on large or complicated sets of polynomials. ShrinkOutput[aListOfPolynomials,fileName] takes the list of polynomials in aListOfPolynomials and puts a subset of aListOfPolynomials into a file via RegularOutput (subsection 7.7.2) This smaller subset is generated by the command SmallBasis (subsection ??)

Arguments: aListOfPolynomials is a list of polynomials. fileName is a character string

\underline{9.4. Brute Force: Many shrinks} 86

9.4 Brute Force: Many shrinks

9.4.1 ShrinkBasis[aListOfPolynomials,iterations]

Aliases: None

Description: ShrinkBasis can take a long time to run and returns a {L_{1}, L_{2},…, L_{r}} of lists of polynomials. Each list L_{j} of polynomials is contained in aListOfPolynomials. Each list L_{j} is a generating set for the ideal generated by aListOfPolynomials and the computer makes a limited attempt to show that any proper subset of L_{j} does not generate the ideal. Moreover, the union of the L_{j}’s is aListOfPolynomials.

ShrinkBasis depends upon the monomial order which is set, because it calls NCMakeGB where it iterates at most iterations times. If all of the runs of NCMakeGB generate Gröbner Bases in iterations iterations, then no proper subset of an L_{j} is a generating set for the ideal generated by aListOfPolynomials.

The command works by brute force. It selects a polynomial from aListOfPolynomials and computes a partial GB for the remaining polynomials (with iterations iterations). It uses these to eliminate the original polynomial.

Arguments: aListOfPolynomials is a list of polynomials. fileName is a string.

Chapter 10

Commands for Making Small Bases for Ideals – C++ version

To be filled in

Commands to Create and Retrieve Categories — Mma version

Crucial to our approach to “semi-automatic” discovery of formulas and theorems is the sorting of relations according to which unknowns appear in them — in other words, sorting lists of polynomials into categories. RegularOutput does this sorting and presents categories of relations (by storing them in file). Actually the core of RegularOutput is a command CreateCategories which creates categories and gives them a name. These categories can be called using the GetCategory command.

Before using these commands one must use SetMonomialOrder.

11.0.2 CreateCategories[aListOfPolynomials,aName]

Aliases: None

Description: CreateCategories[aListOfPolynomials,aName] sorts aListOfPolynomials into categories. Each category and its label is stored in the array associated to the symbol aName and it is accessible by aName[label] using the GetCategory command. aListOfP olynomials is a list of polynomials. aName is a symbol which has not been used previously.

Arguments: aListOfPolynomials is a list of polynomials. aName is a Mathematica symbol.

Comments \ Limitations: Not available before NCAlgebra 1.2. See GetCategory.

11.0.3 GetCategory[aListOfVariables,aName]

Aliases: None

Description: GetCategory[aListOfV ariables, aName] retrieves the polynomials in the category stored in aName corresponding to the list of variables in the list aListOfV ariables.

Arguments: aListOfV ariables is a list of variables. aName is a symbol which has not been

used previously. Comments \ Limitations: Not available before NCAlgebra 1.2. See CreateCategories.

11.0.4 GetCategory[aCharString,aName]

Aliases: None Description:

(1) If aCharString is ”Undigested”, then all of the undigested relations are returned.

(2) If aCharString is ”Digested”, then all of the digested relations are returned.

(3) If aCharString is ”Unknowns”, then all of the undigested relations are returned.

(4) If aCharString is ”Knowns”, then all of the relations involving just knowns are returned.

(5) If aCharString is ”digestedLabels”, then {{}} is returned.

(6) If aCharString is ”digestedRules”, then all of the digested relations are returned.

(7) If aCharString is ”userSelectsRules”, then all of the user selected relations are returned.

(8) If aCharString is ”userSelectsLabels”, then all of the user selected labels are returned.

(9) If aCharString is ”knownsLabels”, then {{}} is returned.

(10) If aCharString is ”knownsRules”, then all of the relations involving just knowns are returned.

Otherwise, aName[aCharString] is returned. Arguments: aCharString is a character string. aName is a symbol. Comments \ Limitations:

As an example, consider the following set of relations with the multigraded lex order

A < B < C0 < D < ACROSS < P 1 < P 2 << proj1 < proj2 << m1 < m2 << leftm1 < leftm2 << rightm1 < rightm2 << a < b < c < e < f < g. This arose in the demo in Subsection ??. So we proceed assuming we have set the order. Suppose eliminatedOriginal has been set so that:

In[4]:= eliminatedOriginal
Out[4]= {c - C0 ** m1, g - C0 ** m2, -1 + leftm1 ** m1, leftm1 ** m2,
>    leftm2 ** m1, -1 + leftm2 ** m2, leftm1 ** A ** m2,
>    e - leftm2 ** A ** m2, b - leftm1 ** B, f - leftm2 ** B,
>    -leftm1 + rightm1, -leftm2 + rightm2, a - leftm1 ** A ** m1,
>    -leftm2 ** A ** m1 + leftm2 ** B ** C0 ** m1,
>    -1 + m1 ** leftm1 + m2 ** leftm2,
>    A ** m1 - B ** C0 ** m1 - m1 ** leftm1 ** A ** m1 +
>     m1 ** leftm1 ** B ** C0 ** m1,

>    -A ** A ** m1 + A ** B ** C0 ** m1 + B ** C0 ** A ** m1 -
>     B ** C0 ** B ** C0 ** m1 + m1 ** leftm1 ** A ** A ** m1 -
>     m1 ** leftm1 ** A ** B ** C0 ** m1 -
>     m1 ** leftm1 ** B ** C0 ** A ** m1 +
>     m1 ** leftm1 ** B ** C0 ** B ** C0 ** m1}

Before demonstrating the Category commands, we apply the RegularOutput command

so the reader can see which categories occur. The following command creates a file junk which has a nicely formatted version of the information stored in dummy (see page 91).

In[6]:= RegularOutput[%4,"junk"]
Outputting results to the stream OutputStream["junk", 6]
Done outputting results to the stream OutputStream["junk", 6]
In[7]:= !!junk
THE ORDER IS NOW THE FOLLOWING:
A < B < C0 < D < ACROSS < P1 < P2 <<
proj1 < proj2 << m1 < m2 << leftm1 <
leftm2 << rightm1 < rightm2 << a < b < c
 < e < f < g
================================================
========= THE ALGORITHM HAS SOLVED FOR==========
================================================
THE FOLLOWING VARIABLES HAVE BEEN SOLVED FOR:
{c,g,e,b,f,rightm1,rightm2,a}
The corresponding rules are the following:
c->C0**m1
g->C0**m2
e->leftm2**A**m2
b->leftm1**B
f->leftm2**B
rightm1->leftm1
rightm2->leftm2
a->leftm1**A**m1

================================================
========= USER CREATIONS APPEAR BELOW ==========
================================================
================================================
========= UNDIGESTED RELATIONS APPEAR BELOW ====
================================================
THE FOLLOWING VARIABLES HAVE NOT BEEN SOLVED FOR:
{leftm1,leftm2,m1,m2}

The expressions with unknown variables {
leftm1,m1}
and knowns {A,B,C0}
---------------------------------------
leftm1**m1->1
m1**leftm1**B**C0**m1-> -A**m1   + B**C0
**m1 + m1**leftm1**A**m1
m1**leftm1**B**C0**B**C0**m1->A^2**m1 +
 -A**B**C0**m1   +  -B**C0**A**m1   + B

**C0**B**C0**m1 +  -m1**leftm1**A^2**m1
   + m1**leftm1**A**B**C0**m1 + m1**
leftm1**B**C0**A**m1

The expressions with unknown variables {
leftm1,m2}
and knowns {A}
---------------------------------------
leftm1**m2->0
leftm1**A**m2->0

The expressions with unknown variables {
leftm2,m1}
and knowns {A,B,C0}
---------------------------------------
leftm2**m1->0
leftm2**B**C0**m1->leftm2**A**m1

The expressions with unknown variables {
leftm2,m2}
and knowns {}
---------------------------------------
leftm2**m2->1

The expressions with unknown variables {
leftm1,leftm2,m1,m2}
and knowns {}
---------------------------------------
m2**leftm2->1 +  -m1**leftm1

Now we illustrate the CreateCategories command. One calls it on the above set of

relations with the above order by typing:

In[5]:= CreateCategories[%,dummy]
Out[5]= dummy

The effect of the above command is to associate the following information to the symbol

dummy.

In[6]:= ??dummy
                           <=== recall Mma does not produce an
                                output in response to ??
                                one gets a screen display (as follows)
Global`dummy

dummy[2] = {{b, leftm1}, {c, m1}, {f, leftm2}, {g, m2}, {leftm1, m1},
   {leftm1, m2}, {leftm1, rightm1}, {leftm2, m1}, {leftm2, m2},
   {leftm2, rightm2}}
dummy[3] = {{a, leftm1, m1}, {e, leftm2, m2}}

dummy[4] = {{leftm1, leftm2, m1, m2}}
dummy["AllCategories"] =
  {{b, leftm1}, {c, m1}, {f, leftm2}, {g, m2}, {leftm1, m1}, {leftm1, m2},
   {leftm1, rightm1}, {leftm2, m1}, {leftm2, m2}, {leftm2, rightm2},
   {a, leftm1, m1}, {e, leftm2, m2}, {leftm1, leftm2, m1, m2}}
dummy["nonsingleVars"] = {leftm1, leftm2, m1, m2}
dummy["numbers"] = {2, 3, 4}
dummy["singleRules"] =
  {c -> C0 ** m1, g -> C0 ** m2, e -> leftm2 ** A ** m2, b -> leftm1 ** B,
   f -> leftm2 ** B, rightm1 -> leftm1, rightm2 -> leftm2,
   a -> leftm1 ** A ** m1}
dummy["singleVars"] = {c, g, e, b, f, rightm1, rightm2, a}
dummy[{b, leftm1}] = {b -> leftm1 ** B}
dummy[{c, m1}] = {c -> C0 ** m1}
dummy[{f, leftm2}] = {f -> leftm2 ** B}
dummy[{g, m2}] = {g -> C0 ** m2}
dummy[{leftm1, m1}] =
  {leftm1 ** m1 -> 1, m1 ** leftm1 ** B ** C0 ** m1 ->
    -A ** m1 + B ** C0 ** m1 + m1 ** leftm1 ** A ** m1,
   m1 ** leftm1 ** B ** C0 ** B ** C0 ** m1 ->
    A ** A ** m1 - A ** B ** C0 ** m1 - B ** C0 ** A ** m1 +
     B ** C0 ** B ** C0 ** m1 - m1 ** leftm1 ** A ** A ** m1 +
     m1 ** leftm1 ** A ** B ** C0 ** m1 + m1 ** leftm1 ** B ** C0 ** A ** m1}
dummy[{leftm1, m2}] = {leftm1 ** m2 -> 0, leftm1 ** A ** m2 -> 0}
dummy[{leftm1, rightm1}] = {rightm1 -> leftm1}
dummy[{leftm2, m1}] =
  {leftm2 ** m1 -> 0, leftm2 ** B ** C0 ** m1 -> leftm2 ** A ** m1}
dummy[{leftm2, m2}] = {leftm2 ** m2 -> 1}
dummy[{leftm2, rightm2}] = {rightm2 -> leftm2}
dummy[{a, leftm1, m1}] = {a -> leftm1 ** A ** m1}
dummy[{e, leftm2, m2}] = {e -> leftm2 ** A ** m2}
dummy[{leftm1, leftm2, m1, m2}] = {m2 ** leftm2 -> 1 - m1 ** leftm1}
dummy[_] := {}

One can pick of categories one by one in Mathematica by using the GetCategories

command.

In[5]:= GetCategories[{leftm2, m1},dummy]
Out[5]= {leftm2 ** m1 -> 0, leftm2 ** B ** C0 ** m1 -> leftm2 ** A ** m1}
In[6]:= GetCategories[{},dummy]

Out[6]= {}
In[7]:= GetCategories[{leftm1,m1},dummy]
Out[7]= {leftm1 ** m1 -> 1, m1 ** leftm1 ** B ** C0 ** m1 ->
>     -A ** m1 + B ** C0 ** m1 + m1 ** leftm1 ** A ** m1,
>    m1 ** leftm1 ** B ** C0 ** B ** C0 ** m1 ->
>     A ** A ** m1 - A ** B ** C0 ** m1 - B ** C0 ** A ** m1 +
>      B ** C0 ** B ** C0 ** m1 - m1 ** leftm1 ** A ** A ** m1 +
>      m1 ** leftm1 ** A ** B ** C0 ** m1 + m1 ** leftm1 ** B ** C0 ** A ** m1
>     }

Commands to Create and Retrieve Categories — C++ version

To be filled in later.

History of the production of a GB and Playing By Numbers

This chapter contains two advanced topics whose relationship is more technical than conceptual.

13.1 Play By Numbers

The Mathematica code and the C++ code both attach numbers to the polynomials which occur in the running of the GB algorithm. While these numbers are not externally visible at least in the commands described so far, they can be accessed by the user and are quite useful. One feature is that they can save typing time for the user who chooses to select or deselect relations in later runs of NCMakeGB. Also, if one is running the C++ version of the code, this will save considerable computer time because the C++ version of the code only has to send a number rather than the full polynomial to the Mathematica session. This time can be very significant when the polynomial has a large number of terms. See also section 13.2. Recall the Option ReturnRelationsToMma → False for NCMakeGB stops the partial GB calculated by the C++ program from transferring the answer back to Mathematica. This is the typical prelude to a “play by numbers ” session.

Recall the option ReturnRelationsToMma→ False for NCMakeGB stops the results from

the NCMakeGB command from being returned to Mathematica. This is typically the first step in “playing by numbers”.

13.1.1 WhatAreGBNumbers[]

Aliases: None

Description: WhatAreGBNumbers[] returns a list of numbers. These numbers correspond to the elements of WhatIsHistory which determine what the ending relations are. If one computes Map[(#[[2]])&,WhatIsHistory[WhatAreGBNumbers[]]] then one gets the same result as WhatIsPartialGB[]

Arguments: None \underline{13.1. Play By Numbers} 96

Comments \ Limitations: Not available before NCAlgebra 1.2

13.1.2 WhatAreNumbers[]

Aliases: None

Description: WhatAreNumbers[] returns a list of numbers. These numbers correspond to all of the polynomials which were used and retained inside the C++ code. One needs this command to make sense of the WhatIsHistory output. No argument is included because it can be applied only to the previous GB run.

Arguments: None

Comments \ Limitations: Not available before NCAlgebra 1.2

13.1.3 WhatIsPartialGB[aListOfIntegers]

Aliases: None

Description: WhatIsPartialGB[aListOfIntegers] returns the polynomials corresponding to the entries in aListOfIntegers. The command WhatIsPartialGB[] is equivalent to WhatIsPartialGB[WhatAreGBNumbers[]].

Arguments: aListOfIntegers is a list of natural numbers.

Comments \ Limitations: Not available before NCAlgebra 1.2. The list of integers does not have to be a subset of the integers in WhatAreGBNumbers[], it can also be a subset of the list of integers in WhatAreNumbers[]. In plain english this says that W hatIsP artialGB can retrieve any polynomial which has occurred in the course of running the last call to NCMakeGB (not just the output of NCMakeGB).

13.1.4 NumbersFromHistory[aPolynomial,history]

Aliases: None

Description: NumbersFromHistory[aPolynomial,history] returns all numbers n such that one of the elements of the list history has the form {n, aP olynomial, whatever, whatever2} where we do not care what the value of whatever or whatever2 is. Usually this function will return only a list with one integer in it.

Arguments: aPolynomial is a polynomial. history is the output from the command WhatIsHistory (subsection ??).

Comments \ Limitations:

\underline{13.2. History of the production of a GB} 97

13.2 History of the production of a GB

13.2.1 WhatIsHistory[aListOfIntegers]

Aliases: None

Description: Applies to any List of Integers subset of the output of WhatAreNumbers[]. WhatIsHistory[ WhatAreNumbers[] ] lists the tree which produced the elements of the previous GB run. Also possible is WhatIsHistory[2,6,7] which will produce only relation numbers 2, 6, 7 and describe their immediate ancestors. It is handy if you already know that you are interested in 2, 6, 7.

Arguments: aListOfIntegers is a list of natural numbers.

Comments \ Limitations: WARNING: The output to the command WhatIsHistory changes after every call to NCMakeGB. The command NCMakeGB is called during the run of the Spreadsheet commands (subsections ??) and the run of any of the variants of the SmallBasis command (subsections 9.3.1 and 9.3.2).

13.2.2 WhatIsKludgeHistory[aListOfIntegers]

Aliases: None

Description: WhatIsKludgeHistory[aListOfIntegers] returns the same output as WhatIsHistory[aListOfIntegers] except that second entry which is a polynomial in WhatIsKludgeHistory is much shorter (and is not a relation in the ideal) than WhatIsHistory. The point is to save time. Kludge History is generated inside of C++ and transferring it back into Mathematica takes much less time than the full history because transferring long polynomials into Mathematica takes a long time. Every polynomial in KludgeHistory lies in the same category as the polynomial it replaces in history. Thus, RemoveRedundentUseNumbers applies to KludgeHistory returns the same relation numbers as RemoveRedundentUseNumbers applied to history (if one uses the option).???

Arguments: None

Comments \ Limitations: WARNING: The output to the command WhatIsHistory changes after every call to NCMakeGB. The command NCMakeGB is called during the run of the Spreadsheet commands (subsections ??) and the run of any of the variants of the SmallBasis command (subsections 9.3.1 and 9.3.2).

13.2.3 More on the History of how NCMakeGB produced its answer

We now continue with the demo from Subsection ??.

In[14]:= WhatAreNumbers[]
Out[14]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
In[15]:= ColumnForm[ WhatIsHistory[Out[14]] ]
Out[15]= {1, x ** x -> a, {0, 0}, {}}
         {2, x ** y -> a, {0, 0}, {}}
         {3, x ** y -> b, {0, 0}, {}}
         {4, x ** x ** x -> b, {0, 0}, {}}
         {5, x ** a -> a ** x, {1, 1}, {}}
         {6, a ** y -> a ** x, {1, 2}, {5}}
         {7, x ** b -> a ** x, {1, 3}, {6}}
         {8, a ** x -> b, {1, 4}, {}}
         {9, a ** a -> b, {1, 4}, {1, 7, 8}}
         {10, b ** x -> b, {4, 1}, {1, 9}}
         {11, b -> a, {2, 3}, {}}

We now describe what the above output means. Notice that each line is a number followed by

a replacement rule followed by a pair of numbers followed by a list of zero or more numbers. The tuples

mean

{relation number, relation, the 2 parents of thr relation, which rules relations were applied to the S-

polynomial}

For example, we say that x ∗ ∗x → a is the first replacement rule, x ∗ ∗y → a is the second

replacement rule,etc. The third entry is the two parents of rule There are two cases:

(Case: the third component is the pair {0, 0}) When the pair {0, 0} appears as the third component of list, the relations was provided as input to the NCMakeGB. In this case, the fourth list is always empty.

(Case: the third component is the pair {a, b} and a and b are positive) When the pair {a, b} appears as the third component of list, then the first step in constructing this rule comes from taking the S-polynomial of the ath and bth replacement rules. The last list of numbers indicates which replacement rules were applied to that S-polynomial in order to produce the relation.

(Case: the third component is the pair {−a, −a} and a is positive) The relation was generated using CleanUpBasis using the ath relation. The last list of numbers indicates which replacement rules were applied to this ath replacement rule to generate the present rule.

Note that one can use history to do two things. The first thing is to see how relations are

derived. The second is to find a smaller subset of the relations mentioned which will generate the same

ideal. Note that in the above example, x ∗ ∗a − a ∗ ∗x lies in the ideal generated by x ∗ ∗x − a can be seen

by referring to only the above history. Also, note that one can see that a ∗ ∗y − a ∗ ∗x lies in the ideal

generated by {x ∗ ∗x − a, x ∗ ∗y − a and x ∗ ∗a − a ∗ ∗x}. This will prove very helpful in finding a subset

of a particular set of a generated relations R which generates the same ideal as R. (See Section ??.??).

13.2.4 The DAG associated with a History

Consider the following tree on the nodes {2, 3, 6, 7, 8, 9}.

[figure: 8; 6; 7; 7; 3; 2; 9; 9; 3; 2; 9]

Let us suppose that this tree represents the history corresponding to {p_{2}, p_{3}, p_{6}, p_{7}, p_{8}, p_{9}}. That

is, p_{8} is generated as an s-polynomial from p_{6} and p_{7}, p_{6} is generated as an S-polynomial from p_{7} and

p_{9} and p_{7} is generated as a reduced S-polynomial. The polynomial generated is from p_{3} and p_{9} and a

reduction step using p_{2} was used. In the notation of the history output, this would take the form

{
{2,p_2,{0,0},{}},
{3,p_3,{0,0},{}},
{6,p_6,{7,9},{}},
{7,p_7,{3,9},{2}},
{8,p_8,{6,7},{}},
{9,p_9,{0,0},{}},
}

One sees from the picture that

(1) p_{8} ∈ ⟨p_{6}, p_{7}⟩

(2) p_{6} ∈ ⟨p_{7}, p_{9}⟩

(3) p_{6} ∈ ⟨p_{3}, p_{2}, p_{9}⟩

(4) p_{7} ∈ ⟨p_{3}, p_{2}, p_{9}⟩

(5) p_{8} ∈ ⟨p_{6}, p_{3}, p_{2}, p_{9}⟩

(6) p_{8} ∈ ⟨p_{7}, p_{9}⟩

(7) p_{8} ∈ ⟨p_{7}, p_{3}, p_{2}, p_{9}⟩

(8) p_{8} ∈ ⟨p_{3}, p_{2}, p_{9}⟩

Other stuff

14.1 Starting Relations

14.1.1 ClearStartingRelations[]

Aliases: None Description: ClearStartingRelations[] empties the data base. The data base holds all occurences of

rules and they are referred to by number by the use of StartingRelations[n] or PartialBasis[n]. See SetStartingRelations[data].

Arguments: None Comments \ Limitations: Not available before NCAlgebra 1.2

14.1.2 SetStartingRelations[data]

Aliases: None Description: SetStartingRelations[data] adds the given data to the data base. Arguments: data is a polynomial or a list of polynomials. Comments \ Limitations: Not available before NCAlgebra 1.2

14.1.3 WhatAreStartingRelations[]

Aliases: None Description: WhatAreStartingRelations[] returns a list of all of the elements in the starting relations.

This is helpful in the middle of a session to remove any doubt about what set of relations one is working on. See StartingRelations[n].

Arguments: None Comments \ Limitations: Not available before NCAlgebra 1.2

\underline{14.2. Experiment recording stuff — not fully implemented} 101

14.2 Experiment recording stuff — not fully implemented

The following commands have been partially implemented and may or may not be supported in the future. (1)StartExperiment (2)StartExperiment[aString] (3)ContinueExperiment[] (3)PauseExperiment[] (3)EndExperiment[] (3)RecordUserCommand[aString] (3)RecordProgramResponse[expr] (3)CreateATranscript[] (3)CreateATranscript[aString]

14.3 Sort commands

14.3.1 SortRelations[aListOfRules]

Aliases: None Description: SortRelations[aListOfRules] sorts the list of rules aListOfRules. First, the sorting is done

by the number of unknowns in each rule. For rules with the same number of unknowns, the one which is considered largest is the one which has a largest left hand side (in terms of the monomial order).

Arguments: aListOfRules is a list of rules. Comments \ Limitations:

14.3.2 SortMonomials[aListOfVariables]

Aliases: None Description: SortMonomials[aListOfVariables] returns a sorted list of monomials in terms of the mono-

mial order. Arguments: aListOfVariables is a list of indeterminates. Comments \ Limitations:

14.3.3 SetMonomialOrderSymmetric[aListOfIndeterminates,anInteger]

Aliases: None Description: SetMonomialOrderSymmetric[[aListOfIndeterminates,anInteger] sets the monomial order

on the anInteger-th level by using the elements of aListOfIndeterminates and their transposes. For example, if aListOfIndeterminates= {a, b, c}, then SetMonomialOrderSymmetric[aListOfIndeterminates,3] would be equivalent to SetMonomialOrder[{a, tp[a], b, tp[b], c, tp[c]}].

Arguments: aListOfIndeterminates is a list of indeterminates. anInteger is an natural number. Comments \ Limitations:

\underline{14.4. Changing the default options for NCMakeGB} 102

14.4 Changing the default options for NCMakeGB

14.4.1 ChangeNCMakeGBOptions[option,value] — need to update de-

scription

Aliases: None Description: When the C++ version of the code is loaded, the statement Options[NCMakeGB] :=

CleanUp-¿1,ReturnRelations-¿True,SupressCOutput-¿False; is found in the code. The content of this command is that CleanUpBasis in by default on, ReturnRelations is by default true and SupressCOutput is by default false. If one wants to change these defaults, then one can use the ChangeNCMakeGBOptions command. For example, ChangeNCMakeGBOptions[{CleanUp- ¿1,ReturnRelations-¿False, SupressCOutput-¿False} changes the default behaviour so that Return-Relations is false by default.

Arguments: ThreeRules is a list containing three rules. The left hand sides of these rules must be

CleanUp, ReturnRelations and SupressCOutput Comments \ Limitations:

14.5 An idea for the future

14.5.1 MultipleTrips – not yet implemented

Aliases: None Description: Arguments: None Comments \ Limitations:

14.6 Small Basis Type Commands

14.6.1 SmallBasis[firstList, keepList,anInteger] — documented elsewhere

Aliases: None Description: Arguments: firstList and keepList are lists of polynomials. anInteger is a natural number. Comments \ Limitations:

14.6.2 SmallMakeBasis

Aliases: None Description: Arguments: None Comments \ Limitations: The average user would never use this command.

\underline{14.7. Technical} 103

14.6.3 Specialcomplement[aList,item]

Aliases: None Description: Arguments: None Comments \ Limitations: The average user would never use this command.

14.6.4 SmallBasisByCategory[aListOfPolynomials,iterations]

Aliases: None Description: iterations denotes the number of iterations which will be executed during the call to

NCMakeGB. Arguments: iterations is an natural number. Comments \ Limitations:

14.6.5 SmallBasisOnEliminationIdeal[ProcessedBasis, topElimLevel,iterations]

Aliases: None Description: iterations denotes the number of iterations which will be executed during the call to

NCMakeGB. Arguments: iterations is a natural number. Comments \ Limitations:

14.6.6 SmallBasisOnMultElimIdeals[ProcessedBasis, topElimLevel,anInteger]

Aliases: None Description: anInteger denotes the number of iterations which will be executed during the call to

NCMakeGB. Arguments: anInteger is a natural number. Comments \ Limitations:

14.7 Technical

14.7.1 GroenbnerCutOffFlag[n Integer]

Aliases: None Description: Turns the “cutting off” operations either on or off. Arguments: n is an natural number. Comments \ Limitations: Not available before NCAlgebra 1.2

14.7.2 GroebnerCutOffMin[n Integer]

Aliases: None Description: Sets the min for sum on polynomial degree cut offs. Arguments: n is an natural number. Comments \ Limitations: Not available before NCAlgebra 1.2

14.7.3 GroebnerCutOffSum[n Integer]

Aliases: None Description: Sets the min for sum on polynomial degree cut offs. Arguments: n is an natural number. Comments \ Limitations: Not available before NCAlgebra 1.2

14.7.4 unExp[anExpression]

Aliases: None Description: Arguments: anExpression is an expression Comments \ Limitations:

14.7.5 unBase[anExpression]

Aliases: None Description: Arguments: anExpression is an expression Comments \ Limitations:

14.7.6 CreateSubCategories[aListOfPolynomials,aSymbol] — not yet im-

plemented

Aliases: None Description: Arguments: aListOfP olynomials is a list of polynomials. aSymbol is a symbol. Comments \ Limitations:

14.7.7 UserSelects[aInteger]

Aliases: None Description: Arguments: aInteger is a natural number. Comments \ Limitations:

14.7.8 UserSelectedQ[aInteger]

Aliases: None Description: Arguments: aInteger is a natural number. Comments \ Limitations:

14.7.9 NumberOfFactorsOnLeftHandSide[anInteger]

Aliases: None Description: NumberOfF actorsOnLeftHandSide[anInteger] returns the number of factors of the left

hand side of the replacement rule associated to the natural number anInteger via the history. Arguments: anInteger is a natural number. Comments \ Limitations:

14.7.10 VariablesOfGBPolynomial[anInteger]

Aliases: None Description: V ariablesOfGBP olynomial[anInteger] returns a character string. If this character string

is inputted to the built-in Mathematica command T oExpression, then the result is a list of the variables which arise in the replacement rule associated to the natural number anInteger via the history.

Arguments: anInteger is a natural number. Comments \ Limitations:

14.7.11 ReinstateOrder[]

Aliases: None Description: After a call to SetGlobalPtr[], ClearMonomialOrder[] or ClearMonomialOrderN[n], Rein-

stateOrder[] is used to restore the previously established order of indeterminates. The exception is ClearOrder[]. After this function is called, the order cannot be restored.

Arguments: None Comments \ Limitations: Not available before NCAlgebra 1.2.

14.7.12 PartialBasis[aNumber]

Aliases: None Description: PartialBasis[aNumber] (where aNumber is a positive integer) returns a character string. If

this character string is input to the built-in Mathematica command ToExpression, then the result is the aNumber-th element of the partial basis data base.

Arguments: aNumber is a natural number. Comments \ Limitations: Not available before NCAlgebra 1.2. See also 13.1.3. Note: aNumber does

not correspond to the numbers generated from the WhatIsHistory command. See ReturnRelations (subsection ??.

14.7.13 SetCleanUpBasis[n]

Aliases: None Description: If n is nonzero (best to use n=1), SetCleanUpBasis[n] indicates that the program used

to implement NCCleanUpRules should be applied after each iteration of the GB algorithm. Set-CleanUpBasis[0] indicates that such additional processing should not be done.

Arguments: n is an integer Comments \ Limitations: Not available before NCAlgebra 1.2

14.7.14 CleanUpBasisQ[]

Aliases: None Description: CleanUpBasisQ[] returns the argument of the SetCleanUpBasis command the last time it

was used. Arguments: None Comments \ Limitations: Not available before NCAlgebra 1.2. This allows one to see which “cleaning”

option is in force.

A notebook like environment under unix: NCSetNb

NCSetNb

NCSetNb (pronounced N C Set Notebook) is designed to speed up calculations that require

information from previous runs, by saving results of past runs in files. When information is needed, the appropriate files are retrieved, thus avoiding calculating something again and again.

To use NCSetNb there are two main commands, NCStartNb[”DirectoryName”] and NCSetNb[”filename”,

MmaCommand].

NCStartNb[”DirectoryName”] creates the directory /home/DirectoryName if it does not already exist. The directory serves as the ”notebook” where all files for a run are stored.

NCSetNb[”filename”, MmaCommand] calculates MmaCommand, and assigns the Mma-variable filename to the result. It then makes 2 files in /DirectoryName called filename and filename.ColumnForm. Filename is a Mma executable file, and filename.ColumnForm is for reading purposes.

$ExecuteNb can be set to either True or False. If $ExecuteNb := True, then for every NC-

SetNb[”filename”, MmaCommand] that has been already run, the file /DirectoryName/filename is read in and the Mma-variable filename is assigned to the information. If there is no file, filename, in /DirectoryName or NCSetNb[”filename”, MmaCommand] has not yet been run, then NCSetNb is executed. If $ExecuteNb := False, then all NCSetNb[”filename”, MmaCommand] are executed and the files in /DirectoryName are not read in.

Here is an example:

$ExecuteNb := False;
NCStartNb["problem1"];
NCSetNb["run1", NCMakeRules[stuff,morestuff,1]];

The directory /home/problem1 is created if it does not exist, and the files, run1 and run1.ColumnForm are created in /problem1 with the results of NCMakeRules. Because $ExecuteNb is false, NCMakeRules will be calculated even if a file already exists in /problem1. Let’s continue and run another step.

$ExecuteNb := True;
NCStartNb["problem1"];
NCSetNb["run1", NCMakeRules[stuff,1]];
NCSetNb["run2", NCMakeRules[run1,1]];

The second NCSetNb command takes advantage of the earlier run by reading in the file run1 in /problem1 and assigns the variable run1 to the partial basis. The only calculation done in Mma is the NCSetNb for run2. If one desires to recalculate the entire run, one can either delete the files in /home/problem1 or change $ExecuteNb := False in the source code.

$ExecuteNb can be used to run parts of the source file. Suppose in the next example that

the entire source code was run once, but changes were made requiring only the second iteration of NC-MakeRules to be rerun. You can accomplish this by resetting $ExecuteNb to False before the second NCMakeRules.

$ExecuteNb := True;
NCStartNb["problem1"];
NCSetNb["run1",NCMakeRules[stuff,1]];
$ExecuteNb := False;
NCSetNb["run2",NCMakeRules[run1,1]];

$ExecuteNb can be reset any number of times.

Another effective strategy for problems that change over successive runs is to create new direc-

tories.

$ExecuteNb := True;
NCStartNb["NEWproblem1"];
NCSetNb["run1", NCMakeRules[stuff,1]];
NCSetNb["run2", NCMakeRules[run1,1]];

All information in this run is now kept in /home/NEWproblem1. Because there are no files in /Newproblem1, the first time this code is run both NCMakeRules will be computed. It is advisable to make a new copy of the source code to reflect changes. Making new directories is useful when initial or starting information needs to be changed.

Here is a nice way to use the .ColumnForm files to view results. Suppose the source file is called

”joe” containing the following:

$ExecuteNb := True;
NCStartNb["problem2"];
NCSetNb["run1",NCMakeRules[stuff,1]];
(*
COMMENT: The above NCSetNb produced the following:
#include "problem2/run1.ColumnForm"
*)

Run joe in Mma, and afterwards type

cc -P joe

The file joe.i is created. The #include command will yank in run1.ColumnForm in the joe.i file. Viewing

the joe.i file reveals the #include command is replaced by the .ColumnForm output.

$ExecuteNb := True;
NCStartNb["problem2"];
NCSetNb["run1",NCMakeRules[stuff,1]];
(*
COMMENT: The above NCSetNb produced the following:
!!!The contents of problem2/run1.ColumnForm would appear here!!!!
*)

The advantage to the last method is that the source file can run in a shell instead of batchmode, and one

can view the .i file when a run is finished.

\underline{.1. The Commutative Case} 110

REFERENCES

[HSStrat] Helton-Stankus strategy paper

[CoxLittleOShea] ?? [FMora] ??

[TMora] ?? [SpV] ?? Background on Gröbner Basis The following chapter provides a brief background concerning how one can use Gröbner Bases

and a few comments about how they are generated.

In order to discuss how the Gröbner Basis algorithm in the noncommutative case has application

to problems involving the manipulation of matrices, we first discuss how the Gröbner Basis Algorithm in the commutative case can help one to solve systems to polynomial equatons.

.1 The Commutative Case

If p_{1},…, p_{m} ∈ K[x_{1},…, x_{n}] and a = (a_{1},…, a_{n}) is a common root of p_{1},…, p_{m}, then a is a root of every polynomial p which lies in the smallest ideal generated by p_{1},…, p_{m}. Furthermore, if q_{1},…, q_{ℓ} is a generating set for the same ideal, then a is a common root of the p‘s if and only if it is a common zero of the q‘s. Therefore, instead of trying to solve for the common roots of p_{1},…, p_{m} directly, it could be advantageous to find a different set of polynomials q_{1},…, q_{ℓ} which generate the same ideal as p_{1},…, p_{m} and then solve for the common roots on the q’s. This is exactly what happens during the procedure of Gauss-Jordan elimination as applied to linear equations — the steps involved are finding a different set of linear equations which genearte the same ideal and so have the same set of solutions. In the case of linear equations, the “solve” step is so easy that, in a sense, it is easy to think that there is no solve step.

As an example for non-linear equations, if one has a system of equations and it turns out that

x_{1} is a member of the ideal generated by the polynomials, then it would be helpful to be able to find that out without using some numerical analysis technique. If x_{1} − x_{2}x_{3} were a member of the ideal, then one would know to solve for x_{2} and x_{3} numerically and tell the computer that x_{1} is x_{2}x_{3}.

.2 The Noncommutative case

If one is working with a system of matrix equations, then some or all of those equations might take the form of equations in matrices M_{1},…, M_{n} of the form p(M_{1},…, M_{n}) = 0 where p is a polynomial in noncommuting indeterminates x_{1},…, x_{n}. For example, M_{1}M_{2}M_{1}−M_{3}M_{2} = 0 and M_{1}M_{2}M_{1}−M_{1}M_{2} = 0 and M_{1}M_{1} − M_{1} = 0 take this form. If one has a system of such equations, then it can be difficult to classify the solutions of these equations or determine “what they mean”. Like the commutative case, the set of matrices which satisfy a system of the matrix equations p_{1} = 0,…, p_{m} = 0 also satisfy another set of matrix equations q_{1} = 0,…, q_{ℓ} = 0 where the q‘s generate the same ideal as the p‘s.

The task of finding different sets of matrix equations which generate the same set of solutions

is is the task of our computer programs which are explained in this document.

\underline{.2. The Noncommutative case} 111

We shall find that the Gröbner Basis algorithm gives us one such different generating set. Often

this generating set is to large and so it is necessary to find a smaller one, if possible. This is the topic of chapter ??.