For a given matrix, return the determinant and the permanent of the matrix.

The determinant is given by

 



det
(
A
)
=

∑

σ


sgn
⁡
(
σ
)

∏

i
=
1


n



M

i
,

σ

i






{\displaystyle \det(A)=\sum _{\sigma }\operatorname {sgn}(\sigma )\prod _{i=1}^{n}M_{i,\sigma _{i}}}


while the permanent is given by

 



perm
⁡
(
A
)
=

∑

σ



∏

i
=
1


n



M

i
,

σ

i






{\displaystyle \operatorname {perm} (A)=\sum _{\sigma }\prod _{i=1}^{n}M_{i,\sigma _{i}}}


In both cases the sum is over the permutations 



σ


{\displaystyle \sigma }

 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.



Related task

 Permutations by swapping


with javascript_semantics
function minor(sequence a, integer x, integer y)
    integer l = length(a)-1
    sequence result = repeat(repeat(0,l),l)
    for i=1 to l do
        for j=1 to l do
            result[i][j] = a[i+(i>=x)][j+(j>=y)]
        end for
    end for
    return result
end function
 
function det(sequence a)
    if length(a)=1 then
        return a[1][1]
    end if
    integer res = 0,
            sgn = 1
    for i=1 to length(a) do
        res += sgn*a[1][i]*det(minor(a,1,i))
        sgn *= -1
    end for
    return res
end function
 
function perm(sequence a)
    if length(a)=1 then
        return a[1][1]
    end if
    integer res = 0
    for i=1 to length(a) do
        res += a[1][i]*perm(minor(a,1,i))
    end for
    return res
end function
 
constant tests = {
{{1,  2},
 {3,  4}},
--Determinant: -2, permanent: 10
{{2, 9, 4},
 {7, 5, 3},
 {6, 1, 8}},
--Determinant: -360, permanent: 900
{{ 1,  2,  3,  4},
 { 4,  5,  6,  7},
 { 7,  8,  9, 10},
 {10, 11, 12, 13}},
--Determinant: 0, permanent: 29556
{{ 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}},
--Determinant: 0, permanent: 6778800
{{5}},
--Determinant: 5, permanent: 5 
{{1,0,0},
 {0,1,0},
 {0,0,1}},
--Determinant: 1, permanent: 1
{{0,0,1},
 {0,1,0},
 {1,0,0}},
--Determinant: -1, Permanent: 1
{{4,3},
 {2,5}},
--Determinant: 14, Permanent: 26
{{2,5},
 {4,3}},
--Determinant: -14, Permanent: 26
{{4,4},
 {2,2}},
--Determinant: 0, Permanent: 16
{{7,    2,      -2,     4},
 {4,    4,      1,      7},
 {11,   -8,     9,      10},
 {10,   5,      12,     13}},
--det:  -4319   permanent:      10723
 
{{-2,   2,      -3},
 {-1,   1,      3},
 {2 ,   0,      -1}}
--det:  18      permanent:      10
}
for i=1 to length(tests) do
    sequence ti = tests[i]
    ?{det(ti),perm(ti)}
end for
