词条 | 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.[1] Both are special cases of a more general function of a matrix called the immanant. DefinitionThe 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, {{harvtxt|Minc|1984}} uses Per(A) for the permanent of rectangular matrices, and uses per(A) when A is a square matrix. {{harvtxt|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 {{harvtxt|Muir|1882}} in the modern, more specific, sense.[3] Properties and applicationsIf 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]
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, while expanding along the last row gives, Unlike the determinant, the permanent has no easy geometrical interpretation; it is mainly used in combinatorics, in treating boson Green's functions in quantum field theory, and in determining state probabilities of boson sampling systems[8]. However, it has two graph-theoretic interpretations: as the sum of weights of cycle covers of a directed graph, and as the sum of weights of perfect matchings in a bipartite graph. Symmetric tensorsThe permanent arises naturally in the study of the symmetric tensor power of Hilbert spaces.[9] In particular, for a Hilbert space , let denote the th symmetric tensor power of , which is the space of symmetric tensors. Note in particular that is spanned by the Symmetric products of elements in . For , we define the symmetric product of these elements by If we consider (as a subspace of , the kth tensor power of ) and define the inner product on accordingly, we find that for Applying the Cauchy–Schwarz inequality, we find that , and that Cycle coversAny square matrix can be viewed as the adjacency matrix of a weighted directed graph, with 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 cycles in the digraph that covers all vertices in the graph. Thus, each vertex i in the digraph has a unique "successor" in the cycle cover, and is a permutation on where n is the number of vertices in the digraph. Conversely, any permutation on corresponds to a cycle cover in which there is an arc from vertex i to vertex for each i. If the weight of a cycle-cover is defined to be the product of the weights of the arcs in each cycle, then The permanent of an matrix A is defined as where is a permutation over . Thus the permanent of A is equal to the sum of the weights of all cycle-covers of the digraph. Perfect matchingsA square matrix can also be viewed as the adjacency matrix of a bipartite graph which has vertices on one side and on the other side, with representing the weight of the edge from vertex to vertex . If the weight of a perfect matching that matches to is defined to be the product of the weights of the edges in the matching, then Thus the permanent of A is equal to the sum of the weights of all perfect matchings of the graph. Permanents of (0, 1) matricesEnumerationThe 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.[10] The incidence matrices of projective planes are in the class Ω(n2 + 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.[10] 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:[11] 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 = 7e and perm(A) = 24e. Permanents can also be used to calculate the number of permutations with restricted (prohibited) positions. For the standard n-set {1, 2, ..., n}, let be the (0, 1)-matrix where aij = 1 if i → j is allowed in a permutation and aij = 0 otherwise. Then perm(A) is equal to the number of permutations of the n-set that satisfy all the restrictions.[7] Two well known special cases of this are the solution of the derangement problem and the ménage problem: the number of permutations of an n-set with no fixed points (derangements) is given by where J is the n×n all 1's matrix and I is the identity matrix, and the ménage numbers are given by where I' is the (0, 1)-matrix with nonzero entries in positions (i, i + 1) and (n, 1). BoundsThe Bregman–Minc inequality, conjectured by H. Minc in 1963[12] and proved by L. M. Brégman in 1973,[13] gives an upper bound for the permanent of an n × n (0, 1)-matrix. If A has ri ones in row i for each 1 ≤ i ≤ n, the inequality states that Van der Waerden's conjectureIn 1926 Van der Waerden conjectured that the minimum permanent among all {{nowrap|n × n}} doubly stochastic matrices is n!/nn, achieved by the matrix for which all entries are equal to 1/n.[14] Proofs of this conjecture were published in 1980 by B. Gyires[15] and in 1981 by G. P. Egorychev[16] and D. I. Falikman;[17] Egorychev's proof is an application of the Alexandrov–Fenchel inequality.[18] For this work, Egorychev and Falikman won the Fulkerson Prize in 1982.[19] Computation{{main|Computing the permanent|Sharp-P-completeness of 01-permanent}}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 ({{harvtxt|Ryser|1963|loc=p. 27}}). Ryser’s method is based on an inclusion–exclusion formula that can be given[20] as follows: Let be obtained from A by deleting k columns, let be the product of the row-sums of , and let be the sum of the values of over all possible . Then It may be rewritten in terms of the matrix entries as follows: 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 , where is the value of the permanent and is arbitrary.[21] 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 ( is again the value of the permanent).[22] MacMahon's Master Theorem{{main|MacMahon Master theorem}}Another way to view permanents is via multivariate generating functions. Let be a square matrix of order n. Consider the multivariate generating function: The coefficient of in is perm(A).[23] As a generalization, for any sequence of n non-negative integers, define: as the coefficient of inMacMahon's Master Theorem relating permanents and determinants is:[24] where I is the order n identity matrix and X is the diagonal matrix with diagonal Permanents of rectangular matricesThe 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.[25] Specifically, for an m × n matrix with m ≤ n, define where P(n,m) is the set of all m-permutations of the n-set {1,2,...,n}.[26] Ryser's computational result for permanents also generalizes. If A is an m × n matrix with m ≤ n, let be obtained from A by deleting k columns, let be the product of the row-sums of , and let be the sum of the values of over all possible . Then [6] Systems of distinct representativesThe 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 S1, S2, ..., Sm 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).[27] See also
Notes1. ^{{cite journal|author=Marcus, Marvin|author2=Minc, Henryk|title=Permanents|journal=Amer. Math. Monthly|volume=72|issue=6|year=1965|pages=577–591|url=http://www.maa.org/programs/maa-awards/writing-awards/permanents|doi=10.2307/2313846|jstor=2313846}} 2. ^{{Citation| last=Cauchy | first=A. L.| title=Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu'elles renferment. |url=http://gallica.bnf.fr/ark:/12148/bpt6k90193x/f97 |journal=Journal de l'École Polytechnique |volume=10 |pages=91–169 |year=1815}} 3. ^{{harvnb|van Lint|Wilson|2001|loc=p. 108}} 4. ^{{harvnb|Ryser|1963|loc=pp. 25 – 26}} 5. ^{{harvnb|Percus|1971|loc=p. 2}} 6. ^1 {{harvnb|Ryser|1963|loc=p. 26}} 7. ^1 {{harvnb|Percus|1971|loc=p. 12}} 8. ^{{cite arXiv |last=Aaronson |first=Scott |date=14 Nov 2010 |title=The Computational Complexity of Linear Optics |eprint=1011.3245|class=quant-ph }} 9. ^{{cite book|last1=Bhatia|first1=Rajendra|title=Matrix Analysis|date=1997|publisher=Springer-Verlag|location=New York|isbn=978-0-387-94846-1|pages=16–19}} 10. ^1 {{harvnb|Ryser|1963|loc=p. 124}} 11. ^{{harvnb|Ryser|1963|loc=p. 125}} 12. ^{{citation|first=Henryk|last=Minc|title=Upper bounds for permanents of (0,1)-matrices|journal=Bulletin of the American Mathematical Society|volume=69|issue=6|year=1963|pages=789–791|doi=10.1090/s0002-9904-1963-11031-9}} 13. ^{{harvnb|van Lint|Wilson|2001|loc=p. 101}} 14. ^{{citation | last = van der Waerden | first = B. L. | author-link = Bartel Leendert van der Waerden | journal = Jber. Deutsch. Math.-Verein. | page = 117 | title = Aufgabe 45 | volume = 35 | year = 1926}}. 15. ^{{citation | last = Gyires | first = B. | issue = 3–4 | journal = Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis | mr = 604006 | pages = 291–304 | title = The common source of several inequalities concerning doubly stochastic matrices | volume = 27 | year = 1980}}. 16. ^{{citation | last = Egoryčev | first = G. P. | language = Russian | location = Krasnoyarsk | mr = 602332 | page = 12 | publisher = Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz. | title = Reshenie problemy van-der-Vardena dlya permanentov | year = 1980}}. {{citation | last = Egorychev | first = G. P. | issue = 6 | journal = Akademiya Nauk SSSR | language = Russian | mr = 638007 | pages = 65–71, 225 | title = Proof of the van der Waerden conjecture for permanents | volume = 22 | year = 1981}}. {{citation | last = Egorychev | first = G. P. | doi = 10.1016/0001-8708(81)90044-X | issue = 3 | journal = Advances in Mathematics | mr = 642395 | pages = 299–305 | title = The solution of van der Waerden's problem for permanents | volume = 42 | year = 1981}}. 17. ^{{citation | last = Falikman | first = D. I. | issue = 6 | journal = Akademiya Nauk Soyuza SSR | language = Russian | mr = 625097 | pages = 931–938, 957 | title = Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix | volume = 29 | year = 1981}}. 18. ^Brualdi (2006) p.487 19. ^Fulkerson Prize, Mathematical Optimization Society, retrieved 2012-08-19. 20. ^{{harvtxt|van Lint|Wilson|2001}} [https://books.google.com/books?id=5l5ps2JkyT0C&pg=PA108&dq=permanent+ryser&lr=#PPA99,M1 p. 99] 21. ^{{Citation|last1= Jerrum | first1= M.|author1-link= Mark Jerrum |last2=Sinclair | first2= A.|author2-link= Alistair Sinclair|last3=Vigoda | first3= E.|title=A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries |journal=Journal of the ACM |year=2004 |volume= 51 | issue= 4|pages= 671–697 | doi=10.1145/1008731.1008738| citeseerx= 10.1.1.18.9466}} 22. ^{{cite journal|last1=Chakhmakhchyan|first1=Levon|last2=Cerf|first2=Nicolas|last3=Garcia-Patron|first3=Raul|title=A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices| journal = Phys. Rev. A|volume=96 |issue=2|pages=022329 |doi=10.1103/PhysRevA.96.022329|year=2017|bibcode=2017PhRvA..96b2329C|arxiv=1609.02416}} 23. ^{{harvnb|Percus|1971|loc=p. 14}} 24. ^{{harvnb|Percus|1971|loc=p. 17}} 25. ^In particular, {{harvtxt|Minc|1984}} and {{harvtxt|Ryser|1963}} do this. 26. ^{{harvnb|Ryser|1963|loc=p. 25}} 27. ^{{harvnb|Ryser|1963|loc=p. 54}} References
Further reading
External links
4 : Algebra|Linear algebra|Matrix theory|Permutations |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。