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


 
def permutationsSgn[T]: List[T] => List[(Int,List[T])] = {
  case Nil => List((1,Nil))
  case xs => {
    for {
      (x, i) <- xs.zipWithIndex
      (sgn,ys) <- permutationsSgn(xs.take(i) ++ xs.drop(1 + i))
    } yield {
      val sgni = sgn * (2 * (i%2) - 1)
      (sgni, (x :: ys))
    }
  }
}
 
def det(m:List[List[Int]]) = {
  val summands =
    for {
      (sgn,sigma) <- permutationsSgn((0 to m.length - 1).toList).toList
    }
    yield {
      val factors =
        for (i <- 0 to (m.length - 1))
        yield m(i)(sigma(i))
      factors.toList.foldLeft(sgn)({case (x,y) => x * y})
    }
  summands.toList.foldLeft(0)({case (x,y) => x + y})
 