Английская Википедия:Computing the permanent

Шаблон:Short description In linear algebra, the computation of the permanent of a matrix is a problem that is thought to be more difficult than the computation of the determinant of a matrix despite the apparent similarity of the definitions.

The permanent is defined similarly to the determinant, as a sum of products of sets of matrix entries that lie in distinct rows and columns. However, where the determinant weights each of these products with a ±1 sign based on the parity of the set, the permanent weights them all with a +1 sign.

While the determinant can be computed in polynomial time by Gaussian elimination, it is generally believed that the permanent cannot be computed in polynomial time. In computational complexity theory, a theorem of Valiant states that computing permanents is #P-hard, and even #P-complete for matrices in which all entries are 0 or 1 Шаблон:Harvtxt. This puts the computation of the permanent in a class of problems believed to be even more difficult to compute than NP. It is known that computing the permanent is impossible for logspace-uniform ACC⁰ circuits.Шаблон:Harv

The development of both exact and approximate algorithms for computing the permanent of a matrix is an active area of research.

Definition and naive algorithm

The permanent of an n-by-n matrix A = (a_i,j) is defined as

<math> \operatorname{perm}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.</math>

The sum here extends over all elements σ of the symmetric group S_n, i.e. over all permutations of the numbers 1, 2, ..., n. This formula differs from the corresponding formula for the determinant only in that, in the determinant, each product is multiplied by the sign of the permutation σ while in this formula each product is unsigned. The formula may be directly translated into an algorithm that naively expands the formula, summing over all permutations and within the sum multiplying out each matrix entry. This requires n! n arithmetic operations.

Ryser formula

The best known^[1] general exact algorithm is due to Шаблон:Harvs. Ryser's method is based on an inclusion–exclusion formula that can be given^[2] as follows: Let <math>A_k</math> be obtained from A by deleting k columns, let <math>P(A_k)</math> be the product of the row-sums of <math>A_k</math>, and let <math>\Sigma_k</math> be the sum of the values of <math>P(A_k)</math> over all possible <math>A_k</math>. Then

<math> \operatorname{perm}(A) = \sum_{k=0}^{n-1} (-1)^k \Sigma_k.</math>

It may be rewritten in terms of the matrix entries as follows^[3]

<math>\operatorname{perm} (A) = (-1)^n \sum_{S\subseteq\{1,\dots,n\}} (-1)^{|S|} \prod_{i=1}^n \sum_{j\in S} a_{ij}.</math>

Ryser's formula can be evaluated using <math>O(2^{n-1}n^2)</math> arithmetic operations, or <math>O(2^{n-1}n)</math> by processing the sets <math>S</math> in Gray code order.^[4]

Balasubramanian–Bax–Franklin–Glynn formula

Another formula that appears to be as fast as Ryser's (or perhaps even twice as fast) is to be found in the two Ph.D. theses; see Шаблон:Harv, Шаблон:Harv; also Шаблон:Harv. The methods to find the formula are quite different, being related to the combinatorics of the Muir algebra, and to finite difference theory respectively. Another way, connected with invariant theory is via the polarization identity for a symmetric tensor Шаблон:Harv. The formula generalizes to infinitely many others, as found by all these authors, although it is not clear if they are any faster than the basic one. See Шаблон:Harv.

The simplest known formula of this type (when the characteristic of the field is not two) is

<math>\operatorname{perm}(A) = \frac{1}{2^{n-1}} \left[\sum_\delta \left(\prod_{k=1}^n \delta_k\right) \prod_{j=1}^n \sum_{i=1}^n \delta_i a_{ij}\right],</math>

where the outer sum is over all <math>2^{n-1}</math> vectors <math>\delta=(\delta_1=1,\delta_2,\dots,\delta_n)\in \{\pm1\}^n</math>.

Special cases

Planar and K_3,3-free

