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

# ryser -- compute permanent using Ryser's formula

- Usage:
    `F = ryser M`
- Inputs:
  - M, a matrix, a square matrix in any commutative ring
- Outputs:
  - F, a ring element, 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 -- ideal generated by square permanents of a matrix

## Ways to use ryser:

- `ryser(Matrix)`

## For the programmer

The object ryser is a method function.

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/Permanents.m2:444:0.