View source for Permanent

''of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p0722501.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p0722502.png" />''

The function

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p0722503.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p0722504.png" /> are elements from a commutative ring and summation is over all one-to-one mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p0722505.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p0722506.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p0722507.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p0722508.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p0722509.png" /> represents all possible permutations, and the permanent is a particular case of the Schur matrix function (cf. [[Immanant]])

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225010.png" /></td> </tr></table>

for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225011.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225012.png" /> is a character of degree 1 on the subgroup <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225013.png" /> (cf. [[Character of a group|Character of a group]]) of the symmetric group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225014.png" /> (one obtains the [[Determinant|determinant]] for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225016.png" />, in accordance with the parity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225017.png" />).

The permanent is used in linear algebra, probability theory and combinatorics. In combinatorics, a permanent can be interpreted as follows: The number of systems of distinct repesentatives for a given family of subsets of a finite set is the permanent of the incidence matrix for the [[Incidence system|incidence system]] related to this family.

The main interest is in the permanent of a matrix consisting of zeros and ones (a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225019.png" />-matrix), of a matrix containing non-negative real numbers, in particular doubly-stochastic matrices (in which the sum of the elements in any row and any column is 1), and of a complex [[Hermitian matrix|Hermitian matrix]]. The basic properties of the permanent include a theorem on expansion (the analogue of Laplace's theorem for determinants) and the Binet–Cauchy theorem, which gives a representation of the permanent of the product of two matrices as the sum of the products of the permanents formed from the cofactors. For the permanents of complex matrices it is convenient to use representations as scalar products in the symmetry classes of completely-symmetric tensors (see, e.g., [[#References|[3]]]). One of the most effective methods for calculating permanents is provided by Ryser's formula:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225020.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225021.png" /> is the set of submatrices of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225022.png" /> for the square matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225024.png" /> is the sum of the elements of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225025.png" />-th row of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225027.png" />. As it is complicated to calculate permanents, estimating them is important. Some lower bounds are given below.

a) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225028.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225029.png" />-matrix with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225031.png" />, then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225032.png" /></td> </tr></table>

for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225033.png" />, and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225034.png" /></td> </tr></table>

if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225035.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225036.png" />.

b) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225037.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225038.png" />-matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225039.png" />, then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225040.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225041.png" /> are the sums of the elements in the rows of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225042.png" /> arranged in non-increasing order and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225043.png" />.

c) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225044.png" /> is a positive semi-definite Hermitian matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225045.png" />, then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225046.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225047.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225048.png" />.

Upper bounds for permanents:

1) For a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225049.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225050.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225051.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225052.png" /></td> </tr></table>

2) For a completely-indecomposable matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225053.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225054.png" /> with non-negative integer elements,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225055.png" /></td> </tr></table>

3) For a complex normal matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225056.png" /> with eigen values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225057.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225058.png" /></td> </tr></table>

The most familiar problem in the theory of permanents was van der Waerden's conjecture: The permanent of a doubly-stochastic matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225059.png" /> is bounded from below by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225060.png" />, and this value is attained only for the matrix composed of fractions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225061.png" />. A positive solution to this problem was obtained in [[#References|[4]]].

Among the applications of permanents one may mention relationships to certain combinatorial problems (cf. [[Combinatorial analysis|Combinatorial analysis]]), such as the  "problème des rencontresproblème de rencontres"  and the  "problème d'attachementproblème d'attachement"  (or  "hook problemhook problem" ), and also to the [[Fibonacci numbers|Fibonacci numbers]], the enumeration of Latin squares (cf. [[Latin square|Latin square]]) and Steiner triple systems (cf. [[Steiner system|Steiner system]]), and to the derivation of the number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225062.png" />-factors and linear subgraphs of a [[Graph|graph]], while doubly-stochastic matrices are related to certain probability models. There are interesting physical applications of permanents, of which the most important is the dimer problem, which arises in research on the [[Adsorption|adsorption]] of di-atomic molecules in surface layers: The permanent of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072250/p07225063.png" />-matrix of a simple structure expresses the number of ways of combining the atoms in the substance into di-atomic molecules. There are also applications of permanents in statistical physics, the theory of crystals and physical chemistry.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  H.J. Ryser,   "Combinatorial mathematics" , Wiley &amp; Math. Assoc. Amer.  (1963)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  V.N. Sachkov,   "Combinatorial methods in discrete mathematics" , Moscow  (1977)  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  H. Minc,   "Permanents" , Addison-Wesley  (1978)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  G.P. Egorichev,   "The solution of van der Waerden's problem on permanents" , Krasnoyarsk  (1980)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  D.I. Falikman,   "Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix"  ''Math. Notes'' , '''29''' :  6  (1981)  pp. 475–479  ''Mat. Zametki'' , '''29''' :  6  (1981)  pp. 931–938</TD></TR></table>



====Comments====
For the upper bound given in 1) see [[#References|[a7]]]. For the enumeration of Steiner triple systems see [[#References|[a6]]].

The solution of the van der Waerden conjecture was obtained simultaneously and independently of each other in 1979 by both O.I. Falikman, [[#References|[5]]], and G.P. Egorichev, [[#References|[4]]], [[#References|[a4]]]. For some details cf. also [[#References|[a2]]]–[[#References|[a5]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D.E. Knuth,   "A permanent inequality"  ''Amer. Math. Monthly'' , '''88'''  (1981)  pp. 731–740</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J.C. Lagarias,   "The van der Waerden conjecture: two Soviet solutions"  ''Notices Amer. Math. Soc.'' , '''29''' :  2  (1982)  pp. 130–133</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.H. van Lint,   "Notes on Egoritsjev's proof of the van der Waerden conjecture"  ''Linear Algebra Appl.'' , '''39'''  (1981)  pp. 1–8</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  G.P. [G.P. Egorichev] Egorychev,   "The solution of van der Waerden's problem for permanents"  ''Adv. in Math.'' , '''42''' :  3  (1981)  pp. 299–305</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  J.H. van Lint,   "The van der Waerden conjecture: Two proofs in one year"  ''Math. Intelligencer'' , '''4'''  (1982)  pp. 72–77</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  R.M. Wilson,   "Non-isomorphic triple systems"  ''Math. Zeitschr.'' , '''135'''  (1974)  pp. 303–313</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A. Schrijver,   "A short proof of Minc's conjecture"  ''J. Comb. Theory (A)'' , '''25'''  (1978)  pp. 80–83</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  H. Minc,   "Nonnegative matrices" , Wiley  (1988)</TD></TR></table>