The number of perfect matchings in a bipartite graph is counted by the permanent of the graph's biadjacency matrix, and the permanent of any 0-1 matrix can be interpreted in this way as the number of perfect matchings in a graph. For planar graphs (regardless of bipartiteness), the FKT algorithm computes the number of perfect matchings in polynomial time by changing the signs of a carefully chosen subset of the entries in the Tutte matrix of the graph, so that the Pfaffian of the resulting skew-symmetric matrix (the square root of its determinant) is the number of perfect matchings. This technique can be generalized to graphs that contain no subgraph homeomorphic to the complete bipartite graph K_3,3.^[5]

George Pólya had asked the question^[6] of when it is possible to change the signs of some of the entries of a 01 matrix A so that the determinant of the new matrix is the permanent of A. Not all 01 matrices are "convertible" in this manner; in fact it is known (Шаблон:Harvtxt) that there is no linear map <math>T</math> such that <math>\operatorname{per} T(A) = \det A</math> for all <math>n\times n</math> matrices <math>A</math>. The characterization of "convertible" matrices was given by Шаблон:Harvtxt who showed that such matrices are precisely those that are the biadjacency matrix of bipartite graphs that have a Pfaffian orientation: an orientation of the edges such that for every even cycle <math>C</math> for which <math>G\setminus C</math> has a perfect matching, there are an odd number of edges directed along C (and thus an odd number with the opposite orientation). It was also shown that these graphs are exactly those that do not contain a subgraph homeomorphic to <math>K_{3,3}</math>, as above.

Computation modulo a number

Modulo 2, the permanent is the same as the determinant, as <math>(-1) \equiv 1 \pmod 2.</math> It can also be computed modulo <math>2^k</math> in time <math>O(n^{4k-3})</math> for <math>k \ge 2</math>. However, it is UP-hard to compute the permanent modulo any number that is not a power of 2. Шаблон:Harvtxt

There are various formulae given by Шаблон:Harvtxt for the computation modulo a prime Шаблон:Mvar. First, there is one using symbolic calculations with partial derivatives.

Second, for Шаблон:Mvar = 3 there is the following formula for an n×n-matrix <math>A</math>, involving the matrix's principal minors (Шаблон:Harvtxt):

<math>\operatorname{per} (A) = (-1)^n \Sigma_{J\subseteq\{1,\dots,n\}} \det(A_J)\det(A_\bar{J}),</math>

where <math>A_J</math> is the submatrix of <math>A</math> induced by the rows and columns of <math>A</math> indexed by <math>J</math>, and <math>\bar J</math> is the complement of <math>J</math> in <math>\{1, \dots, n\}</math>, while the determinant of the empty submatrix is defined to be 1.

The expansion above can be generalized in an arbitrary characteristic p as the following pair of dual identities: <math display="block">\begin{align}

 \operatorname{per} (A) &= (-1)^n \Sigma_{{J_1}, \ldots ,{J_{p-1}}} \det(A_{J_1})\dotsm\det(A_{J_{p-1}}) \\
               \det (A) &= (-1)^n \Sigma_{{J_1}, \ldots ,{J_{p-1}}} \operatorname{per}(A_{J_1})\dotsm\operatorname{per}(A_{J_{p-1}})

\end{align}</math> where in both formulas the sum is taken over all the (p − 1)-tuples <math>{J_1}, \ldots, {J_{p-1}}</math> that are partitions of the set <math>\{1, \dots, n\}</math> into p − 1 subsets, some of them possibly empty.

The former formula possesses an analog for the hafnian of a symmetric <math>A</math> and an odd p:

<math display="block">\operatorname{haf}^2(A) = (-1)^n \Sigma_{{J_1},\ldots,{J_{p-1}}} \det(A_{J_1})\dotsm\det(A_{J_{p-1}})(-1)^{|J_1|+\dots+|J_{(p-1)/2}|}</math>

with the sum taken over the same set of indexes. Moreover, in characteristic zero a similar convolution sum expression involving both the permanent and the determinant yields the Hamiltonian cycle polynomial (defined as <math display="inline"> \operatorname{ham}(A) = \sum_{\sigma\in H_n}\prod_{i=1}^n a_{i,\sigma(i)}</math> where <math>H_n</math> is the set of n-permutations having only one cycle): <math display="block">\operatorname{ham} (A) = \Sigma_{J\subseteq \{2,\dots,n\}} \det(A_J)\operatorname{per}(A_\bar{J})(-1)^{|J|}.</math>

