Determinant and permanent: Difference between revisions

 

The determinant is given by

while the permanent is given by

In both cases the sum is over the permutations <math>\sigma</math> 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 [[wp:Parity of a permutation|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.

 

* [[Permutations by swapping]]

<br><br>

 

=={{header|C}}==

C99 code. By no means efficient or reliable. If you need it for serious work, go find a serious library.

#include <stdlib.h>

#include <string.h>

 

return 0;

A method to calculate determinant that might actually be usable:

#include <stdlib.h>

#include <tgmath.h>

printf("det: %19f\n", det(x, N));

return 0;

 

=={{header|D}}==

This requires the modules from the [[Permutations#D|Permutations]] and [[Permutations_by_swapping#D|Permutations by swapping]] tasks.

{{trans|Python}}

permutations_by_swapping1;

 

a.permanent, a.determinant);

}

{{out}}

<pre>[[ 1, 2],

[20, 21, 22, 23, 24]]

Permanent: 6778800, determinant: 0</pre>

 

=={{header|EchoLisp}}==

This requires the 'list' library for '''(in-permutations n)''' and the 'matrix' library for the built-in '''(determinant M)'''.

(lib 'list)

(lib 'matrix)

(permanent M) → 6778800

 

 

=={{header|Fortran}}==

Please find the compilation and example run at the start of the comments in the f90 source. Thank you.

 

!-*- mode: compilation; default-directory: "/tmp/" -*-

!Compilation started at Sat May 18 23:25:42

 

end program f

 

=={{header|FunL}}==

From the task description:

 

def perm( m ) = sum( product(m(i, sigma(i)) | i <- 0:m.length()) | sigma <- (0:m.length()).permutations() )

 

 

Laplace expansion (recursive):

| m.length() == 1 and m(0).length() == 1 = m(0, 0)

| otherwise = sum( m(i, 0)*perm(m(0:i, 1:m.length()) + m(i+1:m.length(), 1:m.length())) | i <- 0:m.length() )

def det( m )

| m.length() == 1 and m(0).length() == 1 = m(0, 0)

 

Test using the first set of definitions (from task description):

( (1, 2),

(3, 4)),

 

for m <- matrices

 

{{out}}

((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

</pre>

 

=={{header|Go}}==

 

import (

fmt.Println(determinant(m2), permanent(m2))

fmt.Println(determinant(m3), permanent(m3))

{{out}}

<pre>

-360 900

</pre>

 

=={{header|J}}==

 

 

For example, given the matrix:

 

0 1 2 3 4

5 6 7 8 9

10 11 12 13 14

15 16 17 18 19

 

Its determinant is 0. When we use IEEE floating point, we only get an approximation of this result:

 

 

If we use exact (rational) arithmetic, we get a precise result:

 

 

 

 

 

=={{header|Java}}==

 

 

public class MatrixArithmetic {

System.out.println("Permanent: "+perm(a));

}

 

Note that the first input is the size of the matrix.

For example:

 

1 2

3 4

Determinant: 0.0

Permanent: 6778800.0

 

=={{header|jq}}==

{{Works with|jq|1.4}}

====Recursive definitions====

def except(i;j):

reduce del(.[i])[] as $row ([]; . + [$row | del(.[j]) ] );

| reduce range(0; length) as $i

(0; . + $m[0][$i] * ( $m | except(0;$i) | perm) )

'''Examples'''

[ [1, 2],

[3, 4]],

 

"Determinants: ", (matrices | det),

{{Out}}

Determinants:

-2

10

29556

====Determinant via LU Decomposition====

The following uses the jq infrastructure at [[LU decomposition]] to achieve an efficient implementation of det/0:

def det:

def product_diagonal:

| (.[0]|product_diagonal) as $l

| if $l == 0 then 0 else $l * (.[1]|product_diagonal) | tidy end ;

'''Examples'''

 

Using matrices/0 as defined above:

{{Output}}

$ /usr/local/bin/jq -M -n -f LU.rc

 

=={{header|Julia}}==

The determinant of a matrix <code>A</code> can be computed by the built-in function

 

{{trans|Python}}

The following function computes the permanent of a matrix A from the definition:

m, n = size(A)

if m != n; throw(ArgumentError("permanent is for square matrices only")); end

sum(σ -> prod(i -> A[i,σ[i]], 1:n), permutations(1:n))

 

Example output:

julia> det(A), perm(A)

 

=={{header|Lua}}==

_JT={}

function JT(dim)

matrix2:dump();

print("det:",matrix2:det(), "permanent:",matrix2:perm())

{{out}}

<pre>7 2 -2 4

2 0 -1

det: 18 permanent: 10</pre>

 

=={{header|Maple}}==

 

with(LinearAlgebra):

 

Determinant(M);

Output:

<pre> -360

900</pre>

 

Determinant is a built in function Det

With[{v = Array[x, Length[m]]},

Coefficient[Times @@ (m.v), Times @@ v]

 

=={{header|Maxima}}==

 

determinant(a);

 

permanent(a);

 

=={{header|Nim}}==

{{trans|Python}}

Using the permutationsswap module from [[Permutations by swapping#Nim|Permutations by swapping]]:

 

type Matrix[M,N: static[int]] = array[M, array[N, float]]

echo "perm: ", a.perm, " det: ", a.det

echo "perm: ", b.perm, " det: ", b.det

Output:

<pre>perm: 10.0 det: -2.0

perm: 6778800.0 det: 0.0</pre>

 

 

 

 

 

 

 

 

 

}

 

 

 

 

 

 

=={{header|PowerShell}}==

function det-perm ($array) {

if($array) {

det-perm @(@(2,5),@(4,3))

det-perm @(@(4,4),@(2,2))

<b>Output:</b>

<pre>

Using the module file spermutations.py from [[Permutations by swapping#Python|Permutations by swapping]]. The algorithm for the determinant is a more literal translation of the expression in the task description and the Wikipedia reference.

 

from operator import mul

from math import fsum

print('')

pp(a)

 

;Sample output:

 

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.

 

=={{header|Racket}}==

#lang racket

(require math)

(for/product ([i n] [σi σ])

(matrix-ref M i σi))))

 

=={{header|REXX}}==

* Test the two functions determinant and permanent

* using the matrix specifications shown for other languages

Say ' permanent='right(permanent(as),7)

Say copies('-',50)

 

* determinant.rex

* compute the determinant of the given square matrix

Say 'invalid number of elements:' nn 'is not a square.'

Exit

 

* permanent.rex

* compute the permanent of a matrix

Say 'invalid number of elements:' nn 'is not a square.'

Exit

 

Output:

permanent=6778800

--------------------------------------------------</pre>

 

=={{header|Ruby}}==

Matrix in the standard library provides a method for the determinant, but not for the permanent.

 

class Matrix

puts "determinant:\t #{m.determinant}", "permanent:\t #{m.permanent}"

puts

{{Output}}

<pre>

determinant: 0

permanent: 6778800

</pre>

 

{{works with|OpenAxiom}}

{{works with|Axiom}}

 

+2 9 4+

 

(3) 900

 

[http://fricas.github.io/api/Matrix.html?highlight=matrix Domain:Matrix(R)]

 

=={{header|Tcl}}==

{{tcllib|math::linearalgebra}}

{{tcllib|struct::list}}

package require struct::list

 

}

return [::tcl::mathop::+ {*}$sum]

Demonstrating with a sample matrix:

{1 2 3 4}

{4 5 6 7}

}

puts [::math::linearalgebra::det $mat]

{{out}}

<pre>

1.1315223609263888e-29

29556

</pre>