Determinant and permanent: Difference between revisions

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|360 Assembly}}==

and two ASSIST macros (XDECO,XPRNT) to keep it as short as possible.

It works on OS/360 family (MVS,z/OS), on DOS/360 family (z/VSE) use GETVIS,FREEVIS instead of GETMAIN,FREEMAIN.

MATARI START

STM R14,R12,12(R13) save caller's registers

Q DS F sub matrix q((n-1)*(n-1)+1)

YREGS

{{out}}

<pre>

permanent= 900

</pre>

 

=={{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|Forth}}==

{{libheader|Forth Scientific Library}}

{{works with|gforth|0.7.9_20170427}}

Requiring a permute.fs file from the [[Permutations_by_swapping#Forth|Permutations by swapping]] task.

S" fsl/dynmem.seq" REQUIRED

[UNDEFINED] defines [IF] SYNONYM defines IS [THEN]

m3{{ lmat lufact

lmat det F. 3 m3{{ permanent F. CR

 

=={{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}}==

===Implementation===

This implements a naive algorithm for each that follows from the definitions. It imports the permute packge from the [[Permutations_by_swapping#Go|Permutations by swapping]] task.

 

import (

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

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

{{out}}

<pre>

</pre>

===Ryser permanent===

 

import "fmt"

}

return

{{out}}

<pre>

===Library determinant===

'''go.matrix:'''

 

import (

{7, 5, 3},

{6, 1, 8}}).Det())

{{out}}

<pre>

-360

</pre>

 

import (

"fmt"

 

)

 

func main() {

1, 2,

3, 4})))

2, 9, 4,

7, 5, 3,

6, 1, 8})))

{{out}}

<pre>

 

=={{header|Haskell}}==

sPermutations = flip zip (cycle [1, -1]) . foldl aux [[]]

where

, [[2, 5], [4, 3]]

, [[4, 4], [2, 2]]

{{Out}}

<pre>Matrix:

Permanent:

16</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:

 

 

Meanwhile, the permanent does not have this problem in this example (the matrix contains no negative values and permanent does not use subtraction):

 

 

As an aside, note also that for specific verbs (like <code>-/ .*</code>) J uses an algorithm which is more efficient than the brute force approach implied by the [http://www.jsoftware.com/help/dictionary/d300.htm definition of <code> .</code>]. (In general, where there are common, useful, concise definitions where special code can improve resource use by more than a factor of 2, the implementors of J try to make sure that that special code gets used for those definitions.)

=={{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|Kotlin}}==

 

typealias Matrix = Array<DoubleArray>

println(" permanent = ${permanent(m)}\n")

}

 

{{out}}

permanent = 29556.0

</pre>

 

=={{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: 29556.0 det: 0.0

perm: 6778800.0 det: 0.0</pre>

 

=={{header|PARI/GP}}==

The determinant is built in:

and the permanent can be defined as

For better performance, here's a version using Ryser's formula:

{

my(n=matsize(M)[1],innerSums=vectorv(n));

(-1)^hammingweight(gray)*factorback(innerSums)

)*(-1)^n;

 

{{works with|PARI/GP|2.10.0+}}

As of version 2.10, the matrix permanent is built in:

 

 

}

 

 

 

 

 

=={{header|Phix}}==

{{trans|Java}}

{{out}}

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

permanent: 6778800

</pre>

=={{header|Sidef}}==

The `determinant` method is provided by the Array class.

{{trans|Ruby}}

method permanent {

var r = @^self.len

[m1, m2, m3].each { |m|

say "determinant:\t #{m.determinant}\npermanent:\t #{m.permanent}\n"

{{out}}

<pre>determinant: -2

 

=={{header|Simula}}==

BEGIN

 

! PERMANENT: 6778800.0 ;

 

Input:

<pre>

{{works with|OpenAxiom}}

{{works with|Axiom}}

 

+2 9 4+

 

(3) 900

 

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

For x=-1, the main function '''sumrec(a,x)''' computes the determinant of a by developing the determinant along the first column. For x=1, one gets the permanent.

 

if (i < 1 | i > n) {

return(1::n)

}

return(s)

 

Example:

 

: a

[symmetric]

 

: sumrec(a,1)

 

=={{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>

 

=={{header|zkl}}==

fcn perm(A){ // should verify A is square

numRows:=A.rows;

println(A.format());

println("Permanent: %.2f, determinant: %.2f".fmt(perm(A),A.det()));

B:=GSL.Matrix(4,4).set(1,2,3,4, 4,5,6,7, 7,8,9,10, 10,11,12,13);

C:=GSL.Matrix(5,5).set( 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);

{{out}}

<pre>