In characteristic 2 the latter equality turns into <math>\operatorname{ham} (A) = \Sigma_{J\subseteq \{2,\dots,n\}} \det(A_J)\operatorname{det}(A_\bar{J})</math> what therefore provides an opportunity to polynomial-time calculate the Hamiltonian cycle polynomial of any unitary <math>U</math> (i.e. such that <math>U^\textsf{T} U = I</math> where <math>I</math> is the identity n×n-matrix), because each minor of such a matrix coincides with its algebraic complement: <math>\operatorname{ham} (U) = \operatorname{det}^2(U + I_{/1})</math> where <math>I_{/1}</math> is the identity n×n-matrix with the entry of indexes 1,1 replaced by 0. Moreover, it may, in turn, be further generalized for a unitary n×n-matrix <math>U</math> as <math>\operatorname{ham_K} (U) = \operatorname{det}^2(U + I_{/K})</math> where <math>K</math> is a subset of {1, ..., n}, <math>I_{/K}</math> is the identity n×n-matrix with the entries of indexes k,k replaced by 0 for all k belonging to <math>K</math>, and we define <math display="inline">\operatorname{ham_K}(A) = \sum_{\sigma \in H_n(K)} \prod_{i=1}^n a_{i,\sigma(i)}</math> where <math>H_n(K)</math> is the set of n-permutations whose each cycle contains at least one element of <math>K</math>.

This formula also implies the following identities over fields of characteristic 3:

for any invertible <math>A</math>

<math>\operatorname{per}(A^{-1})\operatorname{det}^2(A) = \operatorname{per}(A);</math>

for any unitary <math>U</math>, that is, a square matrix <math>U</math> such that <math>U^\textsf{T} U = I</math> where <math>I</math> is the identity matrix of the corresponding size,

<math>\operatorname{per}^2(U) = \det(U + V)\det(-U)</math>

where <math>V</math> is the matrix whose entries are the cubes of the corresponding entries of <math>U</math>.

It was also shown (Шаблон:Harvtxt) that, if we define a square matrix <math>A</math> as k-semi-unitary when <math>\operatorname{rank}(A^\textsf{T} A - I) = k</math>, the permanent of a 1-semi-unitary matrix is computable in polynomial time over fields of characteristic 3, while for Шаблон:Mvar > 1 the problem becomes #3-P-complete. (A parallel theory concerns the Hamiltonian cycle polynomial in characteristic 2: while computing it on the unitary matrices is polynomial-time feasible, the problem is #2-P-complete for the k-semi-unitary ones for any k > 0). The latter result was essentially extended in 2017 (Шаблон:Harvtxt) and it was proven that in characteristic 3 there is a simple formula relating the permanents of a square matrix and its partial inverse (for <math>A_{11}</math> and <math>A_{22}</math> being square, <math>A_{11}</math> being invertible):

 \operatorname{per}\begin{pmatrix}A_{11} & A_{12}\\ A_{21} & A_{22}\end{pmatrix} =
 \operatorname{det}^2(A_{11})\operatorname{per}\begin{pmatrix}A_{11}^{-1} & A_{11}^{-1}A_{12}\\ A_{21}A_{11}^{-1} & A_{22}-A_{21}A_{11}^{-1}A_{12} \end{pmatrix}

</math>

