TOPICS

# Permanent

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 is the coefficient of in

 (1)

(Vardi 1991). Another equation is the Ryser formula

 (2)

where the sum is over all subsets of , and is the number of elements in (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 is a unitary matrix, then

 (3)

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

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

## Explore with Wolfram|Alpha

More things to try:

## 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 -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 -Matrices." Israel J. Math. 18, 353-361, 1974.

Permanent

## Cite this as:

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