HOME

TheInfoList



OR:

In
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matric ...
, the permanent of a
square matrix In mathematics, a square matrix is a matrix with the same number of rows and columns. An ''n''-by-''n'' matrix is known as a square matrix of order Any two square matrices of the same order can be added and multiplied. Square matrices are ofte ...
is a function of the matrix similar to the
determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if ...
. 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 matrix is defined as \operatorname(A)=\sum_\prod_^n a_. The sum here extends over all elements σ of the
symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group ...
''S''''n''; i.e. over all
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...
s of the numbers 1, 2, ..., ''n''. For example, \operatorname\begina&b \\ c&d\end=ad+bc, and \operatorname\begina&b&c \\ d&e&f \\ g&h&i \end=aei + bfg + cdh + ceg + bdi + afh. The definition of the permanent of ''A'' differs from that of the
determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if ...
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 \overset\quad \overset. The word, ''permanent'', originated with Cauchy in 1812 as “fonctions symétriques permanentes” for a related type of function, and was used by Muir and Metzler in the modern, more specific, sense.


Properties

If one views the permanent as a map that takes ''n'' vectors as arguments, then it is a
multilinear map In linear algebra, a multilinear map is a function of several variables that is linear separately in each variable. More precisely, a multilinear map is a function :f\colon V_1 \times \cdots \times V_n \to W\text where V_1,\ldots,V_n and W ar ...
and it is symmetric (meaning that any order of the vectors results in the same permanent). Furthermore, given a square matrix A = \left(a_\right) of order ''n'': * 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''T). * If A = \left(a_\right) and B=\left(b_\right) are square matrices of order ''n'' then, \operatorname\left(A + B\right) = \sum_ \operatorname \left(a_\right)_ \operatorname \left(b_\right)_, where ''s'' and ''t'' are subsets of the same size of and \bar, \bar are their respective complements in that set. * If A is a
triangular matrix In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal ar ...
, i.e. a_=0, whenever i>j or, alternatively, whenever i, then its permanent (and determinant as well) equals the product of the diagonal entries: \operatorname\left(A\right) = a_ a_ \cdots a_ = \prod_^n a_.


Relation to determinants

Laplace's
expansion by minors In linear algebra, the Laplace expansion, named after Pierre-Simon Laplace, also called cofactor expansion, is an expression of the determinant of an matrix as a weighted sum of minors, which are the determinants of some submatrices of . Spe ...
for computing the determinant along a row, column or diagonal extends to the permanent by ignoring all signs. For example, expanding along the first column, \begin \operatorname \left ( \begin 1 & 1 & 1 & 1\\2 & 1 & 0 & 0\\3 & 0 & 1 & 0\\4 & 0 & 0 & 1 \end \right ) = & 1 \cdot \operatorname \left( \begin 1&0&0\\ 0&1&0\\ 0&0&1 \end\right) + 2\cdot \operatorname \left(\begin1&1&1\\0&1&0\\0&0&1\end\right) \\ & + \ 3\cdot \operatorname \left(\begin1&1&1\\1&0&0\\0&0&1\end\right) + 4 \cdot \operatorname \left(\begin1&1&1\\1&0&0\\0&1&0\end\right) \\ = & 1(1) + 2(1) + 3(1) + 4(1) = 10, \end while expanding along the last row gives, \begin \operatorname \left ( \begin 1 & 1 & 1 & 1\\2 & 1 & 0 & 0\\3 & 0 & 1 & 0\\4 & 0 & 0 & 1 \end \right ) = & 4 \cdot \operatorname \left(\begin1&1&1\\1&0&0\\0&1&0\end\right) + 0\cdot \operatorname \left(\begin1&1&1\\2&0&0\\3&1&0\end\right) \\ & + \ 0\cdot \operatorname \left(\begin1&1&1\\2&1&0\\3&0&0\end\right) + 1 \cdot \operatorname \left( \begin 1&1&1\\ 2&1&0\\ 3&0&1\end\right) \\ = & 4(1) + 0 + 0 + 1(6) = 10. \end On the other hand, the basic multiplicative property of determinants is not valid for permanents. A simple example shows that this is so. \begin 4 &= \operatorname \left ( \begin 1 & 1 \\ 1 & 1 \end \right )\operatorname \left ( \begin 1 & 1 \\ 1 & 1 \end \right ) \\ &\neq \operatorname\left ( \left ( \begin 1 & 1 \\ 1 & 1 \end \right ) \left ( \begin 1 & 1 \\ 1 & 1 \end \right ) \right ) = \operatorname \left ( \begin 2 & 2 \\ 2 & 2 \end \right )= 8. \end Unlike the determinant, the permanent has no easy geometrical interpretation; it is mainly used in
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
, in treating boson Green's functions in
quantum field theory In theoretical physics, quantum field theory (QFT) is a theoretical framework that combines classical field theory, special relativity, and quantum mechanics. QFT is used in particle physics to construct physical models of subatomic particles a ...
, and in determining state probabilities of
boson sampling Boson sampling is a restricted model of non-universal quantum computation introduced by Scott Aaronson and Alex Arkhipov after the original work of Lidror Troyansky and Naftali Tishby, that explored possible usage of boson scattering to evaluate ...
systems. However, it has two graph-theoretic interpretations: as the sum of weights of cycle covers of a
directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pai ...
, and as the sum of weights of perfect matchings in a
bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...
.


Applications


Symmetric tensors

The permanent arises naturally in the study of the symmetric tensor power of Hilbert spaces. In particular, for a Hilbert space H, let \vee^k H denote the kth symmetric tensor power of H, which is the space of symmetric tensors. Note in particular that \vee^k H is spanned by the symmetric products of elements in H. For x_1,x_2,\dots,x_k \in H, we define the symmetric product of these elements by x_1 \vee x_2 \vee \cdots \vee x_k = (k!)^ \sum_ x_ \otimes x_ \otimes \cdots \otimes x_ If we consider \vee^k H (as a subspace of \otimes^kH, the ''k''th
tensor power In mathematics, the tensor algebra of a vector space ''V'', denoted ''T''(''V'') or ''T''(''V''), is the algebra of tensors on ''V'' (of any rank) with multiplication being the tensor product. It is the free algebra on ''V'', in the sense of being ...
of H) and define the inner product on \vee^kH accordingly, we find that for x_j,y_j \in H \langle x_1 \vee x_2 \vee \cdots \vee x_k, y_1 \vee y_2 \vee \cdots \vee y_k \rangle = \operatorname\left langle x_i,y_j \rangle\right^k Applying the
Cauchy–Schwarz inequality The Cauchy–Schwarz inequality (also called Cauchy–Bunyakovsky–Schwarz inequality) is considered one of the most important and widely used inequalities in mathematics. The inequality for sums was published by . The corresponding inequality f ...
, we find that \operatorname \left langle x_i,x_j \rangle\right^k \geq 0, and that \left, \operatorname \left langle x_i,y_j \rangle\right^k \^2 \leq \operatorname \left langle x_i,x_j \rangle\right^k \cdot \operatorname \left langle y_i,y_j \rangle\right^k


Cycle covers

Any square matrix A = (a_)_^n can be viewed as the
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple ...
of a weighted
directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pai ...
on vertex set V=\, with a_ representing the weight of the arc from vertex ''i'' to vertex ''j''. A cycle cover of a weighted directed graph is a collection of vertex-disjoint
directed cycle Director may refer to: Literature * ''Director'' (magazine), a British magazine * ''The Director'' (novel), a 1971 novel by Henry Denker * ''The Director'' (play), a 2000 play by Nancy Hasty Music * Director (band), an Irish rock band * ''D ...
s in the digraph that covers all vertices in the graph. Thus, each vertex ''i'' in the digraph has a unique "successor" \sigma(i) in the cycle cover, and so \sigma represents a
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...
on ''V''. Conversely, any permutation \sigma on ''V'' corresponds to a cycle cover with arcs from each vertex ''i'' to vertex \sigma(i). If the weight of a cycle-cover is defined to be the product of the weights of the arcs in each cycle, then \operatorname(\sigma) = \prod_^n a_, implying that \operatorname(A)=\sum_\sigma \operatorname(\sigma). Thus the permanent of ''A'' is equal to the sum of the weights of all cycle-covers of the digraph.


Perfect matchings

A square matrix A = (a_) can also be viewed as the
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple ...
of a
bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...
which has vertices x_1, x_2, \dots, x_n on one side and y_1, y_2, \dots, y_n on the other side, with a_ representing the weight of the edge from vertex x_i to vertex y_j. If the weight of a
perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
\sigma that matches x_i to y_ is defined to be the product of the weights of the edges in the matching, then \operatorname(\sigma) = \prod_^n a_. Thus the permanent of ''A'' is equal to the sum of the weights of all perfect matchings of the graph.


Permanents of (0, 1) matrices


Enumeration

The answers to many counting questions can be computed as permanents of matrices that only have 0 and 1 as entries. Let Ω(''n'',''k'') be the class of all (0, 1)-matrices of order ''n'' with each row and column sum equal to ''k''. Every matrix ''A'' in this class has perm(''A'') > 0. The incidence matrices of
projective plane In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that ...
s are in the class Ω(''n''2 + ''n'' + 1, ''n'' + 1) for ''n'' an integer > 1. The permanents corresponding to the smallest projective planes have been calculated. For ''n'' = 2, 3, and 4 the values are 24, 3852 and 18,534,400 respectively. Let ''Z'' be the incidence matrix of the projective plane with ''n'' = 2, the Fano plane. Remarkably, perm(''Z'') = 24 = , det (''Z''), , the absolute value of the determinant of ''Z''. This is a consequence of ''Z'' being a circulant matrix and the theorem: :If ''A'' is a circulant matrix in the class Ω(''n'',''k'') then if ''k'' > 3, perm(''A'') > , det (''A''), and if ''k'' = 3, perm(''A'') = , det (''A''), . Furthermore, when ''k'' = 3, by permuting rows and columns, ''A'' can be put into the form of a direct sum of ''e'' copies of the matrix ''Z'' and consequently, ''n'' = 7''e'' and perm(''A'') = 24e. Permanents can also be used to calculate the number of
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...
s with restricted (prohibited) positions. For the standard ''n''-set , let A = (a_) be the (0, 1)-matrix where ''a''''ij'' = 1 if ''i'' → ''j'' is allowed in a permutation and ''a''''ij'' = 0 otherwise. Then perm(''A'') is equal to the number of permutations of the ''n''-set that satisfy all the restrictions. Two well known special cases of this are the solution of the derangement problem and the
ménage problem In combinatorial mathematics, the ménage problem or problème des ménages asks for the number of different ways in which it is possible to seat a set of male-female couples at a round dining table so that men and women alternate and nobody sits ...
: the number of permutations of an ''n''-set with no fixed points (derangements) is given by \operatorname(J - I) = \operatorname\left (\begin 0 & 1 & 1 & \dots & 1 \\ 1 & 0 & 1 & \dots & 1 \\ 1 & 1 & 0 & \dots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \dots & 0 \end \right) = n! \sum_^n \frac, where ''J'' is the ''n''×''n'' all 1's matrix and ''I'' is the identity matrix, and the ménage numbers are given by \begin \operatorname(J - I - I') & = \operatorname\left (\begin 0 & 0 & 1 & \dots & 1 \\ 1 & 0 & 0 & \dots & 1 \\ 1 & 1 & 0 & \dots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 1 & 1 & \dots & 0 \end \right) \\ & = \sum_^n (-1)^k \frac (n-k)!, \end where ''I is the (0, 1)-matrix with nonzero entries in positions (''i'', ''i'' + 1) and (''n'', 1).


Bounds

The
Bregman–Minc inequality In discrete mathematics, the Bregman–Minc inequality, or Bregman's theorem, allows one to estimate the permanent of a binary matrix via its row or column sums. The inequality was conjectured in 1963 by Henryk Minc and first proved in 1973 by Lev ...
, conjectured by H. Minc in 1963 and proved by L. M. Brégman in 1973, gives an upper bound for the permanent of an ''n'' × ''n'' (0, 1)-matrix. If ''A'' has ''r''''i'' ones in row ''i'' for each 1 ≤ ''i'' ≤ ''n'', the inequality states that \operatorname A \leq \prod_^n (r_i)!^.


