Definition:Permanent

From ProofWiki
Jump to: navigation, search

Definition

Let $\mathbf A = \left[{a}\right]_n$ be a square matrix of order $n$.

That is, let:

$\mathbf A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix}$


Let $\lambda: \N_{> 0} \to \N_{> 0}$ be a permutation on $\N_{> 0}$.


Then the permanent of $\mathbf A$ is defined as:

$\displaystyle \sum_{\lambda} \left({\prod_{k \mathop = 1}^n a_{k \lambda \left({k}\right)}}\right) = \sum_{\lambda} a_{1 \lambda \left({1}\right)} a_{2 \lambda \left({2}\right)} \cdots a_{n \lambda \left({n}\right)}$

where:

the summation $\displaystyle \sum_\lambda$ goes over all the $n!$ permutations of $\left\{{1, 2, \ldots, n}\right\}$.


Examples

Matrix whose Entries are Product of Row and Column Indices

The square matrix of the form:

$\begin{pmatrix} 1 \times 1 & 1 \times 2 & \cdots & 1 \times m \\ 2 \times 1 & 2 \times 2 & \cdots & 2 \times m \\ \vdots & \vdots & \ddots & \vdots \\ m \times 1 & m \times 2 & \cdots & m \times m \end{pmatrix}$

has a permanent of $\left({n!}\right)^3$.


Also see


Sources