next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Permanents :: Permanents

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 intractible. 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×n matrix (xi,j) is defined in analogy to the determinant as σ∈Sn ∏xi,σ(i). There are two other formulas for the permanent polynomial, Ryser’s formula and Glynn’s formula, both of which have the assymptotically smaller formula size of O(2n n2). This can be improved further to O(2n 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×n generic matrix N cannot be the determinant of a p(n) ×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 quadartic, i.e. the permanent of the nxn generic matrix is not the affine projection of the determinant of a n2/2xn2/2 matrix. See T. Mignon, N. Ressayre. "A Quadratic Bound for the Determinant and Permanent Problem." (2004).

The best known upper bound is 2n-1 due to Grenet. More specifically, Grenet constructs a 2n-1x2n-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 permament 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 permament using Ryser's formula