For other uses, see Permanent (disambiguation).
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.[1] Both permanent and determinant are special cases of a more general function of a matrix called the immanant.
Contents
- 1 Definition
- 2 Properties and applications
- 2.1 Symmetric tensors
- 2.2 Cycle covers
- 2.3 Perfect matchings
- 3 Permanents of (0,1) matrices
- 4 Van der Waerden's conjecture
- 5 Computation
- 6 MacMahon's Master Theorem
- 7 Permanents of rectangular matrices
- 7.1 Systems of distinct representatives
- 8 See also
- 9 Notes
- 10 References
- 11 Further reading
- 12 External links
Definition
The permanent of an n-by-n matrix A = (ai,j) is defined as
The sum here extends over all elements σ of the symmetric group Sn; 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. In his monograph, Minc (1984) uses Per(A) for the permanent of rectangular matrices, and uses per(A) when A is a square matrix. Muir (1882) uses the notation .
The word, permanent, originated with Cauchy in 1812 as “fonctions symétriques permanentes” for a related type of function,[2] and was used by Muir (1882) in the modern, more specific, sense.[3]
Properties and applications
If one views the permanent as a map that takes n vectors as arguments, then it is a multilinear map and it is symmetric (meaning that any order of the vectors results in the same permanent). Furthermore, given a square matrix of order n, we have:[4]
- perm(A) is invariant under arbitrary permutations of the rows and/or columns of A. This property may be written symbolically as perm(A) = perm(PAQ) for any appropriately sized permutation matrices P and Q,
- multiplying any single row or column of A by a scalar s changes perm(A) to s⋅perm(A),
- perm(A) is invariant under transposition, that is, perm(A) = perm(A⊤).
If and are square matrices of order n then,[5]
where s and t are subsets of the same size of {1,2,...,n} and are their respective complements in that set.
On the other hand, the basic multiplicative property of determinants is not valid for permanents.[6] A simple example shows that this is so.
A formula similar to Laplace's for the development of a determinant along a row, column or diagonal is also valid for the permanent;[7] all signs have to be ignored for the permanent. For example, expanding along the first column,