Van der Waerden's conjecture

In 1926, Van der Waerden conjectured that the minimum permanent among all doubly stochastic matrices is ''n''!/''n''''n'', achieved by the matrix for which all entries are equal to 1/''n''. Proofs of this conjecture were published in 1980 by B. Gyires and in 1981 by G. P. Egorychev and D. I. Falikman; Egorychev's proof is an application of the Alexandrov–Fenchel inequality.Brualdi (2006) p.487 For this work, Egorychev and Falikman won the
Fulkerson Prize The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...
in 1982.


Computation

The naïve approach, using the definition, of computing permanents is computationally infeasible even for relatively small matrices. One of the fastest known algorithms is due to H. J. Ryser. Ryser's method is based on an inclusion–exclusion formula that can be given as follows: Let A_k be obtained from ''A'' by deleting ''k'' columns, let P(A_k) be the product of the row-sums of A_k, and let \Sigma_k be the sum of the values of P(A_k) over all possible A_k. Then \operatorname(A)=\sum_^ (-1)^ \Sigma_k. It may be rewritten in terms of the matrix entries as follows: \operatorname (A) = (-1)^n \sum_ (-1)^ \prod_^n \sum_ a_. The permanent is believed to be more difficult to compute than the determinant. While the determinant can be computed in
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
by
Gaussian elimination In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
, 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 Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speaking, ...
polynomial time, up to an error of \varepsilon M, where M is the value of the permanent and \varepsilon > 0 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 \varepsilon\sqrt (M is again the value of the permanent).


MacMahon's master theorem

Another way to view permanents is via multivariate
generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary ser ...
s. Let A = (a_) be a square matrix of order ''n''. Consider the multivariate generating function: \begin F(x_1,x_2,\dots,x_n) &= \prod_^n \left ( \sum_^n a_ x_j \right ) \\ &= \left( \sum_^n a_ x_j \right ) \left ( \sum_^n a_ x_j \right ) \cdots \left ( \sum_^n a_ x_j \right). \end The coefficient of x_1 x_2 \dots x_n in F(x_1,x_2,\dots,x_n) is perm(''A''). As a generalization, for any sequence of ''n'' non-negative integers, s_1,s_2,\dots,s_n define: \operatorname^(A) as the coefficient of x_1^ x_2^ \cdots x_n^ in\left ( \sum_^n a_ x_j \right )^ \left ( \sum_^n a_ x_j \right )^ \cdots \left ( \sum_^n a_ x_j \right )^. MacMahon's master theorem relating permanents and determinants is: \operatorname^(A) = \textx_1^ x_2^ \cdots x_n^ \text \frac, where ''I'' is the order ''n'' identity matrix and ''X'' is the diagonal matrix with diagonal _1,x_2,\dots,x_n


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 A = (a_) with ''m'' ≤ ''n'', define \operatorname (A) = \sum_ a_ a_ \ldots a_ where P(''n'',''m'') is the set of all ''m''-permutations of the ''n''-set . Ryser's computational result for permanents also generalizes. If ''A'' is an ''m'' × ''n'' matrix with ''m'' ≤ ''n'', let A_k be obtained from ''A'' by deleting ''k'' columns, let P(A_k) be the product of the row-sums of A_k, and let \sigma_k be the sum of the values of P(A_k) over all possible A_k. Then \operatorname(A)=\sum_^ (-1)^\binom\sigma_.


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'').


See also

* Computing the permanent * Bapat–Beg theorem, an application of permanents in order statistics * Slater determinant, an application of permanents in
quantum mechanics Quantum mechanics is a fundamental theory in physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles. It is the foundation of all quantum physics including quantum chemistry, q ...
* Hafnian


Notes


References

* * * * * *


Further reading

* Contains a proof of the Van der Waerden conjecture. *


External links

* *{{PlanetMath , urlname=VanDerWaerdensPermanentConjecture , title=Van der Waerden's permanent conjecture Algebra Linear algebra Matrix theory Permutations