permanent of square matrix

[Albert Chan]

(01-04-2024 08:06 PM)Albert Chan Wrote:  First term = product of (v = column sums)
Other terms, v -= d[j]*M[j], flipped only sign of M j-th row.
This make it very efficient, instead of summing them all from scratch.

Selection of what next j-th row is by idea of Gray Code

Quote:Gray Code is an alternative binary representation, cleverly devised so that,
between any two adjacent numbers, only one bit changes at a time.

Lets examine 5×5 matrix sign flip pattern, to confirm indeed it uses Gray Code.
Again, last row sign never flipped, thus only 2^(5-1) = 16 sign flip patterns.

I reversed bits, to match gray code pattern exactly.

lua> n = 5
lua> f = {1,2,3,4,5}
lua> b = {0,0,0,0}
lua> function bits(k) b[k]=1-b[k]; print(table.concat(b)) end
lua> while f[1]<n do j=f[1]; f[1]=1; f[j]=f[j+1]; f[j+1]=j+1; bits(n-j) end
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000