This is Permanents.info, produced by Macaulay2, version 1.25.11

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

  * permanents (Macaulay2Doc) -- ideal generated by square
    permanents of a matrix
  * determinant (Macaulay2Doc) -- determinant of a matrix

Author
======

  * Tair Akhmejanov (see http://www.math.cornell.edu/~takhmejanov )
    <ta328@cornell.edu>

Version
=======

This documentation describes version 0.9 of Permanents, released July 11, 2014.

Citation
========

If you have used this package in your research, please cite it as follows:

+----------------------------------------------------------------------------+
|@misc{PermanentsSource,                                                     |
|  title = {{Permanents: permanents of a matrix. Version~0.9}},              |
|  author = {Tair Akhmejanov},                                               |
|  howpublished = {A \emph{Macaulay2} package available at                   |
|    \url{https://github.com/Macaulay2/M2/tree/stable/M2/Macaulay2/packages}}|
|}                                                                           |
|                                                                            |
+----------------------------------------------------------------------------+

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 (Macaulay2Doc),
defined in Permanents.m2.

-------------------------------------------------------------------------------

The source of this document is in Permanents.m2:400:0.

glynn -- compute permanent using Glynn's formula
************************************************

  * Usage:
        F = glynn M
  * Inputs:
      * M, a matrix (Macaulay2Doc), a square matrix in any
        commutative ring
  * Outputs:
      * F, a ring element (Macaulay2Doc), the permanent of M

Description
===========

Uses Glynn's formula (see Glynn, David G. (2010), "The permanent of a square
matrix", European Journal of Combinatorics 31 (7): 1887–1891,
doi:10.1016/j.ejc.2010.01.010).

Let $M=(m_{i,j})$ be an nxn matrix. Then
$perm(M)=\sum_{\delta}\prod_{k=1}^n(\delta_k) \prod_{i=1}^n\sum_{j=1}^n
\delta_j m_{i,j}$ where the outer summation is over $\delta\in \{ -1,+1\}^n$
with $\delta_1=1$.

For example, for the 3x3 generic matrix Glynn’s formula gives $2^2 perm(M) =(a
+ b + c)(d + e + f)(g + h + i) − (a − b + c)(d − e + f)(g − h + i) −(a + b −
c)(d + e − f)(g + h − i) + (a − b − c)(d − e − f)(g − h − i)$.

Here is the permanent of a 3x3 generic matrix of variables.

+--------------------------------------------------+
|i1 : R = QQ[vars(0..8)]                           |
|                                                  |
|o1 = R                                            |
|                                                  |
|o1 : PolynomialRing                               |
+--------------------------------------------------+
|i2 : M = genericMatrix(R,a,3,3)                   |
|                                                  |
|o2 = | a d g |                                    |
|     | b e h |                                    |
|     | c f i |                                    |
|                                                  |
|             3      3                             |
|o2 : Matrix R  <-- R                              |
+--------------------------------------------------+
|i3 : glynn M                                      |
|                                                  |
|o3 = c*e*g + b*f*g + c*d*h + a*f*h + b*d*i + a*e*i|
|                                                  |
|o3 : R                                            |
+--------------------------------------------------+

Here is the permanent of a 4x4 generic matrix of variables.

+-----------------------------------------------------------------------------+
|i4 : R = QQ[vars(0..15)]                                                     |
|                                                                             |
|o4 = R                                                                       |
|                                                                             |
|o4 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i5 : M = genericMatrix(R,a,4,4)                                              |
|                                                                             |
|o5 = | a e i m |                                                             |
|     | b f j n |                                                             |
|     | c g k o |                                                             |
|     | d h l p |                                                             |
|                                                                             |
|             4      4                                                        |
|o5 : Matrix R  <-- R                                                         |
+-----------------------------------------------------------------------------+
|i6 : glynn M                                                                 |
|                                                                             |
|o6 = d*g*j*m + c*h*j*m + d*f*k*m + b*h*k*m + c*f*l*m + b*g*l*m + d*g*i*n +   |
|     ------------------------------------------------------------------------|
|     c*h*i*n + d*e*k*n + a*h*k*n + c*e*l*n + a*g*l*n + d*f*i*o + b*h*i*o +   |
|     ------------------------------------------------------------------------|
|     d*e*j*o + a*h*j*o + b*e*l*o + a*f*l*o + c*f*i*p + b*g*i*p + c*e*j*p +   |
|     ------------------------------------------------------------------------|
|     a*g*j*p + b*e*k*p + a*f*k*p                                             |
|                                                                             |
|o6 : R                                                                       |
+-----------------------------------------------------------------------------+

Here is the permanent of a 3x3 matrix of integers.

+--------------------------------------+
|i7 : M=matrix{{1,2,3},{4,5,6},{7,8,9}}|
|                                      |
|o7 = | 1 2 3 |                        |
|     | 4 5 6 |                        |
|     | 7 8 9 |                        |
|                                      |
|              3       3               |
|o7 : Matrix ZZ  <-- ZZ                |
+--------------------------------------+
|i8 : glynn M                          |
|                                      |
|o8 = 450                              |
+--------------------------------------+

Caveat
======

Works in characteristic not equal to 2 because need to divide by $2^{n-1}$.
Computationally intensive for moderate size matrices.

See also
========

  * permanents (Macaulay2Doc) -- ideal generated by square
    permanents of a matrix

Ways to use glynn:
==================

  * "glynn(Matrix)"

For the programmer
==================

The object glynn, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in Permanents.m2:489:0.

grenet -- Construct 2^n-1 by 2^n-1 matrix with determinant equal to the permanent of the input matrix
*****************************************************************************************************

  * Usage:
        F = grenet M
  * Inputs:
      * M, a matrix (Macaulay2Doc), a square matrix in any
        commutative ring
  * Outputs:
      * N, a matrix (Macaulay2Doc), a $2^n-1\times 2^n-1$ matrix
        N with determinant equal to the permanent of M

Description
===========

Uses Grenet's combinatorial construction (see B. Grenet: An Upper Bound for the
Permanent versus Determinant Problem (2012)).

Here is the 7x7 matrix constructed from the 3x3 generic matrix of variables.

+--------------------------------------------------+
|i1 : R = QQ[vars(0..8)]                           |
|                                                  |
|o1 = R                                            |
|                                                  |
|o1 : PolynomialRing                               |
+--------------------------------------------------+
|i2 : M = genericMatrix(R,a,3,3)                   |
|                                                  |
|o2 = | a d g |                                    |
|     | b e h |                                    |
|     | c f i |                                    |
|                                                  |
|             3      3                             |
|o2 : Matrix R  <-- R                              |
+--------------------------------------------------+
|i3 : N = grenet M                                 |
|                                                  |
|o3 = | 1 0 e 0 h 0 0 |                            |
|     | 0 1 b 0 0 h 0 |                            |
|     | 0 0 1 0 0 0 i |                            |
|     | 0 0 0 1 b e 0 |                            |
|     | 0 0 0 0 1 0 f |                            |
|     | 0 0 0 0 0 1 c |                            |
|     | a d 0 g 0 0 0 |                            |
|                                                  |
|             7      7                             |
|o3 : Matrix R  <-- R                              |
+--------------------------------------------------+
|i4 : det N                                        |
|                                                  |
|o4 = c*e*g + b*f*g + c*d*h + a*f*h + b*d*i + a*e*i|
|                                                  |
|o4 : R                                            |
+--------------------------------------------------+

Here is the 15x15 matrix constructed from a 4x4 generic matrix of variable
(note that the even case has -1 on the diagonal).

+-----------------------------------------------------------------------------+
|i5 : R=QQ[a..p]                                                              |
|                                                                             |
|o5 = R                                                                       |
|                                                                             |
|o5 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i6 : M=genericMatrix(R,4,4)                                                  |
|                                                                             |
|o6 = | a e i m |                                                             |
|     | b f j n |                                                             |
|     | c g k o |                                                             |
|     | d h l p |                                                             |
|                                                                             |
|             4      4                                                        |
|o6 : Matrix R  <-- R                                                         |
+-----------------------------------------------------------------------------+
|i7 : N = grenet M                                                            |
|                                                                             |
|o7 = | -1 0  f  0  j  0  0  0  n  0  0  0  0  0  0 |                         |
|     | 0  -1 b  0  0  j  0  0  0  n  0  0  0  0  0 |                         |
|     | 0  0  -1 0  0  0  k  0  0  0  o  0  0  0  0 |                         |
|     | 0  0  0  -1 b  f  0  0  0  0  0  n  0  0  0 |                         |
|     | 0  0  0  0  -1 0  g  0  0  0  0  0  o  0  0 |                         |
|     | 0  0  0  0  0  -1 c  0  0  0  0  0  0  o  0 |                         |
|     | 0  0  0  0  0  0  -1 0  0  0  0  0  0  0  p |                         |
|     | 0  0  0  0  0  0  0  -1 b  f  0  j  0  0  0 |                         |
|     | 0  0  0  0  0  0  0  0  -1 0  g  0  k  0  0 |                         |
|     | 0  0  0  0  0  0  0  0  0  -1 c  0  0  k  0 |                         |
|     | 0  0  0  0  0  0  0  0  0  0  -1 0  0  0  l |                         |
|     | 0  0  0  0  0  0  0  0  0  0  0  -1 c  g  0 |                         |
|     | 0  0  0  0  0  0  0  0  0  0  0  0  -1 0  h |                         |
|     | 0  0  0  0  0  0  0  0  0  0  0  0  0  -1 d |                         |
|     | a  e  0  i  0  0  0  m  0  0  0  0  0  0  0 |                         |
|                                                                             |
|             15      15                                                      |
|o7 : Matrix R   <-- R                                                        |
+-----------------------------------------------------------------------------+
|i8 : det N                                                                   |
|                                                                             |
|o8 = d*g*j*m + c*h*j*m + d*f*k*m + b*h*k*m + c*f*l*m + b*g*l*m + d*g*i*n +   |
|     ------------------------------------------------------------------------|
|     c*h*i*n + d*e*k*n + a*h*k*n + c*e*l*n + a*g*l*n + d*f*i*o + b*h*i*o +   |
|     ------------------------------------------------------------------------|
|     d*e*j*o + a*h*j*o + b*e*l*o + a*f*l*o + c*f*i*p + b*g*i*p + c*e*j*p +   |
|     ------------------------------------------------------------------------|
|     a*g*j*p + b*e*k*p + a*f*k*p                                             |
|                                                                             |
|o8 : R                                                                       |
+-----------------------------------------------------------------------------+

Here is the construction for a matrix of integers.

+---------------------------------------------------------------+
|i9 : M = matrix{{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}}|
|                                                               |
|o9 = | 1  2  3  4  |                                           |
|     | 5  6  7  8  |                                           |
|     | 9  10 11 12 |                                           |
|     | 13 14 15 16 |                                           |
|                                                               |
|              4       4                                        |
|o9 : Matrix ZZ  <-- ZZ                                         |
+---------------------------------------------------------------+
|i10 : permanents(4,M)                                          |
|                                                               |
|o10 = ideal 55456                                              |
|                                                               |
|o10 : Ideal of ZZ                                              |
+---------------------------------------------------------------+
|i11 : N = grenet M                                             |
|                                                               |
|o11 = | -1 0  6  0  7  0  0  0  8  0  0  0  0  0  0  |         |
|      | 0  -1 5  0  0  7  0  0  0  8  0  0  0  0  0  |         |
|      | 0  0  -1 0  0  0  11 0  0  0  12 0  0  0  0  |         |
|      | 0  0  0  -1 5  6  0  0  0  0  0  8  0  0  0  |         |
|      | 0  0  0  0  -1 0  10 0  0  0  0  0  12 0  0  |         |
|      | 0  0  0  0  0  -1 9  0  0  0  0  0  0  12 0  |         |
|      | 0  0  0  0  0  0  -1 0  0  0  0  0  0  0  16 |         |
|      | 0  0  0  0  0  0  0  -1 5  6  0  7  0  0  0  |         |
|      | 0  0  0  0  0  0  0  0  -1 0  10 0  11 0  0  |         |
|      | 0  0  0  0  0  0  0  0  0  -1 9  0  0  11 0  |         |
|      | 0  0  0  0  0  0  0  0  0  0  -1 0  0  0  15 |         |
|      | 0  0  0  0  0  0  0  0  0  0  0  -1 9  10 0  |         |
|      | 0  0  0  0  0  0  0  0  0  0  0  0  -1 0  14 |         |
|      | 0  0  0  0  0  0  0  0  0  0  0  0  0  -1 13 |         |
|      | 1  2  0  3  0  0  0  4  0  0  0  0  0  0  0  |         |
|                                                               |
|               15       15                                     |
|o11 : Matrix ZZ   <-- ZZ                                       |
+---------------------------------------------------------------+
|i12 : det N                                                    |
|                                                               |
|o12 = 55456                                                    |
+---------------------------------------------------------------+

Caveat
======

See also
========

  * permanents (Macaulay2Doc) -- ideal generated by square
    permanents of a matrix

Ways to use grenet:
===================

  * "grenet(Matrix)"

For the programmer
==================

The object grenet, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in Permanents.m2:533:0.

pminors -- Return ideal generated by pminors of a specified size
****************************************************************

  * Usage:
        I = pminors(k,M)
  * Inputs:
      * M, a matrix (Macaulay2Doc), a square matrix in any
        commutative ring
      * k, an integer (Macaulay2Doc), a positive integer
  * Optional inputs (Macaulay2Doc),:
      * Strategy (missing documentation) => ..., default value null,
  * Outputs:
      * I, an ideal (Macaulay2Doc), the ideal generated by the
        $k\times k$ permanent minors of $M$

Description
===========

Computes the ideal generated by $k\times k$ permanent minors of $M$ with the
specified strategy. If no strategy is input then the default is Glynn's
formula.

Here is the ideal generated by the $2\times 2$ permanent minors of the 3x3
generic matrix of variables.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[vars(0..8)]                                                      |
|                                                                             |
|o1 = R                                                                       |
|                                                                             |
|o1 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i2 : M = genericMatrix(R,a,3,3)                                              |
|                                                                             |
|o2 = | a d g |                                                               |
|     | b e h |                                                               |
|     | c f i |                                                               |
|                                                                             |
|             3      3                                                        |
|o2 : Matrix R  <-- R                                                         |
+-----------------------------------------------------------------------------+
|i3 : I = pminors(2,M)                                                        |
|                                                                             |
|o3 = ideal (b*d + a*e, b*g + a*h, e*g + d*h, c*d + a*f, c*g + a*i, f*g + d*i,|
|     ------------------------------------------------------------------------|
|     c*e + b*f, c*h + b*i, f*h + e*i)                                        |
|                                                                             |
|o3 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+

Here is the ideal generated by the $2\times 2$ permanent minors of a $2\times
3$ matrix using the two different strategies.

+---------------------------------+
|i4 : M=matrix{{1,2,3},{4,5,6}}   |
|                                 |
|o4 = | 1 2 3 |                   |
|     | 4 5 6 |                   |
|                                 |
|              2       3          |
|o4 : Matrix ZZ  <-- ZZ           |
+---------------------------------+
|i5 : pminors(2,M,Strategy=>glynn)|
|                                 |
|o5 = ideal (13, 18, 27)          |
|                                 |
|o5 : Ideal of ZZ                 |
+---------------------------------+
|i6 : pminors(2,M,Strategy=>ryser)|
|                                 |
|o6 = ideal (13, 18, 27)          |
|                                 |
|o6 : Ideal of ZZ                 |
+---------------------------------+

Caveat
======

See also
========

  * permanents (Macaulay2Doc) -- ideal generated by square
    permanents of a matrix

Ways to use pminors:
====================

  * "pminors(ZZ,Matrix)"

For the programmer
==================

The object pminors, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in Permanents.m2:570:0.

ryser -- compute permanent using Ryser's formula
************************************************

  * Usage:
        F = ryser M
  * Inputs:
      * M, a matrix (Macaulay2Doc), a square matrix in any
        commutative ring
  * Outputs:
      * F, a ring element (Macaulay2Doc), the permanent of M

Description
===========

Uses Ryser's inclusion-exclusion formula (see page 27 of Ryser, Herbert John
(1963), Combinatorial Mathematics, The Carus mathematical monographs, The
Mathematical Association of America).

