Permanent (mathematics, $\mathrm{perm}A$)

The permanent of a matrix adds the products obtained by choosing one entry in each row and one in each column. For an $n\times n$ matrix $A=(a_{ij})$ with entries in the real numbers or complex numbers,Here each permutation $\sigma$ chooses column $\sigma (i)$ in row $i$, and the symmetric group $S_n$ lists every such bijection. The formula resembles the Leibniz formula for determinants, but omits the sign of a permutation. For a two-by-two matrix,The absence of alternating signs makes the permanent of a matrix particularly useful for counting allowed assignments.

For a zero-one matrix, let rows represent people, columns represent jobs, and $a_{ij}=1$ mean that person $i$ can do job $j$. This is the biadjacency matrix of a bipartite graph. A product in the permanent is one exactly when all the selected assignments are allowed; otherwise it is zero. Each surviving permutation assigns every person a different job, which is a perfect matching. Thus the permanent counts perfect matchings. This interpretation and the definition are given in Yufei Zhao, Probabilistic Methods in Combinatorics, §10.2, pp. 178–179.

For a fully enumerated example, takeAmong the six permutations of three columns, exactly three give nonzero products: $(1,2,3)$, $(1,3,2)$ and $(2,1,3)$. These tuples list the chosen column in each successive row. Each product is one, so $\mathrm{perm}A=3$. Their permutation signs are $+1,-1,-1$, giving $\det A=-1$. The diagram displays all three allowed assignments.

A zero determinant need not mean that no assignment exists. The two-by-two all-ones matrix has permanent $2$ and determinant $0$: its two assignments cancel in the determinant. The nonzero determinant criterion for a perfect matching is sufficient for existence, but the converse fails for a fixed zero-one matrix.

For nonnegative entries, the permanent instead sums assignment weights, with each assignment weighted by the product of its selected entries. It is then a total weight rather than necessarily an integer count. With arbitrary entries in the real numbers or complex numbers, even the permanent can have cancellation; the counting interpretation specifically uses zero-one entries. The permanent as probability of distinct independent choices gives another useful nonnegative interpretation.

There are $n!$ terms in the defining sum, linking direct evaluation to the factorial. For the all-ones $n\times n$ matrix, every term is one and the permanent is exactly $n!$; the identity matrix has permanent one. Finding one allowed assignment and counting all allowed assignments are different questions. Their relationship to computational complexity theory was studied in L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8(2), 189–201, 1979. The elementary sum is useful for small examples, while the existing dense permanent approximation describes a more specialized way of estimating large counts.

Let $X_1,\dots ,X_n$ be independent random variables, each choosing a label from $\{1,\dots ,n\}$. Put their probabilities in the matrix $P=(p_{ij})$, where $p_{ij}=\mathbb{P}(X_i=j)$. Each row sums to one. All choices are distinct precisely when their ordered list is one of the permutations of the $n$ labels. These are mutually exclusive events, and independence makes the probability of one list $\sigma$ equal to ${\prod }_i{p}_{i,\sigma (i)}$. Adding the list probabilities gives the permanent of a matrix:In particular, this permanent lies between zero and one.

For a two-person example,The distinct outcomes $(1,2)$ and $(2,1)$ have probabilities $3/5$ and $1/20$. ThereforeThe colliding outcomes $(1,1)$ and $(2,2)$ have probabilities $3/20$ and $1/5$, totaling $0.35$. All four outcomes are shown below; their probabilities sum to one.

If every choice has the uniform distribution on a finite set of $n$ labels, then $p_{ij}=1/n$ and the distinct-choice probability is $n!/n^n$. For three choices and three labels it is $6/27=2/9$. This counts a subset of all $n^n$ ordered outcomes, not independent pairwise collision events. Independence of the original choices is essential: without it, the individual rows of $P$ do not determine the joint probabilities.

If every row and column of an $n$-by-$n$ zero-one matrix has more than $n/2$ ones, its permanent of a matrix has a fully polynomial randomized approximation scheme. The short augmenting paths in a dense bipartite graph bound makes the leading coefficient dominate the matching generating function at polynomially large activity. The weighted matching Markov chain samples polynomially bounded activities in polynomial mixing time. Estimate successive annealing ratios for a matching generating function and divide by the final activity to the power $n$.