------------------------------------------------------------------ APPENDICES ------------------------------------------------------------------ APPENDIX A. NCAlgebra INSTALLATION NCAlgebra was developed on a UNIX system and it is very easy to install on one. Here we tell you how. Installation under DOS or on a MAC is similar and if you are a novice the assistance of system manager could be valuable to you. (1) Create an NCAlgebra directory (2) Copy NCAlgebra files into directory created in step 1. The files are: NCAlgebra.m CEEP Lots of files starting with NC. Lots of files ending with Extra. A file called NCTeX.process which you should transfer to the bin directory before you use our TeX setting command DoTeX. The most reliable way to find out the names of the NC-files actually used for computation is to consult the file NCAlgebra.m. It automatically loads them. Here is a list of these files at the present time: NCDOCUMENT.doc ----not loaded NCDOC1Appendix.doc ----not loaded NCAdjoints.m NCAlias.m NCBlockPartition.m NCCo.m NCCollect.m NCComplex.m NCDiff.m NCDoTeX.m NCEndPackage.m NCInverses.m NCMatMult.m NCMessyFunction.m NCMono.m NCMultiplication.m NCOutput.m NCRoots.m NCSave.m NCSchur.m NC1SetCommands.m NC2SetCommands.m NC0SimplifyRational.m NC1SimplifyRational.m NC2SimplifyRational.m NCSimplifyRational.m NCSolve.m NCSubstitute.m NCTeXForm.m NCToggle.m NCTools.m NCTransposes.m NCUsage.m The files which have the suffix "Extra." were small programs that are not fully tested and some of which are small specialized functions which may not be (are probably not) valuable to others. We include them just in case they may be valuable to someone and so that they can give examples of how someone may extend the code for their own purposes. The files *.NCTest are not automatically loaded. They are explained in APPENDIX G. (3) Edit the file NCAlgebra.m to replace the System`path =? with whatever path takes you to the NC* files you just loaded in your machine. (4) Edit the file NCAlgebra.m to replace filenames there with the corresponding file names on your system. In UNIX THIS SHOULD REQUIRE NO CHANGE. In DOS filenames have at most 8 characters.3 characters, so some of the files in our UNIX version have their name truncated. When the NC* files are down loaded onto an IBM PC this truncation is done automatically according to DOS conventions. You just need to edit the filenames in NCAlgebra.m to correspond to the names DOS gave the files. The only other wrinkle is you must make sure that each file has a unique name. Peculiar to our package NCAlgebra is one line in NCAlgebra.m $$OperatingSystem="UNIX" You should change it to $$OperatingSystem="DOS" (5) Note: bookkeeping is easier if you create a working subdirectory of the NCAlgebra directory, say WORKDIR, where you compute and save your sessions. To make this easy put NCAlgebra.m in WORKDIR and edit it so that System`path = gets you to NCAlgebra For example, we use the path /home/osiris/helton/mathdir/NCAlgebra/ because our computer is a SUN called osiris, the account is called helton, and standard Mathematica packages are stored in mathdir. (6) If you want to use DoTeX (which is UNIX dependent) follow the instructions in the file DoTeX.install. (7) If you want to run SYSTEMS or NCTEST you possibly must modify paths since these are files whose only purpose is to call other files (as does NCAlgebra.m). Do this just like you would in NCAlgebra.m (see 3. above ). If you did not modify paths in NCAlgebra.m you probably will not have to here. APPENDIX B. UNIX DEPENDENCIES There are several places in the code in which explicit facts about the UNIX operating system are used. Here is a list of ones which we could think of. (1) The assignment statement in NCAlgebra.m System`path = "/home/osiris/helton/mathdir/NCAlgebra/" needs to be adapted to the specific case. (1') There is a line in NCAlgebra.m $$OperatingSystem="UNIX" You should change it to $$OperatingSystem="DOS" if you are going to a PC. (2) In the file NCSubstitute.m, Date[] uses a pipe to the UNIX date command. (4) DoTeX uses UNIX commands and will not run elsewhere. APPENDIX C. AN EXTENDED EXPLANATION OF THE SUBSTITUTE FAMILY OF FUNCTIONS The commands Substitute, SubstituteSymmetric, SubstituteReverse, ... basically serve two purposes, 1) to be noncommutative analogues for ReplaceAll (/.) and ReplaceRepeated (//.) . 2) to do 'handy' frequent substitutions. Because the Flat attribute is not set for NonCommutativeMultiply Mathematica's /. and //. can not properly match expression like: a ** b ** c /. a ** b -> d to give d ** c. In order to record which Substitute rules are executed (for future use), we have provided a facility to store these rules for future use in the file Rules.temp. If you wish to use any of the NCSubstitute commands without recording it in the Rules.temp file, execute the same rule with a 'p' added to the beginning of the name of the command (e.g., pSubstitute). Substitute is the analogue of //. and SubstituteSingleRep is the analogue of /. One can think of the Reverse commands as applying a set of rules 'backwards', that is, in reverse order and with the left and right hand sides reversed. To use any NCSubstitute commands with Reverse in their names, make sure that there isn't any overlapping of variable names if you wish to restore a previous expression from a later one by reversing a set of rules. As a final statement, be aware that patterns may match but not in the same ways as the built-in Mathematica functions. For example; Below /. is using a single-blank to match the entire expression x ** x/. a_ :> {a} --gives-- {x ** x} While SubstituteSingleReplace only matchs the first element SubSingleRep[ x ** x, a_ :> {a} ] --gives-- {x} ** x APPENDIX D. DEMONSTRATION OF SAVERULES ---Let's see that rules are usually being recorded. In[6]:= SaveRulesQ[] SaveRulesQ::On: The Rules.temp file is recording substitution rules. Out[6]= True ---Here is an expression to work with. In[7]= exp = -XX ** inv[1 - YY ** XX] ** YY ** tp[C2] ** inv[tp[d21]] ** inv[d21] ** C2 - XX ** inv[1 - YY ** XX] ** YY ** tp[C2] ** inv[tp[d21]] ** tp[B1] ** XX ---Now, do some substitutions. In[8]:= Sub[ %, {XX->x, YY->y} ] Out[8]= -x ** inv[1 - y ** x] ** y ** tp[C2] ** inv[tp[d21]] ** inv[d21] ** C2 - x ** inv[1 - y ** x] ** y ** tp[C2] ** inv[tp[d21]] ** tp[B1] ** x ---Let's check the Rules.temp file. In[9]:= ShowRules[] "Mon Jul 29 15:08:44 PDT 1991"" ""Substitute" ----the date may not show up. {XX -> x, YY -> y} "------" Out[9]= 0 ---We can also do substitutions, without changing the Rules.temp file. The next command turns off the rules recording. In[11]:= SaveRules[ Off ] ---We can ask if it has been 'turned off.' In[12]:= SaveRulesQ[] SaveRulesQ::Off: The Rules.temp file is not recording substitution rules. Out[12]= False ---But, let's make new substitutions and really check! In[14]:= Sub[ exp, XX->x ] Out[14]= -x ** inv[1 - YY ** x] ** YY ** tp[C2] ** inv[tp[d21]] ** inv[d21] ** C2 - x ** inv[1 - YY ** x] ** YY ** tp[C2] ** inv[tp[d21]] ** tp[B1] ** x In[15]:= ShowRules[] "Mon Jul 29 15:08:44 PDT 1991"" ""Substitute" {XX -> x, YY -> y} "------" Out[15]= 0 ---See, nothing new added. We may also add rules to the Rules.temp file by the optional argument method. In[18]:= Sub[ exp, YY->y, On ] Out[18]= -XX ** inv[1 - y ** XX] ** y ** tp[C2] ** inv[tp[d21]] ** inv[d21] ** C2 - XX ** inv[1 - y ** XX] ** y ** tp[C2] ** inv[tp[d21]] ** tp[B1] ** XX ---Let's check. In[19]:= ShowRules[] "Mon Jul 29 15:08:44 PDT 1991"" ""Substitute" {XX -> x, YY -> y} "------" "Mon Jul 29 15:09:03 PDT 1991"" ""Substitute" {YY -> y} "------" Out[19]= 0 In[20]:= SaveRulesQ[] SaveRulesQ::Off: The Rules.temp file is not recording substitution rules. Out[20]= False ---Note, that you may choose to make 'continuous' records or 'individual' records, but you can not 'block' an individual record from being recorded when the continuous mode is active. The above shows that you can make 'individual' records even when the 'continuous' mode is inactive. Finally, other things may be sent directly to the Rules.temp file. This should send 'exp' to the Rules.temp file also. In[25]:= SaveRules[ exp, tag -> "test expression" ] In[27]:= ShowRules[] "Mon Jul 29 15:08:44 PDT 1991"" ""Substitute" {XX -> x, YY -> y} "------" "Mon Jul 29 15:09:03 PDT 1991"" ""Substitute" {YY -> y} "------" "Mon Jul 29 15:10:16 PDT 1991"" ""test expression" -XX ** inv[1 - YY ** XX] ** YY ** tp[C2] ** inv[tp[d21]] ** inv[d21] ** C2 - XX ** inv[1 - YY ** XX] ** YY ** tp[C2] ** inv[tp[d21]] ** tp[B1] ** XX "------" Out[27]= 0 APPENDIX.E MORE ABOUT PATTERN MATCHING FOR MAKING RULES We refer to expressions with variables and their inverses as rational. There are a few rules which are very powerful in simplifying such expressions. In NCSimplify1Rational we implement some of these rules. Below we discuss some of the things which are involved with adding additional rules. The most serious difficulty comes if you need to match patterns. FLAT ---- The NonCommutativeMultiply function (i.e., '**" ) that ordinarily is defined in Mathematica has the following Attributes; Flat, OneIdentity and Protected. The Flat attribute has an influence on pattern- matching. When a symbol has the Flat attribute it indicates that all expressions involving nested functions of that symbol are to be regarded as unnested during pattern-matching. NCAlgebra has redefined NonCommutativeMultiply and modified all of its former attributes. As a consequence of Flatless NonCommutative- Multiply, pattern-matching becomes significantly more involved. Nevertheless, there are several guidelines we can suggest to the user in the construction of pattern-matching rules and/or functions. DOUBLE-BLANK SEQUENCES ---------------------- Below we use a function to demonstrate the rationale behind our liberal use of double-blank sequences in NCSimplify1Rational. We define a function f that matches the NonCommutativeMultiply product of two Double-Blank Sequences and prints each Double-Blank Sequence on separate lines. Example 1: In[52]:= f[ (y__) ** (z__) ] := (Print[y]; Print[z]) In[52]:= f[a ** b] a b In[53]:= f[a ** b ** c] a bc In[54]:= f[a ** b ** c ** d] a bcd Thus we see that the effect of the pattern y__ ** z__ is the same as the pattern y_ ** z__ This is consistent with Mathematica's tendency to match the first object to the first pattern and the remaining objects to the second pattern. The next example defines a function g with a argument structure similar to many rules used in NCSimplify1Rational. It illustrates how we can force the first Double-Blank Sequence to match more than a single object. Example 2: In[65]:= g[ (x__) ** inv[1 + (x__) ** (y__)] ] := (Print[a]; Print[b]) In[65]:= g[ a ** inv[1 + a ** b] ] a b In[66]:= g[ a ** b ** inv[1 + a ** b ** c ] ] ab c In[67]:= g[ a ** b ** inv[1 + a ** b ** c ** d ] ] ab cd Ordinarily x__ ** y__ in Mathematica, would group the following; a ** b as (a) ** (b) a ** b ** c as (a) ** (b ** c) a ** b ** c ... ** k as (a) ** (b ** c ** ... ** k) We can see that in function g, the x__ (Double-Blank Sequence) that precedes the inv[ 1 + x__ ** y__ ] forces x__ ** y__ to behave in such a way that ANY number of factors can be captured by x__ and the remaining factors are captured by y__. This is due to the fact that the structure of x__ is 'captured' INDEPENDENTLY of it's use in the pattern x__ ** y__ inside of the inv[] function. This is necessary to make the function g more general, since the way the Mathematica ordinarily matches x__ ** y__ as x_ ** y__ is too restrictive to be useful. The interplay between combinations of single, double and triple blank sequences must be thoroughly tested before you can be sure that a pattern is effective. In other words, it is not enough to know how the individual parts of a pattern work because the combination of pattern units can result in unforeseen consequences. Be aware that Mathematica pattern matchs the first (and often smallest) expression which satisfies its conditions. Although, not discussed here, it is possible to use pattern restrictions (e.g. x_Integer), pattern test (e.g. x_?Positive), and/or conditions to further control the behavior of patterns, See Wolfram's text. Examples 1 and 2 are actual functions that were used to build up the rules in NCSimplify1Rational. They illustrate the use of the pattern Double-Blank Sequences that were used in that program and the practice of building up from simple patterns to more complex ones. Note the use of Print[]'s to verify the actual behavior of the match. Once you are satisfied that your pattern matches the correct kinds of objects and no more or less, then you can change the Print[]'s to the desired expression. LISTS OF RULES -------------- (In the following, when we use the term 'rule' we mean all the Mathematica Rule[] or RuleDelayed[] commands we used to represent a single mathematical identity. When we used more than one Rule[] or RuleDelayed[] command we made a list of the those commands.) In NCSimplify1Rational you'll notice that several rules have two parts requiring a list to be made of the RuleDelayed[] expressions. The list is made from the more general double-blank sequence pattern and a single-blank sequence pattern. Sometimes one rule will cover all forms that mathematically satisfy the pattern, but this is not always so. For understandability, we made lists of structural different but mathematically equivalent patterns. This way, one rule represents the list of all equivalent pattern expressions. Make sure that any special forms of the pattern- to-be-matched aren't overlooked by any rules you create yourself. In the following example, which happens to be an actual rule from NCSimplify1Rational, it would 'seem' that there is no need for two parts. (*-----------------------RULE 3-------------------------------*) (* Part 1 ----> inv[1 + K a b ] a b -> (1 - inv[1 + K a b])/K *) (* Part 2 ----> inv[1 + K a] a -> (1 - inv[1 + K a])/K *) (*------------------------------------------------------------*) rule[3] := { (* Part 1 *) (d___) ** inv[Id + (K_.)*(a__) ** (b__)] ** (a__) ** (b__) ** (e___) :> (d ** e + -1*d ** inv[Id + K*a ** b] ** e)/K , (* Part 2 *) (d___) ** inv[Id + (K_.)*(a_)] ** (a_) ** (e___):> (d ** e + -1*d ** inv[Id + K*a] ** e)/K }; It would seem that part 2 is the only necessary rule, but it is not. It turns out that the single blanks in part 2 can't be 'stretched' to cover instances of part 1 and the double-blanks in part 1 require a minimum of two noncommutative factors which rules out the single variable forms of part 2. The triple-blank sequences (d___ and e___) that lead and trail the lhs's (left-hand side) of each pattern are there to capture any leading and trailing terms in the expression. This is the main mechanism used to simulate the Flat attribute. The (K_.) sequence captures any Commutative factor, to be called K, and if missing then to be replaced by 1. (K_.) is equivalent to (K_:1) See Wolfram on globally-defined default values p. 240. For the class of expressions that NCSimplify1Rational is designed to simplify, the mix of single, double, and triple blanks (other than the leading and trail triple-blanks sequences) was not fruitful. As a final suggestion concerning constructing patterns, not enough can be said about the frequent use of the Edit[] and EditDef[] commands when experimenting with patterns. Remember to give the expression a name that is a symbol since EditDef[] works only on symbols. APPENDIX F. WRITING ADDITIONAL PACKAGES It is very likely that people who work with this program will want to add extra packages to the ones which we have included. We would appreciate it if someone has a general tool which may be valuable to others, that he/she would send it to us at UCSD so that we may incorporate it with the other code which we have. In addition to the actual package, it would be very helpful if the following were included: (1) Usage notes for each function (2) Text which could be inserted into this document explaining what the code does. (3) A TEST file which does rather mundane tests so that if it broken in the future (by someone else), then that could be easily detected in the future. See APPENDIX G. We have included some files which are in a state of development. All of these files start with the suffix ".Extra". A list of them at the day which this is being written is: Date.Extra ---the version of Mathematica which we use does not have Date[] built-in. The file is a UNIX hack. FuncAssign.Extra ---Some substitution rules hold for any analytic function. This file takes an expression and tries to find that polynomial Hardy.Extra ---Operator theory. Implements InnerProduct on Hardy space NCDyad.Extra ---Operator Theory. Implement rank 1 operators. NCHereditary.Extra ---Operator Theory. Implement hereditary polynomials (See any one of Jim Agler's paper's) NCKernels.Extra ---Operator Theory. Implement reproducing kernels Operator.Extra ---Operator Theory. Implement A x where A is a matrix and x is a vector (MatMult won't work due to the implementation of NCDyad and NCKernels) SetNumber.Extra ---Treat a symbol as a number. Slows down computations. ineq.Extra ---Try to implement a inequality equation manipulator. APPENDIX G. AUTOMATIC TESTING PROGRAMS We included our programs which automatically test the functions in NCAlgebra. To run all of the testing programs just load in the file NCTEST <a substitution does not always work so we recommend using our Substitute[expr, x->a] 1. eran@slacvm found that it is possible to do a legitimate operation with (the built-in) NonCommutativeMultiply which puts one into an infinite loop. Thus our NonCommutativeMultiply (and eran's) are not the same as Mathematica's. They are missing one rule. This leads directly to problems 2 and 3 below. --see footnote at end of file for details. 2. a**x**j**y-v**f**u -u**f /. x**j->y does not actually make the substitution. Thus we wrote a Substitute function which does. 3. Double blank a__ sometimes causes a to lose its head NonCommutativeMultiply. To fix it write out NonCommutativeMultiply instead of ** on the right hand side of the rule. FOOTNOTE Here is part of a letter from eran@slac to helton@osiris Just try defining NonCommutativeMultiply[] to be something (say 1) without first removing the Flat Attribute. Mathematica goes into an infinite loop when evaluating NonCommutativeMultiply[a, b] because the Flat attribute, in addition to telling it that NCM[a, NCM[b, c]] -> NCM[a, b, c], also tells it that NCM[a, b] should be matched by NCM[NCM[], NCM[a, b]], and, of course, now it has a rule for that second expression. On other words, the difference between the built-in Flat and my corresponding rules is that the built-in Attribute goes both ways. Eran OUR STUFF ------------ 1.Tricky Pattern Matching If you execute the following expression DirectionalD[x, tp[x], h] you get 0. If one executes the following expression thing = DirectionalD[tp[y], y, h]; Sub[thing, y->tp[x]] then one gets the correct answer. The problem is that it is not obvious to Mathematica that x is a function of tp[x]. Indeed, x = f[tp[x]] where f = tp. One cliche one could use is that Mathematica knows that tp is idempotent, but it doesn't know that it knows. When "tp" is defined, code similar to the following is executed. tp[tp[x_]] := x; IdempotentQ[x] = True; So if one types in tp[tp[y]] one gets back y, but if one asks "Is x a function of tp[x]?", then the most simple-minded way of writing the code (the way it is now written) gives the answer no (since the expression x does not have any subexpressions of the form tp[x]). Of course, one usually takes derivatives with respect to a letter (say x and y), but not always (like taking the derivative with respect to Conjugate[z], which is a whole other ballgame.) The code above with the intermediate value thing is probably safer. APPENDIX I. DIRECTION WE ARE HEADED WITH RESPECT TO TeX The following is a explanation for a possible approach to the TeX conversion of an entire file. This is distinct from DoTeX whose goal is to split out TeX expressions interactively. The main objective of this conversion program is to produce text that is easy to edit. There are two different types of text: (1) Comments of three types: (a) text to be left alone no changes - anything not indicated by a special symbol of the form indicating (b) or (c) below. (b) text to be put out as conventional mathematics, but not to be processed by Mathematica - place each line between dollar signs, e.g. $$ math text here $$ $$ math text here $$ $$ math text here $$ $$ math text here $$ Indicate this mode is starting with a (@ and ending with a @). (c) text to be converted to picture - Mark says this is possible. Indicate this mode is starting with a (: and ending with a :). (2) executable Mathematica code - to be processed by TeXForm. Bill wants to be able to "reprocess" a file which is output from this conversion program back through the program again, as revisions are made. To enable this, we need A. to keep the (* *) symbols - do not delete. This is so that program can still tell commented text from executable Mathematica code. B. Make the logic so that anything contained within $$ text $$ or $ text $ should be left alone. (Same logic as text between (* and *) provided no special symbols indicating (b) or (c) above are present.) Embedded symbols of all kinds can be supported, provided Mathematica has the capability to maintain a stack. APPENDIX J. POSSIBLE FUTURE DIRECTIONS We are adding this section to indicate possible future code development possibilities. It should not be construed to be a promise or guarantee of what we do next -- rather a collection of hunches of what we might be doing next. Indeed, we may decide to not further develop the code we have here at all. Having said this, we make the following comments. 0. If you want to actively work on this program, let us know beforehand. We will let you know of progress on the program "as it happens" so that we do not reproduce each others work. Send us the result of your effort so that we may use include it in the next version. Any of the below mentioned items should be easy to develop. See also the appendix on writing your own packages. 1. The files which comprise the NonCommutativeMultiply package will probably not change very much at all. The file NCRoots.m may be added to reproduce the code in NCInverses.m for roots (e.g., NCForwardRoots). Also, the file NC1SetCommands.m may be changed substantially to implement, say, Linear functions in a better way (e.g., so that you can select whether you want to express f[a+b] as f[a+b] or f[a] + f[b]). Also SetMultilinear and other variations can be added. 2. Some of the files in the NCAlgebra package are not packages. We will probably make them packages eventually. Also "Clear" statements should be added in more places than they are already. Eventually this should alleviate the problem on loading NCAlgebra twice. 3. More NCTest files for testing the code which has already been written. 4. Exploration of the program tex-mma (mathsource 0202-239) and its possible interactions with NCAlgebra.m 5. Converting some or all of the *.Extra files into supportable packages. 6. There is a routine LftPatternRule which should be merged with LeftPatternRule into the NCTools.m file. 7. The file NCBlockPartition may be rewritten. 8. SetUnitary may be rewritten so that it interact better with IsometryQ and CoIsometryQ. 9. We plan to add some simplify routines which are substantially better than those in version 0.1.