Permanent (mathematics)

In linear algebra, the permanent of a square matrix is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix. Both are special cases of a more general function of a matrix called the immanant.
Definition.
The permanent of an "n"-by-"n" matrix "A" = ("a""i,j") is defined as
The sum here extends over all elements σ of the symmetric group "S""n"; i.e. over all permutations of the numbers 1, 2, ..., "n".
For example,
and
The definition of the permanent of "A" differs from that of the determinant of "A" in that the signatures of the permutations are not taken into account.
The permanent of a matrix A is denoted per "A", perm "A", or Per "A", sometimes with parentheses around the argument. Minc uses Per("A") for the permanent of rectangular matrices, and per("A") when "A" is a square matrix. Muir and Metzler use the notation formula_4
The permanent is believed to be more difficult to compute than the determinant. While the determinant can be computed in polynomial time by Gaussian elimination, Gaussian elimination cannot be used to compute the permanent. Moreover, computing the permanent of a (0,1)-matrix is #P-complete. Thus, if the permanent can be computed in polynomial time by any method, then FP = #P, which is an even stronger statement than P = NP. When the entries of "A" are nonnegative, however, the permanent can be computed approximately in probabilistic polynomial time, up to an error of formula_5, where formula_6 is the value of the permanent and formula_7 is arbitrary. The permanent of a certain set of positive semidefinite matrices can also be approximated in probabilistic polynomial time: the best achievable error of this approximation is formula_8 (formula_6 is again the value of the permanent).
MacMahon's Master Theorem.
Another way to view permanents is via multivariate generating functions. Let formula_10 be a square matrix of order "n". Consider the multivariate generating function:
The coefficient of formula_13 in formula_14 is perm("A").
As a generalization, for any sequence of "n" non-negative integers, formula_15 define:
MacMahon's Master Theorem relating permanents and determinants is:
where "I" is the order "n" identity matrix and "X" is the diagonal matrix with diagonal formula_20
Permanents of rectangular matrices.
The permanent function can be generalized to apply to non-square matrices. Indeed, several authors make this the definition of a permanent and consider the restriction to square matrices a special case. Specifically, for an "m" × "n" matrix formula_10 with "m" ≤ "n", define
where P("n","m") is the set of all "m"-permutations of the "n"-set {1,2...,n}.
Ryser's computational result for permanents also generalizes. If "A" is an "m" × "n" matrix with "m" ≤ "n", let formula_23 be obtained from "A" by deleting "k" columns, let formula_24 be the product of the row-sums of formula_23, and let formula_26 be the sum of the values of formula_24 over all possible formula_23. Then 
Systems of distinct representatives.
The generalization of the definition of a permanent to non-square matrices allows the concept to be used in a more natural way in some applications. For instance:
Let "S"1, "S"2, ..., "S""m" be subsets (not necessarily distinct) of an "n"-set with "m" ≤ "n". The incidence matrix of this collection of subsets is an "m" × "n" (0,1)-matrix "A". The number of systems of distinct representatives (SDR's) of this collection is perm("A").