# 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 square matrix in any commutative ring
• Outputs:
• N, , 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