and it allows to polynomial-time reduce the computation of the permanent of an n×n-matrix with a subset of k or k − 1 rows expressible as linear combinations of another (disjoint) subset of k rows to the computation of the permanent of an (n − k)×(n − k)- or (n − k + 1)×(n − k + 1)-matrix correspondingly, hence having introduced a compression operator (analogical to the Gaussian modification applied for calculating the determinant) that "preserves" the permanent in characteristic 3. (Analogically, it would be worth noting that the Hamiltonian cycle polynomial in characteristic 2 does possess its invariant matrix compressions as well, taking into account the fact that ham(A) = 0 for any n×n-matrix A having three equal rows or, if n > 2, a pair of indexes i,j such that its i-th and j-th rows are identical and its i-th and j-th columns are identical too.) The closure of that operator defined as the limit of its sequential application together with the transpose transformation (utilized each time the operator leaves the matrix intact) is also an operator mapping, when applied to classes of matrices, one class to another. While the compression operator maps the class of 1-semi-unitary matrices to itself and the classes of unitary and 2-semi-unitary ones, the compression-closure of the 1-semi-unitary class (as well as the class of matrices received from unitary ones through replacing one row by an arbitrary row vector — the permanent of such a matrix is, via the Laplace expansion, the sum of the permanents of 1-semi-unitary matrices and, accordingly, polynomial-time computable) is yet unknown and tensely related to the general problem of the permanent's computational complexity in characteristic 3 and the chief question of P versus NP: as it was shown in (Шаблон:Harvtxt), if such a compression-closure is the set of all square matrices over a field of characteristic 3 or, at least, contains a matrix class the permanent's computation on is #3-P-complete (like the class of 2-semi-unitary matrices) then the permanent is computable in polynomial time in this characteristic.

Besides, the problem of finding and classifying any possible analogs of the permanent-preserving compressions existing in characteristic 3 for other prime characteristics was formulated (Шаблон:Harvtxt), while giving the following identity for an n×n matrix <math>A</math> and two n-vectors (having all their entries from the set {0, ..., p − 1}) <math>\alpha</math> and <math>\beta</math> such that <math display="inline">{\sum_{i=1}^n \alpha_i = \sum_{j=1}^n \beta_j}</math>, valid in an arbitrary prime characteristic p:

 \operatorname{per}(A^{(\alpha, \beta)})
 = \det^{p-1}(A)
   \operatorname{per}(A^{-1})^{((p - 1)\vec{1}_n - \beta, (p-1)\vec{1}_n - \alpha)}
   \left(\prod_{i=1}^n\alpha_i!\right)
   \left(\prod_{j=1}^n\beta_j!\right)
   (-1)^{n+\sum_{i=1}^n\alpha_i}

</math>

where for an n×m-matrix <math>M</math>, an n-vector <math>x</math> and an m-vector <math>y</math>, both vectors having all their entries from the set {0, ..., p − 1}, <math>M^{(x,y)}</math> denotes the matrix received from <math>M</math> via repeating <math>x_i</math> times its i-th row for i = 1, ..., n and <math>y_j</math> times its j-th column for j = 1, ..., m (if some row's or column's multiplicity equals zero it would mean that the row or column was removed, and thus this notion is a generalization of the notion of submatrix), and <math>\vec{1}_n</math> denotes the n-vector all whose entries equal unity. This identity is an exact analog of the classical formula expressing a matrix's minor through a minor of its inverse and hence demonstrates (once more) a kind of duality between the determinant and the permanent as relative immanants. (Actually its own analogue for the hafnian of a symmetric <math>A</math> and an odd prime p is <math display="inline">\operatorname{haf}^2(A^{ (\alpha, \alpha)}) = \det^{p-1}(A) \operatorname{haf}^2(A^{-1})^{((p - 1)\vec{1}_n - \alpha, (p - 1)\vec{1}_n - \alpha)} \left(\prod_{i=1}^n \alpha_i!\right)^2 (-1)^{n(p - 1)/2 + n + \sum_{i=1}^n\alpha_i}</math>).

