Permanent

From Wikipedia, the free encyclopedia

For the hair treatment see Permanent wave.

Look up permanent in Wiktionary, the free dictionary.

In linear algebra, the permanent of an n-by-n matrix A=(a_i,j) is defined as

$\operatorname{perm}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}$

The sum here extends over all elements σ of the symmetric group S_n, i.e. over all permutations of the numbers 1,2,...,n.

For example,

$\operatorname{perm}\begin{pmatrix}a&b\\ c&d\end{pmatrix}=ad+bc.$

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. If 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). A formula similar to Laplace's for the development of a determinant along a row or column is also valid for the permanent; all signs have to be ignored for the permanent.

Unlike the determinant, the permanent has no easy geometrical interpretation; it is mainly used in combinatorics. The permanent describes the number of perfect matchings in a bipartite graph. More specifically, let G be a bipartite graph with vertices A₁, A₂, ..., A_n on one side and B₁, B₂, ..., B_n on the other side. Then, G can be described by an n-by-n matrix A=(a_i,j) where a_i,j = 1 if there is an edge between the vertices A_i and B_j and a_i,j = 0 otherwise. The permanent of this matrix is equal to the number of perfect matchings in the graph.

The permanent is also more difficult to compute than the determinant. The determinant can be computed in polynomial time by Gaussian elimination. The permanent cannot be computed by Gaussian elimination. Moreover, computing the permanent of a 0-1 matrix (matrix whose entries are 0 or 1) is #P-complete (proof). Thus, if the permanent can be computed in polynomial time by any method, then P=#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 εM, where M is the value of the permanent and ε>0 is arbitrary.

Retrieved from "http://en.wikipedia.org../../../p/e/r/Permanent.html"

Categories: Algebra | Linear algebra | Matrix theory | Permutations

Permanent

From Wikipedia, the free encyclopedia

Views

Navigation

interaction

Search

In other languages