Let $M=(m_{i,j})$ be an nxn matrix. Then $perm(M)=\sum_{S\subseteq [n]}
(-1)^{\mid S\mid} \prod_{i=1}^n \sum_{j\in S^c}m_{i,j}$.

For example, for the 3x3 generic matrix Ryser’s formula gives $perm(M) = (a + b
+ c)(d + e + f)(g + h + i) − (a + b)(d + e)(g + h)−(a + c)(d + f)(g + i) − (b +
c)(e + f)(h + i) + adg + beh + cfi$.

Here is the permanent of a 3x3 generic matrix of variables.

+--------------------------------------------------+
|i1 : R = QQ[vars(0..8)]                           |
|                                                  |
|o1 = R                                            |
|                                                  |
|o1 : PolynomialRing                               |
+--------------------------------------------------+
|i2 : M = genericMatrix(R,a,3,3)                   |
|                                                  |
|o2 = | a d g |                                    |
|     | b e h |                                    |
|     | c f i |                                    |
|                                                  |
|             3      3                             |
|o2 : Matrix R  <-- R                              |
+--------------------------------------------------+
|i3 : ryser M                                      |
|                                                  |
|o3 = c*e*g + b*f*g + c*d*h + a*f*h + b*d*i + a*e*i|
|                                                  |
|o3 : R                                            |
+--------------------------------------------------+

