= Permanent
{disambiguate=mathematics}
{title2=$\operatorname{perm}A$}
{wiki}
= Permanent of a matrix
{synonym}
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>,
$$
\operatorname{perm}A=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.
$$
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>,
$$
\operatorname{perm}\begin{pmatrix}a&b\\c&d\end{pmatrix}=ad+bc,
\qquad
\det\begin{pmatrix}a&b\\c&d\end{pmatrix}=ad-bc.
$$
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 https://ocw.mit.edu/courses/18-226-probabilistic-methods-in-combinatorics-fall-2022/mit18_226_f22_lec_full.pdf[Yufei Zhao, Probabilistic Methods in Combinatorics, §10.2, pp. 178–179].
For a fully enumerated example, take
$$
A=\begin{pmatrix}1&1&0\\1&1&1\\0&1&1\end{pmatrix}.
$$
Among 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 $\operatorname{perm}A=3$. Their <permutation signs> are $+1,-1,-1$, giving $\det A=-1$. The diagram displays all three allowed assignments.
\Image[/permanent-perfect-matching-assignments.png]
{title=Three allowed one-to-one assignments contribute positively to the permanent, while their permutation signs give a determinant of minus one}
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 https://www.sciencedirect.com/science/article/pii/0304397579900446[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.
Back to article page
