Permanents is a package of functions for computing the permanent of a square matrix.
Computing the permanent is believed to be computationally intractable. In Valiant's theory of algebraic complexity the permanent polynomial is complete for the class VNP. Even computing the permanent of 0-1 matrices is #P-complete. See Valiant, Leslie G. (1979), "The Complexity of Computing the Permanent," Theoretical Computer Science (Elsevier) 8 (2): 189-201.
The permanent of a $n\times n$ matrix $(x_{i,j})$ is defined in analogy to the determinant as $\sum_{\sigma \in S_n} \prod x_{i,\sigma(i)}$. There are two other formulas for the permanent polynomial, Ryser's formula and Glynn's formula, both of which have the asymptotically smaller formula size of $O(2^n n^2)$. This can be improved further to {$O(2^n n)$} arithmetic operations with the use of Gray codes, and we do so in this package. The connection between the two formulae and the possibility of others is discussed in Glynn, David G. (2013), "Permanent Formulae from the Veronesean." Designs Codes and Cryptography, 68(1-3) pp. 39-47.
It is conjectured that the permanent polynomial does not have a polynomial size formula. By Valiant's theory, a possible strategy for proving this is to show that the permanent of the $n\times n$ generic matrix $N$ cannot be the determinant of a $p(n) \times p(n)$ matrix $M$ with entries affine linear entries of the variables of $M$ where $p(n)$ is a polynomial. The best lower bound is quadratic, i.e. the permanent of the $nxn$ generic matrix is not the affine projection of the determinant of a $n^2/2xn^2/2$ matrix. See T. Mignon, N. Ressayre. "A Quadratic Bound for the Determinant and Permanent Problem." (2004).
The best known upper bound is $2^n-1$ due to Grenet. More specifically, Grenet constructs a $2^n-1x2^n-1$ matrix $M$ with entries $0,1,-1$ and individual variables of the $nxn$ generic matrix $N$, such that the determinant of $M$ is equal to the permanent of $N$. See B. Grenet, "An Upper Bound for the Permanent versus Determinant Problem" (2012).
Computationally intensive
This documentation describes version 0.9 of Permanents.
The source code from which this documentation is derived is in the file Permanents.m2.
The object Permanents is a package.