[Edu-sig] Algebra + Python

[Kirby Urner]

> Now to turn all of that into code. Now I know how I'm 
> teaching recursion
> this summer.

However, if you want to be brute force about it, and non-recursive,
you just need the n! permutations of column elements, picking one
element from each column as you go down the rows.  Each selection
nets you a product, and you still need to compute its sign (talked
about that just a post or two back).

I was relieved to find this, as I was looking at the selective 
(row,column) blocking with recursion, and not liking the looks of
that challenge.  The code is rather simple this other way:

    def det(self):
        """
        Return the determinant of a square matrix
        """
        perms = permutations(self.n)
        prods = []
        for perm in perms:
            prod = reduce(mul,[self.row(i)[int(perm[i])]
                          for i in range(len(perm))])
            prods.append(sign(perm)*prod)
        det = reduce(add,prods)
        return det

Notes:  self.n is just the dimension of the matrix (it's square,
so n is all you need).  permutations(self.n) returns the n! 
combinations, as we were discussing earlier, and you'll see 
sign(perm) as we were discussing earlier also.  That's it:
add the signed products (all n! of 'em) and you're done.

My source is 'Beginning Linear Algebra' by Seymour Lipschutz,
a Schaum's Outline Series (McGraw-Hill, 1997), Chapter 10, 
page 359.  This isn't a computer programming book or anything,
just a study aid I found in the math section of the local 
library.

How do I get the permutations?  Well, I'm sure there's lots
of ways, but I just set up a base-4 number (for a 4x4 matrix)
and count from 0000, 0001, 0002 -- except I eliminate any 
string with repeating digits, so 0123 is the first admitted.
Add 1 to that, base 4, and you get 0130, which isn't "legal"
either, but you get the idea (add up through 3210, crossing
out any with repeating digits, and you've got your 4!=24 
legal permutations).  I could refine this some (i.e. start
with 0123..(n-1) -- but it works well enough for my purposes
as is, so further optimizing is back burner for now.

How do I set up a base-4 number?  Well, I already had these
digit objects defined to add modulo n, and a Number object 
where you line up the digits objects with the bases you want 
(i.e. you can do mixed base numbers if you like).  That was 
all in ciphers.py already.  So I took advantage.  But I bet 
someone here could whip out a permutations generator that 
didn't rely on all this claptrap, would be efficient and 
short.  I just happened to have these tools handy, so I didn't 
spend a lot of time looking for another solution.

Kirby