View source for Permanent

{{TEX|done}}{{MSC|15A15|05B20}}

''of an $m \times n$-matrix $A = \left\Vert a_{ij} \right\Vert$''

The function
$$
\mathrm{per}(A) = \sum_\sigma a_{1\sigma(1)}\cdots a_{m\sigma(m)}
$$

where $a_{ij}$ are elements from a commutative ring and summation is over all one-to-one mappings $\sigma$ from $\{1,\ldots,m\}$ into $\{1,\ldots,n\}$. If $m=n$, then $\sigma$ represents all possible permutations, and the permanent is a particular case of the Schur matrix function (cf. [[Immanant]])
$$
d_\chi^H (A) = \sum_{\sigma\in H} \chi(\sigma) \prod_{i=1}^n a_{i\sigma(i)}
$$
for $H \subseteq S_n$, where $\chi$ is a character of degree 1 on the subgroup $H$ (cf. [[Character of a group]]) of the symmetric group $S_n$ (one obtains the [[determinant]] for $H=S_n$, $\chi =\pm 1$, in accordance with the parity of $\sigma$).

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 $(0,1)$-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:
$$
\mathrm{per}(A) = \sum_{t=0}^{n-1} (-1)^t \sum_{X \in \Gamma_{n-t}} \prod_{i=1}^m r_i(X)
$$
where $\Gamma_k$ is the set of submatrices of dimension $m \times k$ for the square matrix $A$, $r_i = r_i(X)$ is the sum of the elements of the $i$-th row of $X$ and $i,k=1,\ldots,m$.

As it is complicated to calculate permanents, estimating them is important. Some lower bounds are given below.

a) If $A$ is a $(0,1)$-matrix with $r_i(A) \ge t$, $i=1,\ldots,m$, then
$$
\mathrm{per}(A) \ge \frac{t!}{(t-m)!}
$$
for $t \ge m$, and
$$
\mathrm{per}(A) \ge t!
$$
if $t < m$ and $\mathrm{per}(A) > 0$.

b) If $A$ is a $(0,1)$-matrix of order $n$, then
$$
\mathrm{per}(A) \ge \prod_{i=1}^n \{ r_i^* + i - n \}
$$
where $r_1^* \ge \cdots \ge r_n^*$ are the sums of the elements in the rows of $A$ arranged in non-increasing order and $\{ r_i^* + i - n \} = \max(0, r_i^* + i - n )$.

c) If $A$ is a positive semi-definite Hermitian matrix of order $n$, then
$$
\mathrm{per}(A) \ge \frac{n!}{s(A)^n} \prod_{i=1}^n |r_i|^2
$$
where $s(A) = \sum_{i,j} a_{ij}$ if $s(A) > 0$.

Upper bounds for permanents:

1) For a $(0,1)$>-matrix $A$ of order $n$,
$$
\mathrm{per}(A) \le \prod_{i=1}^n (r_i!)^{1/r_1} \ .
$$
2) For a completely-indecomposable matrix $A$ of order $n$ with non-negative integer elements,
$$
\mathrm{per}(A) \le 2^{s(A)-2n} + 1 \ .
$$
3) For a complex [[normal matrix]] $A$ with eigen values $\lambda_1,\ldots,\lambda_n$,
$$
|\mathrm{per}(A)| \le \frac{1}{n}\sum_{i=1}^n |\lambda_i|^n \ .
$$

The most familiar problem in the theory of permanents was van der Waerden's conjecture: The permanent of a [[doubly-stochastic matrix]] of order $n$ is bounded from below by $n!/n^n$, and this value is attained only for the matrix composed of fractions $1/n$. 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]]), such as the  "[[problème des rencontres]]"  and the  "problème d'attachement"  (or  "hook problem" ), and also to the [[Fibonacci numbers]], the enumeration of [[Latin square]]s and [[Steiner triple system]]s, and to the derivation of the number of $1$-factors and linear subgraphs of a [[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 $(0,1)$-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) {{ZBL|0112.24806}}</TD></TR>
<TR><TD valign="top">[2]</TD> <TD valign="top">  V.N. Sachkov,   "Combinatorial methods in discrete mathematics" , Moscow  (1977)  (In Russian); translated by V. Kolchin: 
Encyclopedia of Mathematics and Its Applications '''55'''.  Cambridge University Press (1995) {{ZBL|0845.05003}}</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); 
Adv. Math. '''42''' (1981) 299-305. {{ZBL|0478.15003}}.</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. {{ZBL|0475.15007}}</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>