Monthly Archives: December 2014

Modulating the Permanent

Modulo calculating the permanent is an interesting topic in counting complexity 🙂

Gödel's Lost Letter and P=NP


Thomas Muir coined the term “permanent” as a noun in his treatise on determinants in 1882. He took it from Augustin Cauchy’s distinction in 1815 between symmetric functions that alternate when rows of a matrix are interchanged versus ones that “stay permanent.” To emphasize that all terms of the permanent have positive sign, he modified the contemporary notation $latex {left| A right|}&fg=000000$ for the determinant of a matrix $latex {A}&fg=000000$ into

$latex displaystyle overset{+}{|} A overset{+}{|} &fg=000000$

for the permanent. Perhaps we should be glad that this notation did not become permanent.

Today Ken and I wish to highlight some interesting results on computing the permanent modulo some integer value.

Recall the permanent of a square matrix $latex {A}&fg=000000$ is the function defined as follows by summing over all permutations of $latex {{1,dots,n}}&fg=000000$, that is, over all members of the symmetric group $latex {S_n}&fg=000000$:

$latex displaystyle mathrm{perm}(A)=sum_{sigmain S_n}prod_{i=1}^n a_{i,sigma(i)}. &fg=000000$

View original post 1,060 more words