Permanent

The permanent denotes an object from linear algebra . For matrices similar to the determinant, it is defined as a polynomial in the entries of the matrix.

definition

Let A be a matrix, then the permanent is defined as ${\displaystyle (n\times n)}$ ${\displaystyle \operatorname {perm} (A)}$

${\displaystyle \operatorname {perm} (A):=\sum _{\sigma \in S_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$,

where the sum extends over all elements of the symmetrical group . ${\displaystyle \sigma }$ ${\displaystyle S_{n}}$

Except for the missing sign of the individual summands, this definition corresponds to that of the determinant .

Applications

In contrast to the determinant, no simple geometric interpretation is known. Applications can be found mainly in combinatorics , for example in the calculation of pairings of bipartite graphs . In quantum mechanics, although rarely used, it represents the bosonic counterpart to the fermionic Slater determinant .

Calculation effort

Another difference to the determinant is the computational complexity . The polynomial algorithm for calculating the determinant (see Gaussian algorithm ) cannot be used for the permanent. From a special case for binary matrices one can conclude that a polynomial algorithm for the permanent would be equivalent to the statement FP = #P for complexity classes (a stronger statement than P = NP ).

properties

The permanent is multilinear, fully symmetrical and normalized. A square matrix is written in columns as : ${\displaystyle A=(v_{1},\ldots ,v_{n})}$

• It is multilinear , i.e. H. linear in each column:

The following applies to all : ${\displaystyle v_{1},\ldots ,v_{n},w\in V}$

${\displaystyle {\begin{aligned}&\operatorname {perm} (v_{1},\ldots ,v_{i-1},v_{i}+w,v_{i+1},\ldots ,v_{n})\\&=\operatorname {perm} (v_{1},\ldots ,v_{i-1},v_{i},v_{i+1},\ldots ,v_{n})+\operatorname {perm} (v_{1},\ldots ,v_{i-1},w,v_{i+1},\ldots ,v_{n})\end{aligned}}}$

This applies to everyone and everyone ${\displaystyle v_{1},\ldots ,v_{n}\in V}$ ${\displaystyle r\in K}$

${\displaystyle \operatorname {perm} (v_{1},\ldots ,v_{i-1},r\cdot v_{i},v_{i+1},\ldots ,v_{n})=r\cdot \operatorname {perm} (v_{1},\ldots ,v_{i-1},v_{i},v_{i+1},\ldots ,v_{n})}$

• It is fully symmetrical :

Nothing changes if you swap two columns:

The following applies to everyone and everyone : ${\displaystyle v_{1},\ldots ,v_{n}\in V}$ ${\displaystyle i,j\in \{1,\ldots ,n\},i\neq j}$

${\displaystyle \operatorname {perm} (v_{1},\ldots ,v_{i},\ldots ,v_{j},\ldots ,v_{n})=\operatorname {perm} (v_{1},\ldots ,v_{j},\ldots ,v_{i},\ldots ,v_{n})\,}$

• It is normalized , i.e. H. the identity matrix has the permanent 1:

${\displaystyle \operatorname {perm} (E_{n})=1}$

generalization

As with the determinant, the permanent is a special case of an immanent . For a complex character the symmetric group is defined as ${\displaystyle \chi :S_{n}\rightarrow \mathbb {C} }$

${\displaystyle \operatorname {imm} _{\chi }(A):=\sum _{\sigma \in S_{n}}\chi (\sigma )\prod _{i=1}^{n}a_{i,\sigma (i)}.}$

The permanent results from the choice of the trivial character, the determinant from the choice of the sign function ; these two possibilities are special in that they are the only one-dimensional representations of the symmetric group.

Web links

• Entry at Mathworld (English)
• Derangements revisited - applying permanents to a combinatorial problem.