Permanents of (0,1)-matrices

[jaapspies]

Let A = (a{ij}) be an m x n (m <= n) (0,1)-matrix. We define a matrix X = (x{ij}) with independent indeterminates x{ij}: x{ij} = 0 iff a_{ij} = 0.

So x{ij} only exists iff a{ij} = 1.

Now define a list of equations: (how do I format them properly here?)

\sum{i=1}^{i=m} x{ij} = 1 for j = 1, ..., n

\sum{j=1}^{j=n} x{ij} = 1 for i = 1, ..., m

x{ij}² = x{ij} for i = 1, ..., m and j = 1, ..., n

It is easy to prove that the number of solutions to this equations is equal to the permanent of A.

Based on a paper from Bernasconi, et al.: Computing Groebner Bases in the Boolean Setting with Applications to Counting (1997) (which restricts itself to square matrices and a number of polynomials less than 255), we can do the following:

1) calculate a Groebner basis

2) compute the number of solutions (the permanent)

If this could be done fast, it beats Ryser's algorithm (See the article above).

Jaap

Component: algebraic geometry

Issue created by migration from https://trac.sagemath.org/ticket/933

[malb]

Description changed:

--- 
+++ 
@@ -7,11 +7,11 @@

 Now define a list of equations: (how do I format them properly here?)

-\sum_{i=1}^{i=m} x_{ij} = 1 for j = 1, ..., n
+\sum_{i=1}<sup>{i=m}</sup> x_{ij} = 1 for j = 1, ..., n

-\sum_{j=1}^{j=n} x_{ij} = 1 for i = 1, ..., m
+\sum_{j=1}<sup>{j=n}</sup> x_{ij} = 1 for i = 1, ..., m

-x_{ij}^2 = x_{ij} for i = 1, ..., m and j = 1, ..., n
+x_{ij}<sup>2</sup> = x_{ij} for i = 1, ..., m and j = 1, ..., n

 It is easy to prove that the number of solutions to this equations is

[malb]

comment:3

calculate a Groebner basis

over which field?

[videlec]

comment:8

Replying to @malb:

calculate a Groebner basis

over which field?

ZZ. You want the 0-1 solutions and the x = x^2 guarantees exactly that.