Ordering Products

[Kay Schluehr]

Bernhard Holzmayer schrieb:
> Kay Schluehr wrote:
>
> >
> > Now lets drop the assumption that a and b commute. More general: let be
> > M a set of expressions and X a subset of M where each element of X
> > commutes with each element of M: how can a product with factors in M be
> > evaluated/simplified under the condition of additional information X?
> >
> > It would be interesting to examine some sorting algorithms on factor
> > lists with constrained item transpositions. Any suggestions?
> >
>
> Hello Kay,
>
> take this into account:
> Restrictions like commutativity, associative, distributive and flexibility
> laws don't belong neither to operands nor to operators themselves.
> Instead these are properties of fields (set of numbers with respect to a
> certain operation).
> For a famous example for a somewhat "alternative" behaviour look at the
> Octonions (discovered in 1843 by Graves and 1845 by Cayley), which are not
> associative with respect to addition and/or multiplication.
> (http://en.wikipedia.org/wiki/Octonions) or the Quarternions, which are
> non-commutative (http://en.wikipedia.org/wiki/Quaternion)
>
> Obviously, it's not correct to say: addition is associative, or, that
> multiplication is. With the same right, you could say, multiplication is
> not associative.

It was associative in the tiny example I presented. I did not mentioned
to discuss the evolving structure of the whole CAS here in detail which
would be better done in an own newsgroup once an early version is
released.

Maybe the setting of the original question should be made more precise:
associative, non-commutative multiplicative groups.

Handling non-associative algebras like Lie algebras is a completely
different matter and I'm not even sure which one is the best way to
represent operations in Python?

Maye this way?

>>> lie = Lie()       # create an arbitrary Lie algebra (lie is again a class )
>>> A,B = lie(),lie() # create two arbitrary elements of the Lie algebra
>>> lie[A,B]          # create the commutator of the lie algebra by overloading
lie[A,B]              # the __getitem__ method

>>> lie[A,B] == -lie[-A,B]
True

If one wants to enforce assertions like

>>> lie[r*A,B] == r*lie[A,B]
True

for certain elements r of some group acting on lie, one must refine
creation of lie in the initial assignment statement e.g.

>>> lie = Lie(V)

where V is some vectorspace and the elements of lie are homomorphisms
on V. V is created elsewhere. There are a lot of constraints induced by
all the objects dynamically coupled together.

> With the same reasoning, we can show that it's not easy to generalize
> sorting, commutation, association or distribution mechanisms.
>
> Maybe it would be a very fascinating goal to solve your algorithmic approach
> in such a limited environment like the Quarternions.

No CAS can represent infinitely many different representations of
quaternions. But it should not be to hard to deal with an algebra that
represents admissable operations on quaternions in an abstract fashion.

> A solution for this set of numbers, if achieved in a clean, mathematically
> abstract way, should hold for most other numbers/fields too, natural and
> real included.
>
> I guess that the approach might be this way:
> - define/describe the fields which shall be handled
> - define/describe the rules which shall be supported
> - find methods to reduce sequences of operations to simple binary or unary
> operations (tokens) - this may introduce brackets and stacking mechanisms
> - a weighing algorithm might be necessary to distinguish between plain
> numbers and place holders (variables)
> - application of the distributivity (as far as possible) might help to find
> a rather flat representation and a base for reordering according to the
> weights of the individual sub-expressions
>
> Nevertheless, there are lots of commercial programs which do such sort of
> symbolic mathematics, and which would badly fail when it would come to such
> awkward fields like Quarternions/Octonions.

If you take a look on Mathematica or Maple both programs seem to
interpret pure symbols as members of an associative and commutative
algebra:

   expand( (a+x)^2)  -> a^2 + 2ax + x^2

This works very fast and accurate but is mathematically too restricted
for me. For doing more advanced stuff one needs to do a lot of
programming in either language shipped with the CAS for creating new
packages. But then I ask myself: why not doing the programming labor in
Python and redesign and optimize the core modules of the CAS if
necessary? 

Kay