You are here
Homepermanent
Primary tabs
permanent
Definition of the permanent
Let $M$ be an $n\times n$ matrix over a field (or even a commutative ring) ${{\sf I\kern1.2ptF}}$, and $M_{{ij}}$ its entries (with $i$ ranging over a set $I$ and $j$ over a set $J$, each of $n$ elements).
The permanent of $M$, denoted by $\mathop{\rm per}\nolimits M$, is given by
$\mathop{\rm per}\nolimits M\;\mathrel{\mathop{=}\limits^{{\smash{\hbox{\tiny def% }}}}}\;\sum_{{\pi\,\in\,S}}\;\prod_{{i\,\in\,I}}\;M_{{i\;\pi(i)}}$ 
where $S$ is the set of all $n!$ bijections $\pi:I\to J$. Usually $I$ and $J$ are identified with each other (and with the set of the first $n$ natural numbers, traditionally skipping 0) so that $S$ consists of the elements of the symmetric group $S_{n}$, the group of permutations of $n$ objects.
In words: we want products of each time $n$ matrix elements chosen such that there’s one from each row $i$ and also one from each column $j$. There are $n!$ ways to pick those elements (for any permutation of the column indices relative to the row indices take the elements that end up in diagonal position). The permanent is the sum of those $n!$ products. E.g. ($n=3$)
@ O O O @ O O O @ @ O O O @ O O O @
O @ O + O O @ + @ O O + O O @ + @ O O + O @ O
O O @ @ O O O @ O O @ O O O @ @ O O
Comparison with the determinant
It is closely related to one of the ways to define the determinant,
$\det M\;\mathrel{\mathop{=}\limits^{{\smash{\hbox{\tiny def}}}}}\;\sum_{{\pi\,% \in\,S_{I}}}\pm\prod_{{i\,\in\,I}}\;M_{{i\;\pi(i)}}$ 
where $S_{I}$ is the symmetry group of $I$ (isomorphic to $S_{n}$); the sign is $+$ for even permutations and $$ for odd ones. E.g. ($n=3$)
@ O O O @ O O O @ @ O O O @ O O O @
O @ O + O O @ + @ O O  O O @  @ O O  O @ O
O O @ @ O O O @ O O @ O O O @ @ O O
Note two important differences though.

While the determinant enjoys the property that $(\det A)(\det B)=\det(AB)$, the permanent has no such nice arithmetic properties.

In the definition of the determinant, we must have $I=J$ i.e. we must have a particular way in mind of matching rows to columns. A matrix to transform from one basis to another would be an example where this match is arbitrary. Different conventions which row goes with which column give two different values (one $1$ times the other) for the determinant. By contrast, the permanent is well defined for any $I$ and $J$.
In the representation theory of groups (where the field ${{\sf I\kern1.2ptF}}$ is ${{\sf\kern 1.4pt\raise 0.602pt\hbox{\i}\kern2.37pt\raise 1.849pt\hbox{\i}% \kern4.0ptC}}$) determinant and permanent are special cases of the immanent (there is an immanent for every character of $S_{n}$).
Some properties of the permanent
These follow immediately from the definition:

The permanent is “multilinear” in the rows and columns (i.e. linear in every one of them).

It is “homogeneous of degree $n$”, i.e. $\mathop{\rm per}\nolimits(kA)=k^{n}\mathop{\rm per}\nolimits(A)$, where $k$ is a scalar (i.e. element of ${{\sf I\kern1.2ptF}}$).

When $P$ and $Q$ are permutation matrices, $\mathop{\rm per}\nolimits(PAQ)=\mathop{\rm per}\nolimits(PA)=\mathop{\rm per}% \nolimits(AQ)=\mathop{\rm per}\nolimits(A)$.

$\mathop{\rm per}\nolimits(A^{\top})=\mathop{\rm per}\nolimits(A)$.

$\displaystyle\mathop{\rm per}\nolimits\big({A\;\;0\,\atop\,0\;\;D}\big)=% \mathop{\rm per}\nolimits(A)\mathop{\rm per}\nolimits(D)$.

If $M$ only has nonnegative entries, then
$\mathop{\rm per}\nolimits M\geqslant\det M$ Equality is attained

when the permutations used are all even (which implies only one is used). This happens in a diagonal matrix, but also for instance in
$\left\lgroup\begin{array}[]{cccc}0&1&0&0\\ 1&0&0&0\\ 0&0&0&1\\ 0&0&1&0\end{array}\right\rgroup$
Permanents find application in combinatorics, e.g. in enumerating Latin squares.
See also Van der Waerden’s permanent conjecture (now a theorem) for doubly stochastic matrices (where ${{\sf I\kern1.2ptF}}$ is ${{\sf I\kern1.2ptR}}$).
Note: some authors define something for nonsquare matrices they also call “permanent”.
Mathematics Subject Classification
15A15 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
Recent Activity
new question: Prove a formula is part of the Gentzen System by LadyAnne
Mar 30
new question: A problem about Euler's totient function by mbhatia
new problem: Problem: Show that phi(a^n1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia
new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz
Mar 26
new correction: Misspelled name by DavidSteinsaltz
Mar 21
new correction: underlinetypo by Filipe
Mar 19
new correction: cocycle pro cocyle by pahio
Mar 7
new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier
new image: expected waiting time by robert_dodier
new image: plot W(t) = P(waiting time <= t) by robert_dodier
Comments
Perm(A)*Perm(B)=Perm(AB) ?
Is it true that for any two matrices A,B:
Perm(A)*Perm(B)=Perm(AB)
where Perm(A) is the permanent of A.
(The equation is true for Determinants)
Re: Perm(A)*Perm(B)=Perm(AB) ?
If I'm not mistaken:
1 0 * 1 1 = 1 1
1 1 0 1 1 2
Permanents: 1 * 1 != 3
Regards
T.
(I'm not 100% sure about the complexity of Gauss algorithm for rationals, but my guess is that such a formula would give you a (way too) good way to compute the permanent, a problem that is #Phard (cp. Jerrum et al., A polynomialtime approximation algorithm for the permanent of a matrix with nonnegative entries, JACM 51 (2004) and some survey article of Jerrum on the subject).