permanent

Definition of the permanent

Let $M$ be an $n\times n$ matrix over a field (or even a commutative ring) ${\mathchoice{{\sf I\kern-1.2ptF}}{{\sf I\kern-1.2ptF}}{{\scriptstyle\sf I\kern% -1.2ptF}}{{\scriptscriptstyle\sf I\kern-1.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 ${\mathchoice{{\sf I\kern-1.2ptF}}{{\sf I\kern-1.2ptF}}{{\scriptstyle\sf I\kern% -1.2ptF}}{{\scriptscriptstyle\sf I\kern-1.2ptF}}}$ is ${\mathchoice{{\sf\kern 1.4pt\raise 0.602pt\hbox{\i}\kern-2.37pt\raise 1.849pt% \hbox{\i}\kern-4.0ptC}}{{\sf\kern 1.4pt\raise 0.602pt\hbox{\i}\kern-2.37pt% \raise 1.849pt\hbox{\i}\kern-4.0ptC}}{{\scriptstyle\sf\kern 1.4pt\raise 0.602% pt\hbox{\i}\kern-2.37pt\raise 1.849pt\hbox{\i}\kern-4.0ptC}}{{% \scriptscriptstyle\sf\kern 1.4pt\raise 0.602pt\hbox{\i}\kern-2.37pt\raise 1.84% 9pt\hbox{\i}\kern-4.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 ${\mathchoice{{\sf I\kern-1.2ptF}}{{\sf I\kern-1.2ptF}}{{\scriptstyle\sf I\kern% -1.2ptF}}{{\scriptscriptstyle\sf I\kern-1.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

–

(with value 0) when the products (of entries, one from each row and from each column) that contribute to det and per are all zero. This happens whenever a whole column or row is zero, but also for instance in

$\left\lgroup\begin{array}[]{rrr}12&0&0\\ 13&0&0\\ 14&15&16\end{array}\right\rgroup$

–

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 ${\mathchoice{{\sf I\kern-1.2ptF}}{{\sf I\kern-1.2ptF}}{{\scriptstyle\sf I\kern% -1.2ptF}}{{\scriptscriptstyle\sf I\kern-1.2ptF}}}$ is ${\mathchoice{{\sf I\kern-1.2ptR}}{{\sf I\kern-1.2ptR}}{{\scriptstyle\sf I\kern% -1.2ptR}}{{\scriptscriptstyle\sf I\kern-1.2ptR}}}$ ).

Note: some authors define something for non-square matrices they also call “permanent”.

Title	permanent
Canonical name	Permanent
Date of creation	2013-03-22 14:05:39
Last modified on	2013-03-22 14:05:39
Owner	marijke (8873)
Last modified by	marijke (8873)
Numerical id	12
Author	marijke (8873)
Entry type	Definition
Classification	msc 15A15
Related topic	Immanent
Related topic	Determinant2