#933: Permanents of (0,1)-matrices
--------------------------------+-------------------------------------------
Reporter: jsp | Owner: was
Type: enhancement | Status: new
Priority: major | Milestone: sage-3.1.3
Component: algebraic geometry | Resolution:
Keywords: |
--------------------------------+-------------------------------------------
Old description:
> 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}^2 = 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
New description:
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}^2^ = 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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/933#comment:2>
SAGE <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
