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


import std.algorithm, std.range, std.traits, permutations2,
       permutations_by_swapping1;
 
auto prod(Range)(Range r) nothrow @safe @nogc {
    return reduce!q{a * b}(ForeachType!Range(1), r);
}
 
T permanent(T)(in T[][] a) nothrow @safe
in {
    assert(a.all!(row => row.length == a[0].length));
} body {
    auto r = a.length.iota;
    T tot = 0;
    foreach (const sigma; r.array.permutations)
        tot += r.map!(i => a[i][sigma[i]]).prod;
    return tot;
}
 
T determinant(T)(in T[][] a) nothrow
in {
    assert(a.all!(row => row.length == a[0].length));
} body {
    immutable n = a.length;
    auto r = n.iota;
    T tot = 0;
    //foreach (sigma, sign; n.spermutations) {
    foreach (const sigma_sign; n.spermutations) {
        const sigma = sigma_sign[0];
        immutable sign = sigma_sign[1];
        tot += sign * r.map!(i => a[i][sigma[i]]).prod;
    }
    return tot;
}
 
void main() {
    import std.stdio;
 
    foreach (/*immutable*/ const a; [[[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]]]) {
        writefln("[%([%(%2s, %)],\n %)]]", a);
        writefln("Permanent: %s, determinant: %s\n",
                 a.permanent, a.determinant);
    }
}