12
$\begingroup$

I have a decent understanding of the determinant of a matrix in terms of its role in

  • Telling you if a matrix is invertible (zero vs. nonzero)
  • Expressing the product of a matrix's eigenvalues with multiplicities
  • Representing the constant term in a matrix's characteristic polynomial
  • Having geometrical interpretations

However, I was curious to learn in the operation known as the permanent has any interesting properties. The permanent is defined in the same way a determinant is, but all entries are added instead of alternating between positive and negative terms.

In particular, what are the significant applications of defining the permanent as a notable matrix operation? Also, are there any matrix problems whose solutions directly/indirectly depend on understanding the permanent?

$\endgroup$
3
  • $\begingroup$ math.stackexchange.com/questions/761297/… $\endgroup$
    – Moishe Kohan
    Jan 5, 2015 at 2:44
  • 1
    $\begingroup$ @studiosus I like the information in your link from a theoretical standpoint, but it doesn't quite answer the question. I'm looking for a more application-oriented answer or problem that can be solved using permanents, not necessarily knowing about the time complexity to compute them. $\endgroup$
    – Xoque55
    Jan 5, 2015 at 2:50
  • $\begingroup$ Well, if you really understand permanents, you will prove that P equals NP or, vice versa, that P is not equal to NP; this will have major ramifications in the computer science and will earn you $10^6$ USD among other things. I guess, however, this is not an answer you are looking for, therefore I posted this link just as a comment. (+1 for the question itself.) $\endgroup$
    – Moishe Kohan
    Jan 5, 2015 at 4:26

2 Answers 2

Reset to default
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.