On 7 May 01, at 12:01, edu-sig-request@python.org wrote:
A simple way to compute the determinant is to add the signed products of all permutations of matrix elements, choosing one from each row (a total of row! possibilities). ciphers.py is in charge of returning a list of all those possibilities
Does that work for matrices 4x4 ? I ask because it didn't work for me. I have an algorithm that gives me the permutation in this order for a 3 row matrix: [[0 1 2] [0 2 1] [1 2 0] [1 0 2] [2 0 1] [2 1 0]] 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. For the 3 row matrix I change signs like this (using the same order as above): [1 -1 1 -1 1 -1] 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? The funny thing is that it works nicely for matrices (2x2) and (3x3). Daniel
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
participants (2)
-
Daniel Ajoy -
Kirby Urner