Macaulay2 » Documentation
Packages » Permanents :: Permanents
next | previous | forward | backward | up | index | toc

Permanents -- Computes the permanent of a square matrix.

Description

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

Caveat

Computationally intensive

See also

Author

Version

This documentation describes version 0.9 of Permanents.

Source code

The source code from which this documentation is derived is in the file Permanents.m2.

Exports

  • Functions and commands
    • glynn -- compute permanent using Glynn's formula
    • grenet -- Construct 2^n-1 by 2^n-1 matrix with determinant equal to the permanent of the input matrix
    • pminors -- Return ideal generated by pminors of a specified size
    • ryser -- compute permanent using Ryser's formula
  • Methods
    • glynn(Matrix) -- see glynn -- compute permanent using Glynn's formula
    • grenet(Matrix) -- see grenet -- Construct 2^n-1 by 2^n-1 matrix with determinant equal to the permanent of the input matrix
    • pminors(ZZ,Matrix) -- see pminors -- Return ideal generated by pminors of a specified size
    • ryser(Matrix) -- see ryser -- compute permanent using Ryser's formula

For the programmer

The object Permanents is a package.