What are some Applications of the Permanent of a Matrix?

Solution 1:

Finding Permanent of square matrix is equivalent to finding:

(1) Number of perfect matching in the Bipartite graph (Biadjacencey Matrix).

(2) Number of cycle cover in the Directed graph (adjacency matrix).

You can check on Wiki page

(3) Number of monomial in Read-twice Formula Check this paper

Solution 2:

To complement a previous answer, permanents are common in physics: by the spin-statistics theorem, the many-particle states of identical bosons must be fully symmetric under permutation, and an easy way to construct such fully symmetric states is to use permanents, where the entry $(ij)$ is $\phi_i(x_j)$, describing particle $j$ in state $i$. This works because the permanent is unchanged if one permutes any two rows or columns of a matrix. The many-body state is thus a polynomial in the single particle states. (Conversely the many particle states of identical fermions must be antisymmetric and one uses determinants for those (see this wiki page on Slater determinants.)

Possibly the most spectacular recent application of permanents (and associated computational complexity) is the BosonSampling problem, where it is shown that the distribution of permanents resulting from the interference of indistinguishable photons (they are bosons) is #P-hard (exactly or approximately).