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. Both are special cases of a more general function of a matrix called the immanant.
Definition The permanent of an n×n matrix A = (ai,j) is defined as
perm ( A ) = ∑ σ ∈ S n ∏ i = 1 n a i , σ ( i ) . {\displaystyle \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 Sn; i.e., over all permutations of the numbers 1, 2, ..., n. For example,
perm ( a b c d ) = a d + b c , {\displaystyle \operatorname {perm} {\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc,}
and
perm ( a b c d e f g h i ) = a e i + b f g + c d h + c e g + b d i + a f h . {\displaystyle \operatorname {perm} {\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=aei+bfg+cdh+ceg+bdi+afh.}
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 by per A, perm A, or Per A. Minc uses Per(A) for the permanent of a rectangular matrix, and per(A) when A is a square matrix. Muir and Metzler use the notation | + | + {\displaystyle {\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 more specific modern sense.
Properties 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). Furthermore, given a square matrix A = ( a i j ) {\displaystyle A=\left(a_{ij}\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 λ changes perm(A) to λ⋅perm(A), perm(A) is invariant under transposition, that is, perm(A) = perm(AT). If A = ( a i j ) {\displaystyle A=\left(a_{ij}\right)} and B = ( b i j ) {\displaystyle B=\left(b_{ij}\right)} are square matrices of order n, then perm ( A + B ) = ∑ s , t perm ( a i j ) i ∈ s , j ∈ t perm ( b i j ) i ∈ s ¯ , j ∈ t ¯ , {\displaystyle \operatorname {perm} \left(A+B\right)=\sum _{s,t}\operatorname {perm} \left(a_{ij}\right)_{i\in s,j\in t}\operatorname {perm} \left(b_{ij}\right)_{i\in {\bar {s}},j\in {\bar {t}}},} where s and t are subsets of the same size of {1, 2, ..., n} and s ¯ , t ¯ {\displaystyle {\bar {s}},{\bar {t}}} are their respective complements in that set. If A {\displaystyle A} is a triangular matrix, i.e., a i j = 0 {\displaystyle a_{ij}=0} whenever i > j {\displaystyle i>j} or, alternatively, whenever i < j {\displaystyle i<j} , then its permanent equals the product of the diagonal entries: perm ( A ) = a 11 a 22 ⋯ a n n = ∏ i = 1 n a i i . {\displaystyle \operatorname {perm} \left(A\right)=a_{11}a_{22}\cdots a_{nn}=\prod _{i=1}^{n}a_{ii}.}
Comparison to determinants Laplace's expansion by minors for computing the determinant along a row, column or diagonal extends to the permanent by ignoring all signs. For every i {\textstyle i} ,
p e r m ( B ) = ∑ j = 1 n B i , j M i , j , {\displaystyle \mathbb {perm} (B)=\sum _{j=1}^{n}B_{i,j}M_{i,j},}
where B i , j {\displaystyle B_{i,j}} is the entry of the ith row and the jth column of B, and M i , j {\textstyle M_{i,j}} is the permanent of the submatrix obtained by removing the ith row and the jth column of B. For example, expanding along the first column,
perm ( 1 1 1 1 2 1 0 0 3 0 1 0 4 0 0 1 ) =
1 ⋅ perm ( 1 0 0 0 1 0 0 0 1 ) + 2 ⋅ perm ( 1 1 1 0 1 0 0 0 1 )
+ 3 ⋅ perm ( 1 1 1 1 0 0 0 0 1 ) + 4 ⋅ perm ( 1 1 1 1 0 0 0 1 0 ) =
1 ( 1 ) + 2 ( 1 ) + 3 ( 1 ) + 4 ( 1 ) = 10 , {\displaystyle {\begin{aligned}\operatorname {perm} \left({\begin{matrix}1&1&1&1\\2&1&0&0\\3&0&1&0\\4&0&0&1\end{matrix}}\right)={}&1\cdot \operatorname {perm} \left({\begin{matrix}1&0&0\\0&1&0\\0&0&1\end{matrix}}\right)+2\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\0&1&0\\0&0&1\end{matrix}}\right)\\&{}+\ 3\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&0&1\end{matrix}}\right)+4\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}}\right)\\={}&1(1)+2(1)+3(1)+4(1)=10,\end{aligned}}}
while expanding along the last row gives,
perm ( 1 1 1 1 2 1 0 0 3 0 1 0 4 0 0 1 ) =
4 ⋅ perm ( 1 1 1 1 0 0 0 1 0 ) + 0 ⋅ perm ( 1 1 1 2 0 0 3 1 0 )
+ 0 ⋅ perm ( 1 1 1 2 1 0 3 0 0 ) + 1 ⋅ perm ( 1 1 1 2 1 0 3 0 1 ) =
4 ( 1 ) + 0 + 0 + 1 ( 6 ) = 10. {\displaystyle {\begin{aligned}\operatorname {perm} \left({\begin{matrix}1&1&1&1\\2&1&0&0\\3&0&1&0\\4&0&0&1\end{matrix}}\right)={}&4\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}}\right)+0\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&0&0\\3&1&0\end{matrix}}\right)\\&{}+\ 0\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&1&0\\3&0&0\end{matrix}}\right)+1\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&1&0\\3&0&1\end{matrix}}\right)\\={}&4(1)+0+0+1(6)=10.\end{aligned}}}
On the other hand, the basic multiplicative property of determinants is not valid for permanents. A simple example shows that this is so.
4 = perm ( 1 1 1 1 ) perm ( 1 1 1 1 ) ≠ perm ( ( 1 1 1 1 ) ( 1 1 1 1 ) ) = perm ( 2 2 2 2 ) = 8. {\displaystyle {\begin{aligned}4&=\operatorname {perm} \left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\operatorname {perm} \left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\\&\neq \operatorname {perm} \left(\left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\right)=\operatorname {perm} \left({\begin{matrix}2&2\\2&2\end{matrix}}\right)=8.\end{aligned}}}
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. 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.
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 {\displaystyle H} , let ∨ k H {\displaystyle \vee ^{k}H} denote the k {\displaystyle k} th symmetric tensor power of H {\displaystyle H} , which is the space of symmetric tensors. Note in particular that ∨ k H {\displaystyle \vee ^{k}H} is spanned by the symmetric products of elements in H {\displaystyle H} . For x 1 , x 2 , … , x k ∈ H {\displaystyle x_{1},x_{2},\dots ,x_{k}\in H} , we define the symmetric product of these elements by
x 1 ∨ x 2 ∨ ⋯ ∨ x k = ( k ! ) − 1 / 2 ∑ σ ∈ S k x σ ( 1 ) ⊗ x σ ( 2 ) ⊗ ⋯ ⊗ x σ ( k ) {\displaystyle x_{1}\vee x_{2}\vee \cdots \vee x_{k}=(k!)^{-1/2}\sum _{\sigma \in S_{k}}x_{\sigma (1)}\otimes x_{\sigma (2)}\otimes \cdots \otimes x_{\sigma (k)}}
If we consider ∨ k H {\displaystyle \vee ^{k}H} (as a subspace of ⊗ k H {\displaystyle \otimes ^{k}H} , the kth tensor power of H {\displaystyle H} ) and define the inner product on ∨ k H {\displaystyle \vee ^{k}H} accordingly, we find that for x j , y j ∈ H {\displaystyle x_{j},y_{j}\in H}
⟨ x 1 ∨ x 2 ∨ ⋯ ∨ x k , y 1 ∨ y 2 ∨ ⋯ ∨ y k ⟩ = perm [ ⟨ x i , y j ⟩ ] i , j = 1 k {\displaystyle \langle x_{1}\vee x_{2}\vee \cdots \vee x_{k},y_{1}\vee y_{2}\vee \cdots \vee y_{k}\rangle =\operatorname {perm} \left[\langle x_{i},y_{j}\rangle \right]_{i,j=1}^{k}}
Applying the Cauchy–Schwarz inequality, we find that perm [ ⟨ x i , x j ⟩ ] i , j = 1 k ≥ 0 {\displaystyle \operatorname {perm} \left[\langle x_{i},x_{j}\rangle \right]_{i,j=1}^{k}\geq 0} , and that
| perm [ ⟨ x i , y j ⟩ ] i , j = 1 k | 2 ≤ perm [ ⟨ x i , x j ⟩ ] i , j = 1 k ⋅ perm [ ⟨ y i , y j ⟩ ] i , j = 1 k {\displaystyle \left|\operatorname {perm} \left[\langle x_{i},y_{j}\rangle \right]_{i,j=1}^{k}\right|^{2}\leq \operatorname {perm} \left[\langle x_{i},x_{j}\rangle \right]_{i,j=1}^{k}\cdot \operatorname {perm} \left[\langle y_{i},y_{j}\rangle \right]_{i,j=1}^{k}}
Cycle covers
Any square matrix A = ( a i j ) i , j = 1 n {\displaystyle A=(a_{ij})_{i,j=1}^{n}} can be viewed as the adjacency matrix of a weighted directed graph on vertex set V = { 1 , 2 , … , n } {\displaystyle V=\{1,2,\dots ,n\}} , with a i j {\displaystyle a_{ij}} 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" σ ( i ) {\displaystyle \sigma (i)} in the cycle cover, and so σ {\displaystyle \sigma } represents a permutation on V. Conversely, any permutation σ {\displaystyle \sigma } on V corresponds to a cycle cover with arcs from each vertex i to vertex σ ( i ) {\displaystyle \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
weight ( σ ) = ∏ i = 1 n a i , σ ( i ) , {\displaystyle \operatorname {weight} (\sigma )=\prod _{i=1}^{n}a_{i,\sigma (i)},}
implying that
perm ( A ) = ∑ σ weight ( σ ) . {\displaystyle \operatorname {perm} (A)=\sum _{\sigma }\operatorname {weight} (\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 i j ) {\displaystyle A=(a_{ij})} can also be viewed as the adjacency matrix of a bipartite graph which has vertices x 1 , x 2 , … , x n {\displaystyle x_{1},x_{2},\dots ,x_{n}} on one side and y 1 , y 2 , … , y n {\displaystyle y_{1},y_{2},\dots ,y_{n}} on the other side, with a i j {\displaystyle a_{ij}} representing the weight of the edge from vertex x i {\displaystyle x_{i}} to vertex y j {\displaystyle y_{j}} . If the weight of a perfect matching σ {\displaystyle \sigma } that matches x i