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.
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.
Weisstein, Eric W. "Permanent." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Permanent.html
Contact the MathWorld Team
area inside x^2 - 2xy + 4y^2 = 4