Philip Hall Basis Constructor 7.III.2001

INFORMATION

FILES
phbc.m      - main file
orderpos.m  - function file, see description within the file.

DESCRIPTION
This program takes two inputs.
m: the number of generators X1 ... Xm
k: the degree of the 'deepest' Lie bracket to be generated.
   A system is said to be nilpotent of order k, if all the
   Lie brackets of length greater than k are zero.
   
   The length of a Lie bracket is the number of generators
   involved in its expansion.  We say that a Lie bracket is
   'deeper' than another if its length is greater.  The
   length of a Lie product can be recursively defined as:
      
   l(Xi)=1; i=1,..., m.
   l([A,B])=l(A)+l(B)  where A, B are Lie products themselves.   
   
A Philip Hall basis is an ordered set of Lie brackets or products
denoted by B={B1 B2 ... Bi ...} satisfying:

1. Xi belong to B, i=1,..., m
2. If l(Bi)<l(Bj) then Bi<Bj, i.e. Bi is positioned before Bj in B.
3. [Bi,Bj] belongs to B if and only if
   a. Bi, Bj belong to B and Bi < Bj.
   b. Either -> Bj=Xk for some k.  
          or -> Bj=[Bp, Bq] with Bp, Bq belonging to B and Bp <= Bi.
          
The procedure to build B, in practice only needs condition 3 to be
checked, since the 1, must be assumed true for all initial generators
and 2 is satisfied by performing the multiplications in an orderly 
manner, as briefly described below.

This description was adapted from the book:
A Mathematical Introduction to Robotic Manipulation.
Richard M. Murray, Zexiang Li, S. Shankar Sastry. CRC Press 1994.
pp. 344-345.  The reader is referred to references therein for 
further details.

SOME DETAILS OF THHIS IMPLEMENTATION

The bracketing procedure can be though of as a breeding process.
We must distinguish between to groups per "breeding" iteration,
the offspring and the parents.

On the first iteration the generators are treated as offspring
and are crossed between them.  On the second iteration,
the offspring are called parents, and their offspring are the
new offspring.  Parents are crossed only with their offspring
and not between them, since this happened in the previous iteration.
Offspring are crossed between them.  All the newborns are now
called offspring and the ones that were offspring are now in
the group of parents.  And life goes on...

Offspring cross between each other in the following way.

  A B C
  \ |  \ \
   AB  AC BC  Note that the BC, CA and BA are not valid offspring
              since they violate rule 2, assuming the order is
              A, B, C.

  Now we have two groups parents are {A, B, C} and offspring
  {AB, AC, BC}. Offspring will reproduce again as described above.
  but also they'll be crossed with their parents, all parents with
  all offspring.  In the following way:
  A+AB A+AC A+BC
  B+AB B+AC B+BC
  C+AB C+AC C+BC
  Some off them must be eliminated by rule 3, namely A+BC.

The program actually uses numbers to identify all the generators, so
X1 is simply called 1, X2 is 2 and so on.  And [X1,X2] is written
as [1.2].  In the vector x.

The program can be modified to use ',' instead of '.', simply by
replacing every occurrence of '.' by ','.  I use '.' merely for
aesthetical reasons, however I agree there is no accounting 
for taste. ;)

Feel free to use/modify/hack this program.  If you find any bug,
I'd appreciate you let me know.

Miguel Torres-Torriti
Systems & Control Group
McGill University
migueltt@cim.mcgill.ca