TOPICS
Search

Permanent

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The permanent is an analog of a determinant where all the signs in the expansion by minors are taken as positive. The permanent of a matrix A is the coefficient of x_1...x_n in

product_(i=1)^n(a_(i1)x_1+a_(i2)x_2+...+a_(in)x_n)
(1)

(Vardi 1991). Another equation is the Ryser formula

perm(a_(ij))=(-1)^nsum_(s subset= {1,...,n})(-1)^(|s|)product_(i=1)^nsum_(j in s)a_(ij),
(2)

where the sum is over all subsets of {1,...,n}, and |s| is the number of elements in s (Vardi 1991). Muir (1960, p. 19) uses the notation |; +|; + to denote a permanent.

The permanent can be implemented in the Wolfram Language as 

  Permanent[m_List] :=
    With[{v = Array[x, Length[m]]},
      Coefficient[Times @@ (m.v), Times @@ v]
  ]

The computation of permanents has been studied fairly extensively in algebraic complexity theory. The complexity of the best-known algorithms grows as the exponent of the matrix size (Knuth 1998, p. 499), which would appear to be very surprising, given the permanent's similarity to the tractable determinant. Computation of the permanent is #P-complete (i.e, sharp-P complete; Valiant 1979).

If M is a unitary matrix, then

|perm(M)|<=1
(3)

(Minc 1978, p. 25; Vardi 1991). The maximum permanent for an n×n (0,1)-matrix is n!, corresponding to all elements 1.

See also

Determinant, Frobenius-König Theorem, Immanant, Ryser Formula, Schur Matrix

Explore with Wolfram|Alpha

References

Borovskikh, Y. V. and Korolyuk, V. S. Random Permanents. Philadelphia, PA: Coronet Books, 1994.Comtet, L. "Permanents." §4.9 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 197-198, 1974.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, p. 51, 1997.Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, pp. 499 and 515-516, 1998.Minc, H. Permanents. Reading, MA: Addison-Wesley, 1978.Muir, T. §27 in A Treatise on the Theory of Determinants. New York: Dover, p. 19 1960.Seifter, N. "Upper Bounds for Permanents of (1,-1)-Matrices." Israel J. Math. 48, 69-78, 1984.Valiant, L. G. "The Complexity of Computing the Permanent." Theoret. Comp. Sci. 8, 189-201, 1979.Vardi, I. "Permanents." §6.1 in Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 108 and 110-112, 1991.Wang, E. T.-H. "On Permanents of (1,-1)-Matrices." Israel J. Math. 18, 353-361, 1974.

Referenced on Wolfram|Alpha

Permanent

Cite this as:

Weisstein, Eric W. "Permanent." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Permanent.html

Subject classifications