And, as an even wider generalization for the partial inverse case in a prime characteristic p, for <math>A_{11}</math>, <math>A_{22}</math> being square, <math>A_{11}</math> being invertible and of size <math>{n_1}</math>x<math>{n_1}</math>, and <math display="inline">{\sum_{i=1}^n \alpha_i = \sum_{j=1}^n \beta_j}</math>, there holds also the identity

   \operatorname{per} \begin{pmatrix}A_{11} & A_{12}\\ A_{21} & A_{22}\end{pmatrix} ^{ ( \alpha , \beta  )}
 = {\det}^{p-1}(A_{11}) \operatorname{per} \begin{pmatrix} A_{11}^{-1} & A_{11}^{-1} A_{12} \\ A_{21} A_{11}^{-1} & A_{22} - A_{21} A_{11}^{-1} A_{12}\end{pmatrix}^{((p-1)\vec{1}_n - \beta, (p - 1)\vec{1}_n - \alpha)}
   \left(\prod_{i=1}^n\alpha_{1,i}!\right)\left(\prod_{j=1}^n\beta_{1,j}!\right) (-1)^{n_1 + \sum_{i=1}^{n}\alpha_{1,i}}

</math>

where the common row/column multiplicity vectors <math>\alpha</math> and <math>\beta</math> for the matrix <math>A</math> generate the corresponding row/column multiplicity vectors <math>\alpha_s</math> and <math>\beta_t</math>, s,t = 1,2, for its blocks (the same concerns <math>A</math>'s partial inverse in the equality's right side).

Approximate computation

When the entries of A are nonnegative, the permanent can be computed approximately in probabilistic polynomial time, up to an error of εM, where M is the value of the permanent and ε > 0 is arbitrary. In other words, there exists a fully polynomial-time randomized approximation scheme (FPRAS) (Шаблон:Harvtxt).

The most difficult step in the computation is the construction of an algorithm to sample almost uniformly from the set of all perfect matchings in a given bipartite graph: in other words, a fully polynomial almost uniform sampler (FPAUS). This can be done using a Markov chain Monte Carlo algorithm that uses a Metropolis rule to define and run a Markov chain whose distribution is close to uniform, and whose mixing time is polynomial.

It is possible to approximately count the number of perfect matchings in a graph via the self-reducibility of the permanent, by using the FPAUS in combination with a well-known reduction from sampling to counting due to Шаблон:Harvtxt. Let <math>M(G)</math> denote the number of perfect matchings in <math>G</math>. Roughly, for any particular edge <math>e</math> in <math>G</math>, by sampling many matchings in <math>G</math> and counting how many of them are matchings in <math>G \setminus e</math>, one can obtain an estimate of the ratio <math display="inline">\rho=\frac{M(G)}{M(G \setminus e)}</math>. The number <math>M(G)</math> is then <math>\rho M(G \setminus e)</math>, where <math> M(G \setminus e)</math> can be approximated by applying the same method recursively.

Another class of matrices for which the permanent is of particular interest, is the positive-semidefinite matrices.^[7] Using a technique of Stockmeyer counting, they can be computed within the class <math>\textsf{BPP}^\textsf{NP}</math>, but this is considered a feasible class in general. It is NP-hard to approximate permanents of PSD matrices within a subexponential factor, and it is conjectured to be <math>\textsf{BPP}^\textsf{NP}</math>-hard^[8] If further constraints on the spectrum are imposed, there are more efficient algorithms known. One randomized algorithm is based on the model of boson sampling and it uses the tools proper to quantum optics, to represent the permanent of positive-semidefinite matrices as the expected value of a specific random variable. The latter is then approximated by its sample mean.^[9] This algorithm, for a certain set of positive-semidefinite matrices, approximates their permanent in polynomial time up to an additive error, which is more reliable than that of the standard classical polynomial-time algorithm by Gurvits.^[10]

Notes

Шаблон:Reflist

References

Шаблон:Refbegin

Шаблон:Refend

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Английская Википедия:Computing the permanent

Содержание

Definition and naive algorithm

Ryser formula

Balasubramanian–Bax–Franklin–Glynn formula

Special cases

Planar and K_3,3-free

Computation modulo a number

Approximate computation

Notes

References

Further reading

Навигация

Действия на странице

Действия на странице

Персональные инструменты

Навигация

Поиск

Инструменты

Английская Википедия:Computing the permanent

Definition and naive algorithm

Ryser formula

Balasubramanian–Bax–Franklin–Glynn formula

Special cases

Planar and K3,3-free

Computation modulo a number

Approximate computation

Notes

References

Further reading

Навигация

Поиск

Planar and K_3,3-free