 ...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
nontrivial 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
§.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...2strategy.
 There are less conservative
ways of choosing knowns and unknowns under which
the derivation would be classed as a symmetrized
1strategy.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...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 userselected 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 pq.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.