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

Synopsis

Usage:

F = grenet M
Inputs:
- M, a matrix, a square matrix in any commutative ring
Outputs:
- N, a matrix, 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

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

Synopsis

Description

Caveat

See also

Ways to use grenet :

For the programmer