The Glynn formula expresses the permanent of a matrix as a sum over sign vectors. For
an 
matrix 
over a field
whose characteristic is not 2, with 
a positive
integer, it states that
 |
where the sum is over the 
vectors 
with 
(Glynn 2010).
To prove the formula, expand the product of column sums and let 
count the factors drawn from row 
. Summing over signs cancels every term unless each
with 
is odd. Since 
, this forces
every 
to equal 1. The surviving terms are exactly the permutation
terms defining the permanent, each with weight 
.
Ordering the sign choices by a Gray code changes a single sign at each step, so the 
column sums can be updated in 
arithmetic operations. Forming their
product also takes 
operations per term, giving 
arithmetic complexity, the same asymptotic bound as
the implementation of the Ryser formula using a
Gray code. Here 
denotes big-O notation.
