Uses Glynn's formula (see Glynn, David G. (2010), "The permanent of a square matrix", European Journal of Combinatorics 31 (7): 1887–1891, doi:10.1016/j.ejc.2010.01.010).
Let $M=(m_{i,j})$ be an nxn matrix. Then $perm(M)=\sum_{\delta}\prod_{k=1}^n(\delta_k) \prod_{i=1}^n\sum_{j=1}^n \delta_j m_{i,j}$ where the outer summation is over $\delta\in \{ -1,+1\}^n$ with $\delta_1=1$.
For example, for the 3x3 generic matrix Glynn’s formula gives $2^2 perm(M) =(a + b + c)(d + e + f)(g + h + i) − (a − b + c)(d − e + f)(g − h + i) −(a + b − c)(d + e − f)(g + h − i) + (a − b − c)(d − e − f)(g − h − i)$.
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 : glynn 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 : glynn 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 : glynn M o8 = 450 |
Works in characteristic not equal to 2 because need to divide by $2^{n-1}$. Computationally intensive for moderate size matrices.
The object glynn is a method function.