Here is the permanent of a 4x4 generic matrix of variables.

+-----------------------------------------------------------------------------+
|i4 : R = QQ[vars(0..15)]                                                     |
|                                                                             |
|o4 = R                                                                       |
|                                                                             |
|o4 : PolynomialRing                                                          |
+-----------------------------------------------------------------------------+
|i5 : M = genericMatrix(R,a,4,4)                                              |
|                                                                             |
|o5 = | a e i m |                                                             |
|     | b f j n |                                                             |
|     | c g k o |                                                             |
|     | d h l p |                                                             |
|                                                                             |
|             4      4                                                        |
|o5 : Matrix R  <-- R                                                         |
+-----------------------------------------------------------------------------+
|i6 : ryser M                                                                 |
|                                                                             |
|o6 = d*g*j*m + c*h*j*m + d*f*k*m + b*h*k*m + c*f*l*m + b*g*l*m + d*g*i*n +   |
|     ------------------------------------------------------------------------|
|     c*h*i*n + d*e*k*n + a*h*k*n + c*e*l*n + a*g*l*n + d*f*i*o + b*h*i*o +   |
|     ------------------------------------------------------------------------|
|     d*e*j*o + a*h*j*o + b*e*l*o + a*f*l*o + c*f*i*p + b*g*i*p + c*e*j*p +   |
|     ------------------------------------------------------------------------|
|     a*g*j*p + b*e*k*p + a*f*k*p                                             |
|                                                                             |
|o6 : R                                                                       |
+-----------------------------------------------------------------------------+

Here is the permanent of a 3x3 matrix of integers.

+--------------------------------------+
|i7 : M=matrix{{1,2,3},{4,5,6},{7,8,9}}|
|                                      |
|o7 = | 1 2 3 |                        |
|     | 4 5 6 |                        |
|     | 7 8 9 |                        |
|                                      |
|              3       3               |
|o7 : Matrix ZZ  <-- ZZ                |
+--------------------------------------+
|i8 : ryser M                          |
|                                      |
|o8 = 450                              |
+--------------------------------------+

Caveat
======

Computationally intensive for moderate size matrices.

See also
========

  * permanents (Macaulay2Doc) -- ideal generated by square
    permanents of a matrix

Ways to use ryser:
==================

  * "ryser(Matrix)"

For the programmer
==================

The object ryser, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in Permanents.m2:444:0.