...theory

This work was sponsored by the Air Force Office for Scientific Research and by the National Science Foundation.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...Helton

Department of Mathematics, University of California, San Diego, California

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...Stankus

Department of Mathematics, University of California, San Diego, California

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...polynomial

Informally, a noncommutative polynomial in the indeterminates 4#4 over the field K is a polynomial, but one removes the assumption that the indeterminates commute (e.g., 5#5 is not the zero polynomial). Formally, a noncommutative polynomial in the indeterminates 4#4 over the field K is a formal sum of elements of formal products c t where 6#6 and t is a member of the free semigroup generated by 7#7.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...run.

See Appendix § for an example of this.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...ncalg@ucsd.edu.

The C++ code compiles with the free compiler g++ (version 2.6.3 or higher) from the Free Software Foundation. The C++ code is about 15,000 lines and compiles to a binary of about 1.5 megabytes on a Sun Workstation. We have compiled it with g++ version 2.6.3 on a Sun Workstation running Sun OS 4.1.3 and with g++ version 2.7.0 on a HP workstation. The minimal Mathematica code needed is about 0.30 megabytes, while the Mathematica code for NCAlgebra is about 0.75 megabytes.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...algebras

One can often consider problems which do not seem to involve a single algebra. An example is to consider computations involving 10#10, 11#11, 12#12 and 9#9 matrices. Even though the union of these four sets of matrices is not an algebra, one can create an algebra in which one can embed these four algebras. Without going into the details, this can be done using a path algebra where R13#13 and R14#14 are vertices and, for example, an 11#11 matrix is a path from the R13#13 vertex to the R14#14 vertex, c.f., [FaFeGr].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...compositions

If p and k are polynomials and k is a polynomial in one unknowns (say y), then we say that polynomial p is a composition of k and q if we can obtain p by replacing every occurrence of y with q, that is, 90#90. If p is a composition of k and q, then the composition is trivial if and only if k has the form 91#91 for some scalars c and d. The decomposition is called maximal if k has no non-trivial decomposition.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...first.

The precise algebraic meaning of 112#112 is given in §. For example, one must assume that the there is a notion of conjugation for the coefficients of q. The meaning of this notation will be clear from context whenever it is used in this paper. See also §.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...2-strategy.

There are less conservative ways of choosing knowns and unknowns under which the derivation would be classed as a symmetrized 1-strategy.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...subset

A canonical choice of a large subset would be a Gröbner Basis or a subset Gröbner Basis which could be computed in a reasonable amount of time.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...commands

This is available for free. Send electronic mail to ncalg@osiris.ucsd.edu for more information.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...subsets

small rather than minimal because finding minimal generating subsets is unsolvable by Lemma 12.2.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...Basis

G is a reduced Gröbner Basis if G is a Gröbner Basis and g is irreducible with respect to 114#114 for every 115#115.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...unknowns.

69#69 consists of equations which are selected or created by the user. In the first run of an NCProcess command, the set 69#69 is empty. More details about selecting equations are found in §. See also item O3 below.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...user.

In the first run of an NCProcess command, there are no equations which are selected or created by the user. A user-selected equation is a polynomial equation which the user has selected. When an equation is selected, the algorithms described in § treat these equations as ``digested''. The selected equation is now 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. These equations of this item (O3) are the equations of 69#69 from item I3 above. More details about selecting equations are found in §.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...matrices

This session will also classify bounded linear transformations x. This is slightly less trivial, because we are not necessarily working in a finite dimensional space.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...equations

Even though this article is not intended as a user manual for the software which we have developed, it is important to note that there is often very little typing required in order to input collections of equations. For example, one does not type in the 5 equations of (§), but types in the 127#127 block matrix and tells the computer that it is an isometry and that U is unitary.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...above

More precisely, the spreadsheet displays polynomial equations. We shall continue to blur the distinction between the polynomial equation p=q and the polynomial p-q.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...72#72.

158#158 may not be a subset of 72#72. See § for the related discussion.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...sets

Either the set 76#76 is infinite, equals 155#155 or equals the empty set.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...polynomials.

NCProcess2 cannot guarantee this property, since the ideal membership problem is known to be unsolvable ([TMora]).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...equation

This polynomial is not written as a rule since it has a collected form as described in §. This collect form can be used to assist a person in finding decompositions (§). This will be described in §.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...notice

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...again

There is limit of 2 iterations.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...produced

It is not hard to see that NCProcess2 would not have an effect, since the set of equations found on the previous spreadsheet can be easily seen to be minimal. We include the run here for pedagogical reasons.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...necessary

If NCProcess used a symmetric version of Small Basis By Category (see §), then either 224#224 or 225#225 would have appeared on the spreadsheet, but not both. Therefore we would not have to perform this additional step. A symmetric version of the Small Basis By Category option is being written at the time of the writing of this paper. This option will be available in a future version of the software.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...with

It is important the the equation 226#226 appears after the other equations for this run.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...spreadsheet.

The polynomial L p R will not appear on the spreadsheet, since its normal form with respect to p is zero.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...iterations.

In addition, we bound iterations using the options DegreeCap140#1406,DegreeSumCap140#1409 which limit the degrees of polynomials occurring as the GBA runs. See §.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...a<b<c)

This notation is a modification of the notation found in [CLS].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...spreadsheet

If one does not find all of the necessary conditions that one needs at this point, it will, of course, become clear when trying to prove the converse, because one will not be able to continue with the proof after a certain point. Attempting to prove the converse when one has found most of the necessary conditions will help in pointing out the additional necessary conditions which are needed.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...rule

Recall that 462#462 and x are two different indeterminates and that one needs to explicitly add the equations 463#463 and 464#464

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...can

in every case

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...consists

See §.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...categories

See §.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...argument.

In fact even if one realized from the beginning of the computation that a and c have no common eigenvalues, there is no way to express this hypothesis using polynomial equaions. In fact, a complete analytic argument which showed that b = 0 would consist of an algebraic derivation of the identity ab = bc followed by the use of the hypothesis that a and c have no common eigenvalues. One would not in general know in advance that ab = bc and so it would be premature to add ``b=0'' to the collection of polynomial equations at the beginning of the computation.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.