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. For an n×n matrix A=(a_(ij)), its permanent is

per_(n)(A)=sum_(sigma in S_n)product_(i=1)^na_(i,sigma(i)).
(1)

Here S_n is the symmetric group on n symbols. Equivalently, the permanent of 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).
(2)

(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),
(3)

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 is implemented in the Wolfram Language as Permanent[m].

The exact symbolic computation of permanents has been studied extensively in algebraic complexity theory. Over the complex numbers, the permanent polynomial is complete for Valiant's class VNP (Valiant 1979a).

An AI-generated proof given by OpenAI (2026) established that division-free arithmetic circuits computing per_(n) require Omega(n^2lnlnn) arithmetic gates. It also established that arithmetic formulas require Omega(n^4/lnn) variable-labeled leaves and internal gates, even when division is allowed provided every denominator is a nonzero rational function. Here Omega is big-Omega notation.

These results concern exact symbolic computation and are distinct from numerical evaluation. In particular, evaluating the permanent of a (0,1)-matrix is #P-complete (i.e., sharp-P complete; Valiant 1979b).

If M is a unitary matrix, then

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

(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.OpenAI. "Circuit and Formula Lower Bounds for the Permanent." Ch. 5 in Ten Advances in Mathematics and Theoretical Computer Science. Aug. 1, 2026. https://cdn.openai.com/pdf/ten-proofs-oai.pdf.Seifter, N. "Upper Bounds for Permanents of (1,-1)-Matrices." Israel J. Math. 48, 69-78, 1984.Valiant, L. G. "Completeness Classes in Algebra." In Proc. Eleventh Annual ACM Symposium on Theory of Computing. New York: ACM, pp. 249-261, 1979a. https://doi.org/10.1145/800135.804419.Valiant, L. G. "The Complexity of Computing the Permanent." Theoret. Comp. Sci. 8, 189-201, 1979b. https://doi.org/10.1016/0304-3975(79)90044-6.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 Resource. https://mathworld.wolfram.com/Permanent.html

Subject classifications