[Edu-sig] Algebra + Python

[Kirby Urner]

> and this for a 4 row matrix:
> 
> [[0 1 2 3] [0 1 3 2] [0 2 3 1] [0 2 1 3] [0 3 1 2] [0 3 2 1] 
> [1 2 3 0] 
> [1 2 0 3] [1 3 0 2] [1 3 2 0] [1 0 2 3] [1 0 3 2] [2 3 0 1] [2 3 1 0] 
> [2 0 1 3] [2 0 3 1] [2 1 3 0] [2 1 0 3] [3 0 1 2] [3 0 2 1] [3 1 2 0] 
> [3 1 0 2] [3 2 0 1] [3 2 1 0]]
> 
> Is that the same order you get with your algorithm.

I get those same permutations, although not in the same
order.  Mine are in numeric order, as if the above were
4-digit numbers.

> and for the 4 row matrix something very similar:
> 
> [1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1]
> 
> Am I wrong in this step? using this this sequence of signs?

Below I'm pairing my 24 permutations with their corresponding
signs...

 >>> zip(permutations(4),map(sign,permutations(4)))
 [('0123', 1), ('0132', -1), ('0213', -1), ('0231', 1), 
  ('0312', 1), ('0321', -1), ('1023', -1), ('1032', 1), 
  ('1203', 1), ('1230', -1), ('1302', -1), ('1320', 1), 
  ('2013', 1), ('2031', -1), ('2103', -1), ('2130', 1), 
  ('2301', 1), ('2310', -1), ('3012', -1), ('3021', 1), 
  ('3102', 1), ('3120', -1), ('3201', -1), ('3210', 1)]

I see at least one discrepancy -- the last entry.  I've got
3210 signed 1, but you have it signed -1.

The way I get the sign is to ask how many of the digits
subsequent to each digit are lower, i.e. out of order.
Another way of putting it:  for all i before j, how many
times is i>j.  Take 3210:  3 comes before 2,1,0 and is
greater than all of them, so that's 3 occurances.  Then 
2 is greater than both 1 and 0, so that's two more for 5, 
and then 1 is greater than 0, so one more for 6.  If 
the count is even, sign is positive or 1, if count is 
odd, sign is negative.

Here's my code for sign, given a permutation is a string
of the form '3210' (this algorithm will stop working with
double-digit matrix dimensions -- would need to be modified):

 def sign(perm):
     """
     return the sign of a permutation
     = -1 if odd number of transpositions
     =  1 if even
     """
     trans = 0
     for k in perm[:-1]:
         for j in perm[perm.index(k)+1:]:
             if int(k)>int(j):
                 trans += 1
     if trans%2==0: return 1  
     else: return -1

> The funny thing is that it works nicely for matrices (2x2) and
> (3x3).
> 
> Daniel