Determinant and permanent: Difference between revisions
(→{{header|PARI/GP}}: Add Python.) |
(→{{header|Python}}: Use fsum instead of sum) |
||
Line 50: | Line 50: | ||
<lang python>from itertools import permutations |
<lang python>from itertools import permutations |
||
from operator import mul |
from operator import mul |
||
from math import fsum |
|||
from spermutations import spermutations |
from spermutations import spermutations |
||
Line 59: | Line 60: | ||
r = range(n); |
r = range(n); |
||
s = list(permutations(r)) |
s = list(permutations(r)) |
||
return |
return fsum(prod(a[i][sigma[i]] for i in r) for sigma in s) |
||
def det(a): |
def det(a): |
||
Line 65: | Line 66: | ||
r = range(n); |
r = range(n); |
||
s = list(spermutations(n)) |
s = list(spermutations(n)) |
||
return |
return fsum(sign*prod(a[i][sigma[i]] for i in r) for sigma, sign in s) |
||
Revision as of 09:47, 24 July 2012
Given a matrix, return the determinant and the permanent of the matrix.
The determinant is given by
while the permanent is given by
In both cases the sum is over the permutations of the permutations of 1, 2, ..., n. (A permutation's sign is 1 if there are an even number of inversions and -1 otherwise; see parity of a permutation.)
More efficient algorithms for the determinant are known: LU decomposition, see for example wp:LU decomposition#Computing the determinant. Efficient methods for calculating the permanent are not known.
- Cf.
J
Given the example matrix:
<lang J> i. 5 5
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24</lang>
It's determinant is 0. When we use IEEE floating point, we only get an approximation of this result:
<lang J> -/ .* i. 5 5 _1.30277e_44</lang>
If we use exact (rational) arithmetic, we get a precise result:
<lang J> -/ .* i. 5 5x 0</lang>
The permanent does not have this problem in this example (the matrix contains no negative values and permanent does not use subtraction):
<lang J> +/ .* i. 5 5 6778800</lang>
PARI/GP
The determinant is built in: <lang parigp>matdet(M)</lang> and the permanent can be defined as <lang parigp>matperm(M)=my(n=#M,t);sum(i=1,n!,t=numtoperm(n,i);prod(j=1,n,M[j,t[j]]))</lang>
Python
Using the module file spermutations.py from Permutations by swapping. The algorithm for the determinant is a more literal translation of the expression in the task description and the Wikipedia reference.
<lang python>from itertools import permutations from operator import mul from math import fsum from spermutations import spermutations
def prod(lst):
return reduce(mul, lst, 1)
def perm(a):
n = len(a); r = range(n); s = list(permutations(r)) return fsum(prod(a[i][sigma[i]] for i in r) for sigma in s)
def det(a):
n = len(a); r = range(n); s = list(spermutations(n)) return fsum(sign*prod(a[i][sigma[i]] for i in r) for sigma, sign in s)
if __name__ == '__main__':
from pprint import pprint as pp
for a in ( [ [1, 2], [3, 4]],
[ [1, 2, 3, 4], [4, 5, 6, 7], [7, 8, 9, 10], [10, 11, 12, 13]],
[ [ 0, 1, 2, 3, 4], [ 5, 6, 7, 8, 9], [10, 11, 12, 13, 14], [15, 16, 17, 18, 19], [20, 21, 22, 23, 24]], ): print() pp(a) print('Perm: %s Det: %s' % (perm(a), det(a)))</lang>
- Sample output
[[1, 2], [3, 4]] Perm: 10 Det: -2 [[1, 2, 3, 4], [4, 5, 6, 7], [7, 8, 9, 10], [10, 11, 12, 13]] Perm: 29556 Det: 0 [[0, 1, 2, 3, 4], [5, 6, 7, 8, 9], [10, 11, 12, 13, 14], [15, 16, 17, 18, 19], [20, 21, 22, 23, 24]] Perm: 6778800 Det: 0
The second matrix above is that used in the Tcl example. The third matrix is from the J language example. Note that the determinant seems to be 'exact' using this method of calculation without needing to resort to other than Pythons default numbers.
Tcl
The determinant is provided by the linear algebra package in Tcllib. The permanent (being somewhat less common) requires definition, but is easily described:
<lang tcl>package require math::linearalgebra package require struct::list
proc permanent {matrix} {
for {set plist {};set i 0} {$i<[llength $matrix]} {incr i} {
lappend plist $i
} foreach p [::struct::list permutations $plist] {
foreach i $plist j $p { lappend prod [lindex $matrix $i $j] } lappend sum [::tcl::mathop::* {*}$prod[set prod {}]]
} return [::tcl::mathop::+ {*}$sum]
}</lang> Demonstrating with a sample matrix: <lang tcl>set mat {
{1 2 3 4} {4 5 6 7} {7 8 9 10} {10 11 12 13}
} puts [::math::linearalgebra::det $mat] puts [permanent $mat]</lang>
- Output:
1.1315223609263888e-29 29556